【LeetCode】BFS（共43题）

【101】Symmetric Tree

判断一棵树是不是对称。

题解：直接递归判断了，感觉和bfs没有什么强联系，当然如果你一定要用queue改写的话，勉强也能算bfs。

// 这个题目的重点是比较对象是左子树的左儿子和右子树的右儿子，左子树的右儿子和右子树的左儿子。不要搞错。

// 直接中序遍历的话会有错的情况，最蠢的情况是数字标注改一改。。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 // 这个题目的重点是 比较对象是 左子树的左儿子和右子树的右儿子， 左子树的右儿子和右子树的左儿子。不要搞错。
11 // 直接中序遍历的话会有错的情况，最蠢的情况是数字标注改一改。。
12 class Solution {
13 public:
14     bool isSymmetric(TreeNode* left, TreeNode* right) {
15         if (left == NULL && right == NULL) {return true;}
16         if (left == NULL || right == NULL) {return false;}
17         return (left->val == right->val) && isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
18     }
19     bool isSymmetric(TreeNode* root) {
20         if (!root) {
21             return true;
22         }
23         return isSymmetric(root->left, root->right);
24     }
25 };

View Code

【102】Binary Tree Level Order Traversal

二叉树的层级遍历。

题解：两个队列直接遍历。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrder(TreeNode* root) {
13         vector<vector<int>> ans;
14         if (!root) {
15             return ans;
16         }
17         queue<TreeNode*> que1, que2;
18         que1.push(root);
19         while (!que1.empty()) {
20             vector<int> temp;
21             while (!que1.empty()) {
22                 TreeNode* node = que1.front();
23                 que1.pop();
24                 temp.push_back(node->val);
25                 if (node->left) {
26                     que2.push(node->left);
27                 }
28                 if (node->right) {
29                     que2.push(node->right);
30                 }
31             }
32             ans.push_back(temp);
33             temp.clear();
34             swap(que1, que2);
35         }
36         return ans;
37     }
38 };

View Code

【103】Binary Tree Zigzag Level Order Traversal

二叉树的蛇形层级遍历。

题解：我是直接用了两个栈，当然，也可以直接层级遍历出结果然后reverse。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
13         vector<vector<int>> ans;
14         if (!root) {return ans;}
15         stack<TreeNode*> st1, st2;
16         st1.push(root);
17         bool reverse = true;
18         while (!st1.empty()) {
19             vector<int> temp;
20             while (!st1.empty()) {
21                 TreeNode* node = st1.top();
22                 st1.pop();
23                 temp.push_back(node->val);
24                 if (reverse) {
25                     if (node->left) {
26                         st2.push(node->left);
27                     }
28                     if (node->right) {
29                         st2.push(node->right);
30                     }
31                 } else {
32                     if (node->right) {
33                         st2.push(node->right);
34                     }
35                     if (node->left) {
36                         st2.push(node->left);
37                     }
38                 }
39             }
40             ans.push_back(temp);
41             temp.clear();
42             swap(st1, st2);
43             reverse = 1 - reverse;
44         }
45         return ans;
46     }
47 };

View Code

【107】Binary Tree Level Order Traversal II

二叉树从下往上的层级遍历

题解：我直接把层级遍历reverse了一下。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrderBottom(TreeNode* root) {
13         vector<vector<int>> ans;
14         if (!root) {
15             return ans;
16         }
17         queue<TreeNode*> que1, que2;
18         que1.push(root);
19         while (!que1.empty()) {
20             vector<int> temp;
21             while (!que1.empty()) {
22                 TreeNode* node = que1.front();
23                 que1.pop();
24                 temp.push_back(node->val);
25                 if (node->left) {
26                     que2.push(node->left);
27                 }
28                 if (node->right) {
29                     que2.push(node->right);
30                 }
31             }
32             ans.push_back(temp);
33             temp.clear();
34             swap(que1, que2);
35         }
36         reverse(ans.begin(), ans.end());
37         return ans;
38     }
39 };

View Code

【111】Minimum Depth of Binary Tree

返回一棵二叉树的最短的高度，最短的高度的定义是从根开始到没有左右儿子的叶子节点的最短的距离。

题解：直接bfs，判断出叶子节点就停止。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int minDepth(TreeNode* root) {
13         int ans = 0;
14         if (!root) {return ans;}
15         queue<TreeNode*> que, que2;
16         que.push(root);
17         bool finish = false;
18         while (!que.empty()) {
19             while (!que.empty()) {
20                 TreeNode* node = que.front();
21                 que.pop();
22                 if (node == NULL) {continue;}
23                 if (node->left == NULL && node->right == NULL) {
24                     finish = true;
25                     break;
26                 } else {
27                     que2.push(node->left);
28                     que2.push(node->right);
29                 }
30             }
31             ans++;
32             if (finish) {
33                 break;
34             }
35             swap(que, que2);
36         }
37         return ans;
38     }
39 };

View Code

【126】Word Ladder II

题目和127题一样，区别在于这题要求返回全部最短路径。

