148. 排序链表 代码很复杂

image.png

  • 链表的归并排序

  • 常数空间复杂度需要

    • 自底向上归并
    • for(int i = 1;i<len;i*=2)进行归并

    • now = dummy.next; // 注意：now=head是不对的，因为head在归并之后不一定位于头节点

      1. class Solution {
      2. public ListNode sortList(ListNode head) {
      3.    ListNode dummy = new ListNode(-1);
      4.    ListNode pre = dummy;
      5.    dummy.next = head;
      6.    ListNode now = head;
      7.    int len = 0;
      8.    while(now!=null){
      9.        now=now.next;
      10.        len++;
      11.    }
      13.    // 划分长度
      14.    for(int i = 1; i < len;i*=2) {
      15.        // 初始化第一个位置的节点
      16.        now = dummy.next;  // 注意：now=head是不对的，因为head在归并之后不一定位于头节点
      17.        pre = dummy;
      19.        while(now!=null) {
      20.            ListNode ha = now; // 前一段的最开始
      21.            int n = 1;
      22.            while(n<i) { // 走给定长度的距离
      23.                n++;
      24.                if(now!=null){
      25.                    now = now.next;
      26.                } else {
      27.                    break;
      28.                }
      29.            }
      30.            ListNode hb = null; // 第二段的最开始
      31.            // 第一段的长度>=i,将第一段的最后指向null
      32.            if(now!=null){
      33.                hb = now.next;
      34.                now.next = null;
      35.                now = hb;
      36.            }
      37.            // 划分第二段
      38.            n=1;
      39.            while(n<i) {
      40.                n++;
      41.                if(now!=null){
      42.                    now = now.next;
      43.                }else{
      44.                    break;
      45.                }
      46.            }
      47.            // 下一段的开始
      48.            ListNode next = null;
      49.            if(now!=null){
      50.                next = now.next;
      51.                now.next = null;
      52.                now = next;
      53.            }
      54.            pre.next = merge(ha,hb);
      55.            while(pre.next!=null) {
      56.                pre = pre.next;  // 后面归并的pre，代表下一段的head之前
      57.            }
      58.        }
      59.    }
      60.    return dummy.next;
      61. }
      63. // 二路归并
      64. ListNode merge(ListNode h1,ListNode h2) {
      65.    ListNode dummy = new ListNode(-1);
      66.    ListNode pre = dummy;
      67.    while(h1!=null && h2!=null) {
      68.        if(h1.val<h2.val){
      69.            pre.next = h1;
      70.            h1 = h1.next;
      71.        } else {
      72.            pre.next = h2;
      73.            h2 = h2.next;
      74.        }
      75.        pre = pre.next;
      76.    }
      77.    if(h1!=null) {
      78.        pre.next = h1;
      79.    } else if(h2!=null) {
      80.        pre.next = h2;
      81.    }
      82.    return dummy.next;
      83. }
      84. }

      72. 编辑距离

      image.png

  • 如果A[i]==B[j] ,那么dp[i][j] = dp[i-1][j-1];

  • 如果不等于，那么dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]);

  • 初始状态是填充一个空格，方便初始化

    • word2=” “+word2; word1=” “+word1;

    • image.png

      1. class Solution {
      2. public int minDistance(String word1, String word2) {
      4.    word2=" "+word2;
      5.    word1=" "+word1;
      6.    int len1 = word1.length();
      7.    int len2 = word2.length();
      8.    if(len1==1) return len2-1;
      9.    if(len2==1) return len1-1;
      10.    int[][] dp = new int[len1][len2];
      11.    dp[0][0] = 0; // 空格跟空格相等
      12.    // 空格跟字符的编辑距离就是第二个串长度
      13.    for(int i = 1; i < len1;i++) {
      14.        dp[i][0] = i;
      15.    } 
      16.    for(int i = 1; i < len2;i++) {
      17.        dp[0][i] = i;
      18.    }
      19.    for(int i = 1;i<len1;i++){
      20.        for(int j = 1;j < len2;j++) {
      21.            if(word1.charAt(i)==word2.charAt(j)){
      22.                // 当前字符相等相等
      23.                dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]+1),dp[i-1][j]+1);
      24.            }else {
      25.                // 当前字符不等
      26.                dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]);
      27.            }
      28.        }
      29.    }
      30.    return dp[len1-1][len2-1];
      31. }
      32. }

      10. 正则表达式匹配

      image.png
      image.png

      1. class Solution {
      2. public boolean isMatch(String s, String p) {
      3.    // 填充空格，方便初始化
      4.    s = " "+s;
      5.    p = " "+p;
      6.    int m = s.length();
      7.    int n = p.length();
      8.    boolean[][] dp = new boolean[m][n];
      9.    dp[0][0]=true;
      10.    for(int i = 2; i < n;i+=2) {
      11.        if(p.charAt(i)=='*'){  // a*b*c这样格式的串
      12.            dp[0][i] = true;
      13.        }else{
      14.            break;
      15.        }
      16.    }
      17.    for(int i = 1; i< m ;i++) {
      18.        dp[i][0] = false;
      19.        for(int j = 1; j < n ;j++) {
      20.            if(p.charAt(j)=='*') {
      21.                dp[i][j] = dp[i][j-2] || (dp[i-1][j] && match(s.charAt(i),p.charAt(j-1)));
      22.            } else{
      23.                if(match(s.charAt(i),p.charAt(j))) {
      24.                    dp[i][j] = dp[i-1][j-1];
      25.                }
      26.            }
      27.        }
      28.    }
      29.    // for(int i = 0 ; i < m;i++) {
      30.    //     for(int j = 0; j < n;j++) {
      31.    //         System.out.print(dp[i][j]+" ");
      32.    //     }
      33.    //      System.out.println();
      34.    // }
      35.    return dp[m-1][n-1];
      36. }
      38. boolean match(char a,char b){
      39.    if(b=='.'){
      40.        return true;
      41.    }
      42.    return a==b;
      43. }
      44. }

      32. 最长有效括号

      image.png

  • 统计以当前字符作为结尾的有效括号长度

    • 当前是（，略过
    • 当前是）
      • 如果前一个是（，则dp[i]=dp[i-2]+2
      • 如果前一个是）
        • 得出前一个对应的长度len，判断dp[i-len-1]是不是（
          • 如果是：dp[i] = dp[i-1]+2，
            • 再加上dp[i-len-2] ()(())这样的情况

