LeetCode力扣刷题

程序 = 数据结构 + 算法

力扣解题思路

23. 合并K个升序链表

• 利用归并(分治法)的思路
• 分是将问题不断分成一些小问题然后递归求解，治是将分的各个阶段结果合并
• 归并算法时间复杂度为nlogn

  class Solution {
      public ListNode mergeKLists(ListNode[] lists) {
          if(lists.length==0) return null;
          return split(lists,0,lists.length-1);
      }
      public ListNode split(ListNode[] lists,int left,int right){
          if(left==right){
              return lists[left];
          }
          int mid = (left+right)/2;
          ListNode l = split(lists,left,mid);
          ListNode r = split(lists,mid+1,right);
          return merge(l,r);
      }
      public ListNode merge(ListNode l1,ListNode l2){
          ListNode dummy = new ListNode(-1);
          ListNode p = dummy;
          while(l1!=null&&l2!=null){
              if(l1.val <= l2.val){
                  p.next = new ListNode(l1.val);
                  l1 = l1.next;
              }else {
                  p.next = new ListNode(l2.val);
                  l2 = l2.next;
              }
              p = p.next;
          }
          p.next = l1 == null? l2:l1;
          return dummy.next;
      }
  }

24.两两交换链表中的节点

• 简单模拟,重点在于定一个哑节点简化操作

  class Solution {
      public ListNode swapPairs(ListNode head) {
          ListNode dummy = new ListNode(-1);
          dummy.next = head;
          ListNode pre = dummy;
          ListNode cur = head;
          while(cur!=null&&cur.next!=null){
              pre.next = cur.next;
              cur.next = pre.next.next;
              pre.next.next = cur;
              pre = cur;
              cur = cur.next;
          }
          return dummy.next;
      }
  }

  25.K个一组翻转链表

• 模拟

• 首先定义哑节点简化操作，然后遍历长度算出需要循环的组数

• 每一组内的翻转都需要三个指针（pre，cur，next）来操作，固定好pre指针，每次翻转都是将next指针移动到pre后面

• 一组内的翻转结束后，重置pre和cur

  class Solution {
      public ListNode reverseKGroup(ListNode head, int k) {
          ListNode dummy = new ListNode(-1);
          dummy.next = head;
  
          ListNode cur = dummy;
          int total = 0;
          while(cur.next!=null){
              total++;
              cur = cur.next;
          }
          
          int groupNum = total / k;
          ListNode pre = dummy;
          cur = head;
          for(int i=0;i<groupNum;i++){
              for(int j=0;j<k-1;j++){
                  ListNode next = cur.next;
                  cur.next = next.next;
                  next.next = pre.next;
                  pre.next = next;
              }
              pre = cur;
              cur = cur.next;
          }
          return dummy.next;
      }
  }

  31.下一个排列

• 从后往前找，用尽可能小的「大数」去交换前面最近的「小数」。具体为从后往前找找到第一个升序对（x1,x2),此时x1<x2,x2后面的数全部为降序，即x2为顶点。此时x1就是要替换的「小数」。再反向从降序组中找到比「小数」大的数即为「大数」。

• 然后将「大数」后面的数全部置为升序。由于置换后降序组仍然会保持降序，所以只需要反转降序组就可以置为升序。

  class Solution {
      public void nextPermutation(int[] nums) {
          int n = nums.length;
          if(n==1) return ;
          for(int i=n-1;i>0;i--){
              //找到第一个升序对(i-1,i)
              if(nums[i]>nums[i-1]){
                  //下标i-1即为「小数」
                  int x1 = nums[i-1];
                  //再反向从降序组中找到比「小数」大的数即为「大数」。
                  for(int j=n-1;j>=i;j--){
                      if(nums[j]>x1){
                          swap(nums,j,i-1);
                          reverse(nums,i,n-1);
                          return;
                      }
                  }
              }
          }
          //如果没找到升序对，说明整体降序，直接翻转为最小值即可。
          reverse(nums,0,n-1);
      }
  }

32.最长有效括号

• 动态规划

• 定义dp[i]为包含下标为i在内的最长有效括号子串的长度。

• 当s[i]为左括号时，dp[i]为0

• 当s[i]为右括号时：

  1. s[i-1]为右括号，则要判断i-s[i-1]-1是否为左括号，如果是则还要加上dp[i-s[i-1]-2],如果不是则为0
  2. s[i-1]为左括号，则加上dp[i-2]

• 要注意下标越界的情况

