删除排序数组中的重复项Ⅱ

Date：2020-11-3 周二
image.pngimage.png

双指针

  1. class Solution:
  2.     def removeDuplicates(self, nums: List[int]) -> int:
  3.         memoryIndex = index = 0
  4.         memory = -9999
  5.         max = 1
  6.         while index < len(nums):
  7.             if memory == nums[index]:
  8.                 index += 1
  9.                 continue
  10.             memory = nums[index]
  11.             while index < len(nums) - 1 and nums[index + 1] == memory and max > 0:
  12.                 nums[memoryIndex] = nums[index]
  13.                 memoryIndex += 1
  14.                 index += 1
  15.                 max -= 1
  16.             max = 1
  17.             nums[memoryIndex] = nums[index]
  18.             index += 1
  19.             memoryIndex += 1
  20.         return memoryIndex

大佬思路

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int i = 0;
  4.         for (int n : nums) {
  5.             # 因为限制重复最多为2项 所以在 i>=2 之后 如果 n > nums[i-2] 说明重复项不大于2 否则则多于2
  6.             if (i < 2 || n > nums[i-2]) nums[i++] = n;
  7.         }
  8.         return i;
  9.     }
  10. }

搜索旋转排序数组Ⅱ**

Date：2020-11-3 周二
image.png

二分查找

image.png

  1. class Solution:
  2.     def search(self, nums: List[int], target: int) -> bool:        
  3.         l = 0
  4.         r = len(nums) - 1
  5.         while l<=r:
  6.             mid = (l+r) // 2
  7.             if nums[mid] == target:
  8.                 return True
  10.             if nums[mid] == nums[l]:  # l和mid重复，l加一
  11.                 l += 1
  12.             elif nums[mid] == nums[r]:  # mid和r重复，r减一
  13.                 r -= 1
  14.             elif nums[mid] > nums[l]:  # l到mid是有序的，判断target是否在其中
  15.                 if nums[l] <= target < nums[mid]:  # target在其中，选择l到mid这段
  16.                     r = mid - 1
  17.                 else:  # target不在其中，扔掉l到mid这段
  18.                     l = mid + 1
  19.             elif nums[mid] < nums[r]:  # mid到r是有序的，判断target是否在其中
  20.                 if nums[mid] < target <= nums[r]:
  21.                     l = mid + 1
  22.                 else:
  23.                     r = mid - 1 
  24.         return False

删除排序链表中的重复元素

Date：2020-11-4 周三

image.png**

双指针+头结点

  1. class Solution:
  2.     def deleteDuplicates(self, head: ListNode) -> ListNode:
  3.         if not head or not head.next: return head
  4.         headNode = ListNode(-999)
  5.         headNode.next = head
  6.         left = headNode
  7.         right = headNode.next
  8.         while right != None:
  9.             if right.next and right.val == right.next.val:
  10.                 temp = right.val
  11.                 left.next = right
  12.                 left = left.next
  13.                 while right != None and right.val == temp:
  14.                     right = right.next
  15.             else:
  16.                 left.next = right
  17.                 left = left.next
  18.                 right = right.next
  19.         left.next = right
  20.         return headNode.next

删除排序链表中的重复元素Ⅱ*

Date：2020-11-4 周三
image.png

双指针+头结点

  1. class Solution:
  2.     def deleteDuplicates(self, head: ListNode) -> ListNode:
  3.         if head == None or head.next == None:
  4.             return head
  5.         dummy = ListNode(-1000)
  6.         dummy.next = head
  7.         slow = dummy
  8.         fast = dummy.next
  9.         while fast:
  10.             if  fast.next and fast.next.val == fast.val:
  11.                 tmp = fast.val
  12.                 while fast and tmp == fast.val:
  13.                     fast = fast.next
  14.             else:
  15.                 slow.next = fast
  16.                 slow = fast
  17.                 fast = fast.next
  18.         slow.next = fast
  19.         return dummy.next

柱状图中最大的矩形*

Date：2020-11-5 周四
image.pngimage.png

暴力求解

image.png
image.png
image.png

  1. class Solution:
  2.     def largestRectangleArea(self, heights: List[int]) -> int:
  3.         res = 0
  4.         for i in range(len(heights)):
  5.             left = i
  6.             cur = heights[i]
  7.             while left > 0 and heights[left - 1] >= cur:
  8.                 left -= 1
  9.             right = i
  10.             while right < len(heights) - 1 and heights[right + 1] >= cur:
  11.                 right += 1
  12.             mid = (right - left + 1) * cur
  13.             res = mid if mid > res else res
  14.         return res

空间换时间（单调栈）

解析网址：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
image.pngimage.png

  1. class Solution:
  2.     def largestRectangleArea(self, heights: List[int]) -> int:
  3.         size = len(heights)
  4.         res = 0
  5.         stack = []
  6.         for i in range(size):
  7.             while len(stack) > 0 and heights[i] < heights[stack[-1]]:
  8.                 cur_height = heights[stack.pop()]
  9.                 while len(stack) > 0 and cur_height == heights[stack[-1]]:
  10.                     stack.pop()
  11.                 if len(stack) > 0:
  12.                     cur_width = i - stack[-1] - 1
  13.                 else:
  14.                     cur_width = i
  15.                 res = max(res, cur_height * cur_width)
  16.             stack.append(i)
  17.         while len(stack) > 0 is not None:
  18.             cur_height = heights[stack.pop()]
  19.             while len(stack) > 0 and cur_height == heights[stack[-1]]:
  20.                 stack.pop()
  21.             if len(stack) > 0:
  22.                 cur_width = size - stack[-1] - 1
  23.             else:
  24.                 cur_width = size
  25.             res = max(res, cur_height * cur_width)
  26.         return res

