5. 最长回文子串

只考虑以一个元素为中心时

  1. class Solution10 {
  2. public:
  3.     string longestPalindrome(string s) {
  4.         int res = 0, cur = 0;
  5.         for (int i=0; i<s.size(); i++)
  6.         {
  7.             int curLen = palindromeLen(s, i);
  8.             if (curLen > res)
  9.                 res = curLen, cur = i;
  10.         }
  12.         return s.substr(cur-res+1, res*2);
  13.     }
  15. public:
  16.     // 中心扩散时，如何处理偶数对称？？
  17.     int palindromeLen(string& s, int idx)
  18.     {
  19.         int edge = min(idx, (int)s.size()-idx);
  20.         int i=0;
  21.         for (; i<=edge; i++)
  22.             if (s[idx-i] != s[idx+i]) break;
  24.         return i;
  25.     }
  26. };

中心扩散法

这里的start = i - (mlen - 1) / 2这一步计算还是很精妙的，/2时向下取整了，同时包含了奇数和偶数的情况

  1. class Solution {
  2. public:
  3.     string longestPalindrome(string s) {
  4.         int mlen = 0, start = 0;
  5.         for (int i=0; i<s.size(); i++)
  6.         {
  7.             // 取单中心和双中心的最大值
  8.             int curLen = max(palindromeLen(s, i, i), palindromeLen(s, i, i+1));
  9.             if (curLen > mlen)
  10.                 mlen = curLen, start = i - (mlen - 1) / 2;
  11.         }
  13.         return s.substr(start, mlen);
  14.     }
  16. public:
  17.     int palindromeLen(string& s, int l, int r)
  18.     {
  19.         while (l >= 0 && r < s.size() && s[l] == s[r])
  20.             l--, r++;
  21.         return r - l - 1;
  22.     }
  23. };

动态规划法

Manacher 算法
思路和代码待研究

647. 回文子串

  1. class Solution {
  2. public:
  3.     int countSubstrings(string s) {
  4.         // dp[i][j] s[i,j]是否是回文子串
  5.         int n = s.size(), res = 0;
  6.         vector<vector<bool>> dp(n, vector<bool>(n, false));
  8.         for (int i=0; i<n; i++)
  9.         {
  10.             for (int j=0; j<=i; j++)
  11.             {
  12.                 // 只有一个字符 ｜｜ 去除两边的子串是回文
  13.                 if (s[i] == s[j] && (i-j<2 || dp[j+1][i-1]))
  14.                 {
  15.                     dp[j][i] = true;
  16.                     res++;
  17.                 }
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. };

516. 最长回文子序列

这里的遍历顺序，完全是根据状态转移方程来设定的，保证用到时，已经计算出来了即可。

  1. class Solution {
  2. public:
  3.     int longestPalindromeSubseq(string s) {
  4.         int n = s.size();
  5.         vector<vector<int>> f(n, vector<int>(n, 0));
  6.         for (int i=n-1; i>=0; i--)
  7.         {
  8.             f[i][i] = 1;
  10.             for (int j=i+1; j<n; j++)
  11.             {
  12.                 if (s[i] == s[j])
  13.                     f[i][j] = f[i+1][j-1] + 2;
  14.                 else
  15.                     f[i][j] = max(f[i+1][j], f[i][j-1]);
  16.             }
  17.         }
  19.         return f[0][n-1];
  21.     }
  22. };

11. 盛最多水的容器

我的第一理解这题肯定和接雨水是一样的
其实看了答案之后，还真的没有什么差别；

  1. class Solution {
  2. public:
  3.     int maxArea(vector<int>& height) {
  4.         int l = 0, r = height.size()-1;
  5.         int res = 0;
  6.         while (l < r)
  7.         {
  8.             res = height[l] > height[r] ?  max(res, (r-l)*height[r--]) : max(res, (r-l)*height[l++]);
  9.         }
  10.         return res;
  11.     }
  14. };

15. 三数之和

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) {
  4.         sort(nums.begin(), nums.end());
  5.         vector<vector<int>> res;
  6.         int n = nums.size();
  7.         if (n<3) return res;
  8.         for (int i=0; i<n; i++)
  9.         {
  10.             if (nums[i]>0) break;
  11.             if (i>0 && nums[i]==nums[i-1]) continue;
  13.             int l = i+1, r = n-1;
  14.             while (l < r)
  15.             {
  16.                 int sum = nums[i] + nums[l] + nums[r];
  17.                 if (sum == 0) 
  18.                 {
  19.                     res.push_back({nums[i], nums[l], nums[r]});
  20.                     while (l<r && nums[l]==nums[l+1]) l++;
  21.                     while (l<r && nums[r]==nums[r-1]) r--;
  22.                     l++, r--;
  23.                 }
  24.                 else if(sum < 0) l++;
  25.                 else r--;
  26.             }
  27.         }
  29.         return res;
  30.     }
  31. };
  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& arr) {
  4.         vector<vector<int>> res;
  5.         sort(arr.begin(), arr.end());
  6.         for (int i=0; i<arr.size(); i++ )  {
  7.             if (i && arr[i] == arr[i-1]) continue;
  9.             for (int j = i + 1, k = arr.size()-1; j<k; j++) {
  10.                 if (j > i+1 && arr[j] == arr[j-1]) continue ;
  11.                 while (j < k-1 && arr[i] + arr[j] + arr[k-1] >= 0) k--;
  12.                 if (arr[i] + arr[j] + arr[k] == 0) res.push_back({arr[i], arr[j], arr[k]});
  14.             }
  15.         }
  17.         return res;
  18.     }
  19. };