题解：修改了一下127题的题解，在bfs的时候增加一个层次数组，把每层走过的单词都存起来，一旦找到了目标单词，回溯整个层级数组得到答案。

 1 class Solution {
 2 public:
 3     bool distance1(string& s, string& t) {
 4         int n = s.size();
 5         int dis = 0;
 6         for (int i = 0; i < n; ++i) {
 7             if (s[i] != t[i]) {
 8                 ++dis;
 9             }
10             if (dis >= 2) { return false; }
11         }
12         return dis == 1 ? true : false;
13     }
14     void dfs(vector<vector<string>>& ans, vector<string>& temp, string curWord, int level) {
15         if (temp.back() == beginW) {
16             ans.push_back(temp);
17         }
18         if (level == wordLevel.size()) { return; }
19         vector<string> list = wordLevel[level];
20         for (auto word : list) {
21             if (distance1(word, curWord)) {
22                 temp.push_back(word);
23                 dfs(ans, temp, word, level+1);
24                 temp.pop_back();
25             }
26         }
27     }
28     vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
29         vector<vector<string>> ans;
30         if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) {return ans;}
31         queue<string> que, que2;
32         set<string> st;
33         que.push(beginWord);
34         bool findAns = false;
35         while(!que.empty()) { 
36             vector<string> temp;
37             while (!que.empty()) {
38                 string str = que.front();
39                 temp.push_back(str);
40                 que.pop();
41                 for (auto word : wordList) {
42                     if (distance1(str, word) && st.find(word) == st.end()) {
43                         if (word == endWord) {
44                             findAns = true;
45                         }
46                         que2.push(word);
47                         st.insert(word);
48                     }
49                 }
50             }
51             wordLevel.push_back(temp);
52             if (findAns) {
53                 break;
54             }
55             swap(que, que2);
56         }
57         /*
58         printf("findAns = %d
", findAns);
59         for (int i = 0; i < wordLevel.size(); ++i) {
60             for (int j = 0; j < wordLevel[j].size(); ++j) {
61                 cout << wordLevel[i][j] << "";
62             }
63             cout << endl;
64         }
65         */
66         if (findAns == false) { return ans; }
67         reverse(wordLevel.begin(), wordLevel.end());
68         beginW = beginWord, endW = endWord;
69         vector<string> temp;
70         temp.push_back(endW);
71         dfs(ans, temp, endW, 0);
72         for (int i = 0; i < ans.size(); ++i) {
73             reverse(ans[i].begin(), ans[i].end());
74         }
75         return ans;
76     }
77     string beginW, endW;
78     vector<vector<string>> wordLevel;
79 };

View Code

【127】Word Ladder (2018年12月28日，第一次复习，ko)

给了一个初始单词和一个目标单词和一个单词字典，每次变换只能把当前单词变一个字母变成单词字典里面的一个词，问初始单词经过几次变换能变成目标单词。

题解：从初始单词开始，从字典里面找到能走一步的所有的单词放到队列里，然后遍历队列，直到找到目标单词，注意字典中所有的单词只能用一次，不然可能有环，就死循环了。

 1 class Solution {
 2 public:
 3     bool distance1(string& s, string& t) {
 4         int n = s.size();
 5         int dis = 0;
 6         for (int i = 0; i < n; ++i) {
 7             if (s[i] != t[i]) {
 8                 ++dis;
 9             }
10             if (dis >= 2) { return false; }
11         }
12         return dis == 1 ? true : false;
13     }
14     
15     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
16         int ans = 0;
17         if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) {return ans;}
18         queue<string> que, que2;
19         set<string> st;
20         que.push(beginWord);
21         ans = 1;
22         bool findAns = false;
23         while(!que.empty()) { 
24             while (!que.empty()) {
25                 string str = que.front();
26                 que.pop();
27                 for (auto word : wordList) {
28                     if (distance1(str, word) && st.find(word) == st.end()) {
29                         if (word == endWord) {
30                             findAns = true;
31                             break;
32                         }
33                         que2.push(word);
34                         st.insert(word);
35                     }
36                 }
37                 if (findAns) {
38                     break;
39                 }
40             }
41             ans++;
42             if (findAns) {
43                 break;
44             }
45             swap(que, que2);
46         }
47         return findAns ? ans : 0;
48     }
49 };

View Code

2018年12月28日补充，直接bfs就行了，现在写的很快。

 1 class Solution {
 2 public:
 3     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
 4         set<string> st(wordList.begin(), wordList.end());
 5         if (st.find(endWord) == st.end()) {return 0;}
 6         const int n = wordList.size();
 7         int step = 0;
 8         vector<int> visit(n, 0);
 9         queue<string> que;
10         que.push(beginWord);
11         while (!que.empty()) {
12             const int size = que.size();
13             step++;
14             for (int i = 0; i < size; ++i) {
15                 string cur = que.front(); que.pop();
16                 for (int k = 0; k < n; ++k) {
17                     if (visit[k]) {continue;}
18                     if (diff(cur, wordList[k]) == 1) {
19                         visit[k] = 1;
20                         que.push(wordList[k]);
21                         if (wordList[k] == endWord) {
22                             return step + 1;
23                         }
24                     }
25                 }
26             }
27         }
28         return 0;
29     }
30     int diff(string s1, string s2) {
31         if (s1.size() != s2.size()) {return -1;}
32         int cnt = 0;
33         for (int i = 0; i < s1.size(); ++i) {
34             if (s1[i] != s2[i]) {
35                 ++cnt;
36             }
37         }
38         return cnt;
39     }
40 };

2018/12/28

【130】Surrounded Regions

给了一个矩阵，有字母 ‘O’ 和 ‘X’ 组成，要求把由X包围的所有O都反转成X。跟边界上的O相连的O就不算被X包围。