image.png

最大矩形

Date：2020-11-5 周四
image.pngimage.png

暴力搜索：列优先、按行遍历

  1. class Solution:
  2.     def maximalRectangle(self, matrix: List[List[str]]) -> int:
  3.         if not matrix: return 0
  4.         rows , cols = len(matrix) , len(matrix[0])
  5.         res = 0
  6.         for i in range(rows):
  7.             for j in range(cols):
  8.                 if matrix[i][j] == '1':
  9.                     row = i
  10.                     while row < rows and matrix[row][j] == '1': # 按列查找
  11.                         row += 1
  12.                     col = j
  13.                     while col < cols and matrix[i][col] == '1': # 按行查找
  14.                         col += 1
  15.                     x , y = i , j
  16.                     y_max = col
  17.                     mid = 0
  18.                     while x < row:
  19.                         while y < y_max:
  20.                             if matrix[x][y] != '1':
  21.                                 y_max = y 
  22.                                 break
  23.                             y += 1
  24.                         x += 1
  25.                         mid = max(mid , (x - i) * (y - j))
  26.                         y = j
  27.                     # print("i:{} j:{} col:{} row:{} x:{} y:{} mid:{}".format(i,j,col,row,x,y,mid))
  28.                     res = max(res,row-i,col-j,mid)   
  29.         return res

时间复杂度O(n^4)
自己太垃圾了。。。哎

动态规划 - 使用柱状图的优化暴力方法

image.pngimage.png
image.png

  1. class Solution:
  2.     def maximalRectangle(self, matrix: List[List[str]]) -> int:
  3.         maxarea = 0
  5.         dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
  6.         for i in range(len(matrix)):
  7.             for j in range(len(matrix[0])):
  8.                 if matrix[i][j] == '0': continue
  10.                 # compute the maximum width and update dp with it
  11.                 width = dp[i][j] = dp[i][j-1] + 1 if j else 1
  13.                 # compute the maximum area rectangle with a lower right corner at [i, j]
  14.                 for k in range(i, -1, -1):
  15.                     width = min(width, dp[k][j])
  16.                     maxarea = max(maxarea, width * (i-k+1))
  17.         return maxarea

image.png

时间复杂度还不如我自己写的暴力

动态规划

image.pngimage.pngimage.pngimage.pngimage.png

  2. class Solution:
  4.     def maximalRectangle(self, matrix: List[List[str]]) -> int:
  5.         if not matrix: return 0
  7.         m = len(matrix)
  8.         n = len(matrix[0])
  10.         left = [0] * n # initialize left as the leftmost boundary possible
  11.         right = [n] * n # initialize right as the rightmost boundary possible
  12.         height = [0] * n
  14.         maxarea = 0
  16.         for i in range(m):
  18.             cur_left, cur_right = 0, n
  19.             # update height
  20.             for j in range(n):
  21.                 if matrix[i][j] == '1': height[j] += 1
  22.                 else: height[j] = 0
  23.             # update left
  24.             for j in range(n):
  25.                 if matrix[i][j] == '1': left[j] = max(left[j], cur_left)
  26.                 else:
  27.                     left[j] = 0
  28.                     cur_left = j + 1
  29.             # update right
  30.             for j in range(n-1, -1, -1):
  31.                 if matrix[i][j] == '1': right[j] = min(right[j], cur_right)
  32.                 else:
  33.                     right[j] = n
  34.                     cur_right = j
  35.             # update the area
  36.             for j in range(n):
  37.                 maxarea = max(maxarea, height[j] * (right[j] - left[j]))
  39.         return maxarea

分隔链表

Date：2020-11-6 周五
image.png

以空间换时间

  1. class Solution:
  2.     def partition(self, head: ListNode, x: int) -> ListNode:
  3.         headLeft , headRight = ListNode(-1) , ListNode(-2)
  4.         index = head
  5.         leftIndex , rightIndex = headLeft , headRight
  6.         while index != None:
  7.             if index.val < x:
  8.                 leftIndex.next = index
  9.                 leftIndex = leftIndex.next
  10.             else:
  11.                 rightIndex.next = index
  12.                 rightIndex = rightIndex.next
  13.             index = index.next
  14.         rightIndex.next = None
  15.         leftIndex.next = headRight.next
  16.         return headLeft.next

扰乱字符串**

Date：2020-11-9 周一
image.pngimage.png

区间DP

image.png
5.最长回文子串
516. 最长回文子序列
312. 戳气球
1246. 删除回文子数组（这个题微软面试问的很多）

image.png
image.png

递归实现

  1. class Solution {
  2.     public boolean isScramble(String s1, String s2) {
  3.         // 长度不等，必定不能变换
  4.         if (s1.length() != s2.length()) {
  5.             return false;
  6.         }
  7.         // 长度相等，先特判下
  8.         if (s1.equals(s2)) {
  9.             return true;
  10.         }
  11.         // 看一下字符个数是否一致，不同直接return false
  12.         int n = s1.length();
  13.         HashMap<Character, Integer> map = new HashMap<>();
  14.         for (int i = 0; i < n; i++) {
  15.             char c1 = s1.charAt(i);
  16.             char c2 = s2.charAt(i);
  17.             map.put(c1, map.getOrDefault(c1, 0) + 1);
  18.             map.put(c2, map.getOrDefault(c2, 0) - 1);
  19.         }
  20.         // out.println(map.size());
  21.         for (Character key : map.keySet()) {
  22.             // out.println("key:"+key + " value:"+map.get(key));
  23.             if (map.get(key) != 0) {
  24.                 return false;
  25.             }
  26.         }
  28.         // 相同的话，开始判断判断，满足一个就能 return true
  29.         for (int i = 1; i < n; i++) {
  30.             boolean flag =
  31.                     // S1 -> T1，S2 -> T2   S:[S1,S2]=[[0,i),[i,n)]  T:[T1,T2]=[0,i),[i,n)]
  32.                     (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) ||
  33.                     // S1 -> T2，S2 -> T1
  34.                     (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));
  35.             if (flag) {
  36.                 return true;
  37.             }
  38.         }
  39.         return false;
  40.     }
  41. }