22. 括号生成

合法括号序列的条件：
image.png

  1. class Solution {
  2. public:
  3.     vector<string> res;
  5.     vector<string> generateParenthesis(int n) {
  6.         dfs(n, 0, 0, "");
  8.         return res;
  9.     }
  11.     /*
  12.         lc : left bracket count
  13.         rc : right bracket
  14.     */
  15.     void dfs(int n, int lc, int rc, string seq) {
  16.         if (lc == n && rc == n) res.push_back(seq);
  17.         else {
  18.             if (lc < n) dfs(n, lc+1, rc, seq + '(');
  19.             if (rc < n && rc < lc) dfs(n, lc, rc + 1, seq + ')');
  20.         }
  21.     }
  22. };

23. 合并K个升序链表

  1. class Solution {
  2. public:
  4.     struct cmp {
  5.         bool operator() (ListNode* a, ListNode* b) {
  6.             return a->val > b->val;
  7.         }
  8.     };
  10.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  11.         if (lists.empty()) return nullptr;
  13.         priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // smallest heap
  14.         for (auto &l : lists) if (l) heap.push(l); 
  16.         auto dummy = new ListNode(-1), node = dummy;
  18.         while (!heap.empty()) {
  19.             auto t = heap.top();
  20.             heap.pop(); 
  22.             node = node->next = t;
  24.             if (t->next) heap.push(t->next);
  25.         }
  26.         return dummy->next;
  27.     }  
  28. };
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  14.         return merge(lists, 0, lists.size()-1);
  15.     }
  17.     ListNode* merge(vector<ListNode*>& lists, int l, int r) {
  18.         if (l == r) return lists[l];
  19.         if (l > r) return nullptr;
  21.         int mid = l + r >> 1;
  22.         return mergeTwo(merge(lists, l, mid), merge(lists, mid + 1, r));
  23.     }
  25.     ListNode* mergeTwo(ListNode* l1, ListNode* l2) {
  26.         auto dummy = new ListNode(-1), node = dummy;
  28.         while (l1 && l2) {
  29.             if (l1->val > l2->val) node->next = l2, l2 = l2->next;\
  30.             else node->next = l1, l1 = l1->next;
  32.             node = node->next;
  33.         }
  35.         if (l1) node->next = l1;
  36.         if (l2) node->next = l2;
  38.         return dummy->next;
  39.     }
  40. };

25. K 个一组翻转链表

翻转前先判断是否剩余节点数是否大于k

翻转的过程可以分为四步：
对应图中的1，2，3，4
image.png

  1. ListNode* reverseKGroup(ListNode* head, int k) {
  2.         auto dummy = new ListNode(-1), prev = dummy;
  3.         dummy->next = head;
  4.         while (prev) {
  5.             auto node = prev;
  6.             for (int i=0; i<k && node; i++) node = node->next;
  7.             if (!node) break;
  9.             auto pre = prev->next, cur = pre->next;
  10.             for (int i=0; i<k-1; i++) {
  11.                 auto next = cur->next;
  12.                 cur->next = pre;
  13.                 pre = cur;
  14.                 cur = next;  
  15.             }
  17.             auto c = prev->next;
  18.             prev->next = pre;
  19.             c->next = cur; // next
  21.             prev = c;
  22.         }
  24.         return dummy->next;
  25.     }

31. 下一个排列

image.png

  1. 从后向前找到第一个降序的数， a[i]，
  2. 从后往前找到第一个比a[i]大的数 a[j]
  3. swap(i, j)
  4. reverse(i+1, n)
  1. class Solution {
  2. public:
  3.     void nextPermutation(vector<int>& nums) {
  4.         // 1.从后往前找到第一个比后面小的书a[i]
  5.         //   ==>a[i]后的数都是降序的
  6.         int i = nums.size()-2;
  7.         while (i >= 0 && nums[i] >= nums[i+1]) i--;
  9.         if (i>=0)
  10.         {
  11.             // 2. 从后往前找到第一个比a[i]大的数 a[j]
  12.             int j = nums.size()-1;
  13.             while (j >=0 && nums[j] <= nums[i]) j--;
  14.             // 3. 交换
  15.             swap(nums[i], nums[j]);
  16.         }
  18.         // 4. 交换a[i]后的数字 ==> 变为升序
  19.         reverse(nums.begin()+i+1, nums.end());
  20.     }
  21. };

32. 最长有效括号

