LeetCode - 字节题目3 - 《Java》

148. 排序链表代码很复杂

链表的归并排序

常数空间复杂度需要

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

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

class Solution {
public ListNode sortList(ListNode head) {
   ListNode dummy = new ListNode(-1);
   ListNode pre = dummy;
   dummy.next = head;
   ListNode now = head;
   int len = 0;
   while(now!=null){
       now=now.next;
       len++;
   }
   // 划分长度
   for(int i = 1; i < len;i*=2) {
       // 初始化第一个位置的节点
       now = dummy.next;  // 注意：now=head是不对的，因为head在归并之后不一定位于头节点
       pre = dummy;
       while(now!=null) {
           ListNode ha = now; // 前一段的最开始
           int n = 1;
           while(n<i) { // 走给定长度的距离
               n++;
               if(now!=null){
                   now = now.next;
               } else {
                   break;
               }
           }
           ListNode hb = null; // 第二段的最开始
           // 第一段的长度>=i,将第一段的最后指向null
           if(now!=null){
               hb = now.next;
               now.next = null;
               now = hb;
           }
           // 划分第二段
           n=1;
           while(n<i) {
               n++;
               if(now!=null){
                   now = now.next;
               }else{
                   break;
               }
           }
           // 下一段的开始
           ListNode next = null;
           if(now!=null){
               next = now.next;
               now.next = null;
               now = next;
           }
           pre.next = merge(ha,hb);
           while(pre.next!=null) {
               pre = pre.next;  // 后面归并的pre，代表下一段的head之前
           }
       }
   }
   return dummy.next;
}
// 二路归并
ListNode merge(ListNode h1,ListNode h2) {
   ListNode dummy = new ListNode(-1);
   ListNode pre = dummy;
   while(h1!=null && h2!=null) {
       if(h1.val<h2.val){
           pre.next = h1;
           h1 = h1.next;
       } else {
           pre.next = h2;
           h2 = h2.next;
       }
       pre = pre.next;
   }
   if(h1!=null) {
       pre.next = h1;
   } else if(h2!=null) {
       pre.next = h2;
   }
   return dummy.next;
}
}

72. 编辑距离

如果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;

class Solution {
public int minDistance(String word1, String word2) {
   word2=" "+word2;
   word1=" "+word1;
   int len1 = word1.length();
   int len2 = word2.length();
   if(len1==1) return len2-1;
   if(len2==1) return len1-1;
   int[][] dp = new int[len1][len2];
   dp[0][0] = 0; // 空格跟空格相等
   // 空格跟字符的编辑距离就是第二个串长度
   for(int i = 1; i < len1;i++) {
       dp[i][0] = i;
   } 
   for(int i = 1; i < len2;i++) {
       dp[0][i] = i;
   }
   for(int i = 1;i<len1;i++){
       for(int j = 1;j < len2;j++) {
           if(word1.charAt(i)==word2.charAt(j)){
               // 当前字符相等相等
               dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]+1),dp[i-1][j]+1);
           }else {
               // 当前字符不等
               dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]);
           }
       }
   }
   return dp[len1-1][len2-1];
}
}

10. 正则表达式匹配

class Solution {
public boolean isMatch(String s, String p) {
   // 填充空格，方便初始化
   s = " "+s;
   p = " "+p;
   int m = s.length();
   int n = p.length();
   boolean[][] dp = new boolean[m][n];
   dp[0][0]=true;
   for(int i = 2; i < n;i+=2) {
       if(p.charAt(i)=='*'){  // a*b*c这样格式的串
           dp[0][i] = true;
       }else{
           break;
       }
   }
   for(int i = 1; i< m ;i++) {
       dp[i][0] = false;
       for(int j = 1; j < n ;j++) {
           if(p.charAt(j)=='*') {
               dp[i][j] = dp[i][j-2] || (dp[i-1][j] && match(s.charAt(i),p.charAt(j-1)));
           } else{
               if(match(s.charAt(i),p.charAt(j))) {
                   dp[i][j] = dp[i-1][j-1];
               }
           }
       }
   }
   // for(int i = 0 ; i < m;i++) {
   //     for(int j = 0; j < n;j++) {
   //         System.out.print(dp[i][j]+" ");
   //     }
   //      System.out.println();
   // }
   return dp[m-1][n-1];
}
boolean match(char a,char b){
   if(b=='.'){
       return true;
   }
   return a==b;
}
}

32. 最长有效括号