非递归实现

  1. class Solution {
  2.     public boolean isScramble(String s1, String s2) {
  3.         char[] chs1 = s1.toCharArray();
  4.         char[] chs2 = s2.toCharArray();
  5.         int n = s1.length();
  6.         int m = s2.length();
  7.         if (n != m) {
  8.             return false;
  9.         }
  10.         boolean[][][] dp = new boolean[n][n][n + 1];
  11.         // 初始化单个字符的情况
  12.         for (int i = 0; i < n; i++) {
  13.             for (int j = 0; j < n; j++) {
  14.                 dp[i][j][1] = chs1[i] == chs2[j];
  15.             }
  16.         }
  18.         // 枚举区间长度 2～n
  19.         for (int len = 2; len <= n; len++) {
  20.             // 枚举 S 中的起点位置
  21.             for (int i = 0; i <= n - len; i++) {
  22.                 // 枚举 T 中的起点位置
  23.                 for (int j = 0; j <= n - len; j++) {
  24.                     // 枚举划分位置
  25.                     for (int k = 1; k <= len - 1; k++) {
  26.                         // 第一种情况：S1 -> T1, S2 -> T2
  27.                         if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
  28.                             dp[i][j][len] = true;
  29.                             break;
  30.                         }
  31.                         // 第二种情况：S1 -> T2, S2 -> T1
  32.                         // S1 起点 i，T2 起点 j + 前面那段长度 len-k ，S2 起点 i + 前面长度k
  33.                         if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
  34.                             dp[i][j][len] = true;
  35.                             break;
  36.                         }
  37.                     }
  38.                 }
  39.             }
  40.         }
  41.         return dp[0][0][n];
  42.     }
  43. }

合并两个有序数组

Date：2020-11-9 周一
image.png

合并后排序

image.png

  1. class Solution {
  2.   public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.     System.arraycopy(nums2, 0, nums1, m, n);
  4.     Arrays.sort(nums1);
  5.   }
  6. }
  7. //arraycopy 用法：
  8. //src表示源数组
  9. //srcPos表示源数组中拷贝元素的起始位置。
  10. //dest表示目标数组
  11. //destPos表示拷贝到目标数组的起始位置
  12. //length表示拷贝元素的个数

双指针/从前往后

image.png

  1. class Solution {
  2.   public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.     // Make a copy of nums1.
  4.     int [] nums1_copy = new int[m];
  5.     System.arraycopy(nums1, 0, nums1_copy, 0, m);
  7.     // Two get pointers for nums1_copy and nums2.
  8.     int p1 = 0;
  9.     int p2 = 0;
  11.     // Set pointer for nums1
  12.     int p = 0;
  14.     // Compare elements from nums1_copy and nums2
  15.     // and add the smallest one into nums1.
  16.     while ((p1 < m) && (p2 < n))
  17.       nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
  19.     // if there are still elements to add
  20.     if (p1 < m)
  21.       System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
  22.     if (p2 < n)
  23.       System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  24.   }
  25. }

双指针/从后往前 **

image.png
image.png

  1. class Solution {
  2.   public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.     // two get pointers for nums1 and nums2
  4.     int p1 = m - 1;
  5.     int p2 = n - 1;
  6.     // set pointer for nums1
  7.     int p = m + n - 1;
  9.     // while there are still elements to compare
  10.     while ((p1 >= 0) && (p2 >= 0))
  11.       // compare two elements from nums1 and nums2 
  12.       // and add the largest one in nums1 
  13.       nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
  15.     // add missing elements from nums2
  16.     System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
  17.   }
  18. }

格雷编码**

Date：2020-11-10 周二
image.pngimage.pngimage.png

动态规划（真的妙啊）

image.pngimage.pngimage.png

  1. class Solution {
  2.     public List<Integer> grayCode(int n) {
  3.         List<Integer> gray = new ArrayList<Integer>();
  4.         gray.add(0); //初始化 n = 0 的解
  5.         for (int i = 0; i < n; i++) {
  6.             int add = 1 << i; //要加的数
  7.             //倒序遍历，并且加上一个值添加到结果中
  8.             for (int j = gray.size() - 1; j >= 0; j--) {
  9.                 gray.add(gray.get(j) + add);
  10.             }
  11.         }
  12.         return gray;
  13.     }
  14. }

image.png

直接推导

image.png

  1. public List<Integer> grayCode2(int n) {
  2.     List<Integer> gray = new ArrayList<Integer>();
  3.     gray.add(0); //初始化第零项
  4.     for (int i = 1; i < 1 << n; i++) {
  5.         //得到上一个的值
  6.         int previous = gray.get(i - 1);
  7.         //同第一项的情况
  8.         if (i % 2 == 1) {
  9.             previous ^= 1; //和 0000001 做异或，使得最右边一位取反
  10.             gray.add(previous);
  11.         //同第二项的情况
  12.         } else {
  13.             int temp = previous;
  14.             //寻找右边起第第一个为 1 的位元
  15.             for (int j = 0; j < n; j++) {
  16.                 if ((temp & 1) == 1) {
  17.                     //和 00001000000 类似这样的数做异或，使得相应位取反
  18.                     previous = previous ^ (1 << (j + 1));
  19.                     gray.add(previous);
  20.                     break;
  21.                 }
  22.                 temp = temp >> 1;
  23.             }
  24.         }
  25.     }
  26.     return gray;
  27. }