题解：直接dfs， floodfill。

 1 class Solution {
 2 public:
 3     int dirx[4] = {-1, 0, 1, 0};
 4     int diry[4] = {0, -1, 0, 1};
 5     void solve(vector<vector<char>>& board) {
 6         n = board.size();
 7         if (n == 0) {return;}
 8         m = board[0].size();
 9         if (m == 0) {return;}
10         //mat 0: 没有访问过的，2:和边界上的O相连的
11         vector<vector<int>> mat(n, vector<int>(m, 0));
12         for (int i = 0; i < n; ++i) {
13             if (mat[i][0] == 0 && board[i][0] == 'O') {
14                 floodfill(board, mat, i, 0);
15             }
16             if (mat[i][m-1] == 0 && board[i][m-1] == 'O') {
17                 floodfill(board, mat, i, m -1);
18             }
19         }
20         for (int j = 0; j < m; ++j) {
21             if (mat[0][j] == 0 && board[0][j] == 'O') {
22                 floodfill(board, mat, 0, j);
23             }
24             if (mat[n-1][j] == 0 && board[n-1][j] == 'O') {
25                 floodfill(board, mat, n-1, j);
26             }
27         }
28         
29         for (int i = 0; i < n; ++i) {
30             for (int j = 0; j < m; ++j) {
31                 board[i][j] = mat[i][j] == 2 ? 'O' : 'X';
32             }
33         }
34         return;
35         
36     }
37     void floodfill(vector<vector<char>>& board, vector<vector<int>>& mat, int x, int y) {
38         mat[x][y] = 2;
39         for (int i = 0; i < 4; ++i) {
40             int newx = x + dirx[i], newy = y + diry[i];
41             if (newx >= 0 && newx < n && newy >= 0 && newy < m && board[newx][newy] == 'O' && mat[newx][newy] == 0) {
42                 floodfill(board, mat, newx, newy);
43             }
44         }
45     }
46     int n, m;
47 };

View Code

【133】Clone Graph

题目要求克隆一张图，返回这张图的深拷贝。

题解：这题纠结比较久，主要是因为指针不熟了，为啥p2指针一定要在外面定义，要解决这个问题。这题需要review。

 1 /**
 2  * Definition for undirected graph.
 3  * struct UndirectedGraphNode {
 4  *     int label;
 5  *     vector<UndirectedGraphNode *> neighbors;
 6  *     UndirectedGraphNode(int x) : label(x) {};
 7  * };
 8  */
 9 class Solution {
10 public:
11     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
12         if (!node) {return node;}
13         queue<UndirectedGraphNode *> que;
14         que.push(node);
15         unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> mp;
16         
17         UndirectedGraphNode *ans = new UndirectedGraphNode(node->label);
18         mp[node] = ans;
19         UndirectedGraphNode* p2 = ans;
20         
21         while (!que.empty()) {
22             UndirectedGraphNode *oriNode = que.front();
23             p2 = mp[oriNode];
24             que.pop();
25             
26             vector<UndirectedGraphNode *> nei = oriNode->neighbors;
27             for (int i = 0; i < nei.size(); ++i) {
28                 if (mp.find(nei[i]) != mp.end()) {
29                     p2->neighbors.push_back(mp[nei[i]]);
30                     continue;
31                 }
32                 que.push(nei[i]);
33                 UndirectedGraphNode * newNode = new UndirectedGraphNode(nei[i]->label);
34                 mp[nei[i]] = newNode;
35                 p2->neighbors.push_back(newNode);
36             }
37      
38         }
39         return ans;
40     }
41 };

View Code

【199】Binary Tree Right Side View

一棵二叉树，返回从右看能看到的数值，（只能看到每层最右的值），从上到下返回一个数组。

题解：还是层级遍历的变种。一次过了。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> rightSideView(TreeNode* root) {
13         vector<int> ans;
14         if (!root) { return ans; }
15         queue<TreeNode*> que, que2;
16         que.push(root);
17         while (!que.empty()) {
18             while (!que.empty()) {
19                 TreeNode* node = que.front();
20                 que.pop();
21                 if (que.size() == 0) {
22                     ans.push_back(node->val);
23                 }
24                 if (node->left) { que2.push(node->left); }
25                 if (node->right) { que2.push(node->right); }
26             }
27             swap(que, que2);
28         }
29         return ans;
30     }
31 };

View Code

【200】Number of Islands

给了一个01矩阵，1的连通块代表一个岛，0代表水，问一共有几个岛。（连通是四连通）

题解：直接dfs

 1 class Solution {
 2 public:
 3     int numIslands(vector<vector<char>>& grid) {
 4         n = grid.size();
 5         if (n == 0) {return 0;}
 6         m = grid[0].size();
 7         if (m == 0) {return 0;}
 8         vector<vector<int>> vis(n, vector<int>(m, 0));
 9         int ans = 0;
10         for (int i = 0; i < n; ++i) {
11             for (int j = 0; j < m; ++j) {
12                 if (grid[i][j] == '1' && !vis[i][j]) {
13                     dfs(grid, vis, i, j);
14                     ans++;
15                 }
16             }
17         }
18         return ans;
19     }
20     void dfs(const vector<vector<char>>& grid, vector<vector<int>>& vis, int x, int y) {
21         vis[x][y] = 1;
22         for (int i = 0; i < 4; ++i) {
23             int newx = x + dirx[i], newy = y + diry[i];
24             if (newx >= 0 && newx < n && newy >= 0 && newy < m && !vis[newx][newy] && grid[newx][newy] == '1') {
25                 dfs(grid, vis, newx, newy);
26             }
27         }
28     }
29     
30     int n, m;
31     int dirx[4] = {-1, 0, 1, 0};
32     int diry[4] = {0, -1, 0, 1};
33 
34 };

View Code

【207】Course Schedule (2019年1月20日，topologic sort 的bfs形式)

给了n门课程，有些课程在修之前有前置课程，给出了这些前置限制，判断这些课程能否修完。

题解：直接拓扑排序。

 1 class Solution {
 2 public:
 3     bool dfs(const vector<vector<int>>& g, vector<int>& c, int u) {
 4         c[u] = -1;
 5         for (int v = 0; v < n; ++v) {
 6             if (g[u][v]) {
 7                 if (c[v] < 0) { return false; }
 8                 else if (!c[v] && !dfs(g, c, v)) {
 9                     return false;
10                 }
11             }
12         }
13         c[u] = 1;
14         topo[--t] = u;
15         return true;
16     }
17     bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
18         vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
19         n = numCourses;
20         topo.resize(n);
21         t = n;
22         for (auto ele : prerequisites) {
23             int u = ele.first, v = ele.second;
24             graph[v][u] = 1;
25         }
26         vector<int> c(n, 0);
27         for (int i = 0; i < n; ++i) {
28             if (!c[i]) {
29                 if (!dfs(graph, c, i)) {
30                     return false;
31                 }
32             }
33         }
34         /*
35         for (int i = 0; i < n; ++i) {
36             cout << topo[i] << " " ;
37         }
38         cout << endl;
39         */
40         return true;
41     }
42     vector<int> topo;
43     int n, t;
44 };