image.png

  1. class Solution {
  2.     public int longestValidParentheses(String s) {
  3.         char[] ch = s.toCharArray();
  4.         int[] dp = new int[ch.length];
  5.         if(ch.length<=1)
  6.             return 0;
  7.         dp[0] = 0;
  8.         int max = 0;
  9.         for(int i = 1; i < ch.length;i++) {
  10.             if(ch[i]==')'){
  11.                 if(ch[i-1]=='(') { //....()
  12.                     dp[i] = 2;
  13.                     if(i-2>=0) {
  14.                         dp[i] += dp[i-2];
  15.                     }
  16.                 } else { // ....))
  17.                     int len = dp[i-1];
  18.                     if(i-len-1>=0 && ch[i-len-1]=='(') {
  19.                         dp[i] = len +2;
  20.                         if(i-dp[i]>=0) {
  21.                             dp[i] += dp[i-dp[i]];
  22.                         }
  23.                     }
  24.                 }
  25.                 max = Math.max(max,dp[i]);
  26.             }
  27.         }
  28.         // System.out.println(Arrays.toString(dp));
  29.         return max;
  30.     }
  31. }

300. 最长递增子序列

image.png

  • 设置一个数组，pos[i]代表长度为i+1的子序列的末尾的那个最大值

  • image.png

    1. class Solution {
    2.   public int lengthOfLIS(int[] nums) {
    3.       int len = nums.length;
    4.       if(len<=1)
    5.           return len;
    6.       int[] pos = new int[len+1]; // pos[i]存储的是i+1长度的递增子序列中最大的元素位置
    7.       pos[0] = nums[0];
    8.       int usePosLen = 1;
    9.       for(int i = 1;i < len; i++) {
    10.           int p = find(pos,0,usePosLen,nums[i]);
    11.           pos[p] = nums[i];
    12.           if(p==usePosLen)
    13.               usePosLen++;
    14.       }
    15.       return usePosLen;
    16.   }
    18.   // 找大于等于target的第一个数的位置
    19.   int find(int[] pos,int left,int right,int target) {
    20.       while(left<right) {
    21.           int m = left+right>>1;
    22.           if(target>pos[m]) {
    23.               left = m+1;
    24.           } else {
    25.               right=m;
    26.           }
    27.       }
    28.       return left;
    29.   }
    30. }

    88. 合并两个有序数组

    image.png

  • 因为1的长度是足够的，所以在1的最后位置开始往前插入

