namespace matchstick_my {
int isDividedby4(vector<int>& matrix) {
int n = matrix.size();
if (n <= 3)return -1;
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += matrix[i];
}
if (sum % 4 != 0)return -1;
for (int i = 0; i < matrix.size(); ++i) {
if (matrix[i] > sum / 4)return false;
}
return sum / 4;
}
int rowsum(vector<int> &matrix, int edge) {
int sum = 0;
for (int i = 0; i < matrix.size(); ++i) {
sum += matrix[i];
//if (sum > edge)return false;
}
return sum;
}
bool zongOK(vector<vector<int>> &tag, int edge) {
for (int i = 0; i < tag.size(); ++i) {
int sum = 0;
for (int j = 0; j < tag[i].size(); ++j) {
sum += tag[i][j];
}
if (sum != edge)return false;
}
return true;
}
vector<int>rev(vector<int>&matrix) {
vector<int>ret(matrix.size());
int t = 0;
for (int i = matrix.size() - 1; i >= 0; --i) {
ret[t++] = matrix[i];
}
return ret;
}
bool dfs(vector<int>&matrix, vector<vector<int>>& path, int cur, int tong, int edge, vector<int>&visited) {
if (cur == matrix.size()) {
if (zongOK(path, edge)) {
/*for (int i = 0; i < path.size(); ++i) {
printf("tong[%d]:", i + 1);
for (int j = 0; j < path[i].size(); ++j) {
cout << path[i][j] << " ";
}
cout << endl;
}cout << endl; cout << endl; cout << endl;*/
return true;
}
return false;
}
for (int j = 0; j < tong; ++j) {
if (rowsum(path[j], edge) == edge) {
if (!dfs(matrix, path, 0, tong - 1, edge, visited)) {
return false;
}
}
if (rowsum(path[j], edge) + matrix[cur]>edge)return false;
if (visited[cur] == 0) {
visited[cur] = 1;
path[j].push_back(matrix[cur]);
if (dfs(matrix, path, cur + 1, tong, edge, visited))return true;
path[j].pop_back();
visited[cur] = 0;
}
}
cout << "hello" << endl;
return false;
}
bool makesquare(vector<int>& matchsticks) {
int edge = isDividedby4(matchsticks);
cout << edge << endl;
vector<vector<int>>path(4);
vector<int>visited(matchsticks.size(), 0);
sort(matchsticks.begin(), matchsticks.end());
return dfs(matchsticks, path, 0, 4, edge, visited);
}
struct matchstick_usecase {
int con = 0;
vector<int>matrix3{ 1,2,1,2,2, 113,113,113,113,3,3,3,3 };//64=4^3
vector<int>matrix4{ 1,2,3,4 };//256=4^4
vector<int>matrix5{ 1,2,3,4,5 };//1024
vector<int>matrix6{ 1,1,2,2,3,3 };//4096
vector<int>matrix7{ 1,2,3,4,5,6,7 };//
vector<int>matrix8{ 1,2,3,4,5,6,7,8 };//65535=4^8=2^16
vector<int>matrix9{ 3,1,3,3,10,7,10,3,6,9,10,3,7,6,7 };//9980HK 15s (true),???? 404ms??????? 111ms?
vector<int>matrix10{ 10,6,5,5,5,3,3,3,2,2,2,2 };//9980HK 159ms (true) ???? 146ms?
vector<int>matrix11{ 12,12,12,16,20,24,28,32,36,40,44,48,52,56,60 };//9980HK 16.3s (false) ???? 16ms?
};
}
namespace subset_my {
//subset I AC 100% 97% sub: current subset elements amount cur: current index
void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>&ret, int cur, int sub, vector<int>&visited) {
if (path.size() == sub) {
ret.push_back(path);
return;
}
for (int i = cur; i < nums.size(); ++i) {
if (visited[i] == 0) {
//??????base????????????????????????????cur???????????????????????????????????????????
//if (visited[i] == 0) { //????????????????????????
path.push_back(nums[i]);
visited[i] = 1;
dfs(nums, path, ret, i + 1, sub, visited);
path.pop_back();
visited[i] = 0;
}
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>>ret;
ret.push_back({});
vector<int>path;
vector<int>visited(nums.size(), 0);
for (int i = 1; i < nums.size(); ++i) {
dfs(nums, path, ret, 0, i, visited);
}
ret.push_back(nums);
return ret;
}
//subset II AC 100% 87% ???????????
void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>&ret, int cur, int sub) {
if (path.size() == sub) {
ret.push_back(path);
return;
}
for (int i = cur; i < nums.size(); ++i) {
if (i != cur&&nums[i] == nums[i - 1])continue;
path.push_back(nums[i]);
// visited[i] = 1;
dfs(nums, path, ret, i + 1, sub); //i+1 instead of cur+1 (all view)
path.pop_back();
// visited[i] = 0;
//}
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>>ret;
sort(nums.begin(), nums.end());//???????
ret.push_back({});
vector<int>path;
for (int i = 1; i < nums.size(); ++i) {
dfs(nums, path, ret, 0, i);
}
ret.push_back(nums);
return ret;
}
}
namespace subset_clever {
//?????????????????????????????????????????
}
namespace maxUniqueSplit {
/*AC */
void dfs(string s,int& max,vector<string>& path,int cur,unordered_set<string>&us) {
if (cur==s.size()) {
if (path.size() > max) {
max = path.size();
}
return;
}
for (int i = 1; i < s.size()-cur+1; ++i) {
if (us.find(s.substr(cur, i)) == us.end()) {
us.insert(s.substr(cur, i));
path.push_back(s.substr(cur, i));
for (auto i : path)cout << i << " "; cout << endl;//"ababccc";
dfs(s,max,path,cur+i,us);
path.pop_back();
us.erase(s.substr(cur, i));
}
}
}
int maxUniqueSplit(string s) {
int ans = 0;
string sg("aaaaabbbabcab");
string b = "aaaaabbbabcab";
string a = "ababccc";
vector<string>path;
unordered_set<string>us;
dfs(sg,ans,path, 0, us);
return ans;
}
}
namespace numTilePossiblity {
/*AC 30% 40% */
void dfs(string tiles, int cur, int sub, int &ans, string&path, vector<int>&visited, unordered_set<string>&us) {
if (cur == sub) {
if (us.find(path) == us.end()) {
us.insert(path);
ans++;
}
return;
}
for (int i = 0; i < tiles.size(); ++i) {
if (visited[i] == 0) {
visited[i] = 1;
path.push_back(tiles[i]);
dfs(tiles, cur + 1, sub, ans, path, visited, us);
path.pop_back();
visited[i] = 0;
}
}
}
int numTilePossibilities(string tiles) {
int ans = 0;
string path;
vector<int>visited(tiles.size(), 0);
unordered_set<string>us;
for (int sub = 1; sub <= tiles.size(); ++sub)
{
dfs(tiles,0,sub,ans,path,visited,us);
}
return ans;
}
}
namespace wordexist {
/*AC 25 24 608ms */
bool dfs(vector<vector<char>>& board, string &path, int wpos, string word, int i, int j, vector<vector<int>>&visited) {
if (path == word) {//wpos==word.size()
return true;
}
if (j >= board[0].size() || i<0 || i >= board.size() || j < 0)return false;
if (board[i][j] == word[wpos] && visited[i][j] == 0) {
visited[i][j] = 1;
path.push_back(board[i][j]);
//cout << "path=" << path << endl;
if (
dfs(board, path, wpos + 1, word, i + 1, j, visited) ||
dfs(board, path, wpos + 1, word, i, j + 1, visited) ||
dfs(board, path, wpos + 1, word, i - 1, j, visited) ||
dfs(board, path, wpos + 1, word, i, j - 1, visited))
return true;
path.pop_back();
visited[i][j] = 0;
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
string path; int np = board[0].size();
vector<int>cat(np, 0);
vector<vector<int>>visited;
for (int i = 0; i < board.size(); ++i)visited.push_back(cat);
char start = word[0];
vector<vector<int>>ak;
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == start) ak.push_back({ i,j });
}
}
if (ak.size() == 0) { cout << "no way" << endl; return false; }
for (int i = 0; i < ak.size(); ++i) {
if (dfs(board, path, 0, word, ak[i][0], ak[i][1], visited))
return true;
}
return false;
}
}
namespace maxAreaOfIsland {
/*AC 78% 25% 16ms-28ms */
void dfs(vector<vector<int>>& grid,int curi,int curj,int &ret,int &cache,vector<vector<int>>&visited) {
if (curi < 0 || curj < 0 || curi >= grid.size() || curj >= grid[0].size()||visited[curi][curj]==1) return;
if (grid[curi][curj] != 0) {
cache += 1;
//cout << "cache=" << cache << endl;
visited[curi][curj] = 1;
if (cache > ret) {
ret = cache;
cout << "curi=" << curi << " curj=" << curj << " ret==" << ret <<" cache=="<<cache<< endl;
}
dfs(grid, curi, curj + 1, ret, cache, visited);
//cout << "backup1" << endl;
dfs(grid, curi + 1, curj, ret, cache, visited);
//cout << "backup2" << endl;
dfs(grid, curi - 1, curj, ret, cache, visited);
//cout << "backup3" << endl;
dfs(grid, curi, curj - 1, ret, cache, visited);
//cout << "backup4" << endl;
cout << "fanhui" << endl;
//visited[curi][curj] = 0;
//cache = 0;
//dfs(grid, curi - 1, curj, ret, cache);
//(grid, curi, curj - 1, ret, cache);
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ret = 0;
int cta = 0;
vector<int>cache(grid[0].size(), 0);
vector<vector<int>>visited(grid.size(),cache);
vector<int>resk;
//dfs(grid, 1, 2, ret, 0, visited);
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 0) {
continue;
}
cta = 0;
dfs(grid, i, j, ret, cta, visited);
resk.push_back(ret);
ret = 0;
}
}
cout << "ret==" << ret << endl;
for (auto i : resk)cout << i << " "; cout << endl;
for (int i = 0; i < resk.size(); ++i) {
if (ret < resk[i])ret = resk[i];
}
return ret;
}
}
namespace solve {
//chess “eat zi”
/*AC 5% 5%*/
void dfs(vector<vector<char>>& board,int curi,int curj,vector<vector<int>>&path,vector<vector<int>>&visited) {
//memory search ,tag the path for nodes touch the edge area
//firstly,find all path
//second,save the special node(path)
//return board
if (curi >= board.size() || curi < 0 || curj >= board[0].size() || curj < 0||visited[curi][curj]==1) {
return;
}
if (board[curi][curj] == 'O')
{
path.push_back({ curi,curj });
visited[curi][curj] = 1;
//for (int i = 0; i < path.size(); ++i)cout << path[i][0] << " " << path[i][1] << endl; cout <<endl<< endl;
dfs(board, curi, curj + 1, path, visited);//right
dfs(board, curi + 1, curj, path, visited);//down
dfs(board, curi, curj - 1, path, visited);//left
dfs(board, curi - 1, curj, path, visited);//up
}
}
void solve(vector<vector<char>>& board)
{
//firstly,edge node become X with no evidience to support inner node
vector<vector<int>>path;
vector<int>adf(board[0].size(),0);
vector<vector<int>>visited(board.size(),adf);
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] != 'X')
{
dfs(board, i, j, path, visited);
//for (int i = 0; i < path.size(); ++i)cout << path[i][0] << " " << path[i][1] << endl;
int cv = 0;
for (int i = 0; i < path.size(); ++i) {
if (path[i][0] == 0 || path[i][0] == board.size() - 1 || path[i][1] == 0 || path[i][1] == board[0].size() - 1) {
cv = 1;//save this path
//cin.get();
break;
}
}
if (cv == 0) {
for (int i = 0; i < path.size(); ++i) {
board[path[i][0]][path[i][1]] = 'X';
}
}
path.clear();
}
}
}
}
struct solve_usecase {
vector<vector<char>>sua{
{ 'X','X','X','X' } ,
{ 'X','O','O','X' } ,
{ 'X','X','O','X' } ,
{ 'X','O','X','X' } ,
{ 'X','O','O','X' } ,
{ 'X','O','X','X' }
};
};
}
namespace pacificAtlantic {
/*AC 7% 43% 176ms ?3day?*/
void swapforPacificAtlitic(int a[], int m, int n) {
if (m != n) {
a[m] = a[m] ^ a[n];
a[n] = a[m] ^ a[n];
a[m] = a[m] ^ a[n];
}
}
int maxof(int sf[],int n) {
for (int i = 0; i < n; ++i) {
int c = i;
for (int left = c-1; left >= 0; --left) {
if (sf[c] < sf[left]) {
swapforPacificAtlitic(sf, c, left);
c--;
}
else {
break;
}
}
}
return sf[n-1];
}
//use return value idea:have some problems
//int dfs(vector<vector<int>>& heights, int curi, int curj, vector<vector<int>>& visited) {
// if (curi < 0 || curi >= heights.size() || curj < 0 || curj >= heights[0].size()) return 0;
// if (curi == 0 || curj == 0) {
// if ((curi == 0 && curj != heights[0].size() - 1) || (curj == 0 && curi != heights.size() - 1)) {
// visited[curi][curj] = 1;
// return 1;
// }//only pacific
// else if ((curi == 0 && curj == heights[0].size() - 1) || (curj == 0 && curi == heights.size() - 1)) {
// visited[curi][curj] = 3;
// return 3;
// }// all have
// }
// else if (curj == heights[0].size() - 1 || curi == heights.size() - 1) {
// visited[curi][curj] = 2;//only atlantic
// return 2;
// }
// int l = 0, r = 0, up = 0, down = 0;
// if (visited[curi][curj] == 0) {
// //if (curj + 1 <= heights[0].size() && heights[curi][curj + 1] <= heights[curi][curj]) {
// // int r = dfs(heights, curi, curj + 1, visited);
// //}
// //if (curj - 1 <= heights[0].size() && heights[curi][curj - 1] <= heights[curi][curj]) {
// // int l = dfs(heights, curi, curj - 1, visited);
// //}
// //if (curi + 1 <= heights[0].size() && heights[curi + 1][curj] <= heights[curi][curj]) {
// // int down = dfs(heights, curi + 1, curj, visited);
// //}
// //if (curi - 1 <= heights[0].size() && heights[curi - 1][curj] <= heights[curi][curj]) {
// // int up = dfs(heights, curi - 1, curj, visited);
// //}
// l = dfs(heights, curi, curj - 1, visited);
// r = dfs(heights, curi, curj + 1, visited);
// up = dfs(heights, curi - 1, curj, visited);
// down = dfs(heights, curi + 1, curj, visited);
// }
// int a[4]{ l,r,up,down };
// return maxof(a,4);
//}
//vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
// vector<int>cache(heights[0].size(), 0);
// vector<vector<int>>visited(heights.size(), cache);
// vector<vector<int>>ret;
// //give every node its "tag"
// for (int i = 0; i < heights[0].size(); ++i) {
// for (int j = 0; j < heights.size(); ++j) {
// dfs(heights, i, j, visited);
// }
// }
// for (int i = 0; i < heights.size(); ++i) {
// for (int j = 0; j < heights[0].size(); ++j) {
// if (visited[i][j] >= 3) ret.push_back({i,j});
// }
// }
// return ret;
//}
//int dfs(vector<vector<int>>& heights, int curi, int curj, vector<vector<int>>& visited, vector<vector<int>>&TagVisited) {
// //if (curi < 0 || curi >= heights.size() || curj < 0 || curj >= heights[0].size()) return 0;
// if (visited[curi][curj] != 0 && visited[curi][curj]>10000 && visited[curi][curj] % 10000 != 0)
// return visited[curi][curj];//??????????double????????????????????????????????
// if (curi == 0 || curj == 0) {
// if ((curi == 0 && curj != heights[0].size() - 1) || (curj == 0 && curi != heights.size() - 1)) {
// visited[curi][curj] = 1; //only pacific
// }
// else if ((curi == 0 && curj == heights[0].size() - 1) || (curj == 0 && curi == heights.size() - 1)) {
// visited[curi][curj] = 10001;
// return 10001;//??????
// }// all have
// }
// else if (curj == heights[0].size() - 1 || curi == heights.size() - 1) {
// visited[curi][curj] = 10000;//only atlantic
// }
// int l = 0, r = 0, up = 0, down = 0;
// if (TagVisited[curi][curj] == 0) {
// TagVisited[curi][curj] = 1;
// if (curj + 1 < heights[0].size() && heights[curi][curj + 1] <= heights[curi][curj]) {
// r = dfs(heights, curi, curj + 1, visited, TagVisited);
// }
// if (curj - 1 >= 0 && heights[curi][curj - 1] <= heights[curi][curj]) {
// l = dfs(heights, curi, curj - 1, visited, TagVisited);
// }
// if (curi + 1 < heights.size() && heights[curi + 1][curj] <= heights[curi][curj]) {
// down = dfs(heights, curi + 1, curj, visited, TagVisited);
// }
// if (curi - 1 >= 0 && heights[curi - 1][curj] <= heights[curi][curj]) {
// up = dfs(heights, curi - 1, curj, visited, TagVisited);
// }
// int other = r + l + down + up;
// if (other > 10000 && other % 10000 != 0) { other = 10001; }
// else if (other >= 10000 && other % 10000 == 0) { other == 10000; }
// else if (other < 10000 && other != 0) { other = 1; }
// else other = 0;
// visited[curi][curj] += other;
// if (visited[curi][curj] % 10000 == 0)visited[curi][curj] = 10000;
// else if(visited[curi][curj]<10000&&visited[curi][curj]>0)visited[curi][curj] = 1;
// TagVisited[curi][curj] = 0;
// }
// return visited[curi][curj];
//}
//vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
// vector<int>cache(heights[0].size(), 0);
// vector<vector<int>>visited(heights.size(), cache);
// vector<vector<int>>ret;
// vector<vector<int>>Tagvisited(heights.size(), cache);
// //give every node its "tag"
// for (int i = 0; i < heights.size(); ++i) {
// for (int j = 0; j < heights[0].size(); ++j) {
// dfs(heights, i, j, visited, Tagvisited);
// for (int i = 0; i < visited.size(); ++i) {
// for (int j = 0; j < visited[0].size(); ++j) {
// cout << visited[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl; cout << endl; cout << endl;
// }
// }
// for (int i = 0; i < heights.size(); ++i) {
// for (int j = 0; j < heights[0].size(); ++j) {
// if (visited[i][j] > 100 && visited[i][j] % 100 != 0) ret.push_back({ i,j });
// }
// }
// return ret;
//}
int dfs(vector<vector<int>>& heights, int curi, int curj, vector<vector<int>>& visited, vector<vector<int>>&TagVisited) {
//if (curi < 0 || curi >= heights.size() || curj < 0 || curj >= heights[0].size()) return 0;
if (visited[curi][curj] >= 101 && visited[curi][curj] % 100 != 0)
return visited[curi][curj];//??????????double????????????????????????????????
if (curi == 0 || curj == 0) {
if ((curi == 0 && curj != heights[0].size() - 1) || (curj == 0 && curi != heights.size() - 1)) {
visited[curi][curj] = 1; //only pacific
}
if ((curi == 0 && curj == heights[0].size() - 1) || (curj == 0 && curi == heights.size() - 1)) {
visited[curi][curj] = 101;
return 101;//??????
}// all have
}
if (curj == heights[0].size() - 1 || curi == heights.size() - 1) {
visited[curi][curj] = 100;//only atlantic
}
if (curi == 0 && heights.size() == 1) { visited[curi][curj] = 101; return 101; }
if (curj == 0 && heights[0].size() == 1) { visited[curi][curj] = 101; return 101; }
int l = 0, r = 0, up = 0, down = 0;
if (TagVisited[curi][curj] == 0) {
TagVisited[curi][curj] = 1;
if (curj + 1 < heights[0].size() && heights[curi][curj + 1] <= heights[curi][curj]) {
r = dfs(heights, curi, curj + 1, visited, TagVisited);
}
if (curj - 1 >= 0 && heights[curi][curj - 1] <= heights[curi][curj]) {
l = dfs(heights, curi, curj - 1, visited, TagVisited);
}
if (curi + 1 < heights.size() && heights[curi + 1][curj] <= heights[curi][curj]) {
down = dfs(heights, curi + 1, curj, visited, TagVisited);
}
if (curi - 1 >= 0 && heights[curi - 1][curj] <= heights[curi][curj]) {
up = dfs(heights, curi - 1, curj, visited, TagVisited);
}
int other = r + l + down + up;
visited[curi][curj] += other;
if (visited[curi][curj] % 100 == 0 && visited[curi][curj] != 0)
visited[curi][curj] = 100;
else if (visited[curi][curj]<100 && visited[curi][curj]>0)
visited[curi][curj] = 1;
else if (visited[curi][curj] > 100)
visited[curi][curj] = 101;
TagVisited[curi][curj] = 0;
}
return visited[curi][curj];
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
vector<int>cache(heights[0].size(), 0);
vector<vector<int>>visited(heights.size(), cache);
vector<vector<int>>ret;
vector<vector<int>>Tagvisited(heights.size(), cache);
//give every node its "tag"
for (int i = 0; i < heights.size(); ++i) {
for (int j = 0; j < heights[0].size(); ++j) {
dfs(heights, i, j, visited, Tagvisited);
if (visited[i][j] > 100 && visited[i][j] % 100 != 0) ret.push_back({ i,j });
}
}
return ret;
}
struct pacific {
vector<vector<int>>heights{ { 3 },{ 1 },{ 5 } ,{ 2 } };
vector<vector<int>>res = pacificAtlantic::pacificAtlantic(heights);
//for (int i = 0; i < res.size(); ++i) {
// for (int j = 0; j < res[0].size(); ++j) {
// cout << res[i][j] << " ";
// }
// cout << endl;
//}
};
}
namespace numEnclaves {
/* over time\ AC 5% 5% */
string extra(string s) {
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '[')s[i] = '{';
else if (s[i] == ']')s[i] = '}';
}
for (auto i:s)cout << i << "";
return s;
}
int dfs(vector<vector<int>>& heights, int curi, int curj, vector<vector<int>>& visited, vector<vector<int>>&TagVisited) {
if (visited[curi][curj] == 1){
TagVisited[curi][curj] = 1;
return 1;//edge here
}
if(curi == 0 || curj == 0 || curj == heights[0].size() - 1 || curi == heights.size() - 1) {
visited[curi][curj] = 1;//4 edge ,each is ok
TagVisited[curi][curj] = 1;
return 1;
}
int l = 0, r = 0, up = 0, down = 0;
if (TagVisited[curi][curj] == 0) {
TagVisited[curi][curj] = 1;
if (curj + 1 < heights[0].size() && heights[curi][curj + 1] == 1) {
r = dfs(heights, curi, curj + 1, visited, TagVisited);
}
if (curj - 1 >= 0 && heights[curi][curj - 1] == 1) {
l = dfs(heights, curi, curj - 1, visited, TagVisited);
}
if (curi + 1 < heights.size() && heights[curi + 1][curj] == 1) {
down = dfs(heights, curi + 1, curj, visited, TagVisited);
}
if (curi - 1 >= 0 && heights[curi - 1][curj] == 1) {
up = dfs(heights, curi - 1, curj, visited, TagVisited);
}
int other = r + l + down + up;
visited[curi][curj] += other;
if (visited[curi][curj] > 0) {
visited[curi][curj] = 1;
}
//TagVisited[curi][curj] = 0;//repeat left code running some times
}
return visited[curi][curj];
}
int numEnclaves(vector<vector<int>>& heights) {
vector<int>cache(heights[0].size(), 0);
vector<vector<int>>visited(heights.size(), cache);
int ret=0;
vector<vector<int>>Tagvisited(heights.size(), cache);
for (int i = 0; i < heights.size(); ++i) {
for (int j = 0; j < heights[0].size(); ++j) {
if (heights[i][j] == 1) {
//cout << "i=" << i << " j=" << j << endl;
dfs(heights, i, j, visited, Tagvisited);
if (visited[i][j] == 0 && heights[i][j] == 1) ret++;
//for (int i = 0; i < visited.size(); ++i) {
// for (int j = 0; j < visited[i].size(); ++j) {
// cout << visited[i][j] << " ";
// }
// cout << endl;
//}cout << endl; cout << endl; cout << endl;
}
}
}
return ret;
}
struct usecases
{
vector<vector<int>>hei{ { 0,1,0,1,1,1,0,0,0,1,1,0,1,0,1,0,1,1,0,0,1,0,1,0 },
{ 0,1,0,1,1,1,0,0,0,1,1,0,1,0,1,0,1,1,0,0,1,0,1,0 } };
vector<vector<int>>hei1{
{ 0,0,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,0,1,1,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,1,0,0 },
{ 1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,1 },
{ 1,0,0,1,1,1,0,1,0,0,0,0,1,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,1,1,0,0,0,1,0,1,0,0,0,1,1,1,1,1,0,1,1,0,0,1 },//qudiao 8s ; jiashang $$
{ 1,0,1,1,0,1,1,0,0,1,1,1,0,0,0,1,0,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0 },//qudiao 878ms
{ 1,1,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,0,0,1,0,0,1,0,1,1,1 },
{ 1,0,1,0,1,0,1,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,0 },
{ 1,1,1,1,0,1,0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,1,1,0,1,0 },
{ 1,0,1,1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,1,1,1,1,0,1,0,1,0,0,1,1,0,0,0,1,1,0,0,0,1 },
{ 0,1,0,1,1,1,0,1,0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,0,1,0,1,1,1,1,0,1,0,1,1,0,0,1,1,1 },
{ 1,1,0,1,1,1,0,0,0,1,0,1,0,0,1,0,1,1,1,0,0,1,1,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0 },
{ 1,0,1,1,1,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,1,0,0,0,1,0,1,1,1,1,1,0,1,1,1,0,0,1,1,1,0,0,1,0,0,0,0,1 },
{ 1,1,0,1,1,1,0,1,1,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0,1,1 },
{ 0,1,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,0,1,1 },
{ 0,0,0,1,1,1,1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,0,0,0,0,1,1,1 } };
};
}
namespace closedIsland {
/* 47/47 ?? */
//??????????????????????????????????,?????????????
int dfs(vector<vector<int>>& heights, int curi, int curj, vector<vector<int>>&visited, vector<vector<int>>&tagvisited)
{
if (visited[curi][curj] == 1 || (curi == 0 || curj == 0 || curi == heights.size() - 1 || curj == heights[0].size() - 1) && (heights[curi][curj] == 0)) {//edge is 1
visited[curi][curj] = 1;
return 1;
}
int l = 0, r = 0, up = 0, down = 0, other = 0;
// 2.DFS
if (tagvisited[curi][curj] == 0) {
tagvisited[curi][curj] = 1;
if (curi - 1 >= 0 && heights[curi - 1][curj] == 0) {
up = dfs(heights, curi - 1, curj, visited, tagvisited);
if (up >= 1) { visited[curi][curj] = 1; tagvisited[curi][curj] = 1; return 1; }
}
if (curj - 1 >= 0 && heights[curi][curj - 1] == 0) {
l = dfs(heights, curi, curj - 1, visited, tagvisited);
if (l >= 1) { visited[curi][curj] = 1; tagvisited[curi][curj] = 1; return 1; }
}
if (curj + 1 < heights[0].size() && heights[curi][curj + 1] == 0) {
r = dfs(heights, curi, curj + 1, visited, tagvisited);
if (r >= 1) { visited[curi][curj] = 1; tagvisited[curi][curj] = 1; return 1; }
}
if (curi + 1 < heights.size() && heights[curi + 1][curj] == 0) {
down = dfs(heights, curi + 1, curj, visited, tagvisited);
if (down >= 1) { visited[curi][curj] = 1; tagvisited[curi][curj] = 1; return 1; }
}
}
// 3. give value to this node
return visited[curi][curj];
}
void dfsisland(vector<vector<int>>& ret, int curi, int curj, vector<vector<int>>&visited) {
if (visited[curi][curj] == 1)return;
visited[curi][curj] = 1;
for (int i = 0; i < ret.size(); ++i) {
if(visited[ret[i][0]][ret[i][1]] == 0){
if ((ret[i][0] == curi&&ret[i][1] == curj + 1)) {
dfsisland(ret, ret[i][0], ret[i][1], visited);
}
if ((ret[i][0] == curi&&ret[i][1] == curj - 1)) {
dfsisland(ret, ret[i][0], ret[i][1], visited);
}
if ((ret[i][0] == curi + 1 && ret[i][1] == curj)) {
dfsisland(ret, ret[i][0], ret[i][1], visited);
}
if ((ret[i][0] == curi - 1 && ret[i][1] == curj)) {
dfsisland(ret, ret[i][0], ret[i][1], visited);
}
}
}
}
int closedIsland(vector<vector<int>>& heights) {
vector<int>cache(heights[0].size(), 0);
vector<vector<int>>visited(heights.size(), cache);
vector<vector<int>>ret;
int ans = 0;
int vc = 0;
while (vc<2) {
vector<vector<int>>tagvisited(heights.size(), cache);
for (int i = 0; i < heights.size(); ++i) {
for (int j = 0; j < heights[0].size(); ++j) {
if (heights[i][j] == 1)continue;
dfs(heights, i, j, visited, tagvisited);
}
}
vc++;
}
vector<vector<int>>tagvisited3(heights.size(), cache);
for (int i = 0; i < heights.size(); ++i) {
for (int j = 0; j < heights[0].size(); ++j) {
if (heights[i][j] == 1)continue;
dfs(heights, i, j, visited, tagvisited3);
if (visited[i][j] == 0) {
ret.push_back({ i,j });
}
}
}
/*
for(int i=0;i<ret.size();++i){
cout<<ret[i][0]<<" "<<ret[i][1]<<" "<<endl;
} */
// find island
vector<int>cachegt(100, 0);
vector<vector<int>>visitedgt(100, cachegt);
int bmw = 0;
for (int i = 0; i < ret.size(); ++i) {
if (visitedgt[ret[i][0]][ret[i][1]] == 1)continue;
dfsisland(ret, ret[i][0], ret[i][1], visitedgt);
bmw++;
}
//cout << "bmw=" << bmw << endl;
return bmw;
}
}
namespace colorBorder {
/*AC 71 62 16ms 13.6MB*/
void dfs(vector<vector<int>>& grid, int row, int col, int color, vector<vector<int>>&tag, vector<vector<int>>&visited) {
if (row == 0 || row == grid.size() - 1 || col == 0 || col == grid[0].size() - 1) {//edge situation
tag[row][col] = color;
}
if (visited[row][col] == 0) {
visited[row][col] = 1;
if (col + 1 < grid[0].size() && grid[row][col + 1] == grid[row][col])dfs(grid, row, col + 1, color, tag, visited);
else tag[row][col] = color;
if (col - 1 >= 0 && grid[row][col - 1] == grid[row][col])dfs(grid, row, col - 1, color, tag, visited);
else tag[row][col] = color;
if (row + 1 < grid.size() && grid[row + 1][col] == grid[row][col])dfs(grid, row + 1, col, color, tag, visited);
else tag[row][col] = color;
if (row - 1 >= 0 && grid[row - 1][col] == grid[row][col])dfs(grid, row - 1, col, color, tag, visited);
else tag[row][col] = color;
}
}
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
vector<int>cache(grid[0].size(), 0);
vector<vector<int>>tag(grid.size(), cache);
vector<vector<int>>visited(grid.size(), cache);
tag = grid;
dfs(grid, row, col, color, tag, visited);
return tag;
}
}
namespace cloneGraph {
/* X79 PRO aced */
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
//void dfs(Node* curhead,Node* original) {
// if (curhead->val == original->val && curhead->val!=1 && curhead->neighbors.size() == original->neighbors.size())return;
// curhead->val = original->val;
// for (int i = 0; i < original->neighbors.size(); ++i) {
// Node *cur = new Node(original->neighbors[i]->val,original->neighbors);
// curhead->neighbors.push_back(cur);
// dfs(cur, original->neighbors[i]);
// }
//}
void dfs(Node* curhead,Node*& copyhead,int visited[]) {
if (visited[curhead->val] == 0) {
cout << curhead->val << " " << curhead <<" " << copyhead->val << " " << copyhead << endl;
copyhead = new Node(curhead->val);
visited[curhead->val] = 1;
for (int i = 0; i < curhead->neighbors.size(); ++i) {
Node *cur = new Node(curhead->neighbors[i]->val);
copyhead->neighbors.push_back(cur);
dfs(curhead->neighbors[i], copyhead->neighbors[i], visited);
}
}
}
Node* cloneGraph() {
Node* n1 = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
n1->neighbors.push_back(n2);
n1->neighbors.push_back(n4);
n2->neighbors.push_back(n1);
n2->neighbors.push_back(n3);
n3->neighbors.push_back(n2);
n3->neighbors.push_back(n4);
n4->neighbors.push_back(n1);
n4->neighbors.push_back(n3);
Node *head = new Node(1);
Node *head1 = new Node(1);
int vis[10]{ 0 };
dfs(n1, head, vis); cout << endl;
return head;
}
class Solution_learning {
public:
Node* visited[101] = { nullptr };
Node* cloneGraph(Node* node) {
int size = node->neighbors.size();
Node *root = new Node(node->val, vector<Node*>{});
visited[node->val] = root;
for (int i = 0; i < size; i++) {
if (!visited[node->neighbors[i]->val])
root->neighbors.push_back(cloneGraph(node->neighbors[i]));
else
root->neighbors.push_back(visited[node->neighbors[i]->val]);
}
return root;
}
};
//if (curhead->val == original->val && curhead->val!=1 && curhead->neighbors.size() == original->neighbors.size())
//{
// cout<<"return"<<endl;
// return;
//}
//curhead=new Node(original->val);
//for (int i = 0; i < original->neighbors.size(); ++i) {
// Node *cur = new Node(original->neighbors[i]->val,original->neighbors[i]->neighbors);
// curhead->neighbors.push_back(cur);
// dfs(cur, original->neighbors[i]);
//}
//Node *cur=new Node(original->neighbors[0]->val,original->neighbors[0]->neighbors);
//curhead->neighbors.push_back(cur);
}
namespace minesweeper {
/*AC 82.75% 21% 16ms 12.4MB*/
/* fuzzy idea?all reveal??
class Solution {
public:
int dfs(int m,int n,vector<vector<char>>& board,int row,int col, vector<vector<int>>& vis) {
//8 diaganal
if (row < 0 || col < 0 || row >= m || col >= n|| board[row][col] == 'B'||board[row][col]=='1')
return 0;
if (board[row][col] == 'M') {
return 1;
}
int cur_mine = 0; int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0;
if (vis[row][col] == 0) {
vis[row][col] = 1;
a = dfs(m, n, board, row - 1, col - 1, vis);
b = dfs(m, n, board, row - 1, col, vis);
c = dfs(m, n, board, row - 1, col + 1, vis);
d = dfs(m, n, board, row + 1, col - 1, vis);
e = dfs(m, n, board, row + 1, col + 1, vis);
f = dfs(m, n, board, row, col - 1, vis);
g = dfs(m, n, board, row, col + 1, vis);
h = dfs(m, n, board, row + 1, col, vis);
vis[row][col] = 0;
}
cur_mine = a + b + c + d + e + f + g + h;
if (cur_mine == 0&&board[row][col]!='1') {
board[row][col] = 'B';
}
else{
board[row][col] = cur_mine + 48;
}
return 0;
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
vector<int>cad(board[0].size(), 0);
vector<vector<int>>vis(board.size(),cad);
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
else {
dfs(board.size(), board[0].size(), board, click[0], click[1],vis);
}
int m = board.size(); int n = board[0].size();
for (int row = 0; row < board.size(); ++row) {
for (int col = 0; col < board[0].size(); ++col) {
if (!(
(row - 1 >= 0 && col - 1 >= 0 && board[row - 1][col - 1] == 'B') ||
(row - 1 >= 0 && board[row - 1][col] == 'B' )||
(row - 1 >= 0 && col + 1 < n&&board[row - 1][col + 1] == 'B') ||
(row + 1 < m&&col + 1 < n&&board[row + 1][col + 1] == 'B') ||
(row + 1 < m&&col - 1 >= 0 && board[row + 1][col - 1] == 'B') ||
(row + 1 < m&&board[row + 1][col] == 'B') ||
(col - 1 >= 0 && board[row][col - 1] == 'B') ||
(col + 1 < n&&board[row][col + 1] == 'B')
) &&board[row][col]!='M'){
board[row][col] = 'E';
}
}
}
return board;
}
};
*/
//first decide the node value ,then dicide search the neghibor or not
int search(vector<vector<char>>& board, int row, int col) {
int ret = 0;
int n = board[0].size(); int m = board.size();
if (row - 1 >= 0 && col - 1 >= 0 && board[row - 1][col - 1] == 'M') ret++;
if (row - 1 >= 0 && board[row - 1][col] == 'M') ret++;
if (row - 1 >= 0 && col + 1 < n&&board[row - 1][col + 1] == 'M') ret++;
if (row + 1 < m&&col + 1 < n&&board[row + 1][col + 1] == 'M') ret++;
if (row + 1 < m&&col - 1 >= 0 && board[row + 1][col - 1] == 'M') ret++;
if (row + 1 < m&&board[row + 1][col] == 'M') ret++;
if (col - 1 >= 0 && board[row][col - 1] == 'M') ret++;
if (col + 1 < n&&board[row][col + 1] == 'M') ret++;
return ret;
}
void dfs(int m, int n, vector<vector<char>>& board, vector<vector<char>>& board1, int row, int col, vector<vector<int>>& vis) {
//8 diaganal
if (row < 0 || col < 0 || row >= m || col >= n)
return;
if (vis[row][col] == 1 || board1[row][col] != 'E')return;
vis[row][col] = 1;
int cur_mine = search(board1, row, col);
if (cur_mine == 0) {//no mines in 8 directions , recursive for this directions
board[row][col] = 'B';
dfs(m, n, board, board1, row - 1, col - 1, vis);
dfs(m, n, board, board1, row - 1, col, vis);
dfs(m, n, board, board1, row - 1, col + 1, vis);
dfs(m, n, board, board1, row + 1, col - 1, vis);
dfs(m, n, board, board1, row + 1, col + 1, vis);
dfs(m, n, board, board1, row, col - 1, vis);
dfs(m, n, board, board1, row, col + 1, vis);
dfs(m, n, board, board1, row + 1, col, vis);
}
else {
board[row][col] = cur_mine + 48;
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
vector<vector<char>>board1 = board;
vector<int>cad(board[0].size(), 0);
vector<vector<int>>vis(board.size(), cad);
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
else {
dfs(board.size(), board[0].size(), board, board1, click[0], click[1], vis);
}
return board;
}
void usecases(){
vector<vector<char>> board{
{ 'B' ,'1' ,'E' ,'E' ,'B' },
{ 'B' ,'1' ,'M' ,'E' ,'B' },
{ 'B' ,'1' ,'1' ,'1' ,'B' },
{ 'B' ,'E' ,'E' ,'E' ,'B' }
};
vector<int> click({ 3,0 });
minesweeper::updateBoard(board,click);
}
}
namespace depthoftree {
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct 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) {}
}*pTreenode;
pTreenode n1 = new TreeNode(1);
pTreenode n2 = new TreeNode(2);
pTreenode n3 = new TreeNode(3);
pTreenode n4 = new TreeNode(4);
pTreenode n5 = new TreeNode(5);
pTreenode n6 = new TreeNode(2);
pTreenode n7 = new TreeNode(-6);
pTreenode n8 = new TreeNode(-6);
pTreenode n9 = new TreeNode(-6);
pTreenode n10 = new TreeNode(10);
pTreenode n11 = new TreeNode(11);
int depthoftree(pTreenode node) {
if (node == nullptr)return -1;
return depthoftree(node->left) > depthoftree(node->right) ? depthoftree(node->left) + 1 : depthoftree(node->right) + 1;
}
//
int smg(pTreenode node) {
if (!node)return 0;
smg(node->left);
smg(node->right);
/*.....*/
return 0;
}
//
void f() {
//n1->left = n2;
n1->right = n3;
//n2->left = n4;
//n2->right = n5;
n3->left = n2;
n3->right = n4;
n4->right = n5;
//n5->left = n6;
//n6->left = n7;
//n6->right = n8;
//n7->left = n9;
//n7->right = n9;
//n3->left = n10;
//n10->left = n11;
//cout<<longestConsecutive(n1);
}
}
namespace longesttreeroute {
/*AC 32.7% 61% 28ms 26.9MB */
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct 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) {}
}*pTreenode;
int dfs1(TreeNode* root, int &max) {
if (!root)
return 0;
int lmax = dfs1(root->left, max);
int rmax = dfs1(root->right, max);
int curmax = root->val;
if (lmax>0)
curmax += lmax;
if (rmax>0)
curmax += rmax;
if (curmax>max)max = curmax;
if (lmax > 0 && lmax > rmax)return root->val + lmax;
if (rmax > 0 && rmax > lmax)return root->val + rmax;
return root->val;
}
int maxPathSum(TreeNode* root) {
int max = root->val;
dfs1(root, max);
return max;
}
}
namespace longestConsecutive {
/*AC 93.03% 37% 28ms 32MB */
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct 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) {}
}*pTreenode;
//void dfs(TreeNode* root, int lastval, int lastmax, int &max) {
// //find every node continus increasing route
// if (!root) return;
// if (lastval + 1 == root->val) {
// lastmax += 1;
// if (lastmax > max)max = lastmax;
// dfs(root->left, root->val, lastmax, max);
// dfs(root->right, root->val, lastmax, max);
// }
// else {
// lastmax = 1;
// dfs(root->left, root->val, lastmax, max);
// dfs(root->right, root->val, lastmax, max);
// }
//}
//int longestConsecutive(TreeNode* root) {
// if (!root)return 0;
// int max = 1;
// dfs(root, root->val, 1, max);
// return max;
//}
//LC 865 most deep child tree of deepest nodes
/*first try (something diule)
void dfs(TreeNode* root, TreeNode* fa, TreeNode*& res,int curmax,int &max,unordered_map<int,TreeNode*>&tag) {
//???????????????????????
if (!root)return;
if(tag.find(root->val)==tag.end()){
tag.insert({root->val,root});
}
curmax += 1;
if (curmax > max){
max = curmax;
res = fa;
}
else if(curmax==max){
}
dfs(root->left, root, res, curmax, max);
dfs(root->right, root, res, curmax, max);
}
*/
//first find deepest distance
int depth(TreeNode* root) {
if (!root)return 0;
return depth(root->left) > depth(root->right) ? depth(root->left) + 1 : depth(root->right) + 1;
}
//second find how many deepest
void everydeep(TreeNode* root,int curmax,int max,unordered_map<int, TreeNode*>&deepnodes) {
if (!root)return;
if (curmax == max && deepnodes.find(root->val) == deepnodes.end()) {
deepnodes.insert({root->val,root});
}
everydeep(root->left, curmax + 1, max, deepnodes);
everydeep(root->right, curmax + 1, max, deepnodes);
}
void findeverydeep(TreeNode* root,int curdeep,int &max,int a[]) {
if (!root)return;
curdeep++;
}
void dfs(TreeNode* root, TreeNode* fa, TreeNode*& res,int curmax,int &max) {
if (!root)return;
curmax += 1;
if (curmax > max)max = curmax;
res = fa;
dfs(root->left, root, res, curmax, max);
dfs(root->right, root, res, curmax, max);
}
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
TreeNode*res = root;
int max = 0;
if (!root->left&&!root->right)return root;
dfs(root, root, res, 0, max);
return res;
}
}
namespace longestZigZag {
/*AC 5% 5% 800+ms 327.3MB */
// 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) {}
};
vector<vector<int>> dfs(TreeNode* root, int &max) {
//derection(0):left (1):right
//?????????????????????????????????????????????????
//????????????DFS??
//?????????????????????????????
//????????????????????????
//???????????????????????????????????????
//????????????????????????
vector<vector<int>>cp = { { 0,0 } };
if (!root)return cp;
int drmax = dfs(root->right, max)[0][0];
int dlmax = dfs(root->left, max)[0][1];
cp[0][0] = dlmax + 1;
cp[0][1] = drmax + 1;
int curlevelmax = 0;
curlevelmax = dlmax>drmax ? dlmax + 1 : drmax + 1;
if (curlevelmax>max)max = curlevelmax;
return cp;
}
int longestZigZag(TreeNode* root) {
int max = 0;
dfs(root, max);
return max - 1;
}
}
namespace minimumEffortPath {
void dfs(vector<vector<int>>& heights,int curi,int curj, int lastval, int curmin, int &min, vector<vector<int>>&vis) {
if (curi < 0 || curj < 0 || curi >= heights.size() - 1 || curj >= heights[0].size() - 1||vis[curi][curj]==1)return;
if (curi == heights.size() - 1 && curj == heights[0].size() - 1) {
if (curmin<min)min = curmin;
return;
}
vis[curi][curj] = 1;
int secmin = heights[curi][curj]>lastval ? heights[curi][curj] - lastval : lastval - heights[curi][curj];
if (secmin >= min)return;
if (secmin < curmin)curmin = secmin;
dfs(heights, curi, curj + 1, heights[curi][curj], curmin, min, vis);
dfs(heights, curi, curj - 1, heights[curi][curj], curmin, min, vis);
dfs(heights, curi + 1, curj, heights[curi][curj], curmin, min, vis);
dfs(heights, curi - 1, curj, heights[curi][curj], curmin, min, vis);
vis[curi][curj] = 1;
}
int minimumEffortPath(vector<vector<int>>& heights) {
//???????????????DFS??????????????????????????????????????????????
int min = -1;
vector<int>cache(heights[0].size(), 0);
vector<vector<int>>vis(heights.size(), cache);
int curmin = 10000000;
dfs(heights, 0, 0, heights[0][0], curmin, min, vis);
return min;
}
}
namespace longestConsecutive {
typedef 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) {}
}treenode,*ptreenode;
//全树最长连续（递增或递减）序列
vector<vector<int>> dfs_zeng(TreeNode* root, int lastval, int &max, vector<vector<int>>res) {
/*AC 8.24% 7.06% 64ms 50.7MB */
//每个点作为必经点都需要判断，这玩意搜索域是全部节点，只不过二分下去的O（N）复杂度还行，不是很高
//经过一个点的最长连续路径描述（必由下列情况之一构成）[分析过程]：
//1.左边递减最长+右边递增最长
//2.左边递增最长+右边递减最长
//3.以上二者必有一个会是当前节点最长路径
//z总结：必须经过某一个点的最长递减路径和最长递增路径之和是该点的最长总路径
//(注意：本题的序列是整数连续，并不是单调递增，一开始写的递增，最后发现用例有问题，这点题意没说太明白)
if (!root)
return{ { 0, 0 } };
//cout << "root=" << root->val << endl;
vector<vector<int>>cacheA = dfs_zeng(root->left, root->val, max, res);
vector<vector<int>>cacheB = dfs_zeng(root->right, root->val, max, res);
int a = cacheA[0][0];//left decrease MAX
int b = cacheA[0][1];//left increase MAX
int c = cacheB[0][0];//right decrease MAX
int d = cacheB[0][1];//right increase MAX
int downdecrease = 0; // current node decrease MAX
int downincrease = 0;// current node increase MAX
//cout << "a=" << a << " b=" << b << " c=" << c << " d=" << d << endl;
//decrease
if (root->left && root->val == root->left->val + 1 || root->right && root->val == root->right->val + 1) {
if (root->left && root->val == root->left->val + 1 && root->right && root->val == root->right->val + 1) {
downdecrease = a>c ? a + 1 : c + 1;
}
else if (root->left && root->val == root->left->val + 1) {
downdecrease = a + 1;
}
else {
downdecrease = c + 1;
}
}
//increase
if (root->left && root->val + 1 == root->left->val || root->right && root->val + 1 == root->right->val) {
if (root->left && root->val + 1 == root->left->val&&root->right && root->val + 1 == root->right->val) {
downincrease = b>d ? b + 1 : d + 1;
}
else if (root->left && root->val + 1 == root->left->val) {
downincrease = b + 1;
}
else {
downincrease = d + 1;
}
}
//cout << "downdecrease=" << downdecrease << " downincrease=" << downincrease << endl;
if (downdecrease > 0)res[0][0] = downdecrease;
if (downincrease > 0)res[0][1] = downincrease;
int curmax = res[0][0] + res[0][1] + 1;
//if (curmax == 0) curmax += 1;
if (curmax > max)max = curmax;
return res;
}
int longestConsecutive(TreeNode* root) {
if (!root)return 0;
int max = 1; //int zeng = 1; int jian = 1;
vector<vector<int>>res{ { 0,0 } };
dfs_zeng(root, root->val, max, res);
return max;
}
//全树最长同值序列
/*AC 79.95% 57% 112ms 70MB */
int dfs_tongzhi(TreeNode* root, int lastval, int &max) {// lastmax: default single max of this level
if (!root)return 0;
int curmax = 0;
int lmax = 0;
int rmax = 0;
lmax = dfs_tongzhi(root->left, root->val, max);
rmax = dfs_tongzhi(root->right, root->val, max);
if (rmax > 0)curmax = curmax + rmax;
if (lmax > 0)curmax = curmax + lmax;
if (curmax > max)max = curmax;
int cursinglemax = rmax > lmax ? rmax : lmax;//current single max
if (root->val == lastval) {
return cursinglemax + 1;
}
else {
return 0;
}
return 0;
}
int longestUnivaluePath(TreeNode* root) {
if (!root)return 0;
int max = 0;
dfs_tongzhi(root, root->val - 1, max);
return max;
}
//最深叶子最小公共祖先
/*AC 7.59% 10.76% 88ms 16.2MB */
int depth(TreeNode*root) {
if (!root)return 0;
return depth(root->left)>depth(root->right) ? depth(root->left) + 1 : depth(root->right) + 1;
}
void everydeep(TreeNode*root, int curmax, int max, TreeNode*fa, unordered_map<int, TreeNode*>&deepnodes, unordered_map<int, TreeNode*>&ancester) {
if (!root)return;
ancester.insert({ root->val,fa });
if (curmax == max&&deepnodes.find(root->val) == deepnodes.end()) {
deepnodes.insert({ root->val,root });
}
everydeep(root->left, curmax + 1, max, root, deepnodes, ancester);
everydeep(root->right, curmax + 1, max, root, deepnodes, ancester);
}
bool canreach(TreeNode*root, unordered_map<int, TreeNode*>&deepnodes, int &hege) {
if (!root)return false;
if (deepnodes.find(root->val) != deepnodes.end())hege++;
if (hege == deepnodes.size())return true;
return canreach(root->left, deepnodes, hege) || canreach(root->right, deepnodes, hege);
}
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
unordered_map<int, TreeNode*>deepnodes;
unordered_map<int, TreeNode*>ancester;
int dep = depth(root);
everydeep(root, 1, dep, root, deepnodes, ancester);
if (deepnodes.size() == 1)return deepnodes.begin()->second;
TreeNode*curnode = ancester.find(deepnodes.begin()->second->val)->second;
int c = 0;
while (1) {
if (canreach(curnode, deepnodes, c)) return curnode;
else {
curnode = ancester.find(curnode->val)->second;
c = 0;
}
}
return root;
}
void f() {
ptreenode n1 = new TreeNode(1);
ptreenode n2 = new TreeNode(2);
ptreenode n3 = new TreeNode(3);
n2->left = n1;
n2-> right = n3;
cout << longestUnivaluePath(n2);
}
}
namespace maximumMinimumPath {
//LC 1102 得分最高的路径（路径上最小值的最大值）
/*AC 97.52% 53.42% 160ms 43MB */
bool MinDFS(vector<vector<int>>&heights, int curi, int curj, int min, vector<vector<int>>&vis) {
if (curi<0 || curj<0 || curi >= heights.size() || curj >= heights[0].size() || vis[curi][curj] == 1)return false;
if (heights[curi][curj]<min)return false;
if (curi == heights.size() - 1 && curj == heights[0].size() - 1)return true;
vis[curi][curj] = 1;
return
MinDFS(heights, curi, curj - 1, min, vis) ||
MinDFS(heights, curi, curj + 1, min, vis) ||
MinDFS(heights, curi - 1, curj, min, vis) ||
MinDFS(heights, curi + 1, curj, min, vis);
}
int maximumMinimumPath(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<int>cache(grid[0].size(), 0);
vector<vector<int>>vis1(grid.size(), cache);
int max = grid[0][0]>grid[row - 1][col - 1] ? grid[row - 1][col - 1] : grid[0][0];//上界是两个里面较小的一个
int left = 0, right = max, mid = 0;//
if (MinDFS(grid, 0, 0, max, vis1))return max;
while (left<right) {
mid = (right - left) / 2 + left;
vector<vector<int>>vis(grid.size(), cache);
bool toyota = MinDFS(grid, 0, 0, mid, vis);
if (toyota&&left != mid)left = mid;
else if (!toyota)right = mid;
else if (toyota&&left == mid) {
return mid;
}
}
return mid;
}
//idea1 回溯（正确，但超时）
//void dfs(vector<vector<int>>& grid, int curi, int curj, vector<int>tmp, int &min, int smin, vector<vector<int>>& vis) {
// if (curi<0 || curj<0 || curi >= grid.size() || curj >= grid[0].size() || vis[curi][curj] == 1 || grid[curi][curj] <= min || smin <= min)return;
// if (curi == grid.size() - 1 && curj == grid[0].size() - 1) {
// //for(auto i:tmp)cout<<i<<" ";cout<<endl;
// int curmin = smin < grid[curi][curj] ? smin : grid[curi][curj];
// if (curmin>min) min = curmin;
// cout << "cumin=" << curmin << " quanjuMAX=" << min << endl;
// return;
// }
// vis[curi][curj] = 1;
// if (smin>grid[curi][curj]) smin = grid[curi][curj];
// //tmp.push_back(grid[curi][curj]);
// dfs(grid, curi, curj + 1, tmp, min, smin, vis);
// dfs(grid, curi, curj - 1, tmp, min, smin, vis);
// dfs(grid, curi + 1, curj, tmp, min, smin, vis);
// dfs(grid, curi - 1, curj, tmp, min, smin, vis);
// vis[curi][curj] = 0;
//}
//int maximumMinimumPath(vector<vector<int>>& grid) {
// int min = -1;
// vector<int>cache(grid[0].size(), 0);
// vector<vector<int>>vis(grid.size(), cache);
// vector<int>tmp;
// int smin = 100000000;
// dfs(grid, 0, 0, tmp, min, smin, vis);
// return min;
//}
//idea2 可能的排序再找（正确，也超时）以全局倒数第二小的路径能不能找到？以倒数第三小的能不能找到？。。。直到找到的倒数第N小的之后停止,上面暴力方法数据量一旦上来就hold不住了
//vector<int>quchong(vector<int>&) {
// vector<int>shuanglihe;
// for (int i = 0; i<amp.size(); ++i) {
// shuanglihe.push_back(amp[i]);
// while (i + 1<amp.size() && amp[i] == amp[i + 1])i++;
// }
// return shuanglihe;
//}
//vector<int>findmostsmall(vector<vector<int>>& grid) {
// int row = grid.size();
// int col = grid[0].size();
// vector<int>amp;
// for (int i = 0; i<row; ++i) {
// for (int j = 0; j<col; ++j) {
// amp.push_back(grid[i][j]);
// }
// }
// sort(amp.rbegin(), amp.rend());
// return quchong(amp);
//}
//bool dfs(vector<vector<int>>& grid, int curi, int curj, int min, vector<vector<int>>&vis) {
// if (curi<0 || curj<0 || curi >= grid.size() || curj >= grid[0].size() || vis[curi][curj] == 1 || grid[curi][curj]<min)return false;
// if (curi == grid.size() - 1 && curj == grid[0].size() - 1 && grid[curi][curj] >= min) { return true; }
// vis[curi][curj] = 1;
// bool cvt = dfs(grid, curi, curj + 1, min, vis) || dfs(grid, curi, curj - 1, min, vis) || dfs(grid, curi + 1, curj, min, vis) || dfs(grid, curi - 1, curj, min, vis);
// vis[curi][curj] = 0;
// return cvt;
//}
//int maximumMinimumPath(vector<vector<int>>& grid) {
// vector<int>cache = findmostsmall(grid);
// vector<int>smallvec(grid[0].size(), 0);
// vector<vector<int>>vis(grid.size(), smallvec);
// for (auto i : cache)cout << i << " ";
// int k = 0;
// for (int i = 0; i<cache.size(); ++i) { if (cache[i] == grid[0][0])k = i; }
// for (int i = k; i < cache.size(); ++i) {
// cout << endl << "current i is:" << cache[i] << endl;
// if (dfs(grid, 0, 0, cache[i], vis)) {
// return cache[i];
// }
// }
// //cout << endl;
// //cout << dfs(grid, 0, 0, 64, vis);
// return 0;
//}
}
namespace minimumEffortPath {
/*AC 43% 39% 232ms 40.6MB */
//LC 1631 和 LC 1102相似，暴力会超时
//void searchFirstMin(vector<vector<int>>& heights, int curi, int curj, int curmin,int& min,vector<vector<int>>&vis) {
// if (curi == heights.size() - 1 && curj == heights[0].size() - 1) {
// min = curmin;
// return;
// }
// if (vis[curi][curj] == 0) {
// vis[curi][curj] = 1;
// int left = 0, right = 0, up = 0, down = 0;
// int a = 0, b = 0, c = 0, d = 0;
// if (curj - 1 >= 0) {
// cout << "??";
// left = heights[curi][curj - 1];
// a = left > heights[curi][curj] ? left - heights[curi][curj] : heights[curi][curj] - left;
// }
// if (curj + 1 < heights[0].size() && vis[curi][curj + 1] == 0) {
// right = heights[curi][curj + 1];
// b = right > heights[curi][curj] ? right - heights[curi][curj] : heights[curi][curj] - right;
// }
// if (curi - 1 >= 0 && vis[curi - 1][curj] == 0) {
// up = heights[curi - 1][curj];
// c = up > heights[curi][curj] ? up - heights[curi][curj] : heights[curi][curj] - up;
// }
// if (curi + 1 < heights.size() && vis[curi + 1][curj] == 0) {
// down = heights[curi + 1][curj];
// d = down > heights[curi][curj] ? down - heights[curi][curj] : heights[curi][curj] - down;
// }
// vector<int>cache;
// cache.push_back(a);
// cache.push_back(b);
// cache.push_back(c);
// cache.push_back(d);
// sort(cache.begin(), cache.end());
// if (curmin < cache[0])curmin = cache[0];
// if (cache[0] == a) {
// curmin = a;
// searchFirstMin(heights, curi, curj - 1, curmin, min, vis);
// }
// else if (cache[0] == b) {
// curmin = b;
// searchFirstMin(heights, curi, curj + 1, curmin, min, vis);
// }
// else if (cache[0] == c) {
// curmin = c;
// searchFirstMin(heights, curi - 1, curj, curmin, min, vis);
// }
// else if (cache[0] == d) {
// curmin = d;
// searchFirstMin(heights, curi + 1, curj, curmin, min, vis);
// }
// }
//
//}
//void dfs(vector<vector<int>>& heights, int curi, int curj, int curmin, int &min, int lastval, vector<vector<int>>&vis) {
// if (curi < 0 || curj < 0 || curi >= heights.size() || curj >= heights[0].size() || vis[curi][curj] == 1 || (curmin >= min))
// return;
// if (curi == heights.size() - 1 && curj == heights[0].size() - 1) {
// int levelmin1 = heights[curi][curj] < lastval ? lastval - heights[curi][curj] : heights[curi][curj] - lastval;
// curmin = levelmin1 > curmin ? levelmin1 : curmin;
// if (curmin < min)min = curmin;
// return;
// }
// int levelmin = heights[curi][curj] < lastval ? lastval - heights[curi][curj] : heights[curi][curj] - lastval;
// if (levelmin > curmin) curmin = levelmin;//单趟冒泡找最大
// if (curmin >= min)return;
// vis[curi][curj] = 1;
// dfs(heights, curi, curj + 1, curmin, min, heights[curi][curj], vis);
// dfs(heights, curi, curj - 1, curmin, min, heights[curi][curj], vis);
// dfs(heights, curi + 1, curj, curmin, min, heights[curi][curj], vis);
// dfs(heights, curi - 1, curj, curmin, min, heights[curi][curj], vis);
// vis[curi][curj] = 0;
//}
//int minimumEffortPath(vector<vector<int>>& heights) {
// if (heights.size() == 1 && heights[0].size() == 1)return 0;
//
// vector<int>cache(heights[0].size(), 0);
// vector<vector<int>>vis(heights.size(), cache);
// int min = 100000000;
// searchFirstMin(heights,0,0,1000000,min,vis);
// cout << "min==" << min << endl;
// vector<vector<int>>vis1(heights.size(), cache);
// dfs(heights, 0, 0, 0, min, 0, vis1);
// return min;
//}
//本函数功能：寻找，按照阈值k来算找一找有没有可以走通的路（不加引用同样超时）加了引用AC
bool MinDFS(vector<vector<int>>& heights, int curi, int curj, int lastval, int min, vector<vector<int>>&vis) {
if (curi<0 || curj<0 || curi >= heights.size() || curj >= heights[0].size() || vis[curi][curj] == 1) return false;
int curlevel = lastval > heights[curi][curj] ? lastval - heights[curi][curj] : (heights[curi][curj] - lastval);
if (curi == heights.size() - 1 && curj == heights[0].size() - 1) {
int curlevel1 = lastval > heights[curi][curj] ? lastval - heights[curi][curj] : (heights[curi][curj] - lastval);
if (curlevel1 <= min) return true;
return false;
}
if (curlevel <= min) {
vis[curi][curj] = 1;
return
MinDFS(heights, curi, curj - 1, heights[curi][curj], min, vis) ||
MinDFS(heights, curi, curj + 1, heights[curi][curj], min, vis) ||
MinDFS(heights, curi - 1, curj, heights[curi][curj], min, vis) ||
MinDFS(heights, curi + 1, curj, heights[curi][curj], min, vis);
}
return false;
}
int minimumEffortPath(vector<vector<int>>& heights) {
//二分
vector<int>cache(heights[0].size(), 0);
if (heights.size() == 1 && heights[0].size() == 1)return 0;
int left = 0, right = 1e6, mid = 0;
//cout<<MinDFS(heights, 0, 0, heights[0][0], 1561, vis);
while (left<right) {
mid = (right + left) / 2;
//cout << mid << endl;
vector<vector<int>>vis(heights.size(), cache);
if (MinDFS(heights, 0, 0, heights[0][0], mid, vis) == true) {
right = mid;//如果中间值可以，右边界更新为中间点
}
else if (left == mid) {
return right;
}
else {
left = mid;//如果中间值不可以，左边界更新为中间点
}
}
// vector<vector<int>>vis(heights.size(), cache);
// if(MinDFS(heights, 0, 0, heights[0][0], mid, vis) == true && MinDFS(heights, 0, 0, heights[0][0], mid-1, vis) == false){
// return mid-1;
// }
return mid;
}
}
namespace FrogJump{
//LC 403 Frog Jump
/* */
/// version 1( pure DFS ) OVERTIME
bool dfs1(vector<int>& stones,int lastK, int curpos,unordered_map<int,int>&um) {
//now ,we have 3 choice K-1 K K+1 ; POS:curpos
if (curpos == stones.size() - 1)return true;
bool curres = false; bool a(false), b(false), c(false);
if (um.find(stones[curpos] + lastK - 1) != um.end() && lastK>1) {
a = dfs1(stones, lastK - 1, um.find(stones[curpos] + lastK - 1)->second, um);
}
if (um.find(stones[curpos] + lastK) != um.end()) {
b = dfs1(stones, lastK, um.find(stones[curpos] + lastK)->second, um);
}
if (um.find(stones[curpos] + lastK + 1) != um.end()) {
c = dfs1(stones, lastK + 1, um.find(stones[curpos] + lastK + 1)->second, um);
}
curres = a || b || c;
return curres;
}
bool canCross1(vector<int>& stones) {
if (stones.size() == 1)return true;
if (stones.size() > 1 && stones[1] != 1)return false;
unordered_map<int, int>um;
for (int i = 0; i < stones.size(); ++i)um.insert({ stones[i], i });
return dfs1(stones, 1, 1, um);
}
///version 2
bool dfs2(vector<int>& stones, int lastK, int curpos, unordered_map<int, int>&um,unordered_map<int,int>&tag) {
//now ,we have 3 choice K-1 K K+1 ; POS:curpos
if (curpos == stones.size() - 1)return true;
bool curres(false); bool a(false), b(false), c(false);
if (um.find(stones[curpos] + lastK - 1) != um.end() && lastK>1) {
a = dfs2(stones, lastK - 1, um.find(stones[curpos] + lastK - 1)->second, um, tag);
}
if (um.find(stones[curpos] + lastK) != um.end()) {
b = dfs2(stones, lastK, um.find(stones[curpos] + lastK)->second, um, tag);
}
if (um.find(stones[curpos] + lastK + 1) != um.end()) {
c = dfs2(stones, lastK + 1, um.find(stones[curpos] + lastK + 1)->second, um, tag);
}
curres = a || b || c;
return curres;
}
bool canCross2(vector<int>& stones) {
if (stones.size() == 1)return true;
if (stones.size() > 1 && stones[1] != 1)return false;
unordered_map<int, int>um;
for (int i = 0; i < stones.size(); ++i)um.insert({ stones[i], i });
unordered_map<int, int>tag;
return dfs2(stones, 1, 1, um, tag);
}
//version 3 (DFS+UltraMemory [DP?]) /*AC 33.54% 5.38% 156ms 397.5MB */
bool dfs3(vector<int>& stones, int lastK, int curpos, unordered_map<int, int>&um,vector<vector<int>>&tag) {
//now ,we have 3 choice K-1 K K+1 ; POS:curpos
if (curpos == stones.size() - 1)return true;
bool a(false), b(false), c(false);
if (um.find(stones[curpos] + lastK - 1) != um.end() && lastK>1) {
if(tag[curpos][lastK-1]==-1)
a = dfs3(stones, lastK - 1, um.find(stones[curpos] + lastK - 1)->second, um, tag);
if (!a)tag[curpos][lastK - 1] = 0;
else return true;
}
if (um.find(stones[curpos] + lastK) != um.end()) {
if (tag[curpos][lastK] == -1)
b = dfs3(stones, lastK, um.find(stones[curpos] + lastK)->second, um, tag);
if (!b)tag[curpos][lastK] = 0;
else return true;
}
if (um.find(stones[curpos] + lastK + 1) != um.end()) {
if (tag[curpos][lastK + 1] == -1)
c = dfs3(stones, lastK + 1, um.find(stones[curpos] + lastK + 1)->second, um, tag);
if (!c)tag[curpos][lastK + 1] = 0;
else return true;
}
return a || b || c;
}
bool canCross3(vector<int>& stones) {
if (stones.size() == 1)return true;
if (stones.size() > 1 && stones[1] != 1)return false;
unordered_map<int, int>um;
for (int i = 0; i < stones.size(); ++i)um.insert({ stones[i], i });
vector<int>cache(2000, -1);
vector<vector<int>>tag(2000, cache);
return dfs3(stones, 1, 1, um, tag);
}
}
下面是测试用例函数和主函数
int usecase() {
//vector<vector<int>>ret{ {1,1},{1,2},{1,3} ,{1,4} ,{2,1} ,{2,3} ,{ 2,4 } ,{3,1} ,{3,2} ,{3,3} ,{3,4},{ 3,5},{3,6} };
//vector<vector<int>>visitedcc(ret.size(), {0,0});
//cloneGraph::cloneGraph();
//char a = '1';//49
//printf("%c\n",1+48);
//cout << a + 48 << endl;
vector<int>amp0{0, 1, 2, 3, 6, 7, 8, 10};
vector<int>amp1{ 0,1,3,5,6,8,12,17,18,19,20,22,24,25,26,27,28,29,30,31,32,33,34,35,36,37,39,40,41,42,43,44,46,47,48,49,50,51,52,53,54,55,57,58,59,60,61,62,63,64,65,66,68,69,70,73,75,77,79,80,82,85,98,99,100,101,102,103,111,124,137,150,163,177,192 };
int dif = 0;
int v = 0;
cout << "{";
for (int i = 1; i <= 2000; ++i) {
dif++;
v += dif;
cout << v << ",";
}cout << "}";
//cout<<FrogJump::canCross3(amp1);
return 0;
}
//**************************main func************************//
void main()
{
clock_t start = clock();
//vector<int> nums{ 1,2,3,4,5 };
//vector<vector<int>> ta = permuteUnique(nums);;
//for (int i = 0; i < ta.size(); ++i) {
// for (int j = 0; j < ta[0].size(); ++j) {
// cout << ta[i][j] << " ";
// }
// cout << endl;
//}
//printf("%d %d",'A'+32,'a');
usecase()
;
{
clock_t end = clock();
cout <<endl<< end - start << "ms" << endl;
system("pause");
}
}