image.png

公式法

image.png

  1. public List<Integer> grayCode(int n) {
  2.     List<Integer> gray = new ArrayList<Integer>();
  3.     for(int binary = 0;binary < 1 << n; binary++){
  4.         gray.add(binary ^ binary >> 1);
  5.     }
  6.     return gray;
  7. }

image.png

子集Ⅱ

Date：2020-11-10 周二
image.png

回溯法

这个比较好改，我们只需要判断当前数字和上一个数字是否相同，相同的话跳过即可。当然，要把数字首先进行排序。

  1. class Solution {
  2.     private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) {
  3.         ans.add(new ArrayList<>(temp));
  4.         for (int i = start; i < nums.length; i++) {
  5.             if (i > start && nums[i] == nums[i - 1]) {
  6.                 continue;
  7.             }
  8.             temp.add(nums[i]);
  9.             getAns(nums, i + 1, temp, ans);
  10.             temp.remove(temp.size() - 1);
  11.         }
  12.     }
  14.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  15.         List<List<Integer>> ans =new ArrayList<>();
  16.         Arrays.sort(nums);
  17.         getAns(nums,0,new ArrayList<>(),ans);
  18.         return ans;
  19.     }
  20. }

公式转换

Date：2020-11-12 周四
image.png

非递归 + 栈

  1. package com.company;
  3. import java.util.Stack;
  5. public class TString {
  6.     static public String merge(String[] nums){
  7.         StringBuilder pushNum = new StringBuilder();
  8.         for (String num : nums) {
  9.             pushNum.append("+").append(num);
  10.         }
  11.         System.out.println("merge - pushNum: "+pushNum.toString().substring(1));
  12.         return pushNum.toString().substring(1);
  13.     }
  14.     static public String change(String s){
  15.         if(s.equals("1")){
  16.             return "1";
  17.         }
  18.         return "Y["+s.substring(1)+"]";
  19.     }
  20.     public static String transformation(String target){
  21.         char[] str = target.toCharArray();
  22.         Stack<Character> symbolStack = new Stack<>();
  23.         Stack<String> numStack = new Stack<>();
  24.         StringBuilder midNum = new StringBuilder();
  25.         for (int i = 0; i < str.length; i++) {
  26.             switch (str[i]){
  27.                 case '(':
  28.                     symbolStack.push('(');
  29.                     break;
  30.                 case ')':
  31.                     if (midNum.length()>0){
  32.                         numStack.push(change(midNum.toString()));
  33.                         midNum = new StringBuilder();
  34.                     }
  35.                     StringBuilder nums = new StringBuilder();
  36.                     while (symbolStack.peek()!='('){
  37.                         nums.insert(0, symbolStack.pop()+numStack.pop());
  38.                     }
  39.                     nums.insert(0,numStack.pop()); // 获得每个()内的公式 :(x106+x85+x42+x21) -> Y[106]+Y[85]+Y[42]+Y[21]
  40.                     System.out.println(nums.toString());
  41.                     numStack.push(nums.toString());
  42.                     break;
  43.                 case '+':
  44.                     symbolStack.push('+');
  45.                     if (midNum.length()>0){
  46.                         numStack.push(change(midNum.toString())); //将 x116 -> Y[116]
  47.                         midNum = new StringBuilder();
  48.                     }
  49.                     break;
  50.                 case '*':
  51.                     String[] midNums = numStack.pop().split("\\+");
  52.                     int index = i+1;
  53.                     StringBuilder e = new StringBuilder();
  54.                     while (index < str.length && str[index] != '(' && str[index] != ')' && str[index] != '+'){
  55.                         e.append(str[index]);
  56.                         index ++;
  57.                     }
  58.                     i = index - 1;
  59.                     String midS = "";
  60.                     midS = "[" +e.toString().substring(1)+"]"; // 默认只有 *x11 这种情况 读入一个x116 -> [116]
  61.                     for (int j = 0; j < midNums.length; j++) {
  62.                         if (midNums[j].equals("1")){
  63.                             midNums[j] = "Y"+midS;
  64.                         }else {
  65.                             midNums[j] += midS;
  66.                         }
  67.                     }
  68.                     numStack.push(merge(midNums));
  69.                     break;
  70.                 default:
  71.                     midNum.append(str[i]);
  72.                     break;
  73.             }
  74.         }
  75.         return numStack.pop();
  76.     }
  77.     public static void main(String[] args) {
  78.         System.out.println(transformation("((x106+x85+x42+x21)*x116+(x95+x85+x52+x31+1)*x106+x13)*x95"));
  79.     }
  80. }

解码方法**

Date：2020-11-12 周四
image.png
image.png
我还是想吐槽下，这道题就没说明白。比如”01”算不算。md

DFS（超时）

image.png

  1. public int numDecodings(String s) {
  2.     return getAns(s, 0);
  3. }
  5. private int getAns(String s, int start) {
  6.     //划分到了最后返回 1
  7.     if (start == s.length()) {
  8.         return 1;
  9.     }
  10.     //开头是 0,0 不对应任何字母，直接返回 0
  11.     if (s.charAt(start) == '0') {
  12.         return 0;
  13.     }
  14.     //得到第一种的划分的解码方式
  15.     int ans1 = getAns(s, start + 1);
  16.     int ans2 = 0;
  17.     //判断前两个数字是不是小于等于 26 的
  18.     if (start < s.length() - 1) {
  19.         int ten = (s.charAt(start) - '0') * 10;
  20.         int one = s.charAt(start + 1) - '0';
  21.         if (ten + one <= 26) {
  22.             ans2 = getAns(s, start + 2);
  23.         }
  24.     }
  25.     return ans1 + ans2;
  26. }