image.png

  1. class Solution {
  2.     public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.         if(m==0) {
  4.             for(int i = 0 ; i < n;i++) {
  5.                 nums1[i] = nums2[i];
  6.             }
  7.             return;
  8.         } 
  9.         if(n==0)
  10.             return;
  12.         int index1 = m-1;  // num1指针
  13.         int index2 = n-1;  // num2指针
  14.         int index = m+n-1; // 排序后的数组的指针
  15.         while(index1>=0 && index2>=0) {
  16.             if(nums1[index1] > nums2[index2]) {
  17.                 nums1[index] = nums1[index1];
  18.                 index1--; 
  19.             } else{
  20.                 nums1[index] = nums2[index2];
  21.                 index2--;
  22.             }
  23.             index--;
  24.         }
  27.         // 如果数组2还有元素，往后退
  28.         while(index2>=0) {
  29.             nums1[index--] = nums2[index2--];
  30.         }
  31.         // 不需要管数组1有没有元素
  32.         return;
  33.     }
  34. }

41. 缺失的第一个正数

image.png.

  • 参考剑指offer哪一题，可以归位
  • 返回值在[1，len+1]中产生
    • 对于不在这个区间的数字，可以忽略
    • 交换的两个数字不能一样，要不死循环
    • while(nums[i]>=1 && nums[i]<=len && nums[nums[i] - 1] != nums[i])

  • 借鉴：如果给定一个数组且需要给出空间复杂度为1的，可以使用原数组作为hash进行修改

    1. class Solution {
    2.   public int firstMissingPositive(int[] nums) {
    3.       int len = nums.length;
    4.       if(len<=0){
    5.           return 1;
    6.       }
    7.       for(int i = 0 ; i < len;i++) {
    8.           while(nums[i]>=1 && nums[i]<=len && nums[nums[i] - 1] != nums[i]) {
    9.               System.out.println(i);
    10.               int t = nums[nums[i]-1];
    11.               nums[nums[i]-1] = nums[i];
    12.               nums[i] = t;
    13.           }
    14.       }
    15.       for(int i = 0 ; i < len;i++) {
    16.           if(nums[i]!=i+1)
    17.               return i+1;
    18.       }
    19.       return len+1;
    20.   }
    21. }

    440. 字典序的第K小数字

    字节题目3 - 图13
    字节题目3 - 图14
    字节题目3 - 图15
    字节题目3 - 图16

  • count=k 的时候，注意因为之前k—了，所以count=1的时候说明的是这个前缀只有一种长度的，k=1的时候说明的是当前前缀开头的下一个的元素(因为k=0的时候代表的是当前前缀开头的那个元素)

    • 例如:1,10,100；题目给定的k=3
    • 首先cur=1;K—;k=2
      • 代表查找cur=1开头的前缀的下两个元素
    • getcount = 3;代表以1开头的有三个元素
    • 因为count>k(3>2);所以k—;cur*=10;
  1. class Solution {
  2.     public int findKthNumber(int n, int k) {
  3.         long start = 1;
  4.         while(k>0) {
  5.             long count = find(start,n);  // 当前的数量
  6.             if(count>=k) {  // 被当前前缀包围
  7.                 k--; // 减去start占用的数量
  8.                 if(k==0){ 
  9.                     return (int)start;
  10.                 }
  11.                 start*=10; // 比如start=1的时候,如果包含在1前缀里面,那么下一个该比较的就是10了
  12.             } else {
  13.                 k-=count;  // 比如start=10的时候,如果不包含在10前缀里面,那么下一个该比较的就是11了
  14.                 start++;
  15.             }
  16.         }
  17.         return 0;
  18.     }
  20.     // 以start作为前缀的的数字的数量
  21.     long find(long start,int n) {
  22.         long end = start+1;
  23.         long res = 0;
  24.         while(start<=n) {
  25.             res += Math.min(end,n+1)-start;  // n+1是为了对应start=1,n=1这样的情况,end是start开头的前缀的第一个不符合的,n+1应该和end对应
  26.             start *= 10;
  27.             end *= 10;
  28.         }
  29.         return res;
  30.     }
  31. }

