/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int n = 0, p = 0;
bool dfs(TreeNode* root, int k) {
if(!root) return true;
if(k > 100) return false;
n ++, p = max(k, p);
return dfs(root->left, 2 * k) && dfs(root->right, 2 * k + 1);
}
bool isCompleteTree(TreeNode* root) {
if(!dfs(root, 1)) return false;
return n == p;
}
};
活动打卡代码
LeetCode 958. 二叉树的完全性检验
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int n = 0, p = 0;
bool dfs(TreeNode* root, int k) {
if(!root) return true;
if(k > 100) return false;
n ++, p = max(k, p);
return dfs(root->left, 2 * k) && dfs(root->right, 2 * k + 1);
}
bool isCompleteTree(TreeNode* root) {
if(!dfs(root, 1)) return false;
return n == p;
}
};
活动打卡代码
LeetCode 678. 有效的括号字符串
class Solution {
public:
bool checkValidString(string s) {
int low = 0, high = 0;
for(auto& c : s) {
if(c == '(') low ++, high ++;
else if(c == ')') low --, high --;
else low --, high ++;
low = max(0, low);
if(low > high) return false;
}
return !low;
}
};
class Solution {
public:
bool checkValidString(string s) {
int low = 0, high = 0;
for(auto& c : s) {
if(c == '(') low ++, high ++;
else if(c == ')') low --, high --;
else low --, high ++;
low = max(0, low);
if(low > high) return false;
}
return !low;
}
};
const int N = 2510;
int son[N][26], S[N], V[N], idx;
class MapSum {
public:
void add(string& s, int last, int value) {
int p = 0;
for(auto& c : s) {
int u = c - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
S[p] += value - last;
}
V[p] = value;
}
int query(string& s) {
int p = 0;
for(auto& c : s) {
int u = c - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return p;
}
MapSum() {
idx = 0;
memset(son, 0, sizeof son);
memset(S, 0, sizeof S);
memset(V, 0, sizeof V);
}
void insert(string key, int val) {
add(key, V[query(key)], val);
}
int sum(string prefix) {
return S[query(prefix)];
}
};
/**
* Your MapSum object will be instantiated and called as such:
* MapSum* obj = new MapSum();
* obj->insert(key,val);
* int param_2 = obj->sum(prefix);
*/
活动打卡代码
LeetCode 677. 键值映射
const int N = 2510;
int son[N][26], S[N], V[N], idx;
class MapSum {
public:
void add(string& s, int last, int value) {
int p = 0;
for(auto& c : s) {
int u = c - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
S[p] += value - last;
}
V[p] = value;
}
int query(string& s) {
int p = 0;
for(auto& c : s) {
int u = c - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return p;
}
MapSum() {
idx = 0;
memset(son, 0, sizeof son);
memset(S, 0, sizeof S);
memset(V, 0, sizeof V);
}
void insert(string key, int val) {
add(key, V[query(key)], val);
}
int sum(string prefix) {
return S[query(prefix)];
}
};
/**
* Your MapSum object will be instantiated and called as such:
* MapSum* obj = new MapSum();
* obj->insert(key,val);
* int param_2 = obj->sum(prefix);
*/
活动打卡代码
LeetCode 676. 实现一个魔法字典
const int N = 10010;
int son[N][26], idx;
bool is_end[N];
class MagicDictionary {
public:
void insert(string& s) {
int p = 0;
for(auto& c : s) {
int u = c - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
is_end[p] = true;
}
MagicDictionary() {
memset(son, 0, sizeof son);
memset(is_end, 0, sizeof is_end);
idx = 0;
}
void buildDict(vector<string> dictionary) {
for(auto& s : dictionary) insert(s);
}
//p代表trie树中的位置，u代表当前字符位置，c表示字符差异值
bool dfs(string& s, int p, int u, int c) {
if(is_end[p] && u == s.size() && c == 1) return true;
if(c > 1 || u == s.size()) return false;
for(int i = 0; i < 26; i ++) {
if(!son[p][i]) continue;
if(dfs(s, son[p][i], u + 1, c + (s[u] - 'a' != i))) return true;
}
return false;
}
bool search(string searchWord) {
return dfs(searchWord, 0, 0, 0);
}
};
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
*/
const int N = 10010;
int son[N][26], idx;
bool is_end[N];
class MagicDictionary {
public:
void insert(string& s) {
int p = 0;
for(auto& c : s) {
int u = c - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
is_end[p] = true;
}
MagicDictionary() {
memset(son, 0, sizeof son);
memset(is_end, 0, sizeof is_end);
idx = 0;
}
void buildDict(vector<string> dictionary) {
for(auto& s : dictionary) insert(s);
}
//p代表trie树中的位置，u代表当前字符位置，c表示字符差异值
bool dfs(string& s, int p, int u, int c) {
if(is_end[p] && u == s.size() && c == 1) return true;
if(c > 1 || u == s.size()) return false;
for(int i = 0; i < 26; i ++) {
if(!son[p][i]) continue;
if(dfs(s, son[p][i], u + 1, c + (s[u] - 'a' != i))) return true;
}
return false;
}
bool search(string searchWord) {
return dfs(searchWord, 0, 0, 0);
}
};
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
*/
活动打卡代码
LeetCode 675. 为高尔夫比赛砍树
class Solution {
public:
struct Tree{
int x, y, h;
bool operator< (const Tree& t) const {
return h < t.h;
}
};
int row, col;
vector<vector<int>> g;
int bfs(Tree start, Tree end) {
if(start.x == end.x && start.y == end.y) return 0;
queue<Tree> q;
q.push({start});
const int INF = 1e8;
vector<vector<int>> dist(row, vector<int>(col, INF));
dist[start.x][start.y] = 0;
int direction[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while(q.size()) {
auto cur = q.front();
q.pop();
for(int i = 0; i < 4; i ++) {
int x = cur.x + direction[i][0];
int y = cur.y + direction[i][1];
if(x >= 0 && x < row && y >= 0 && y < col && g[x][y] && dist[x][y] > dist[cur.x][cur.y] + 1) {
dist[x][y] = dist[cur.x][cur.y] + 1;
if(x == end.x && y == end.y) return dist[x][y];
q.push({x, y});
}
}
}
return -1;
}
int cutOffTree(vector<vector<int>>& forest) {
g = forest;
int result = 0;
row = g.size(), col = g[0].size();
vector<Tree> record;
for(int i = 0; i < row; i ++) {
for(int j = 0; j < col; j ++) {
if(g[i][j] > 1) {
record.push_back({i, j, g[i][j]});
}
}
}
sort(record.begin(), record.end());
Tree last = {0, 0};
for(auto& t : record) {
int distance = bfs(last, t);
if(distance == -1) return -1;
result += distance;
last = t;
}
return result;
}
};
class Solution {
public:
struct Tree{
int x, y, h;
bool operator< (const Tree& t) const {
return h < t.h;
}
};
int row, col;
vector<vector<int>> g;
int bfs(Tree start, Tree end) {
if(start.x == end.x && start.y == end.y) return 0;
queue<Tree> q;
q.push({start});
const int INF = 1e8;
vector<vector<int>> dist(row, vector<int>(col, INF));
dist[start.x][start.y] = 0;
int direction[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while(q.size()) {
auto cur = q.front();
q.pop();
for(int i = 0; i < 4; i ++) {
int x = cur.x + direction[i][0];
int y = cur.y + direction[i][1];
if(x >= 0 && x < row && y >= 0 && y < col && g[x][y] && dist[x][y] > dist[cur.x][cur.y] + 1) {
dist[x][y] = dist[cur.x][cur.y] + 1;
if(x == end.x && y == end.y) return dist[x][y];
q.push({x, y});
}
}
}
return -1;
}
int cutOffTree(vector<vector<int>>& forest) {
g = forest;
int result = 0;
row = g.size(), col = g[0].size();
vector<Tree> record;
for(int i = 0; i < row; i ++) {
for(int j = 0; j < col; j ++) {
if(g[i][j] > 1) {
record.push_back({i, j, g[i][j]});
}
}
}
sort(record.begin(), record.end());
Tree last = {0, 0};
for(auto& t : record) {
int distance = bfs(last, t);
if(distance == -1) return -1;
result += distance;
last = t;
}
return result;
}
};