上边的递归中，走完左子树，再走右子树会把一些已经算过的结果重新算，所以我们可以用 memoization 技术，就是算出一个结果很就保存，第二次算这个的时候直接拿出来就可以了。

  1. public int numDecodings(String s) {
  2.     HashMap<Integer, Integer> memoization = new HashMap<>();
  3.     return getAns(s, 0, memoization);
  4. }
  6. private int getAns(String s, int start, HashMap<Integer, Integer> memoization) {
  7.     if (start == s.length()) {
  8.         return 1;
  9.     }
  10.     if (s.charAt(start) == '0') {
  11.         return 0;
  12.     }
  13.     //判断之前是否计算过
  14.     int m = memoization.getOrDefault(start, -1);
  15.     if (m != -1) {
  16.         return m;
  17.     }
  18.     int ans1 = getAns(s, start + 1, memoization);
  19.     int ans2 = 0;
  20.     if (start < s.length() - 1) {
  21.         int ten = (s.charAt(start) - '0') * 10;
  22.         int one = s.charAt(start + 1) - '0';
  23.         if (ten + one <= 26) {
  24.             ans2 = getAns(s, start + 2, memoization);
  25.         }
  26.     }
  27.     //将结果保存
  28.     memoization.put(start, ans1 + ans2);
  29.     return ans1 + ans2;
  30. }

动态规划（反向易懂）

image.png

  1. public int numDecodings(String s) {
  2.     int len = s.length();
  3.     int[] dp = new int[len + 1];
  4.     dp[len] = 1; //将递归法的结束条件初始化为 1 
  5.     //最后一个数字不等于 0 就初始化为 1
  6.     if (s.charAt(len - 1) != '0') {
  7.         dp[len - 1] = 1;
  8.     }
  9.     for (int i = len - 2; i >= 0; i--) {
  10.         //当前数字时 0 ，直接跳过，0 不代表任何字母
  11.         if (s.charAt(i) == '0') {
  12.             continue;
  13.         }
  14.         int ans1 = dp[i + 1];
  15.         //判断两个字母组成的数字是否小于等于 26
  16.         int ans2 = 0;
  17.         int ten = (s.charAt(i) - '0') * 10;
  18.         int one = s.charAt(i + 1) - '0';
  19.         if (ten + one <= 26) {
  20.             ans2 = dp[i + 2];
  21.         }
  22.         dp[i] = ans1 + ans2;
  24.     }
  25.     return dp[0];
  26. }

反转链表

Date：2020-11-12 周四
image.png

头插法（一次遍历）

  1. class Solution {
  2.     public ListNode reverseBetween(ListNode head, int m, int n) {
  3.         if (m==n) return head;
  4.         ListNode headNode = new ListNode(-1) , right ,left , last; //left指向第m个节点的前方 right用来遍历
  5.         headNode.next = head;
  6.         left = headNode;
  7.         int index = 0;
  8.         while (left!=null && index++ < m-1){
  9.             left = left.next;
  10.         }
  11.         right = left.next;
  12.         last = left.next;
  13.         index--;
  14.         while (right!=null && index++ < n){
  15.             ListNode mid = right.next;
  16.             right.next=left.next;
  17.             left.next = right;
  18.             right = mid;
  19.         }
  20.         last.next = right;
  21.         return headNode.next;
  22.     }
  23. }

复原IP地址**

Date：2020-11-16 周一
image.pngimage.png

递归

image.png

  1. class Solution {
  2.     static final int SEG_COUNT = 4;
  3.     List<String> ans = new ArrayList<String>();
  4.     int[] segments = new int[SEG_COUNT];
  6.     public List<String> restoreIpAddresses(String s) {
  7.         segments = new int[SEG_COUNT];
  8.         dfs(s, 0, 0);
  9.         return ans;
  10.     }
  12.     public void dfs(String s, int segId, int segStart) {
  13.         // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
  14.         if (segId == SEG_COUNT) {
  15.             if (segStart == s.length()) {
  16.                 StringBuffer ipAddr = new StringBuffer();
  17.                 for (int i = 0; i < SEG_COUNT; ++i) {
  18.                     ipAddr.append(segments[i]);
  19.                     if (i != SEG_COUNT - 1) {
  20.                         ipAddr.append('.');
  21.                     }
  22.                 }
  23.                 ans.add(ipAddr.toString());
  24.             }
  25.             return;
  26.         }
  28.         // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
  29.         if (segStart == s.length()) {
  30.             return;
  31.         }
  33.         // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
  34.         if (s.charAt(segStart) == '0') {
  35.             segments[segId] = 0;
  36.             dfs(s, segId + 1, segStart + 1);
  37.         }
  39.         // 一般情况，枚举每一种可能性并递归
  40.         int addr = 0;
  41.         for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
  42.             addr = addr * 10 + (s.charAt(segEnd) - '0');
  43.             if (addr > 0 && addr <= 0xFF) {
  44.                 segments[segId] = addr;
  45.                 dfs(s, segId + 1, segEnd + 1);
  46.             } else {
  47.                 break;
  48.             }
  49.         }
  50.     }
  51. }

二叉树的中序遍历

Date：2020-11-16 周一
image.pngimage.pngimage.pngimage.pngimage.png