198. 打家劫舍

image.png
image.png

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int len = nums.length;
  4.         if(len<=1){
  5.             return nums[len-1];
  6.         }
  7.         int[] dp = new int[len];
  8.         dp[0] = nums[0];
  9.         dp[1] = Math.max(nums[0],nums[1]);
  10.         int max =dp[1];
  11.         for(int i = 2; i < len;i++) {
  12.             dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
  13.             max = Math.max(max,dp[i]);
  14.         }
  15.         return max;
  16.     }
  17. }

213. 打家劫舍 II

image.png
image.png

337. 打家劫舍 III

image.png
image.png

  1. class Solution {
  2.     int max = 0;
  3.     public int rob(TreeNode root) {
  4.         find(root);
  5.         return max;
  6.     }
  8.     // int[0]:包含当前根
  9.     // int[1]:不包含当前根的最大值
  10.     public int[] find(TreeNode root) {
  11.         if(root==null){
  12.             return new int[]{0,0};
  13.         }
  14.         int[] l = find(root.left);
  15.         int[] r = find(root.right);
  16.         // 不包括自己的时候，也可能没有用到自己的直接子树
  17.         int noSelf = Math.max(l[0],l[1])+Math.max(r[0],r[1]);  
  18.         max = Math.max(noSelf,max);
  19.         // 用到自己的时候，一定不能包含自己的子树
  20.         int containSelf = root.val+l[1]+r[1];
  21.         max = Math.max(containSelf,max);
  22.         return new int[]{containSelf,noSelf};
  23.     }
  24. }

79. 单词搜索

image.png

  1. class Solution {
  2.     int m = 0;
  3.     int n = 0;
  4.     public boolean exist(char[][] board, String word) {
  5.         m = board.length;
  6.         n = board[0].length;
  7.         boolean[][] flag = new boolean[m][n];
  8.         for(int i = 0 ; i < m ; i++) {
  9.             for(int j = 0; j < n ;j++) {
  10.                 if(find(board,i,j,word,0,flag)){
  11.                     return true;
  12.                 }
  13.             }
  14.         }
  15.         return false;
  16.     }
  18.     boolean find(char[][] board,int a,int b,String word,int index,boolean[][] flag) {
  19.         if(index==word.length())  // 已经匹配完所有的字符
  20.             return true;
  22.         if(a>=m || b>=n || a<0 || b<0) // 超出棋盘边界
  23.             return false;
  25.         if(flag[a][b]) // 该地方已经被使用
  26.             return false;
  28.         if(board[a][b]==word.charAt(index)){
  29.             flag[a][b]=true;
  30.             // 上 下 左 右
  31.             if( find(board,a-1,b,word,index+1,flag) ||
  32.                 find(board,a+1,b,word,index+1,flag) ||
  33.                 find(board,a,b-1,word,index+1,flag) ||
  34.                 find(board,a,b+1,word,index+1,flag) ){
  35.                 return true;
  36.             }
  37.             flag[a][b]=false;
  38.         }
  39.         return false;
  40.     }
  41. }