View Code

2019年1月20日更新，topologic sort 的bfs形式更加好写。也更好理解。

我们先建图（邻接链表），然后去计算入度，然后把入度为0的点全都放进队列。开始bfs。注意这次bfs的循环结束条件是 for(int i = 0; i < n; ++i) 因为可能有环。

 1 class Solution {
 2 public:
 3     bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
 4         vector<vector<int>> g = initGraph(numCourses, prerequisites);
 5         vector<int> degree = calDegree(g);
 6         //find the vertex where degree == 0 and push them all into queue.
 7         queue<int> que;
 8         for (int i = 0; i < degree.size(); ++i) {
 9             if (degree[i] == 0) {
10                 que.push(i);
11             }
12         }
13         //start topologic sort
14         int idx = 0;
15         for (; idx < numCourses; ++idx) {
16             if (que.empty()) {
17                 return false;
18             }
19             int cur = que.front(); que.pop();
20             for (auto v : g[cur]) {
21                 if (--degree[v] == 0) {
22                     que.push(v);
23                 }
24             }
25         }
26         return true;
27     }
28 private:
29     vector<vector<int>> initGraph(int n, vector<pair<int, int>>& pre) {
30         vector<vector<int>> g(n, vector<int>());
31         for (auto e : pre) {
32             int start = e.second, end = e.first;
33             g[start].push_back(end);
34         }
35         return g;
36     }
37     vector<int> calDegree(vector<vector<int>>& g) {
38         vector<int> d(g.size(), 0);
39         const int n = g.size();
40         for (auto e : g) {
41             for (auto v : e) {
42                 d[v]++;
43             }
44         }
45         return d;
46     }
47 };

View Code

【210】Course Schedule II (2019年1月20日，topologic sort 的bfs形式)

跟207一样，区别在于这题需要返回合法顺序。

题解：拓扑排序。

 1 class Solution {
 2 public:
 3     vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
 4         vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
 5         n = numCourses;
 6         topo.resize(n);
 7         t = n;
 8         for (auto ele : prerequisites) {
 9             int u = ele.first, v = ele.second;
10             graph[v][u] = 1;
11         }
12         vector<int> c(n, 0);
13         for (int i = 0; i < n; ++i) {
14             if (!c[i]) {
15                 if (!dfs(graph, c, i)) {
16                     topo.clear();
17                     return topo;
18                 }
19             }
20         }
21         return topo;
22     }
23     bool dfs(const vector<vector<int>>& g, vector<int>& c, int u) {
24         c[u] = -1;
25         for (int v = 0; v < n; ++v) {
26             if (g[u][v]) {
27                 if (c[v] < 0) { return false; }
28                 else if (!c[v] && !dfs(g, c, v)) {
29                     return false;
30                 }
31             }
32         }
33         c[u] = 1;
34         topo[--t] = u;
35         return true;
36     }
37     vector<int> topo;
38     int n, t;
39 };

View Code

bfs 版本，特别简单。

 1 class Solution {
 2 public:
 3     vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
 4         vector<vector<int>> g = initGraph(numCourses, prerequisites);
 5         vector<int> degree = calDegree(g);
 6         vector<int> ret(numCourses, 0);
 7         queue<int> que;
 8         for (int i = 0; i < degree.size(); ++i) {
 9             if (degree[i] == 0) {
10                 que.push(i);
11             }
12         }
13         for (int i = 0; i < numCourses; ++i) {
14             if (que.empty()) {
15                 return vector<int>();
16             }
17             int cur = que.front(); que.pop();
18             ret[i] = cur;
19             for (auto e : g[cur]) {
20                 if (--degree[e] == 0) {
21                     que.push(e);
22                 }
23             }
24         }
25         return ret;
26     }
27 private:
28     vector<vector<int>> initGraph(int n, vector<pair<int, int>>& pre) {
29         vector<vector<int>> g(n, vector<int>());
30         for (auto e : pre) {
31             int start = e.second, end = e.first;
32             g[start].push_back(end);
33         }
34         return g;
35     }
36     vector<int> calDegree(vector<vector<int>>& g) {
37         vector<int> d(g.size(), 0);
38         const int n = g.size();
39         for (auto e : g) {
40             for (auto v : e) {
41                 d[v]++;
42             }
43         }
44         return d;
45     }
46 };

View Code

【261】Graph Valid Tree

今天一会儿再看。

【279】Perfect Squares (2019年1月26日，谷歌tag复习)

给了一个正整数n，求最少需要几个完全平方数(1, 4, 9, 16...)才能凑成和是n。

题解：看了小Q的题解，一个月之后写还是不会写。==

首先我们可以分析出来，因为1是个完全平方数，所以，n可以为任意正整数。只不过是最少怎么求的问题。我们可以设置一个数组f，f[i]表示i最少需要几个完全平方数表示。

转移方程就是 f[m] = f[i + t*t] = f[i] +1。我们用一个队列存储已经求出来的 m = i + t * t。

 1 class Solution {
 2 public:
 3     int numSquares(int n) {
 4         vector<int> f(n+1, -1);
 5         f[0] = 0;
 6         queue<int> que;
 7         que.push(0);
 8         int m = 0;
 9         while (!que.empty()) {
10             int m = que.front(); 
11             que.pop();
12             for (int i = 1; i * i + m <= n; ++i) {
13                 if (f[i * i + m] == -1) {
14                     f[i*i+m] = f[m] + 1;
15                     que.push(i * i + m);
16                 }
17             }
18         }
19         return f[n];
20     }
21 };