有问题啊

  1. class Solution {
  2. public:
  4.     int longestValidParentheses(string s) {
  5.         stack<char> st;
  6.         int res = 0, stackTearIdx = 0;
  7.         for (int i=0; i<s.size(); i++)
  8.         {
  9.             char ch = s[i];
  10.             if (!st.empty() && isSuit(st.top(), ch))
  11.             {
  12.                 st.pop();
  13.                 res = max(res, i-(int)st.size()+1);
  14.             }
  15.             else
  16.             {
  17.                 if (st.empty())
  18.                     stackTearIdx = i;
  19.                 st.push(ch);
  20.             }
  22.         }
  24.         // "()(()"  2  how to solve this case
  25.         // 当栈不为空，且栈顶元素对应的的idx+最长有效长度>字符长度时，
  26.         // 出现部分无效的情况，需要取前面和后面部分的最大值
  27.         if (!st.empty() && res + stackTearIdx > s.size())
  28.             res = max(stackTearIdx, res-stackTearIdx);
  30.         return res;
  31.     }
  33.     bool isSuit(char a, char b)
  34.     {
  35.         return a == '(' && b == ')';
  36.     }
  37. };
  1. 测试用例:"(()"
  2.             ")()())"
  3.             ""
  4.             "()(()"
  5.             "()(())"
  6.             "(())(()"
  7.             "((())(()"
  8.             测试结果:2
  9.             4
  10.             0
  11.             2
  12.             6
  13.             4
  14.             6
  15.             期望结果:2
  16.             4
  17.             0
  18.             2
  19.             6
  20.             4
  21.             4

最长回文子串思路（但是也不对啊）

  1. class Solution {
  2. public:
  3.     int longestValidParentheses(string s) {
  4.         int res = 0;
  5.         for (int i=0; i<s.size(); i++)
  6.         {
  7.             int cur = max(longPa(s, i, i), longPa(s, i, i+1));
  8.             res = max(res, cur);
  9.         }
  11.         return res;
  12.     }
  14.     int longPa(const string &s, int l, int r)
  15.     {
  16.         while (l>=0 && r<s.size() && isSuit(s[l], s[r]))
  17.             l--, r++;
  19.         return r-l-1;
  20.     }
  22.     bool isSuit(char a, char b)
  23.     {
  24.         return a == '(' && b == ')';
  25.     }
  26. };

上面抓着左右括号匹配的思路是不正确的

新思路：

  1. 左括号：

直接压入栈对应的idx

  1. 右括号


    1. ```cpp class Solution { public: int longestValidParentheses(string s) { stack st; st.push(-1); int res = 0; for (int i=0; i<s.length(); i++) {

      1.   if (s[i] == '(') st.push(i);
      2.   else
      3.   {
      4.       st.pop();
      5.       if (st.empty()) st.push(i);
      6.       else res = max(res, i - st.top());
      8.   }

      } return res; }

};

  1. [ref](https://leetcode.cn/problems/longest-valid-parentheses/solution/shou-hua-tu-jie-zhan-de-xiang-xi-si-lu-by-hyj8/)
  3. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/25838471/1655776871519-ed64abcf-42c3-4f3e-b852-7b8744e163f9.png#clientId=ud61bd62c-66dc-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=335&id=u2d10af64&margin=%5Bobject%20Object%5D&name=image.png&originHeight=669&originWidth=1316&originalType=binary&ratio=1&rotation=0&showTitle=false&size=344408&status=done&style=none&taskId=u52202178-2ab3-4461-8f53-205069efc84&title=&width=658)<br />下面的图是使用反证法证明
  5. <a name="edi81"></a>
  6. #### [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
  7. > 感受上这题并不难，但是我刷了好久啊
  8. > 需要加油啊T_T
  9. > 
  11. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/25838471/1655779802402-23664056-6b20-40e1-885f-60703506bc3d.png#clientId=u69e0439b-7dc9-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=188&id=u4b719612&margin=%5Bobject%20Object%5D&name=image.png&originHeight=376&originWidth=517&originalType=binary&ratio=1&rotation=0&showTitle=false&size=42816&status=done&style=none&taskId=u11815322-a721-4ea1-a4ff-78aa9421e05&title=&width=258.5)<br />本题可以分为三步：
  13. 1. 找到两段区间的分界点
  14. 1. 判断位于哪段区间
  15. 1. 找出target
  17. ```cpp
  18. class Solution {
  19. public:
  20.     int search(vector<int>& nums, int target) {
  21.         if (nums.empty()) return -1;
  22.         // 1. 找到两段区间的分界点
  23.         int l = 0, r = nums.size() - 1;
  25.         while (l < r ) {
  26.             int mid = l + r + 1>> 1;
  27.             if (nums[mid] >= nums[0]) l = mid;
  28.             else r = mid - 1;
  29.         }
  31.         // 2. 判断target位于哪个区间
  32.         if (target >= nums[0]){ // target位于第一段区间
  33.             l = 0;
  34.         } else { //target位于第er段区间
  35.             l = r + 1, r = nums.size() - 1; 
  36.         }
  38.         while (l < r) {
  39.             int mid = l + r + 1 >> 1;
  40.             if (nums[mid] <= target) l = mid;
  41.             else r = mid - 1;
  42.         }
  44.         if (nums[r] == target) return r; // 通常使用的是l，这里使用的是r
  45.         else return -1;
  46.     }
  47. };
  1. int search(vector<int>& nums, int target) {
  2.         int l = 0, r = nums.size() - 1;
  3.         while (l <= r)
  4.         {
  5.             int mid = l + r >> 1;
  7.             if (nums[mid] == target) return mid;
  8.             // left is sorted
  9.             if (nums[l] <= nums[mid])
  10.             {
  11.                 if (target >= nums[l] && target <= nums[mid]) // in [l, mid)
  12.                     r = mid - 1;
  13.                 else
  14.                     l = mid + 1;
  15.             }
  16.             else // right is sorted
  17.             {
  18.                 if (target >= nums[mid] && target <= nums[r]) // in (mid, r]
  19.                     l = mid + 1;
  20.                 else
  21.                     r = mid - 1;
  22.             }
  23.         }
  24.         return -1;
  25.     }

