1. 530. Minimum Absolute Difference in BST
最小的差一定发生在有序数组的相邻两个数之间，所以对每一个数，找他的前驱和后继，更新结果即可！再仔细一想，bst的中序遍历就是有序数组，每次记录上一个数字，求他们的差，更新结果即可！
1 class Solution { 2 public: 3 int res; 4 int x; 5 void work(TreeNode* root) { 6 if(!root) return; 7 if(root->left) work(root->left); 8 if(x != -1) { 9 res = min(res, abs(x - root->val)); 10 } 11 x = root->val; 12 if(root->right) work(root->right); 13 } 14 int getMinimumDifference(TreeNode* root) { 15 res = INT_MAX; 16 x = -1; 17 work(root); 18 return res; 19 } 20 };
2. 523. Continuous Subarray Sum
这题，我太坑了，错了4次，导致罚时非常多！
一看这题，不很简单么！1. 求连续的和为某一个数，用前缀和处理一下就好了， 2. 求是k的倍数，倍数很多怎么办，转化为求余数即可。（然后你就注意到：如果k=0，怎么解决，这是个大坑啊！）。
这题一定注意，长度要大于等于2啊！时刻牢记！
1 class Solution { 2 public: 3 bool checkSubarraySum(vector<int>& nums, int k) { 4 int n = nums.size(); 5 if(n < 2) return 0; 6 if(k == 0) { 7 for (int i = 0; i < n - 1; i++) { 8 if(nums[i] + nums[i + 1] == 0) return 1; 9 } 10 return 0; 11 } 12 int s = 0; 13 set<int> se; 14 int c = 0; 15 for (int x : nums) { 16 s += x; 17 c++; 18 s %= k; 19 if(s == 0 && c > 1) return 1; 20 if(se.count(s)) return 1; 21 se.insert(s); 22 } 23 return 0; 24 } 25 };
我这个代码好像还不对，没有判读长度为2的情况！会不会重判，上面的代码，显然是错误的！
采用map记录一下下标！
1 class Solution { 2 public: 3 bool checkSubarraySum(vector<int>& nums, int k) { 4 int n = nums.size(); 5 if(n < 2) return 0; 6 if(k == 0) { 7 for (int i = 0; i < n - 1; i++) { 8 if(nums[i] + nums[i + 1] == 0) return 1; 9 } 10 return 0; 11 } 12 int s = 0; 13 set<int> se; 14 map<int, int> ma; 15 int c = 0; 16 for (int x : nums) { 17 s += x; 18 c++; 19 s %= k; 20 if(s == 0 && c > 1) return 1; 21 if(se.count(s) && (c - ma[s]) >= 2) return 1; 22 se.insert(s); 23 ma[s] = c; 24 } 25 return 0; 26 } 27 };
3. 524. Longest Word in Dictionary through Deleting
这题就是暴力，先对字典排序，然后逐个比较，返回。
1 class Solution { 2 public: 3 string findLongestWord(string s, vector<string>& d) { 4 int n = s.size(); 5 if(n == 0) return s; 6 int m = d.size(); 7 if(m == 0) return ""; 8 sort(d.begin(), d.end(), [&](string x, string y) { 9 if(x.size() == y.size()) return x < y; 10 return x.size() > y.size(); 11 }); 12 for (string x : d) { 13 if(x.size() > n) continue; 14 int i, j; 15 i = j = 0; 16 int len = x.size(); 17 while(i < n && j < len) { 18 if(s[i] == x[j]) { 19 i++; j++; 20 } else i++; 21 } 22 if(j == len) { 23 return x; 24 } 25 } 26 return ""; 27 } 28 };
4. 529. Minesweeper
我就想，这次的最后一题分值有点小啊！原来是medium的！
理解题意，考虑各种情况，然后就是做一个bfs，记住判重和边界条件。
1 class Solution { 2 public: 3 int n, m; 4 bool check(int x, int y) { 5 if(x >= 0 && x < n && y >= 0 && y < m) return 1; 6 return 0; 7 } 8 vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { 9 n = board.size(), m = board[0].size(); 10 int x = click[0], y = click[1]; 11 if(board[x][y] == 'M') { 12 board[x][y] = 'X'; 13 return board; 14 } 15 int s = 0; 16 for (int i = -1; i <= 1; i++) { 17 for (int j = -1; j <= 1; j++) { 18 int cx = x + i, cy = y + j; 19 if(!check(cx, cy)) continue; 20 s += board[cx][cy] == 'M'; 21 } 22 } 23 if(s != 0) { 24 board[x][y] = '0' + s; 25 return board; 26 } 27 vector<vector<bool>> in(n, vector<bool>(m, 0)); 28 queue<pair<int, int>> q; 29 q.push({x, y}); 30 while(!q.empty()) { 31 auto t = q.front(); q.pop(); 32 x = t.first, y = t.second; 33 s = 0; 34 for (int i = -1; i <= 1; i++) { 35 for (int j = -1; j <= 1; j++) { 36 int cx = x + i, cy = y + j; 37 if(!check(cx, cy)) continue; 38 s += board[cx][cy] == 'M'; 39 } 40 } 41 if(s == 0) { 42 board[x][y] = 'B'; 43 for (int i = -1; i <= 1; i++) { 44 for (int j = -1; j <= 1; j++) { 45 int cx = x + i, cy = y + j; 46 if(!check(cx, cy)) continue; 47 if(board[cx][cy] == 'E' && !in[cx][cy]) { 48 q.push({cx, cy}); 49 in[cx][cy] = 1; 50 } 51 } 52 } 53 } else { 54 board[x][y] = '0' + s; 55 } 56 } 57 58 return board; 59 } 60 };