View Code

【286】Walls and Gates

一个矩阵，0代表大门，1代表障碍物，INF代表可以走的方块。要求返回这个矩阵，把可达的INF都换成离门的最短距离。

题解：类似于bfs，从大门开始一层一层标记INF。

 1 class Solution {
 2 public:
 3     void wallsAndGates(vector<vector<int>>& rooms) {
 4         n = rooms.size();
 5         if (n == 0) { return; }
 6         m = rooms[0].size();
 7         if (m == 0) { return; }
 8         
 9         vector<pair<int, int>> begin;
10         for (int i = 0; i < n; ++i) {
11             for (int j = 0; j < m; ++j) {
12                 if (rooms[i][j] == 0) {
13                      begin.push_back(make_pair(i, j));
14                 }
15             }
16         }
17         for (auto b : begin) {
18             queue<pair<int, int>> que;
19             que.push(b);
20             for (; !que.empty(); que.pop()) {
21                 pair<int, int> p = que.front();
22                 int x = p.first, y = p.second;
23                 for (int i = 0; i < 4; ++i) {
24                     int newx = x + dirx[i], newy = y + diry[i];
25                     if (newx >= 0 && newx < n && newy >= 0 && newy < m && rooms[newx][newy] != -1) {
26                         if (rooms[newx][newy] > rooms[x][y] + 1) {
27                             rooms[newx][newy] = rooms[x][y] + 1;
28                             que.push(make_pair(newx, newy));
29                         }
30                     }
31                 }
32             }
33         }
34         return;
35     }
36     int n, m;
37     int dirx[4] = {-1, 0 ,1, 0};
38     int diry[4] = {0, -1, 0, 1};
39 };

View Code

【301】Remove Invalid Parentheses

【310】Minimum Height Trees （算法群， 2018年11月13日）

给了一个有树特征的无向图，我们可以选任何一个结点作为树的根，然后这个图就可以变成一个有根树。在所有可能的有根树中，高度最小的就叫做 MHT，写一个函数，要求返回这个图的 MHT 的所有的根。

题解：我一开始是直接暴力枚举每个结点作为树的根结点，然后用bfs求树的高度，比较最小值。时间复杂度是 O(N^2)，超时了。后来看了答案和群里，小Q的视频，和discuss。有 O(N) 的解法。我们想象一下，我们每次可以去除一棵树的最外层的叶子结点（叶子结点的 degree 是 1），一层一层从外往里面剥洋葱，最后心里的结点就是所求树的根。

 1 class Solution {
 2 public:
 3     vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
 4         if (n == 0) {return vector<int>(); }
 5         if (n == 1) {return vector<int>{0};}
 6         vector<unordered_set<int>> edge(n, unordered_set<int>{});
 7         vector<int> degree(n, 0);
 8         //init graph
 9         for (auto p : edges) {
10             edge[p.first].insert(p.second);
11             edge[p.second].insert(p.first);
12             degree[p.first]++, degree[p.second]++;
13         }
14         //bfs
15         queue<int> que;
16         //put all leaves nodes into queue
17         for (int i = 0; i < n; ++i) {
18             if (degree[i] == 1) {
19                 que.push(i);
20             }
21         }
22         //bfs
23         vector<int> ret(0);
24         while (!que.empty()) {
25             int size = que.size();
26             ret.clear();
27             for (int i = 0; i < size; ++i) {
28                 int node = que.front(); que.pop();
29                 ret.push_back(node);
30                 for (auto adj : edge[node]) {
31                     degree[adj]--;
32                     if (degree[adj] == 1) {  //new leaves
33                         que.push(adj);
34                     }
35                 }
36             }
37         }
38         return ret;
39     }
40 };

View Code

小Q的视频地址如下：https://www.bilibili.com/video/av13605504/?p=4 他用了dfs，我没怎么看懂，估计还是题量不够。唉。

然后discuss的链接：https://leetcode.com/problems/minimum-height-trees/discuss/76055/Share-some-thoughts

【317】Shortest Distance from All Buildings

【323】Number of Connected Components in an Undirected Graph

【407】Trapping Rain Water II

【417】Pacific Atlantic Water Flow

【429】N-ary Tree Level Order Traversal

【490】The Maze

给了一个二维矩阵做迷宫(0代表可以走， 1代表障碍物)，一个小球，给了小球的开始位置和结束位置，问小球能否停止在结束位置。小球可以四个方向滚动，但是它只会碰到墙/障碍物才会停止，然后才能改变运动方向。

题解：可以dfs，也可以bfs。一开始觉得纠结的地方就是vis数组是小球经过这个位置就设置为1，还是只有小球停止在当前位置才能设置为1。后来看了别人的解法，只有小球在某个位置停止，才能把那个位置设置为1。

 1 class Solution {
 2 public:
 3     bool dfs(int cur_x, int cur_y) {
 4         if (cur_x == des.first && cur_y == des.second) {
 5             return true;
 6         }
 7         vis[cur_x][cur_y] = 1;
 8         for (int i = 0; i < 4; ++i) {
 9             int new_x = cur_x + dirx[i], new_y = cur_y + diry[i];
10             while (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && mat[new_x][new_y] == 0) {
11                 new_x += dirx[i], new_y += diry[i];
12             }
13             new_x -= dirx[i], new_y -= diry[i];
14             if (!vis[new_x][new_y]) {  //vis数组只在停留的地方有用。
15                 bool temp = dfs(new_x, new_y);
16                 if (temp) { return true; }
17             }
18         }
19         return false;
20     }
21     bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
22         st.first = start[0], st.second = start[1], des.first = destination[0], des.second = destination[1];
23         n = maze.size(), m = maze[0].size();
24         vector<vector<int>> temp(n, vector<int>(m, 0));
25         vis = temp;
26         mat = maze;
27         return dfs(st.first, st.second);
28         
29     }
30     vector<vector<int>> vis, mat;
31     pair<int, int> st, des;
32     int n, m;
33     int dirx[4] = {-1, 0, 1, 0};
34     int diry[4] = {0, -1, 0, 1};
35 };