42. 接雨水

  1. 双指针 解法

image.png
这里需要思考一个问题，为啥低的要先移动？

若是高的先移动，马上就会得到，根据下面的算法，就会得到第二个也能接雨水，若是后面没有出现比第二个高的柱子，这里会出现矛盾

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& h) {
  4.         int res = 0;
  6.         int i = 0, j = h.size() - 1;
  7.         int lm = h[i], rm = h[j];
  9.         while ( i < j) {
  10.             if (h[i] <= h[j]) {
  11.                 if (h[i] <= lm) res += (lm - h[i]);
  12.                 else lm = h[i];
  13.                 i++;
  14.             } else {
  15.                 if (h[j] < rm) res += (rm - h[j]);
  16.                 else rm = h[j];
  17.                 j--;
  18.             }
  19.         }
  21.         return res;
  22.     }
  23. };
  1. 栈

    感觉这个解法有点难懂233

image.png

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         stack<int> stk;
  5.         int res = 0;
  6.         for (int i = 0; i < height.size(); i ++) {
  7.             //记录栈中的上一个柱子的高度
  8.             int last = 0;
  9.             while (stk.size() && height[stk.top()] <= height[i]) {
  10.                 res += (height[stk.top()] - last) * (i - stk.top() - 1);
  11.                 last = height[stk.top()];
  12.                 stk.pop();
  13.             }
  15.             if (stk.size()) res += (i - stk.top() - 1) * (height[i] - last);
  16.             stk.push(i);
  17.         }
  18.         return res;
  19.     }
  20. };

48. 旋转图像

image.png

先水平翻转，然后对角线翻转

  1. class Solution {
  2. public:
  3.     // 先上下翻转，然后对角翻转
  4.     void rotate(vector<vector<int>>& matrix) {
  5.         int n = matrix[0].size();
  6.         // 水平翻转
  7.         for (int i=0; i<n/2; i++) swap(matrix[i], matrix[n-i-1]);
  9.         // 对角翻转
  10.         for (int i=0 ; i<n; i++)
  11.             for (int j=0; j<i; j++)
  12.                 swap(matrix[i][j], matrix[j][i]);
  13.     }
  14. };

498. 对角线遍历

image.png

  1. class Solution {
  2. public:
  3.     vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
  4.         vector<int> res;
  6.         int n = mat.size(), m = mat[0].size();
  8.         for (int i=0; i<m+n-1; i++) // 一共有m+n-1条对角线
  9.         {
  10.             if(i & 1) //奇数行对角线
  11.             {
  12.                 for (int x=max(0, i-m+1); x<=min(i, n-1); x++)
  13.                     res.push_back(mat[x][i-x]);
  14.             }
  15.             else
  16.             {
  17.                 for (int x=min(i, n-1); x>=max(0, i-m+1); x--)
  18.                     res.push_back(mat[x][i-x]);
  19.             }
  20.         }
  21.         return res;
  22.     }
  23. };

49. 字母异位词分组

这里有一个很简单的思路，就是对string进行排序，将所有排序相同的元素放到一个value中

  1. class Solution {
  2. public:
  3.     vector<vector<string>> groupAnagrams(vector<string>& strs) {
  4.         unordered_map<string, vector<string>> mp;
  6.         for (auto& str : strs)
  7.         {
  8.             string key(26, 0);
  9.             for (auto& ch : str) key[ch-'a']++;
  11.             /*
  12.             string key = str;
  13.             sort(key.begin(), key.end());
  14.             */
  16.             mp[key].push_back(str);
  20.         }
  22.         vector<vector<string>> res;
  23.         for (auto iter : mp)
  24.             res.push_back(iter.second);
  26.         return res;
  27.     }
  28. };

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

  1. class Solution {
  2. public:
  3.     int minDistance(string s1, string s2) {
  4.         int n1= s1.size(), n2 = s2.size();
  6.         vector<vector<int>> f(n1, vector<int>(n2, INT_MAX));
  8.         for (int i=0; i<n1; i++) {
  9.             for (int j=0; j<n2; j++) {
  10.                 if (!i && !j) f[i][j] = 0;
  11.                 else if (!i) f[i][j] = j;
  12.                 else if (!j) f[i][j] = i;
  13.                 else {    
  14.                     f[i][j] =min(f[i][j], min(f[i][j-1], f[i-1][j]) + 1);
  15.                     if (s1[i] == s2[j]) f[i][j] = min(f[i][j], f[i-1][j-1]);
  16.                     else f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
  17.                 }
  19.             }
  20.         }
  22.         return f[n1-1][n2-1];
  23.     }
  24. };

如果随手写，大概率会写出上面的代码，那么存在一个问题，就是f[0][0]的场景默认是给了一个相等0, f[i][0]也是默认的是f[0][0]相等

单独处理s1[0] s2[0]的场景目前还是存在一些问题