递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     List<Integer> ans = new ArrayList<>();
  18.     public void dfs(TreeNode node){
  19.         if (node!=null){
  20.             dfs(node.left);
  21.             ans.add(node.val);
  22.             dfs(node.right);
  23.         }
  24.     }
  25.     public List<Integer> inorderTraversal(TreeNode root) {
  26.         dfs(root);
  27.         return ans;
  28.     }
  29. }

不同的二叉搜索树**

Date：2020-11-16 周一
image.png

动态规划

image.pngimage.pngimage.pngimage.pngimage.png

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         int[] G = new int[n+1];
  4.         G[0] = 1;
  5.         G[1] = 1;
  6.         for (int i = 2; i <= n; i++) {
  7.             for (int j = 1; j <= i; j++) {
  8.                 G[i]+=G[j-1]*G[i-j];
  9.             }
  10.         }
  11.         return G[n];
  12.     }
  13. }

image.png

数学

image.png

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
  4.         long C = 1;
  5.         for (int i = 0; i < n; ++i) {
  6.             C = C * 2 * (2 * i + 1) / (i + 2);
  7.         }
  8.         return (int) C;
  9.     }
  10. }

不同的二叉搜索树Ⅱ*

Date：2020-11-17 周二
给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。
image.png

递归

image.png

  1. class Solution {
  2.     public List<TreeNode> generateTrees(int n) {
  3.         if (n == 0) {
  4.             return new LinkedList<TreeNode>();
  5.         }
  6.         return generateTrees(1, n);
  7.     }
  9.     public List<TreeNode> generateTrees(int start, int end) {
  10.         List<TreeNode> allTrees = new LinkedList<TreeNode>();
  11.         if (start > end) {
  12.             allTrees.add(null);
  13.             return allTrees;
  14.         }
  16.         // 枚举可行根节点
  17.         for (int i = start; i <= end; i++) {
  18.             // 获得所有可行的左子树集合
  19.             List<TreeNode> leftTrees = generateTrees(start, i - 1);
  21.             // 获得所有可行的右子树集合
  22.             List<TreeNode> rightTrees = generateTrees(i + 1, end);
  24.             // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
  25.             for (TreeNode left : leftTrees) {
  26.                 for (TreeNode right : rightTrees) {
  27.                     TreeNode currTree = new TreeNode(i);
  28.                     currTree.left = left;
  29.                     currTree.right = right;
  30.                     allTrees.add(currTree);
  31.                 }
  32.             }
  33.         }
  34.         return allTrees;
  35.     }
  36. }

image.png

构建一棵二叉树的递归

  1. public TreeNode createBinaryTree(int n){
  2.     return helper(1, n);
  3. }
  5. public TreeNode helper(int start, int end){
  6.     if(start > end)
  7.         return null;
  9.     // 这里可以选择从start到end的任何一个值做为根结点，
  10.     // 这里选择它们的中点，实际上，这样构建出来的是一颗平衡二叉搜索树
  11.     int val = (start + end) / 2;
  12.     TreeNode root = new TreeNode(val);
  14.     root.left = helper(start, val - 1);
  15.     root.right = helper(val + 1, end);
  17.     return root;
  18. }

同样解法的另一种解释

交错字符串

Date：2020-11-17 周二
image.png

暴力递归（超时）

  1. class Solution {
  2.     public boolean dp(String s1,int index_1,String s2,int index_2,String s3,int index){
  3.         if (index_1 >= s1.length() && index_2 >= s2.length() && index >= s3.length())
  4.             return true;
  5.         boolean l = false , r = false;
  6.         if (index < s3.length() && index_1 < s1.length() && s3.charAt(index) == s1.charAt(index_1)){
  7.             l = dp(s1,index_1 + 1,s2,index_2,s3,index+1);
  8.         }
  9.         if (index < s3.length() && index_2 < s2.length() && s3.charAt(index) == s2.charAt(index_2)){
  10.             r = dp(s1,index_1,s2,index_2 + 1,s3,index+1);
  11.         }
  12.         return l || r;
  13.     }
  14.     public boolean isInterleave(String s1, String s2, String s3) {
  15.         return dp(s1,0,s2,0,s3,0);
  16.     }
  17. }

动态规划

image.png

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.         int n = s1.length(), m = s2.length(), t = s3.length();
  5.         if (n + m != t) {
  6.             return false;
  7.         }
  9.         boolean[][] f = new boolean[n + 1][m + 1];
  11.         f[0][0] = true;
  12.         for (int i = 0; i <= n; ++i) {
  13.             for (int j = 0; j <= m; ++j) {
  14.                 int p = i + j - 1;
  15.                 if (i > 0) {
  16.                     f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
  17.                 }
  18.                 if (j > 0) {
  19.                     f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
  20.                 }
  21.             }
  22.         }
  24.         return f[n][m];
  25.     }
  26. }

不难看出这个实现的时间复杂度和空间复杂度都是 O(nm)O(nm)。

滚动数组

image.png

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.         int n = s1.length(), m = s2.length(), t = s3.length();
  5.         if (n + m != t) {
  6.             return false;
  7.         }
  9.         boolean[] f = new boolean[m + 1];
  11.         f[0] = true;
  12.         for (int i = 0; i <= n; ++i) {
  13.             for (int j = 0; j <= m; ++j) {
  14.                 int p = i + j - 1;
  15.                 if (i > 0) {
  16.                     f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);
  17.                 }
  18.                 if (j > 0) {
  19.                     f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
  20.                 }
  21.             }
  22.         }
  24.         return f[m];
  25.     }
  26. }

验证二叉搜索树

Date：2020-11-18 周三
image.png

中序遍历+判断