dfs

 1 class Solution {
 2 public:
 3     bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
 4         st.first = start[0], st.second = start[1], des.first = destination[0], des.second = destination[1];
 5         n = maze.size(), m = maze[0].size();
 6         vector<vector<int>> vis(n, vector<int>(m, 0));
 7         queue<pair<int, int>> que;
 8         que.push(st);
 9         for ( ;!que.empty(); que.pop()) {
10             pair<int, int> cur = que.front();
11             for (int i = 0; i < 4; ++i) {
12                 int new_x = cur.first + dirx[i], new_y = cur.second + diry[i];
13                 while (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && maze[new_x][new_y] == 0) {
14                     new_x += dirx[i], new_y += diry[i];
15                 }
16                 new_x -= dirx[i], new_y -= diry[i];
17                 if (new_x == des.first && new_y == des.second) {
18                     return true;
19                 }
20                 if (!vis[new_x][new_y]) {
21                     vis[new_x][new_y] = 1;
22                     que.push(make_pair(new_x, new_y));
23                 }
24             }
25         }
26         return false;
27     }
28     pair<int, int> st, des;
29     int n, m;
30     int dirx[4] = {-1, 0, 1, 0};
31     int diry[4] = {0, -1, 0, 1};
32 };

bfs

【499】The Maze III

题目背景和490题差不多，就是小球走迷宫。但是一开始给了一个球的位置和一个洞的位置。（不同的是本题是洞，小球经过洞就能掉下去。而上一题是停止位置，小球必须撞到障碍物才能停止。）要求返回小球能不能落进洞里，如果能，返回最短路径的方向。如果有多条最短路，那么返回方向字典序最小的那个。不好写，需要review。

题解：还是bfs。我一开始想的是用一个字符标记从这个点走的方向，但是不行。（判断不出来是不是方向字典序最短）。后来看了discuss，是用了一个string标记从开始位置到当前位置的所有的方向，这样如果有新的路径比原来的路径短，就更新string和路径长度，如果有一条新的路径和原来的路径一样长，就判断谁的字典序小就用谁。

 1 class Solution {
 2 public:
 3     string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
 4         st.first = ball[0], st.second = ball[1], des.first = hole[0], des.second = hole[1];
 5         n = maze.size(), m = maze[0].size();
 6         vector<vector<point>> cnt(n, vector<point>(m, point()));  //cnt[x][y] --> (path, tot)
 7         queue<pair<int, int>> que;
 8         cnt[st.first][st.second].tot = 0;
 9         que.push(st);
10         bool findAns = false;
11         for ( ;!que.empty(); que.pop()) {
12             pair<int, int> cur = que.front();
13             int curx = cur.first, cury = cur.second;
14             for (int i = 0; i < 4; ++i) {
15                 int newx = curx + dirx[i], newy = cury + diry[i], step = 1;
16                 bool onRoad = false;
17                 while (newx >= 0 && newx < n && newy >= 0 && newy < m && maze[newx][newy] == 0) {
18                     //如果hole就在当前的路上，球能掉进洞里
19                     if (newx == des.first && newy == des.second) {
20                         findAns = true; onRoad = true;
21                         if (cnt[newx][newy].tot == -1 || cnt[newx][newy].tot > step + cnt[curx][cury].tot) {
22                             cnt[newx][newy].tot = step + cnt[curx][cury].tot;
23                             cnt[newx][newy].path = cnt[curx][cury].path + dir2str[i];
24                         } else if (cnt[newx][newy].tot == step + cnt[curx][cury].tot) {//如果最短路径相等，但是新的路径字典序更小，更新路径
25                             string newPath = cnt[curx][cury].path + dir2str[i];
26                             if (cnt[newx][newy].path > newPath) {
27                                 cnt[newx][newy].path = newPath;
28                             }
29                         }
30                         break;
31                     }
32                     newx += dirx[i], newy += diry[i], step++;
33                 }
34                 //如果洞不在路上，就更新撞到墙的那个点
35                 if (!onRoad) {
36                     newx -= dirx[i], newy -= diry[i], step--;
37                     if (cnt[newx][newy].tot == -1 || cnt[newx][newy].tot > step + cnt[curx][cury].tot) {
38                         cnt[newx][newy].tot = step + cnt[curx][cury].tot;
39                         cnt[newx][newy].path = cnt[curx][cury].path + dir2str[i];
40                         que.push(make_pair(newx, newy));
41                     } else if (cnt[newx][newy].tot == step + cnt[curx][cury].tot) { //如果最短路径相等，但是新的路径字典序更小，更新路径，然后把这个点重新放进队列里面。
42                             string newPath = cnt[curx][cury].path + dir2str[i];
43                             if (cnt[newx][newy].path > newPath) {
44                                 cnt[newx][newy].path = newPath;
45                                 que.push(make_pair(newx, newy));
46                             }
47                     }
48                 }
49             }
50         }
51         string ans;
52         if (!findAns) {
53             ans = "impossible";
54             return ans;
55         }
56         ans = cnt[des.first][des.second].path;
57         return ans;
58     }
59     pair<int, int> st, des;
60     int n, m;
61     int dirx[4] = {0, -1, 1, 0};
62     int diry[4] = {1, 0, 0, -1};
63     string dir2str[4] = {"r", "u", "d", "l"};
64     struct point {
65         point():path(""), tot(-1) {
66             
67         }
68         string path;  //到每个点而且满足条件的最短路径
69         int tot; //到每个点的最短路径长度
70     };
71 };