最后还是将：f变大计算时，更好处理
image.png

  1. class Solution {
  2. public:
  3.     int minDistance(string s1, string s2) {
  4.         int n1= s1.size(), n2 = s2.size();
  6.         vector<vector<int>> f(n1+1, vector<int>(n2+1, INT_MAX));
  8.         for (int i=0; i<=n1; i++) {
  9.             for (int j=0; j<=n2; j++) {
  10.                 if (!i && !j) f[i][j] = 0;
  11.                 else if (!i) f[i][j] = j;
  12.                 else if (!j) f[i][j] = i;
  13.                 else {    
  14.                     f[i][j] =min(f[i][j], min(f[i][j-1], f[i-1][j]) + 1);
  15.                     if (s1[i-1] == s2[j-1]) f[i][j] = min(f[i][j], f[i-1][j-1]);
  16.                     else f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
  17.                 }
  19.             }
  20.         }
  22.         return f[n1][n2];
  23.     }
  24. };

78. 子集

由于n位的二进制数对应的01可以表示所有的选和不选的方案，所以可以采用如下的迭代的方法
时间复杂度O（leetcode刷题记录 - 图9） 

  1. class Solution {
  2.     public:
  3.     vector<vector<int>> subsets(vector<int>& nums) {
  4.         vector<vector<int>> res;
  6.         int n = nums.size();
  7.         for (int i=0; i< 1<<n; i++) {
  8.             vector<int> path;
  9.             for (int j=0; j<n; j++) {
  10.                 if (i>>j & 1) path.push_back(nums[j]);
  11.             }
  12.             res.push_back(path);
  13.         }
  14.         return res;
  15.     }    
  16. };

递归的方式
时间复杂度O（leetcode刷题记录 - 图10）

  1. class Solution {
  2. public:
  4.     vector<vector<int>> res;
  5.     vector<int> cur;
  6.     vector<int> nums;
  7.     vector<vector<int>> subsets(vector<int>& nums) {
  8.         this->nums = nums;
  9.         dfs(0);
  11.         return res;
  12.     }
  14.     void dfs(int idx) {
  16.         res.push_back(cur);
  18.         for (int i = idx; i<nums.size(); i++) {
  19.             cur.push_back(nums[i]);
  20.             dfs(i+1);
  21.             cur.pop_back();
  22.         }
  23.     }
  24. };

79. 单词搜索

这里是使用特殊符号标记，然后回复原来的字符。以此来减少数组的开销

  1. class Solution {
  2. public:
  3.     bool exist(vector<vector<char>>& g, string w) {
  4.         for (int i=0; i<g.size(); i++) 
  5.             for (int j=0; j<g[i].size(); j++) 
  6.                 if (dfs(g, w, i, j, 0)) return true;
  8.         return false;
  9.     }
  11.     int dx[4] = {-1, 0, 1, 0};
  12.     int dy[4] = {0, -1, 0, 1};
  14.     bool dfs(vector<vector<char>> &g, string &w, int x, int y, int idx) {
  15.         if (g[x][y] != w[idx]) return false;
  16.         if (idx == w.size() - 1) return true;
  18.         char t = g[x][y];
  19.         g[x][y] = '.';
  20.         for (int i = 0; i<4; i++) {
  21.             int a = x + dx[i], b = y + dy[i];
  22.             if (a<0 || a>=g.size() || b<0 || b>=g[0].size() || g[a][b] == '.') continue;
  23.             if (dfs(g, w, a, b, idx + 1)) return true;
  24.         }
  25.         g[x][y] = t;
  26.         return false;
  27.     }
  28. };


90. 子集 II

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> nums_;
  5.     vector<int> combi_;
  6.     vector<bool> used_;
  7.     int n_;
  8. public:
  9.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  10.         sort(nums.begin(), nums.end());
  11.         n_ = nums.size();
  12.         nums_ = nums;
  13.         used_ = vector<bool>(n_, false);
  15.         dfs(0, 0);
  17.         return res_;
  19.     }
  21.     void dfs(int idx, int count)
  22.     {
  23.         if (count == n_)
  24.         {
  25.             res_.push_back(combi_);
  26.             return;
  27.         }
  29.         for (int i=idx; i<n_; i++)
  30.         {
  31.             dfs(i+1, count+1); // this is different
  32.             if (i>0 && nums_[i]==nums_[i-1] && !used_[i-1])
  33.                 continue;
  35.             combi_.push_back(nums_[i]);
  36.             used_[i] = true;
  37.             dfs(i+1, count+1);
  38.             used_[i] = false;
  39.             combi_.pop_back();
  41.         }
  42.     }
  43. };

这里有个不一样到地方，就是将不选在循环的每一步都执行

image.png
通过绘图可以发现，每次dfs时，插入一个元素，得到都是一个子集，只需要注意剪枝即可

  1. class Solution {
  2. private:
  3.     vector<vector<int>> res_;
  4.     vector<int> nums_;
  5.     vector<int> combi_;
  6.     vector<bool> used_;
  7.     int n_;
  8. public:
  9.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  10.         sort(nums.begin(), nums.end());
  11.         n_ = nums.size();
  12.         nums_ = nums;
  13.         used_ = vector<bool>(n_, false);
  15.         dfs(0);
  17.         return res_;
  19.     }
  21.     void dfs(int idx)
  22.     {
  23.         res_.push_back(combi_);
  25.         for (int i=idx; i<n_; i++)
  26.         {
  27.             if (i>0 && nums_[i]==nums_[i-1] && !used_[i-1])
  28.                 continue;
  30.             combi_.push_back(nums_[i]);
  31.             used_[i] = true;
  32.             dfs(i+1);
  33.             used_[i] = false;
  34.             combi_.pop_back();
  36.         }
  37.     }
  38. };

