Leetcode记录3

这里不对每道题都做记录。

904题， Fruit Into Baskets，中等难度，题目比较难读懂，其实简单来说就是找出数组中长度最大的连续由2种元素构成的子数组，返回这个子数组的长度。HashMap+滑动窗口。

class Solution {
    public int totalFruit(int[] tree) {
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        int res = 0, start = 0; //start为滑动窗口头
        for(int i = 0; i < tree.length; i++) {
            count.put(tree[i], count.getOrDefault(tree[i], 0) + 1); //如果存在key对应的value,则value+1;如果key不存在，则value设为默认值0+1
        while(count.size() > 2) {
            count.put(tree[start], count.get(tree[start]) - 1);
            if(count.get(tree[start]) == 0){
                count.remove(tree[start]);
            }
            start++;
        }
            res = Math.max(res, i - start +1);
        }
        return res;
    }
}

41题，First Missing Positive，找出给出的数组中没有出现的最小正整数。重点是要求时间复杂度O(n)，另外空间复杂度O(1)，那么只能覆盖原有数组

class Solution {
    public int firstMissingPositive(int[] nums) {
        //桶排序的思想
        if(nums==null || nums.length == 0 ) return 1;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= nums.length && nums[i] > 0 && nums[nums[i]-1] != nums[i]){
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
                i--;    //不要忘了这一步
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != i+1)
                return i+1;
        }
        return nums.length+1;    
    }
}

152，Maximum Product Subarray，寻找最大乘积的子数组。DP，保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现，所以到这一位为止的能得到的最大值，可能是由之前的最大值和这个数相乘得到，也可能是最小值和这个数相乘得到的。

class Solution {
    public int maxProduct(int[] nums) {
        int global = nums[0]; //全局最优
        int max = nums[0]; //记录局部最大值
        int min = nums[0]; //记录局部最小值
        for(int i = 1;i < nums.length; i++)  {   //注意从1开始
            // 最大值一定在max*nums[i], min*nums[i]), nums[i]三个数之间
            // 更新max,min
            int maxTemp = Math.max(max * nums[i], min * nums[i]); //Math的max方法只能比较两个数的大小
            int minTemp = Math.min(max * nums[i], min * nums[i]);
            max = Math.max(maxTemp, nums[i]);  
            min = Math.min(minTemp, nums[i]);

            global = Math.max(global, max);
        }
        return global;
    }
}

142，Linked List Cycle II，环形链表。置快指针每次走两步、慢指针每次走一步，当它们相遇时，表示该链表有环。然后再将slow指针指向头结点，slow和fast同时向前走，下一个相遇的点即是入环节点。

图解.png

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          if(head == null || head.next == null) return null;
          ListNode slow = head;
          ListNode fast = head;
          while (fast != null && fast.next != null){
              fast = fast.next.next;
              slow = slow.next;
              if (fast == slow) {
                  fast = head;      //fast指向头，同时变慢
                  while(fast != slow) {
                      fast = fast.next;  
                      slow = slow.next;
                  } 
                  return slow;
              }
          }
          return null;
      }
}

Spiral Matrix，螺旋矩阵，下边给个高票答案。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if(matrix == null || matrix.length == 0) return res;
        int rowBegin = 0;
        int rowEnd = matrix.length - 1;
        int colBegin = 0;
        int colEnd = matrix[0].length - 1;
        while(rowBegin <= rowEnd && colBegin <= colEnd) {
            // Traverse Right
            for(int i = colBegin; i <= colEnd; ++i) {
                res.add(matrix[rowBegin][i]);
            }
            rowBegin++;
            // Traverse Down
            for(int i = rowBegin; i <= rowEnd; ++i) {
                res.add(matrix[i][colEnd]);
            }
            colEnd--;
            // Traverse Left
            if(rowBegin <= rowEnd) {
                for(int i = colEnd; i >= colBegin; i--) {
                    res.add(matrix[rowEnd][i]);
                }
                rowEnd--;
            }
            // Traver Up
            if(colBegin <= colEnd) {
                for(int i = rowEnd; i >= rowBegin; i--) {
                    res.add(matrix[i][colBegin]);
                }
                colBegin++;
            }
        }
        return res;
    }
}

39题，combination Sum，在给出的数中找到和为target的组合，回溯递归

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 组合得到target
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>()；
        dfs(res,temp,target,candidates,0);
        return res;
    }
    private void dfs(List<List<Integer>> res, List<Integer> temp, int target,int[] candidates, int j) {
        if(target == 0) {  //target为0，说明已找到合适的结果,将中间集加入结果集
            res.add(new ArrayList<>(temp));
        }
        for (int i = j; i < candidates.length && target > candidates[i]; i++) {
            temp.add(candidates[i]);
            dfs(res, temp, target - candidates[i], candidates, i);
            temp.remove(temp.size() - 1);
        }
    }
}

关于回溯：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

63题. Unique Paths II，DP

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1){
            return 0;
        } else {
            obstacleGrid[0][0] = 1;   //左上开始计数为1
        }
        // 填充第一列和第一行
        for (int i = 1; i < row; i++) {    // 如果当前块无阻碍且前一块可走到当前块，当前块计数为1
            if (obstacleGrid[i][0] == 0 && obstacleGrid[i-1][0] == 1) {
                obstacleGrid[i][0] = 1;
            }else {
                obstacleGrid[i][0] = 0;
            }
        }
        for (int i = 1; i < col; i++) {
            if (obstacleGrid[0][i] == 0 && obstacleGrid[0][i-1] == 1) {
                obstacleGrid[0][i] = 1;
            }else {
                obstacleGrid[0][i] = 0;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                }else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }
        return obstacleGrid[row-1][col-1];
    }
}

56题，区间合并。这道题目分析之前先了解一下Arrays.sort()之前没见过的用法

package test;
import java.util.Arrays;
import java.util.Comparator;

public class Solution28 {
    public static void main(String[] args) {
        //注意，要想改变默认的排列顺序，不能使用基本类型（int,double, char）
        //而要使用它们对应的类
        Integer[] a = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
        //定义一个自定义类MyComparator的对象
        Comparator cmp = new MyComparator();
        Arrays.sort(a, cmp);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

//Comparator是一个接口，所以这里我们自己定义的类MyComparator要implents该接口
//而不是extends Comparator
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        //如果o1小于o2，我们就返回正值，如果o1大于o2我们就返回负值，
        //这样颠倒一下，就可以实现反向排序了
        if (o1 < o2) {
            return 1;
        } else if (o1 > o2) {
            return -1;
        } else {
            return 0;
        }
    }

}

解法：

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
// 钉钉面试，数组合并
class Solution27 {
    public int[][] merge(int[][] arr) {
        Arrays.parallelSort(arr, Comparator.comparingInt(x -> x[0]));  //lambda表达式，按照数组左端点排序
        //匿名内部类写法
/*        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });*/

        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            if (list.size() == 0 || list.getLast()[1] < arr[i][0]) {
                list.add(arr[i]);//集合为空，或不满足条件，向后新增
            } else {//满足条件，集合最后元素的end=最大值
                list.getLast()[1] = Math.max(list.getLast()[1], arr[i][1]);
            }
        }
        int[][] res = new int[list.size()][2];//生成结果数组
        int index = 0;
        while (!list.isEmpty()) {//遍历集合
            res[index++] = list.removeFirst();//删除集合首元素
        }
        return res;
    }
}

注：转载文章请注明出处，谢谢~