hot100（5）

41.309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

状态转换更加复杂一些

持有状态、卖出状态、今天卖出状态、冷冻期状态

1.dp数组及下标定义

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

即不持有股票分为两个状态：不是今天操作导致的卖出状态、今天操作导致的卖出状态

2.状态转移方程;

dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] - prices[i] , dp[i-1][3] - prices[i]);

dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][3]);

dp[i][2] = dp[i-1][0] + prices[i];

dp[i][3] = dp[i-1][2];

3.初始化

dp[0][0] = -prices[0];

dp[0][1] = 0;

dp[0][2] = 0;

dp[0][3] = 0;

4.遍历顺序

从前向后遍历

5.举例推导dp数组

public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        for(int i = 1 ; i < prices.length ; i++){
            dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i]));
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);
            dp[i][2] = dp[i-1][0] + prices[i];
            dp[i][3] = dp[i-1][2];
        }
        return Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
    }

42.301. 删除无效的括号 - 力扣（LeetCode）

题目要求找到所有的可能的删除方法，由于涉及到所有的答案而不是一种答案，可以想到需要遍历所有可能，进而思考到字符串回溯的方法。

首先进行预处理，遍历一遍字符串得到需要删除的左括号数量lremove和需要删除的右括号数量rremove。

回溯三部曲：

1.参数：待处理的字符串，lremove, rremove，当前处理到的位置

2.返回值：void

3.层中逻辑：根据lremove 和 rremove，结合当前处理到的位置i进行从i开始的遍历，遍历到可能的位置，则删除该位置的括号，递归调用dfs，并传递对应的lremove和rremove参数
 

判断字符串符合规范的方法：

lremove == 0 && rremove == 0 && isValid(s)

其中isValid判断右括号先出现的数量不会比左括号多。

由于记录的字符串可能存在重复，因此需要对重复的结果进行去重，去重的办法有如下两种：

利用哈希表对最终生成的字符串去重。
我们在每次进行搜索时，如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 "(((())"，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 "((())"，因此我们在尝试搜索时，只需去掉一个左括号进行下一轮搜索，不需要将前四个左括号都尝试一遍。

List<String> res = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        int lremove = 0, rremove = 0;
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == '('){
                lremove++;
            }else if(s.charAt(i) == ')'){
                if(lremove == 0){
                    rremove++;
                }else{
                    lremove--;
                }
            }
        }
        dfs(s,0,lremove,rremove);
        return res;
    }

    public void dfs(String s , int startIndex, int lremove , int rremove){
        if(lremove == 0 && rremove == 0){
            if(isValid(s)){
                res.add(s);
                return ;
            }
        }
        
        for(int i = startIndex ; i < s.length() ; i++){
            if(lremove + rremove > s.length() - i){
                return ;
            }
            if(i != startIndex && s.charAt(i) == s.charAt(i-1)){
                continue;
            }
            if(lremove > 0 && s.charAt(i) == '('){
                dfs(s.substring(startIndex,i) + s.substring(i+1),i,lremove-1,rremove);
            }
            if(rremove > 0 && s.charAt(i) == ')'){
                dfs(s.substring(startIndex,i) + s.substring(i+1),i,lremove,rremove-1);
            }
        }
    }
    public boolean isValid(String s){
        int cnt = 0;
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == '('){
                cnt++;
            }else if(s.charAt(i) == ')'){
                cnt--;
            }
            if(cnt < 0){
                return false;
            }
        }
        return cnt == 0;

    }

43.300. 最长递增子序列 - 力扣（LeetCode）

子序列问题是动态规划解决的经典问题，当前下标i的递增子序列长度，其实和i之前的下标j的子序列长度有关系

用动规五部曲分析：

1.dp[i]的定义

本题中，正确定义dp数组的含义十分重要。

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。

2.状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

3.dp[i]的初始化

每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4.确定遍历顺序

dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

遍历i的循环在外层，遍历j则在内层，代码如下：

for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
    if (dp[i] > result) result = dp[i]; // 取长的子序列
}

5.举例推导dp数组

public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int result = 0;
        for(int i = 1 ; i < nums.length ; i++){
            for(int j = 0 ; j < i ; j++){
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i],dp[j] + 1);
            }
        }
        for (int i : dp) {
            result = Math.max(result,i);
        }
        return result;
    }

44.297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

45.287. 寻找重复数 - 力扣（LeetCode）

方法I 暴力搜索，时间复杂度O(n^2)，时间超限