加一个y总常用的去重解法；

  1. 统计每一个元素的个数，
  2. 然后依次枚举，
  3. 最后依次弹出
  1. class Solution {
  2. public:
  4.     vector<vector<int>> res;
  5.     vector<int> path;
  6.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  7.         sort(nums.begin(), nums.end());
  8.         dfs(nums, 0);
  10.         return res;
  11.     }
  13.     void dfs(vector<int> &nums, int u) {
  14.         if (u == nums.size()) {
  15.             res.push_back(path);
  16.             return ;
  17.         }
  19.         int k = u + 1;
  20.         while (k<nums.size() && nums[k] == nums[k-1]) k++;
  22.         for (int i=0; i <= k-u; i++) {
  23.             dfs(nums, k);
  24.             path.push_back(nums[u]); // 先递归，后加入元素
  25.         }
  27.         for (int i=0; i<=k-u; i++)
  28.             path.pop_back();
  29.     }
  30. };

output:
[[],[2],[2,2],[1],[1,2],[1,2,2]]

95. 不同的二叉搜索树 II

image.png

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {nullptr};

        return dfs(1, n);
    }

    vector<TreeNode*> dfs(int l, int r) {
        if (l > r) return {nullptr};
        vector<TreeNode*> res;
        for (int k=l; k<=r; k++) {
            auto left = dfs(l, k-1), right = dfs(k+1, r);

            for (auto i : left) {
                for (auto j : right) {
                    auto root = new TreeNode(k);
                    root->left = i, root->right = j;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

类似题型可见 241

96. 不同的二叉搜索树

image.png

class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n+1);

        f[0] = 1;
        for (int i=1; i<=n; i++) 
        {
            for (int j=1; j<=i; j++)
                f[i] += f[j - 1] * f[i - j];
        }
        return f[n];
    }
};

98. 验证二叉搜索树

class Solution {
public:
    long pre = LONG_MIN;    
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;

        bool left = isValidBST(root->left);

        if (root->val <= pre) return false;
        pre = root->val;

        bool right = isValidBST(root->right);

        return left && right;

    }
};

根据二叉搜索树的中序遍历为有序来进行

101. 对称二叉树

写判断条件的时候不要重叠某些情况

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* l, TreeNode* r)
    {
        if (!l && !r) return true;
        else if (!l || !r || l->val != r->val) return false;

        return dfs(l->left, r->right) && dfs(l->right, r->left);
    }
};

146. LRU 缓存

class LRUCache {
public:
    int cap_;
    list<int> l_;

    unordered_map<int, int> mp;
public:
    LRUCache(int capacity) : cap_(capacity) {

    }

    /*
         查找要完成更新的过程
        1. 删除key
        2. 将key移动到最新的地方
    */
    int get(int key) {
        auto iter = mp.find(key);
        if (iter != mp.end())
        {
            updateList
            return iter->second;
        }
        return -1;
    }

    /*
    首先用哈希表判断key是否存在：

        如果key存在:
            则修改对应的value，同时将key对应的节点放到双链表的最左侧；
        如果key不存在：
            1. 如果缓存已满，则删除双链表最右侧的节点（上次使用时间最老的节点），更新哈希表；
            2. 否则，插入(key, value)：同时将key对应的节点放到双链表的最左侧，更新哈希表；

    */
    void put(int key, int value) {
        auto iter = mp.find(key);
        if (iter != mp.end()) // key exist
        {
            updateList(key);
            iter->second = value;
        }
        else // key don't exist
        {
            if (mp.size() == cap_) // 
            {
                auto front = l_.front();
                l_.pop_front();
                mp.erase(front);

            }

            mp.insert({key, value});
            l_.push_back(key);

        }
    }

    // 在链表中找到当前元素，并且移动到链表的最右端
    // 我这里是直接删除，然后插入
    void updateList(int key)
    {
        for (auto iter=l_.begin(); iter!=l_.end(); iter++)
        {
            bool flag = false;
            if (*iter == key)
            {
                l_.erase(iter);
                flag = true;
                break;
            }
            if (flag) break;
        }

        l_.push_back(key);
    }
};

这个解法非常的费时。。。

236. 二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left == nullptr) return right;
        if (right == nullptr) return left;

        return root;

    }
};

ref2
ref3

241. 为运算表达式设计优先级

class Solution {
public:
    vector<string> e;

    vector<int> diffWaysToCompute(string exp) {

        transfer(exp);
        return dfs(0, e.size() - 1);

    }

    vector<int> dfs(int l, int r) {
        if (l == r) return {stoi(e[l])};

        vector<int> res;

        for (int i=l+1; i < r; i += 2) {
            auto left = dfs(l, i-1), right = dfs(i+1, r);
            for (auto x : left) {
                for (auto y : right) {
                    int z;
                    if (e[i] == "+") z = x + y;
                    else if (e[i] == "-") z = x - y;
                    else z = x * y;

                    res.push_back(z);
                }
            }
        }

        return res;
    }