统计以当前字符作为结尾的有效括号长度
- 当前是（，略过
- 当前是）
  - 如果前一个是（，则dp[i]=dp[i-2]+2
  - 如果前一个是）
    - 得出前一个对应的长度len，判断dp[i-len-1]是不是（
      - 如果是：dp[i] = dp[i-1]+2，
        
        再加上dp[i-len-2] ()(())这样的情况

class Solution {
    public int longestValidParentheses(String s) {
        char[] ch = s.toCharArray();
        int[] dp = new int[ch.length];
        if(ch.length<=1)
            return 0;
        dp[0] = 0;
        int max = 0;
        for(int i = 1; i < ch.length;i++) {
            if(ch[i]==')'){
                if(ch[i-1]=='(') { //....()
                    dp[i] = 2;
                    if(i-2>=0) {
                        dp[i] += dp[i-2];
                    }
                } else { // ....))
                    int len = dp[i-1];
                    if(i-len-1>=0 && ch[i-len-1]=='(') {
                        dp[i] = len +2;
                        if(i-dp[i]>=0) {
                            dp[i] += dp[i-dp[i]];
                        }
                    }
                }
                max = Math.max(max,dp[i]);
            }
        }
        // System.out.println(Arrays.toString(dp));
        return max;
    }
}

300. 最长递增子序列

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

class Solution {
  public int lengthOfLIS(int[] nums) {
      int len = nums.length;
      if(len<=1)
          return len;
      int[] pos = new int[len+1]; // pos[i]存储的是i+1长度的递增子序列中最大的元素位置
      pos[0] = nums[0];
      int usePosLen = 1;
      for(int i = 1;i < len; i++) {
          int p = find(pos,0,usePosLen,nums[i]);
          pos[p] = nums[i];
          if(p==usePosLen)
              usePosLen++;
      }
      return usePosLen;
  }
  // 找大于等于target的第一个数的位置
  int find(int[] pos,int left,int right,int target) {
      while(left<right) {
          int m = left+right>>1;
          if(target>pos[m]) {
              left = m+1;
          } else {
              right=m;
          }
      }
      return left;
  }
}

88. 合并两个有序数组

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

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(m==0) {
            for(int i = 0 ; i < n;i++) {
                nums1[i] = nums2[i];
            }
            return;
        } 
        if(n==0)
            return;
        int index1 = m-1;  // num1指针
        int index2 = n-1;  // num2指针
        int index = m+n-1; // 排序后的数组的指针
        while(index1>=0 && index2>=0) {
            if(nums1[index1] > nums2[index2]) {
                nums1[index] = nums1[index1];
                index1--; 
            } else{
                nums1[index] = nums2[index2];
                index2--;
            }
            index--;
        }
        // 如果数组2还有元素，往后退
        while(index2>=0) {
            nums1[index--] = nums2[index2--];
        }
        // 不需要管数组1有没有元素
        return;
    }
}

41. 缺失的第一个正数

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

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

class Solution {
  public int firstMissingPositive(int[] nums) {
      int len = nums.length;
      if(len<=0){
          return 1;
      }
      for(int i = 0 ; i < len;i++) {
          while(nums[i]>=1 && nums[i]<=len && nums[nums[i] - 1] != nums[i]) {
              System.out.println(i);
              int t = nums[nums[i]-1];
              nums[nums[i]-1] = nums[i];
              nums[i] = t;
          }
      }
      for(int i = 0 ; i < len;i++) {
          if(nums[i]!=i+1)
              return i+1;
      }
      return len+1;
  }
}

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;

class Solution {
    public int findKthNumber(int n, int k) {
        long start = 1;
        while(k>0) {
            long count = find(start,n);  // 当前的数量
            if(count>=k) {  // 被当前前缀包围
                k--; // 减去start占用的数量
                if(k==0){ 
                    return (int)start;
                }
                start*=10; // 比如start=1的时候,如果包含在1前缀里面,那么下一个该比较的就是10了
            } else {
                k-=count;  // 比如start=10的时候,如果不包含在10前缀里面,那么下一个该比较的就是11了
                start++;
            }
        }
        return 0;
    }
    // 以start作为前缀的的数字的数量
    long find(long start,int n) {
        long end = start+1;
        long res = 0;
        while(start<=n) {
            res += Math.min(end,n+1)-start;  // n+1是为了对应start=1,n=1这样的情况,end是start开头的前缀的第一个不符合的,n+1应该和end对应
            start *= 10;
            end *= 10;
        }
        return res;
    }
}