View Code

【505】The Maze II

题目背景和490题一样，都是小球在迷宫里面走。这题不同之处要求出小球从开始位置走到结束位置的最短距离，不可达返回-1。

题解：直接bfs了。有一点需要注意，如果有一个点到开始位置的距离更新了，那么这个点要重新放回队列里面搜索。不然最小距离更新的不准。

 1 class Solution {
 2 public:
 3     int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
 4         st.first = start[0], st.second = start[1], des.first = destination[0], des.second = destination[1];
 5         n = maze.size(), m = maze[0].size();
 6         vector<vector<int>> cnt(n, vector<int>(m, -1));
 7         queue<pair<int, int>> que;
 8         cnt[st.first][st.second] = 0;
 9         que.push(st);
10         bool findAns = false;
11         int ans = 0;
12         for (; !que.empty(); que.pop()) {
13             pair<int, int> cur = que.front();
14             for (int i = 0; i < 4; ++i) {
15                 int newx = cur.first + dirx[i], newy = cur.second + diry[i], step = 1;
16                 while (newx >= 0 && newx < n && newy >= 0 && newy < m && maze[newx][newy] == 0) {
17                     newx += dirx[i], newy += diry[i], step++;
18                 }
19                 newx -= dirx[i], newy -= diry[i], step--;
20                 if (cnt[newx][newy] == -1) {
21                     cnt[newx][newy] = step + cnt[cur.first][cur.second];
22                     que.push(make_pair(newx, newy));
23                 } else if (cnt[newx][newy] > step + cnt[cur.first][cur.second]){
24                     que.push(make_pair(newx, newy)); //如果当前点的最短距离有更新的话， 依然要push进入队列，不然最小距离不准的。
25                     cnt[newx][newy] = min(cnt[newx][newy], step + cnt[cur.first][cur.second]) ;
26                 }
27                 if (newx == des.first && newy == des.second) {
28                     findAns = true;
29                 }
30             }
31         }
32         return findAns ? cnt[des.first][des.second] : -1;
33     }
34     pair<int, int> st, des;
35     int n, m;
36     int dirx[4] = {-1, 0, 1, 0};
37     int diry[4] = {0, -1, 0, 1};
38 };

View Code

【513】Find Bottom Left Tree Value

给了一棵二叉树，返回这棵树最后一层的最左边的节点的值。

题解：二叉树的层级遍历，直接bfs。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int findBottomLeftValue(TreeNode* root) {
13         if (!root) {return -1;}
14         queue<TreeNode*> que, que2;
15         vector<int> level;
16         que.push(root);
17         int ans = -1;
18         while (!que.empty()) {
19             while (!que.empty()) {
20                 TreeNode* node = que.front(); que.pop();
21                 level.push_back(node->val);
22                 if (node->left) { que2.push(node->left); }
23                 if (node->right) { que2.push(node->right); }
24             }
25             swap(que, que2);
26             ans = level[0];
27             level.clear();
28         }
29         return ans;
30     }
31 };

View Code

【515】Find Largest Value in Each Tree Row

给了一棵二叉树，返回每层的最大值。

题解：二叉树的层级遍历，直接bfs。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> largestValues(TreeNode* root) {
13         vector<int> ans;
14         queue<TreeNode*> que, que2;
15         if (!root) {return ans;}
16         que.push(root);
17         while (!que.empty()) {
18             int maxx = INT_MIN;
19             while (!que.empty()) {
20                 TreeNode* node = que.front();
21                 que.pop();
22                 maxx = max(node->val, maxx);
23                 if (node->left) {que2.push(node->left);}
24                 if (node->right) {que2.push(node->right);}
25             }
26             ans.push_back(maxx);
27             swap(que, que2);
28         }
29         return ans;
30     }
31 };

View Code

【529】Minesweeper

【542】01 Matrix (2019年2月23日)

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Example 2: 
Input:
0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1

题解：BFS

 1 class Solution {
 2 public:
 3     vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
 4         if (matrix.empty() || matrix[0].empty()) {return matrix;}
 5         const int n = matrix.size(), m = matrix[0].size();
 6         vector<vector<int>> res = matrix;
 7         queue<vector<int>> que;
 8         for (int i = 0; i < n; ++i) {
 9             for (int j = 0; j < m; ++j) {
10                 if (matrix[i][j] == 0) {
11                     que.push({i, j});
12                 } else {
13                     res[i][j] = -1;
14                 }
15             }
16         }
17         const vector<int> dirx = {-1, 0 ,1, 0};
18         const vector<int> diry = {0 ,-1, 0, 1};
19         int step = 1;
20         while (!que.empty()) {
21             int size = que.size();
22             for (int i = 0; i < size; ++i, que.pop()) {
23                 auto x = que.front()[0], y = que.front()[1];
24                 for (int k = 0; k < 4; ++k) {
25                     int newx = x + dirx[k], newy = y + diry[k];
26                     if (newx < 0 || newx >= n || newy < 0 || newy >= m) {continue;}
27                     if (res[newx][newy] != -1) {continue;}
28                     res[newx][newy] = step;
29                     que.push({newx, newy});
30                 }
31             }
32             ++step;
33         }
34         return res;
35     }
36 };

View Code

【559】Maximum Depth of N-ary Tree

【675】Cut Off Trees for Golf Event

【690】Employee Importance

给了一个数据结构，[1, 15, [2]], 代表1号员工他的value是15，他的下属是2号员工。输入一个这样的数据结构的数组，和一个员工编号。返回这个员工和他所有的直接下属和间接下属的价值之和。