    void transfer(const string& s) {
        for (int i=0; i<s.size(); i++) {
            if (isdigit(s[i])) {
                int j = i, x = 0;
                while (j < s.size() && isdigit(s[j])) 
                    x = x * 10 + (s[j++] - '0');
                i = j - 1;
                e.push_back(to_string(x));
            } else {
                e.push_back(s.substr(i, 1));
            }
        }
    }

};

621. 任务调度器

image.png
ref1
ref2

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int maxTimes = 0; //出现次数最多的任务的次数
        int maxCnt = 0;     //
        unordered_map<char, int> mp;
        for (const auto& ch : tasks)
        {
            mp[ch]++;
            maxTimes = max(maxTimes, mp[ch]);
        }

        for (auto iter : mp)
            if (iter.second == maxTimes)
                maxCnt++;

        return max((int)tasks.size(), (maxTimes-1)*(n+1) + maxCnt);
    }
};

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目

dfs

class Solution {
    vector<int> nums;
    int tar;
    int n;
    int res;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        n = nums.size();
        this->nums = nums;
        tar = target;

        dfs(0, 0);

        return res;
    }

    void dfs(int idx, int curSum)
    {
        if (idx == n)
        {
            if (curSum == tar) res++;
            return ;            
        }

        dfs(idx+1, curSum + nums[idx]);
        dfs(idx+1, curSum - nums[idx]);

        return ;
    }

};

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        /*
        1. 先求数组的总和sum
            a. sum奇数， 返回false
            b. sum偶数
                i. 将问题转化为01背包问题，然后进行求解
                    target = sum/2
        */


        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int n = nums.size(), m = sum / 2;
        vector<vector<int>> f(n+1, vector<int>(m+1, 0));

        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=m; j++)
            {
                int wv = nums[i-1];
                if (j >= wv)
                    f[i][j] = max(f[i-1][j], f[i-1][j-wv] + wv);
                else 
                    f[i][j] = f[i-1][j];
            }
        }

        if (f[n][m] == m) return true;

        return false;

    }
};

空间优化

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int n = nums.size(), m = sum / 2;
        vector<int> f(m+1, 0);

        for (int i=1; i<=n; i++)
        {
            int wv = nums[i-1];
            for (int j=m; j>=wv; j--)
                f[j] = max (f[j], f[j-wv] + wv);
        }

        if (f[m] == m) return true;

        return false;
    }
};

394. 字符串解码

这里使用的是模拟

class Solution {
public:
    string decodeString(string s) {
        stack<string> st;
        for (auto ch : s)
        {
            if (ch == ']')
            {
                string cur, curCombi;
                while (st.top()[0] != '[')
                {
                    string c = st.top();
                    st.pop();

                    cur = c + cur;
                }
                st.pop(); // [ pop

                string num;
                while (!st.empty() && isdigit(st.top()[0])) // 注意判空
                {
                    num = st.top() + num;
                    st.pop();
                }
                int n = stoi(num);

                while (n--) curCombi += cur;

                st.push(curCombi);

            }
            else
                st.push(string(1, ch));
        }

        string res;
        while (!st.empty())
        {
            res = st.top() + res;
            st.pop();
        }

        return res;
    }
};

399. 除法求值

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& eq, vector<double>& vals, vector<vector<string>>& qry){
        //  建图
        unordered_map<string, int> hash;
        int n = eq.size(), cnt = 0; // 图中有多少条边

        for (int i=0; i<n; i++) {
            if (hash.find(eq[i][0]) == hash.end()) hash[eq[i][0]] = cnt++;
            if (hash.find(eq[i][1]) == hash.end()) hash[eq[i][1]] = cnt++;
        }

        vector<vector<double>> g(cnt, vector<double>(cnt, -1.0)); // g(graph)
        for (int i=0; i<n; i++) {
            int k1 =hash[eq[i][0]];
            int k2 = hash[eq[i][1]];
            g[k1][k2] = vals[i];
            g[k2][k1] = 1.0 / vals[i];
        }

        // floyd update
        for (int k=0; k<cnt; k++) {
            for (int i=0; i<cnt; i++) {
                for (int j=0; j<cnt; j++) {
                    if (g[i][k]>0 && g[k][j]>0) // 已经构建了边（初始化时，都为-1）
                        g[i][j] = g[i][k] * g[k][j];
                }
            }
        }

        // get query answer
        vector<double> res;
        for (auto& q : qry) {
            double ans = -1.0;
            if (hash.find(q[0]) != hash.end() && hash.find(q[1]) != hash.end()) {
                int k1 = hash[q[0]], k2 = hash[q[1]];
                if (g[k1][k2] > 0) 
                    ans = g[k1][k2];
            }
            res.push_back(ans);
        }

        return res;
    }
};

347. 前 K 个高频元素

 class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for (auto& i : nums) mp[i]++;

        struct mycmp {
            bool operator() (pair<int, int>&p1, pair<int, int>& p2) {
                return p1.second > p2.second;
            }
        };

        priority_queue<pair<int, int>, vector<pair<int, int>>, mycmp> q;
        for (auto &i : mp) {
            q.push(i);
            if (q.size() > k) q.pop();
        }

        vector<int> res;
        while (!q.empty()) {
            res.emplace_back(q.top().first);
            q.pop();
        }

        return res; 
    }
};