如果是一棵二叉搜索树的话，那么他的中序遍历是一个有序的集合，那么就可以先进行先序排列，然后在根据遍历出来的数组进行判断是否是一棵二叉搜索树。

  1. class Solution {
  2.     List<Integer> rootValList = new ArrayList<>();
  3.     public void lRr(TreeNode root){
  4.         if (root.left!=null)
  5.             lRr(root.left);
  6.         rootValList.add(root.val);
  7.         if (root.right!=null)
  8.             lRr(root.right);
  9.     }
  10.     public boolean isValidBST(TreeNode root) {
  11.         if (root==null) return true;
  12.         lRr(root);
  13.         for (int i = 1; i < rootValList.size(); i++) {
  14.             if (rootValList.get(i-1)>=rootValList.get(i))
  15.                 return false;
  16.         }
  17.         return true;
  18.     }
  19. }

官方中序

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         Deque<TreeNode> stack = new LinkedList<TreeNode>();
  4.         double inorder = -Double.MAX_VALUE;
  6.         while (!stack.isEmpty() || root != null) {
  7.             while (root != null) {
  8.                 stack.push(root);
  9.                 root = root.left;
  10.             }
  11.             root = stack.pop();
  12.             // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
  13.             if (root.val <= inorder) {
  14.                 return false;
  15.             }
  16.             inorder = root.val;
  17.             root = root.right;
  18.         }
  19.         return true;
  20.     }
  21. }

递归

最开始做递归没做出来是因为没有设置上下界，导致出错。
image.png

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return helper(root, null, null);
  4.     }
  6.     public boolean helper(TreeNode node, Integer lower, Integer upper) {
  7.         if (node == null) {
  8.             return true;
  9.         }
  11.         int val = node.val;
  12.         if (lower != null && val <= lower) {
  13.             return false;
  14.         }
  15.         if (upper != null && val >= upper) {
  16.             return false;
  17.         }
  19.         if (!helper(node.right, val, upper)) {
  20.             return false;
  21.         }
  22.         if (!helper(node.left, lower, val)) {
  23.             return false;
  24.         }
  25.         return true;
  26.     }
  27. }

恢复二叉搜索树

Date：2020-11-18 周三
image.pngimage.png

显式中序遍历

image.png
image.png

  1. class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.         List<Integer> nums = new ArrayList<Integer>();
  4.         inorder(root, nums);
  5.         int[] swapped = findTwoSwapped(nums);
  6.         recover(root, 2, swapped[0], swapped[1]);
  7.     }
  9.     public void inorder(TreeNode root, List<Integer> nums) {
  10.         if (root == null) {
  11.             return;
  12.         }
  13.         inorder(root.left, nums);
  14.         nums.add(root.val);
  15.         inorder(root.right, nums);
  16.     }
  18.     public int[] findTwoSwapped(List<Integer> nums) {
  19.         int n = nums.size();
  20.         int x = -1, y = -1;
  21.         for (int i = 0; i < n - 1; ++i) {
  22.             if (nums.get(i + 1) < nums.get(i)) {
  23.                 y = nums.get(i + 1);
  24.                 if (x == -1) {
  25.                     x = nums.get(i);
  26.                 } else {
  27.                     break;
  28.                 }
  29.             }
  30.         }
  31.         return new int[]{x, y};
  32.     }
  34.     public void recover(TreeNode root, int count, int x, int y) {
  35.         if (root != null) {
  36.             if (root.val == x || root.val == y) {
  37.                 root.val = root.val == x ? y : x;
  38.                 if (--count == 0) {
  39.                     return;
  40.                 }
  41.             }
  42.             recover(root.right, count, x, y);
  43.             recover(root.left, count, x, y);
  44.         }
  45.     }
  46. }

隐式中序排序

image.png
image.png
image.pngimage.png

  1. class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  4.         TreeNode x = null, y = null, pred = null;
  6.         while (!stack.isEmpty() || root != null) {
  7.             while (root != null) {
  8.                 stack.push(root);
  9.                 root = root.left;
  10.             }
  11.             root = stack.pop();
  12.             if (pred != null && root.val < pred.val) {
  13.                 y = root;
  14.                 if (x == null) {
  15.                     x = pred;
  16.                 } else {
  17.                     break;
  18.                 }
  19.             }
  20.             pred = root;
  21.             root = root.right;
  22.         }
  24.         swap(x, y);
  25.     }
  27.     public void swap(TreeNode x, TreeNode y) {
  28.         int tmp = x.val;
  29.         x.val = y.val;
  30.         y.val = tmp;
  31.     }
  32. }

Morris 中序遍历

image.png

image.png

  1. class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.         TreeNode x = null, y = null, pred = null, predecessor = null;
  5.         while (root != null) {
  6.             if (root.left != null) {
  7.                 // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
  8.                 predecessor = root.left;
  9.                 while (predecessor.right != null && predecessor.right != root) {
  10.                     predecessor = predecessor.right;
  11.                 }
  13.                 // 让 predecessor 的右指针指向 root，继续遍历左子树
  14.                 if (predecessor.right == null) {
  15.                     predecessor.right = root;
  16.                     root = root.left;
  17.                 }
  18.                 // 说明左子树已经访问完了，我们需要断开链接
  19.                 else {
  20.                     if (pred != null && root.val < pred.val) {
  21.                         y = root;
  22.                         if (x == null) {
  23.                             x = pred;
  24.                         }
  25.                     }
  26.                     pred = root;
  28.                     predecessor.right = null;
  29.                     root = root.right;
  30.                 }
  31.             }
  32.             // 如果没有左孩子，则直接访问右孩子
  33.             else {
  34.                 if (pred != null && root.val < pred.val) {
  35.                     y = root;
  36.                     if (x == null) {
  37.                         x = pred;
  38.                     }
  39.                 }
  40.                 pred = root;
  41.                 root = root.right;
  42.             }
  43.         }
  44.         swap(x, y);
  45.     }
  47.     public void swap(TreeNode x, TreeNode y) {
  48.         int tmp = x.val;
  49.         x.val = y.val;
  50.         y.val = tmp;
  51.     }
  52. }