78. 子集

image.png
image.png

  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList();
  3.     List<Integer> list = new ArrayList();
  5.     public List<List<Integer>> subsets(int[] nums) {
  6.         dfs(nums,0);
  7.         return res;
  8.     }
  10.     void dfs(int[] nums,int start){
  11.         if(start==nums.length){
  12.             res.add(new ArrayList(list));
  13.             return;
  14.         }
  15.         list.add(nums[start]);
  16.         dfs(nums,start+1);
  17.         list.remove(list.size()-1);
  18.         dfs(nums,start+1);
  19.     }
  20. }

方法2：
使用位运算
image.png

  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> res = new ArrayList();
  4.         List<Integer> list = new ArrayList();
  5.         int len = nums.length;
  6.         for(int i = 0; i < (1<<len);i++) {
  7.             int now = i; // 当前位项
  8.             int index = 0;
  9.             list.clear();
  10.             while(now!=0) {
  11.                 if((now&1)!=0) {
  12.                     list.add(nums[index]);
  13.                 }
  14.                 now>>=1;
  15.                 index++;
  16.             }
  17.             res.add(new ArrayList(list));
  18.         }
  19.         return res;
  20.     }
  21. }

90. 子集 II

image.png

  • 排序

  • 相同元素只有前一个已经使用的时候才能继续使用

    1. class Solution {
    2.   List<List<Integer>> res = new ArrayList();
    3.   List<Integer> list = new ArrayList();
    5.   public List<List<Integer>> subsetsWithDup(int[] nums) {
    6.       Arrays.sort(nums); // 排序，使重复数字连续放置
    7.       boolean[] flag = new boolean[nums.length];
    8.       find(nums,flag,0);
    9.       return res;
    10.   }
    12.   void find(int[] nums,boolean[] flag,int start) {
    13.       if(start==nums.length){
    14.           res.add(new ArrayList(list));
    15.           return;
    16.       }
    17.       // 不能使用当前元素
    18.       if(start>0 && nums[start-1]==nums[start] && !flag[start-1]) {
    19.           find(nums,flag,start+1);
    20.       } else {
    21.           // 可以使用当前元素
    22.           list.add(nums[start]);
    23.           flag[start]=true;
    24.           find(nums,flag,start+1);
    25.           flag[start]=false;
    26.           list.remove(list.size()-1);
    27.           find(nums,flag,start+1);
    28.       }
    29.   }
    30. }

    322. 零钱兑换

    image.png
    image.pngimage.pngimage.pngimage.png
    image.png
    image.png

    1. class Solution {
    2.   public int coinChange(int[] coins, int amount) {
    3.       Arrays.sort(coins);
    4.       int len = coins.length;
    5.       if(amount==0)
    6.           return 0;
    7.       if(len==0 ){
    8.           return -1;
    9.       }
    10.       int[] dp = new int[amount+1];
    11.       Arrays.fill(dp,amount+1);
    12.       dp[0] =0 ;
    13.       for(int i = 1;i<=amount;i++) {
    14.           for(int j = 0 ; j < coins.length;j++) {
    15.               if(coins[j]<=i) {
    16.                   dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
    17.               }
    18.           }
    19.       }
    20.       // System.out.println(Arrays.toString(dp));
    21.       return dp[amount]==amount+1?-1:dp[amount];
    22.   }
    23. }

    518. 零钱兑换 II

    image.png

image.png

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         int[] dp = new int[amount+1];
  4.         dp[0]=1;
  5.         for(int c:coins){
  6.             for(int j=c;j<=amount;j++) {
  7.                 dp[j] += dp[j-c];
  8.             }
  9.         }
  10.         System.out.println(Arrays.toString(dp));
  11.         return dp[amount];
  12.     }
  13. }