221. 最大正方形

image.png

class Solution {
public:
    int maximalSquare(vector<vector<char>>& mat) {
        int m = mat.size(), n = mat[0].size();

        int res = 0;
        vector<vector<int>> f(m+1, vector<int>(n+1, 0));
        for (int i=0; i<m; i++) f[i][0] = mat[i][0] - '0', res = max(res, f[i][0]);
        for (int i=0; i<n; i++) f[0][i] = mat[0][i] - '0', res = max(res, f[0][i]);


        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                if (mat[i][j] == '1') {
                    f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1;
                    res = max(res, f[i][j]);
                }
            }
        }

        return res*res;
    }
};

将第一行和第一列的处理放到循环中

class Solution {
public:
    int maximalSquare(vector<vector<char>>& mat) {
        int m = mat.size(), n = mat[0].size();

        vector<vector<int>> f(m+1, vector<int>(n+1, 0));

        int res = 0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (mat[i][j] == '1') {
                    if (i == 0 || j == 0) f[i][j] = 1;
                    else f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1;
                }
                res = max(res, f[i][j]);
            }
        }

        return res*res;
    }
};

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额

状态机模型

class Solution {
public:
    unordered_map<TreeNode*, pair<int, int>> f;// first : not choose  second :  choose

    int rob(TreeNode* root) {
        dfs(root);

        return max(f[root].first, f[root].second);
    }

    void dfs(TreeNode* node)
    {
        if (node == nullptr) return ;

        dfs(node->left);
        dfs(node->right);
        f[node].second = node->val + f[node->left].first + f[node->right].first;
        f[node].first = max(f[node->left].first, f[node->left].second) \
                        + max(f[node->right].first, f[node->right].second);

    }
};

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false

有向无环图的拓扑排序

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& edges) {

        /*
             有向无环图的拓扑排序 
        */

        vector<vector<int>> g(n);

        vector<int> d(n); // in-degree

        for (auto &e : edges) {
            int a = e[0], b = e[1];
            g[b].push_back(a); // g[b] b's next point
            d[a]++; // a's in-degree ++
        }

        // find first in-degree == 0, push into queue
        queue<int> q;
        for (int i=0; i<n; i++)
            if (d[i] == 0)
                q.push(i);

        int cnt = 0;
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            cnt++;

            for (auto& i : g[t]) { // tranverse all g[t]'s next point in graph 
                if (--d[i] == 0)
                    q.push(i);
            }

        }

        return cnt == n;

    }
};

297. 二叉树的序列化与反序列化

采用的是先序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {

string path;
public:
/*
    input :    [1,2,3,null,null,4,5]
    seralize : "[1,2,3,#,#,4,5]"
*/

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        dfs_serialize(root);
        return path;
    }

    void dfs_serialize(TreeNode* root) {
        if (!root) path +=  "#,";
        else {
            path += to_string(root->val) + ',';
            dfs_serialize(root->left);
            dfs_serialize(root->right);
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_deserialize(data, u);
    }

    TreeNode* dfs_deserialize(string& data, int& u) {
        if (data[u] == '#') {
            u += 2;
            return nullptr;
        } else {
            int k = u;
            while (data[u] != ',') u++;
            auto root = new TreeNode(stoi(data.substr(k, u-k)));
            u++; // skip ","

            root->left  = dfs_deserialize(data, u);
            root->right = dfs_deserialize(data, u);
            return root;
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

6111. 螺旋矩阵 IV

朴素做法

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> res(m, vector<int>(n, -1));

        int l = 0, r = n-1, u = 0, d = m-1;
        while (head) {
            // l - > r
            for (int i=l; i<=r && head; i++) {
                res[u][i] = head->val;
                head = head->next;
            }
            u++;

            // u -> d
            for (int i = u; i <= d && head; i++) {
                res[i][r] = head->val;
                head = head->next;
            }
            r--;

            // r -> l
            for (int i = r; i >= l && head; i--) {
                res[d][i] = head->val;
                head = head->next;
            }
            d--;

            // d -> u
            for (int i = d; i >= u && head; i--) {
                res[i][l] = head->val;
                head = head->next;
            }
            l++;
        }

        return res;
    }
};

![image.png](https://cdn.nlark.com/yuque/0/2022/png/25838471/1656836898153-8f21e40c-f18d-43a4-9417-84a5f337c5a2.png#clientId=ue0b23964-7556-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=356&id=u17ce6d3f&margin=%5Bobject%20Object%5D&name=image.png&originHeight=849&originWidth=1314&originalType=binary&ratio=1&rotation=0&showTitle=false&size=417002&status=done&style=none&taskId=u421f060c-87cc-4174-b057-be0a3cc01c9&title=&width=551)

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> res(m, vector<int>(n, -1));

        int x = 0, y = 0 , d = 1;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 

        for (int i = 0; i <= m * n && head; i++) {
            res[x][y] = head->val;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= m || b < 0 || b >= n || res[a][b] != -1) { // 碰壁
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }

            x = a, y = b;
            head = head->next;

        }
        return res;
    }
};