相同的树

Date：2020-11-24 周二
image.png

递归遍历判断

  1. class Solution {
  2.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         if (p==null || q==null)
  4.            return q==p;
  5.         if (p.val!=q.val)
  6.             return false;
  7.         boolean l = true , r = true;
  8.         if ((p.left==null && q.left !=null)||(p.left!=null && q.left ==null)) return false;
  9.         if (p.left!=null){
  10.             l = isSameTree(p.left,q.left);
  11.         }
  12.         if ((p.right==null && q.right !=null)||(p.right!=null && q.right ==null)) return false;
  13.         if (p.right!=null){
  14.             r = isSameTree(p.right,q.right);
  15.         }
  16.         return l && r;
  17.     }
  18. }

对称二叉树

Date：2020-11-24 周二
image.png

递归

  1. class Solution {
  2.     public boolean judgeLR(TreeNode left , TreeNode right){
  3.         if (left.val!=right.val) return false;
  4.         boolean j1 = true , j2 = true;
  5.         if ((left.right == null && right.left != null) || left.right != null && right.left == null) return false;
  6.         if (left.right!=null){
  7.             j1 = judgeLR(left.right,right.left);
  8.         }
  9.         if ((left.left == null && right.right != null) || left.left != null && right.right == null) return false;
  10.         if (left.left!=null){
  11.             j2 = judgeLR(left.left,right.right);
  12.         }
  13.         return j1 && j2;
  14.     }
  15.     public boolean isSymmetric(TreeNode root) {
  16.         if (root==null) return true;
  17.         if ((root.right == null && root.left != null) || root.right != null && root.left == null) return false;
  18.         if (root.left!=null) return judgeLR(root.left,root.right);
  19.         else return true;
  20.     }
  21. }

迭代**

首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         return check(root, root);
  4.     }
  6.     public boolean check(TreeNode u, TreeNode v) {
  7.         Queue<TreeNode> q = new LinkedList<TreeNode>();
  8.         q.offer(u);
  9.         q.offer(v);
  10.         while (!q.isEmpty()) {
  11.             u = q.poll();
  12.             v = q.poll();
  13.             if (u == null && v == null) {
  14.                 continue;
  15.             }
  16.             if ((u == null || v == null) || (u.val != v.val)) {
  17.                 return false;
  18.             }
  20.             q.offer(u.left);
  21.             q.offer(v.right);
  23.             q.offer(u.right);
  24.             q.offer(v.left);
  25.         }
  26.         return true;
  27.     }
  28. }

image.png

二叉树的层次遍历

Date：2020-11-27 周五
image.png

队列实现

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         Queue<TreeNode> queue = new LinkedList<>();
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         if (root==null) return res;
  6.         int nodes = 1;
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()){
  9.             TreeNode node;
  10.             List<Integer> list = new ArrayList<>();
  11.             int index = nodes;
  12.             nodes = 0;
  13.             for (int i = 0; i < index; i++) {
  14.                 node = queue.poll();
  15.                 list.add(node.val);
  16.                 if (node.left!=null){
  17.                     queue.offer(node.left);
  18.                     nodes++;
  19.                 }
  20.                 if (node.right!=null){
  21.                     queue.offer(node.right);
  22.                     nodes++;
  23.                 }
  24.             }
  25.             res.add(list);
  26.         }
  27.         return res;
  28.     }
  29. }

二叉树的锯齿形层次遍历

Date：2020-11-27 周五
image.png

队列实现

这道题相较上道题之间的区别就是：需要在奇数层将节点值逆序存放，也就只需要在存入节点值的时候进行一下区分即可。

  1. class Solution {
  2.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  3.         Queue<TreeNode> queue = new LinkedList<>();
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         if (root==null) return res;
  6.         int nodes = 1;
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()){
  9.             TreeNode node;
  10.             List<Integer> list = new ArrayList<>();
  11.             int index = nodes;
  12.             nodes = 0;
  13.             for (int i = 0; i < index; i++) {
  14.                 node = queue.poll();
  15.                 if (res.size()%2!=0){ #区分奇偶层进行存储
  16.                     list.add(0,node.val);
  17.                 }else {
  18.                     list.add(node.val);
  19.                 }
  20.                 if (node.left!=null){
  21.                     queue.offer(node.left);
  22.                     nodes++;
  23.                 }
  24.                 if (node.right!=null){
  25.                     queue.offer(node.right);
  26.                     nodes++;
  27.                 }
  28.             }
  30.             res.add(list);
  31.         }
  32.         return res;
  33.     }
  34. }

二叉树的最大深度

Date：2020-11-27 周五
image.png

递归

  1. class Solution {
  2.     public int findDepth(TreeNode root , int height , int maxH){
  3.         if (height + 1 > maxH)
  4.             maxH = height + 1;
  5.         int l = 0 , r = 0;
  6.         if (root.left != null)
  7.             l = findDepth(root.left,height+1,maxH);
  8.         if (root.right != null)
  9.             r = findDepth(root.right,height+1,maxH);
  10.         return Math.max(Math.max(l , r),maxH);
  11.     }
  12.     public int maxDepth(TreeNode root) {
  13.         if (root==null) return 0;
  14.         return findDepth(root,0,0);
  15.     }
  16. }