class Solution {
    public int longestValidParentheses(String s) {
        char cs[] = s.toCharArray();
        int n = cs.length;
        if(n<=1) return 0;
        int max = 0;
        int dp[] = new int[n];
        for(int i=1;i<n;i++){
            if(cs[i]==')'){
                if(cs[i-1]=='('){
                    dp[i] = 2 + (i-2>=0?dp[i-2]:0);
                }else{
                    int left = i-dp[i-1]-1;
                    if(left>=0&&cs[left]=='('){
                        dp[i] = 2 + dp[i-1] + (left-1>=0?dp[left-1]:0);
                    }
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

33.搜索旋转排序数组

• 二分查找，复杂度为logn
• 重点在于判断出左右哪一部分是有序的，然后根据target是不是在有序序列中来区别边界。

  class Solution {
      public int search(int[] nums, int target) {
          int n = nums.length;
          if(n==0) return -1;
          if(n==1) return nums[0]==target?0:-1;
          int l = 0,r = n-1;
          while(l<=r){
              int m =(l+r)/2;
              if(target==nums[m]){
                  return m;
              }
              //左半部分有序
              if(nums[0]<=nums[m]){
                  if(nums[0]<=target&&target<nums[m]){
                      r = m-1;
                  }else{
                      l = m+1;
                  }
              }
              //右半部分有序
              else{
                  if(nums[m]<target&&target<=nums[n-1]){
                      l = m+1;
                  }else{
                      r = m-1;
                  }
              }
          }
          return -1;
      }
  }

  39.组合总数

• 无重复，无限制重复选取
• 利用dfs深度搜索
• 无限制重复选取只需要dfs方法传一个depth，每次遍历都将当前下标i传入进行递归。

public void dfs(int[] candidates,int target,Stack<Integer> path,int depth){
    if(target==0){
        res.add(new ArrayList<>(path));
        return;
    }
    if(target<0) return ;

    for(int i=depth;i<candidates.length;i++){
        path.push(candidates[i]);
        dfs(candidates,target-candidates[i],path,i);
        path.pop();
    }
}

41.缺失的第一个正数

• 循环遍历数组
• 每一个「大于0且小于等于数组长度的数」都要置换到它应在的地方
• 如果置换回来的数也是「大于0且小于等于数组长度的数」则要循环继续置换，并且置换回来的数不能等于原来的数，否则会陷入死循环
• 如果换回来的数不是「大于0且小于等于数组长度的数」则说明该下标对应的数还未遍历到
• 如果两个数置换后正好都处在应该在的位置，则下一次遍历nums[i]-1就是本身，就会停止

  public int firstMissingPositive(int[] nums) {
      int n = nums.length;
      for(int i=0;i<n;i++){
          while(nums[i]>=1&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){
              swap(nums,i,nums[i]-1);
          }
      }
      for(int i=0;i<n;i++){
          if(nums[i]!=i+1){
              return i+1;
          }
      }
      return n+1;
  }

42.接雨水

• 遍历三次数组
• 第一次遍历：从左到右计算往左看能看到的最大柱子高度
• 第二次遍历：从右往左计算往右看能看到的最大柱子高度
• 第三次遍历：每一根柱子上所能累积的水，即当前下标左右所能看到的最大柱子高度中的较小值和当前柱子的高度差。
• 第二次遍历和第三次遍历可同时进行。

  public int trap(int[] height) {
      int n = height.length;
      int[] left = new int[n];
      int[] right = new int[n];
      left[0] = height[0];
      right[n-1] = height[n-1];
      for(int i=1;i<n;i++){
          left[i] = Math.max(left[i-1],height[i]);
      }
      int res = 0;
      for(int i=n-2;i>=0;i--){
          right[i] = Math.max(right[i+1],height[i]);
          res += Math.min(left[i],right[i])-height[i];
      }
      return res;
  }

  48.旋转图像

1. 左上角到右下角的翻转
2. 上下对称翻转

   public void rotate(int[][] matrix) {
       int n = matrix.length;
       int m = matrix[0].length;
       //对角线翻转
       for(int i=0;i<n-1;i++){
           for(int j=0;j<m-1-i;j++){
               int t = matrix[i][j];
               matrix[i][j] = matrix[n-1-j][m-1-i];
               matrix[n-1-j][m-1-i] = t;
           }
       }
       //左右翻转
       for(int i=0;i<n/2;i++){
           for(int j=0;j<m;j++){
               int t = matrix[i][j];
               matrix[i][j] = matrix[n-1-i][j];
               matrix[n-1-i][j] = t;
           }
       }
   }