public int findDuplicate(int[] nums) {
        for(int i = 0 ; i < nums.length-1 ; i++){
            for(int j = i+1 ; j < nums.length ; j++){
                if(nums[i] == nums[j]){
                    return nums[i];
                }
            }
        }
        return 0;
    }

方法II 环形指针II

题解：287. 寻找重复数 - 力扣（LeetCode）

public int findDuplicate(int[] nums) {
        int slow = 0 , fast = 0 ;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int p1 = 0 , p2 = slow;
        while(p1 != p2){
            p1 = nums[p1];
            p2 = nums[p2];
        }
        return p1;
    }

46.283. 移动零 - 力扣（LeetCode）

I移动

public void moveZeroes(int[] nums) {
        int len = nums.length;
        if(nums == null){
            return;
        }
        int j = 0; //j-1是确定的非0数字的下标
        for(int i=0 ; i< len ;i++){
                if(nums[i]!=0){
                    int tmp = nums[i];
                    nums[i]=nums[j];
                    nums[j]=tmp;
                    j++;
                }
        }
    }

II修改

public void moveZeroes(int[] nums) {
        int i = 0,j = 0;
        for(i = 0 ; i < nums.length ; i++){
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        for( ; j < nums.length ; j++){
            nums[j] = 0;
        }
    }

明确两个下标的含义，一个是遍历数组 遍历到当前位置的下标，另一个是确定的非零数字的下标。

47.279. 完全平方数 - 力扣（LeetCode）

完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

1.dp数组下标及含义

dp[j] : 凑成 j 所需要的最小完全平方数个数

2.递推公式

dp[j] = Math.min(dp[j] , dp[j - i*i]);

3.初始化

Arrays.fill(dp,Integer.MAX_VALUE);

dp[0] = 0;

4.递推顺序

从前向后

5.举例推导dp数组

public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0 ; i <= n ; i++){
            for(int j = 1 ; j*j <= i ; j++){
                if(dp[i-j*j]!= Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i] , dp[i-j*j]+1);
                }
            }
        }
        return dp[n];
    }

48.240. 搜索二维矩阵 II - 力扣（LeetCode）

I暴力搜索

时间复杂度O(m*n)

II对每一行进行二分查找

时间复杂度O(m*logn)

public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row,target);
            if(index >= 0){
                return true;
            }
        }
        return false;
    }
    public int search(int[] nums,int target){
        int low = 0 , high = nums.length - 1;
        while(low <= high){
            int mid = (high - low)/2 + low;
            int num = nums[mid];
            if(num == target){
                return mid;
            }else if(num < target){
                low = mid +1;
            }else if(num > target){
                high = mid -1;
            }
        }
        return -1;
    }

III Z字形查找 从右上角开始查找

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0 , y = n-1;
        while(x < m && y >= 0){
            if(matrix[x][y] == target){
                return true;
            }else if(matrix[x][y] > target){
                y--;
            }else{
                x++;
            }
        }
        return false;
    }

时间复杂度O(m+n)

在搜索的过程中，如果我们没有找到 target，那么我们要么将 y 减少 1，要么将 x 增加 1。由于 (x,y) 的初始值分别为 (0,n−1)，因此 y 最多能被减少 n 次，x 最多能被增加 m 次，总搜索次数为 m+n。在这之后，x 和 y 就会超出矩阵的边界。

空间复杂度O(1)

50.239. 滑动窗口最大值 - 力扣（LeetCode）

I暴力搜索 时间超限

时间复杂度O(n*k)

可能会想用一个大顶堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了， 但是问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。

此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

（迎合了滑动窗口 和 求最大值 两个特点）

II单调队列维护可能成为滑动窗口最大值的值

思路解释：代码随想录_滑动窗口最大值

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

单调决定了其可以在线性时间内得到最大值，同时适配push、pop操作在保证单调的同时迎合滑动窗口的需要。

public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length - k + 1;
        int[] res = new int[len];
        MyQueue queue = new MyQueue();
        for(int i = 0 ; i < k; i++){
            queue.add(nums[i]);
        }
        int num = 0;
        res[num++] = queue.peek();
        for(int i = k ; i <nums.length ; i++){
            queue.poll(nums[i-k]);
            queue.add(nums[i]);
            res[num++] = queue.peek();
        }
        return res;
    }
    class MyQueue{
        Deque<Integer> queue = new ArrayDeque<>();
        void add(int val){
            while(!queue.isEmpty() && val > queue.getLast()){
                queue.removeLast();
            }
            queue.add(val);
        }

        void poll(int val){
            if(!queue.isEmpty() && val == queue.peek()){
                queue.poll();
            }
        }
        int peek(){
            return queue.peek();
        }
    }