题解：直接bfs。

 1 /*
 2 // Employee info
 3 class Employee {
 4 public:
 5     // It's the unique ID of each node.
 6     // unique id of this employee
 7     int id;
 8     // the importance value of this employee
 9     int importance;
10     // the id of direct subordinates
11     vector<int> subordinates;
12 };
13 */
14 class Solution {
15 public:
16     int getImportance(vector<Employee*> employees, int id) {
17         int ans = 0;
18         queue<int> que;
19         que.push(id);
20         for (; !que.empty(); que.pop()) {
21             int user = que.front();
22             Employee* ptr = 0;
23             for (int i = 0; i < employees.size(); ++i) {
24                 ptr = employees[i];
25                 if (ptr->id == user) {
26                     break;
27                 }
28             }
29             if (ptr == 0) {
30                 cout << "err" << endl;
31                 return -1;
32             }
33             ans += ptr->importance;
34             for (int i = 0; i < ptr->subordinates.size(); ++i) {
35                 que.push(ptr->subordinates[i]);
36             }
37         }
38         return ans;
39     }
40 };

View Code

【743】Network Delay Time

【752】Open the Lock (2018年11月29日，算法群)

一个字符串四个字符，开始位置是 “0000”，给了一个集合，里面限制了这个字符串不能转换到这个集合里面的元素，否则算这个游戏挂了。给了一个终点字符串 target，问从 “0000” 开始至少要经过多少步能到达 target。一步的定义是一个字符加一或者减一（0-9循环），比如，'1' -> '0' ,'0'->'1', '0'->'9', '9->0'。

题解：bfs，难点是生成下一个结点的集合。（直接暴力生成）这题solution也是这个解法，但是300+ms，beats 10%不到。为啥呢，真的很慢了。

 1 //本题的重点是如何生成不在 deadends 里面的下一个结点。
 2 class Solution {
 3 public:
 4     int openLock(vector<string>& deadends, string target) {
 5         set<string> st(deadends.begin(), deadends.end());
 6         set<string> visited;
 7         if (st.find("0000") != st.end() || st.find(target) != st.end()) {return -1;}
 8         queue<string> que;
 9         que.push("0000"); visited.insert("0000");
10         int step = 0;
11         bool findAns = false;
12         while (!que.empty()) {
13             const int size = que.size();
14             for (int i = 0; i < size; ++i) {
15                 string cur = que.front(); que.pop();
16                 if (cur == target) { findAns = true; break; }
17                 vector<string> nextNodes = genNextNodes(cur, st, target);
18                 for (auto node : nextNodes) {
19                     if (visited.find(node) != visited.end()) {continue;}
20                     que.push(node);
21                     visited.insert(node);
22                 }
23             }
24             if (findAns) { return step; }
25             step++;
26         }
27         return -1;
28     }
29     vector<string> genNextNodes(const string& cur, const set<string>& st, const string& target) {
30         vector<string> ret;
31         string temp = cur;
32         for (int i = 0; i < 4; ++i) {
33             int num = temp[i] - '0' + 10;
34             for (int dis = -1; dis <= 1; dis +=2) {
35                 int newNum = (num + dis) % 10;
36                 string str = temp.substr(0, i) + to_string(newNum) + temp.substr(i+1);
37                 if (st.find(str) != st.end()) {continue;} 
38                 ret.push_back(str);
39             }
40         }
41         return ret;
42     }
43 };

View Code

【773】Sliding Puzzle (2019年3月10日， H)

八数码问题

题解：bfs 用 encode棋盘成字符串的方式来保存状态。

 1 class Solution {
 2 public:
 3     int slidingPuzzle(vector<vector<int>>& board) {
 4         queue<string> que;
 5         string state = toString(board), target = "123450";
 6         if (state == target) {return 0;}
 7         que.push(state);
 8         unordered_set<string> st;
 9         st.insert(state);
10         const int n = board.size(), m = board[0].size();
11         int step = 0;
12         while (!que.empty()) {
13             int size = que.size();
14             while (size--) {
15                 string cur = que.front(); que.pop();
16                 toBoard(cur, board);
17                 int pos = cur.find('0');
18                 int x = pos / m, y = pos % m;
19                 for (int k = 0; k < 4; ++k) {
20                     int newx = x + dirx[k], newy = y + diry[k];
21                     if (newx < 0 || newx >= n || newy < 0 || newy >= m) {continue;}
22                     vector<vector<int>> newBoard(board);
23                     swap(newBoard[x][y], newBoard[newx][newy]);
24                     string newState = toString(newBoard);          
25                     if (newState == target) {return step + 1;}
26                     if (st.find(newState) != st.end()) {continue;}
27                     st.insert(newState);
28                     que.push(newState);
29                 }
30             }
31             step++;
32         }
33         return -1;    
34     }
35     const int dirx[4] = {-1, 0, 1, 0};
36     const int diry[4] = {0, -1, 0, 1};
37     string toString(vector<vector<int>>& board) {
38         string res;
39         for (int i = 0; i < board.size(); ++i) {
40             for (int j = 0; j < board[i].size(); ++j) {
41                 res += board[i][j] + '0';
42             }
43         }
44         return res;
45     }
46     void toBoard(string& s, vector<vector<int>>& board) {
47         int m = board[0].size();
48         for (int i = 0; i < s.size(); ++i) {
49             board[i/m][i%m] = s[i] - '0';
50         }
51     }
52 };

View Code

【785】Is Graph Bipartite?

【787】Cheapest Flights Within K Stops

【815】Bus Routes

【847】Shortest Path Visiting All Nodes (算法群 2018年10月24日) 这题似懂非懂，最后写了一个BFS+状态压缩的写法。但是似乎可以dp+状态压缩。

【854】K-Similar Strings

【863】All Nodes Distance K in Binary Tree

【864】Shortest Path to Get All Keys