kidforever911

5.6万

yxc的小迷妹

@Dong

Q_83
kemingyu
summerrr
Dreamqkz
Suzuka_
tobylhy
Y._75

PseudorandomGenerators
20090514
macheny

/**
* 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;
}
};


/**
* 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;
}
};


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) {
}

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);
*/


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) {
}

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);
*/


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);
*/


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;
}
};