198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len<=1){
            return nums[len-1];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        int max =dp[1];
        for(int i = 2; i < len;i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

213. 打家劫舍 II

337. 打家劫舍 III

class Solution {
    int max = 0;
    public int rob(TreeNode root) {
        find(root);
        return max;
    }
    // int[0]:包含当前根
    // int[1]:不包含当前根的最大值
    public int[] find(TreeNode root) {
        if(root==null){
            return new int[]{0,0};
        }
        int[] l = find(root.left);
        int[] r = find(root.right);
        // 不包括自己的时候，也可能没有用到自己的直接子树
        int noSelf = Math.max(l[0],l[1])+Math.max(r[0],r[1]);  
        max = Math.max(noSelf,max);
        // 用到自己的时候，一定不能包含自己的子树
        int containSelf = root.val+l[1]+r[1];
        max = Math.max(containSelf,max);
        return new int[]{containSelf,noSelf};
    }
}

79. 单词搜索

class Solution {
    int m = 0;
    int n = 0;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        boolean[][] flag = new boolean[m][n];
        for(int i = 0 ; i < m ; i++) {
            for(int j = 0; j < n ;j++) {
                if(find(board,i,j,word,0,flag)){
                    return true;
                }
            }
        }
        return false;
    }
    boolean find(char[][] board,int a,int b,String word,int index,boolean[][] flag) {
        if(index==word.length())  // 已经匹配完所有的字符
            return true;
        if(a>=m || b>=n || a<0 || b<0) // 超出棋盘边界
            return false;
        if(flag[a][b]) // 该地方已经被使用
            return false;
        if(board[a][b]==word.charAt(index)){
            flag[a][b]=true;
            // 上 下 左 右
            if( find(board,a-1,b,word,index+1,flag) ||
                find(board,a+1,b,word,index+1,flag) ||
                find(board,a,b-1,word,index+1,flag) ||
                find(board,a,b+1,word,index+1,flag) ){
                return true;
            }
            flag[a][b]=false;
        }
        return false;
    }
}

78. 子集

class Solution {
    List<List<Integer>> res = new ArrayList();
    List<Integer> list = new ArrayList();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return res;
    }
    void dfs(int[] nums,int start){
        if(start==nums.length){
            res.add(new ArrayList(list));
            return;
        }
        list.add(nums[start]);
        dfs(nums,start+1);
        list.remove(list.size()-1);
        dfs(nums,start+1);
    }
}

方法2：
使用位运算

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> list = new ArrayList();
        int len = nums.length;
        for(int i = 0; i < (1<<len);i++) {
            int now = i; // 当前位项
            int index = 0;
            list.clear();
            while(now!=0) {
                if((now&1)!=0) {
                    list.add(nums[index]);
                }
                now>>=1;
                index++;
            }
            res.add(new ArrayList(list));
        }
        return res;
    }
}

90. 子集 II

排序

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

class Solution {
  List<List<Integer>> res = new ArrayList();
  List<Integer> list = new ArrayList();
  public List<List<Integer>> subsetsWithDup(int[] nums) {
      Arrays.sort(nums); // 排序，使重复数字连续放置
      boolean[] flag = new boolean[nums.length];
      find(nums,flag,0);
      return res;
  }
  void find(int[] nums,boolean[] flag,int start) {
      if(start==nums.length){
          res.add(new ArrayList(list));
          return;
      }
      // 不能使用当前元素
      if(start>0 && nums[start-1]==nums[start] && !flag[start-1]) {
          find(nums,flag,start+1);
      } else {
          // 可以使用当前元素
          list.add(nums[start]);
          flag[start]=true;
          find(nums,flag,start+1);
          flag[start]=false;
          list.remove(list.size()-1);
          find(nums,flag,start+1);
      }
  }
}

322. 零钱兑换

class Solution {
  public int coinChange(int[] coins, int amount) {
      Arrays.sort(coins);
      int len = coins.length;
      if(amount==0)
          return 0;
      if(len==0 ){
          return -1;
      }
      int[] dp = new int[amount+1];
      Arrays.fill(dp,amount+1);
      dp[0] =0 ;
      for(int i = 1;i<=amount;i++) {
          for(int j = 0 ; j < coins.length;j++) {
              if(coins[j]<=i) {
                  dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
              }
          }
      }
      // System.out.println(Arrays.toString(dp));
      return dp[amount]==amount+1?-1:dp[amount];
  }
}

518. 零钱兑换 II

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0]=1;
        for(int c:coins){
            for(int j=c;j<=amount;j++) {
                dp[j] += dp[j-c];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount];
    }
}

字节题目3

148. 排序链表 代码很复杂

148. 排序链表代码很复杂