代码随想录第四十三天

Posted on 2024-02-07 In 代码随想录

复习

509 斐波那契数

class Solution {
    public int fib(int n) {
        if (n < 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

70 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

746 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n <= 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < n + 1; i++){
            dp[i] = Math.min(dp[i-1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
}

62 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

63 不同路径II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

343 拆分整数

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];

        dp[2] = 1;

        for (int i = 3; i < n + 1; i++){
            for (int j = 1; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

96 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < n + 1; i++){
            for (int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }
}

01背包理论基础二维

int[] weights;
int[] values;

int size;
int len = weights.length;
int[][] dp = new int[len + 1][size + 1];

for (int i = 1; i < len + 1; i++){
    for (int j = 1; j < size + 1; j++){
        if (j < weights[i - 1]){
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
        }
    }
}

return dp[len][size];

动态规划 01背包理论基础（滚动数组）一维

int[] weights;
int[] values;

int size;
int[] dp = new int[size + 1];

for (int i = 0; i < weights.length; i++){
    for (int j = size; j >= weights[i]; j--){
        dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
}

return dp[size];

416 分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length == 0 || nums == null) return false;

        Arrays.sort(nums);

        int sum = 0;
        for (int i : nums){
            sum += i;
        }

        if (sum % 2 != 0) return false;

        int bagSize = sum / 2;

        int[] dp = new int[bagSize + 1];
        for (int i = 0; i < nums.length; i++){
            for (int j = bagSize; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            if (dp[bagSize] == bagSize) return true;
        }

        return dp[bagSize] == bagSize;
    }
}

1049 最后一块石头的重量II

动态规划五步曲：

确定dp数组以及下标的含义
dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
递推公式
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
初始化
遍历顺序

模拟过程
把整个石头分成两堆就是，dp[size] 和 sum-dp[size];
因为sum / 2 是向下取整，所以sum- dp[size] 一定大于 dp[size];

class Solution {
    public int lastStoneWeightII(int[] stones) {
        if (stones.length == 0 || stones == null) return 0;
    
        int sum = 0;

        for (int i: stones){
            sum += i;
        }

        int size = sum / 2;
        int[] dp = new int[size + 1];
        for (int i = 0; i < stones.length; i++){
            for (int j = size; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return (sum - dp[size]) - dp[size];
    }
}

494 目标和

此题转化为01背包问题
假设加法总和为x，减法总和是sum - x
所以要求 x - （sum - x）= target
x = (target + sum) / 2

确定dp数组以及下标的含义
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
确定递推公式
dp[j]，j 为5，

已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有 dp[2]中方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有 dp[1]中方法凑成容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法凑成容量为5的背包
累加dp[j - nums[i]]

组合问题常用递推公式

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        int sum = 0;
        for (int i : nums){
            sum += i;
        }
        if (target < 0 && -target > sum) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int bagSize = (target + sum) / 2;

        if (bagSize < 0) bagSize = -bagSize;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++){
            for (int j = bagSize; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[bagSize];
    }
}

474 一和零

确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推关系
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) return 0;

        int[][] dp = new int[m + 1][n + 1];

        int zeroNum, oneNum;
        for (String str : strs){
            oneNum = 0;
            zeroNum = 0;

            for (char ch : str.toCharArray()){
                if (ch == '0') zeroNum++;
                else oneNum++;
            }

            for (int i = m; i >= zeroNum; i--){
                for (int j = n; j >= oneNum; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

每日一题： 451 Sort Characters By Frequency

利用priority queue，把value排序

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new TreeMap<>();
        char[] chars = s.toCharArray();

        for (char i: chars){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );
        pq.addAll(map.entrySet());

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()){
            Map.Entry<Character, Integer> entry = pq.poll();
            sb.append(String.valueOf(entry.getKey()).repeat(entry.getValue()));
        }

        return new String(sb);
    }
}

代码随想录第四十二天

Posted on 2024-02-05 In 代码随想录

复习

509 斐波那契数

class Solution {
    public int fib(int n) {
        if (n < 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

70 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

746 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n <= 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < n + 1; i++){
            dp[i] = Math.min(dp[i-1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
}

62 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

63 不同路径II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

343 拆分整数

利用 for loop j遍历整个可能

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;

        for (int i = 3; i < n + 1; i++){
            for (int j = 1; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i -j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

96 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < n + 1; i++){
            for (int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }
}

另一种解法：

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n +1];

        dp[0] = 1;

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

01背包理论基础二维

需要掌握01背包，完全背包，再加多重背包

01背包问题：
有n件物品，一个最多能背重量为w的背包，第i件物品的重量为weight[i], 得到的价值是value[i]，每件物品只能用一次，求解怎么装物品价值最大

例子：
0 1 15
1 3 20
2 4 30

利用二维dp数组01背包：

确定dp数组及下标含义
dp[i][j] 表示从下标为[0-i]的物品任意取，放进容器为j的背包，价值总和最大是多少
确定递推公式
有两个方向：
不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
利用物品的冗余层：
判断j和weight[i- 1]此时i比物品编号大一
因为i从1开始
放物品i：由dp[i - 1][j - weight[i - 1]]推出，dp[i - 1][j - weight[i - 1]] 为背包容量为j - weight[i - 1]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i - 1]] + value[i - 1] （物品i的价值），就是背包放物品i得到的最大价值
确定初始化
第一列是0
第一行大于等于1时，都可以放i

import java.util.Arrays;

public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 初始化 dp 数组做了简化(给物品增加冗余维)。这样初始化dp数组，默认全为0即可。
     * dp[i][j] 表示从下标为[0 - i-1]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
     * 其实是模仿背包重量从 0 开始，背包容量 j 为 0 的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。
     * 可选物品也可以从无开始，也就是没有物品可选，即dp[0][j]，这样无论背包容量为多少，背包价值总和一定为 0。
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods + 1][bagSize + 1];  // 给物品增加冗余维，i = 0 表示没有物品可选

        // 初始化dp数组，默认全为0即可
        // 填充dp数组
        for (int i = 1; i <= goods; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i - 1]) {  // i - 1 对应物品 i
                    /**
                     * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i - 1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i - 1]] + value[i - 1]);  // i - 1 对应物品 i
                }
            }
        }

        // 打印dp数组
        for(int[] arr : dp){
            System.out.println(Arrays.toString(arr));
        }
    }
}

简化写法：

int[] weight;
int[] value;

int bagSize;
int items = weight.length;
int[][] dp = int[items + 1][bagSize + 1];
for (int i = 1; i < items + 1; i++){
    for (int j = 1; j < bagSize + 1; j++){
        if (j < weight[i - 1]){
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1);
        }
    }
}

return dp[items][bagSize];

动态规划 01背包理论基础（滚动数组）一维

可以把dp[i-1]那一层拷贝到dp[i]上

动态规划五部：

dp数组的意义
dp[j] 是容量为j的背包，所背的物品的价值最大为dp[j]
一维dp递推公式
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示容量为 j - 物品i重量的背包加上物品i的价值。

此时dp[j]有两个选择：一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值

即dp[j] = Math.max(dp[j], dp[j - weight[i]] +value[i]);

一维数组初始化：
直接所有位置初始为0；
遍历时j要倒序，因为要保证i只被放进一次，从后面倒序，可以保证不会重复使用一个物品，因为dp从0开始

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWight = 4;
    testWeightBagProblem(weight, value, bagWight);
}

public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
    int wLen = weight.length;
    //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    //遍历顺序：先遍历物品，再遍历背包容量
    for (int i = 0; i < wLen; i++){
        for (int j = bagWeight; j >= weight[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    //打印dp数组
    for (int j = 0; j <= bagWeight; j++){
        System.out.print(dp[j] + " ");
    }
}

int[] weight;
int[] value;

int bagSize;
int items = weight.length;
int[] dp = int[bagSize + 1];
for (int i = 0; i < items; i++){
    for (int j = bagSize; j >= weight[i]; j--){
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

return dp[bagSize];

416 分割等和子集

使用01背包：
N件物品放进最多W的背包，计算value，求解value最大的情况

要求解总和sum/2的子集
背包体积：sum / 2
背包放入的物品的重量和价值皆为元素的数值
背包如果正好装满，说明找到了总和为2的子集
背包中每一个元素不可重复放入

5部曲：

dp[j] j的最大value
在本题，dp[j]表示背包总容量是j，放进物品后，背的最大重量是dp[j]
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
初始化：题目如果有负数，非0下标就要初始化为-无穷，此题为0
遍历顺序，j从后向前，i从前向后

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int sum = 0;
        for (int i : nums){
            sum += i;
        }

        int n = nums.length;
        if (sum % 2 != 0) return false;
        int[] dp = new int[sum / 2 + 1];

        for (int i = 0; i < n; i++){
            for (int j = sum/2; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            if (dp[sum/2] == sum/2) return true;
        } 
        return dp[sum/2] == sum/2;
    }
}

每日一题: 49 Group Anagrams


class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String i : strs){
            char[] chars = i.toCharArray();
            Arrays.sort(chars);
            String str = new String(chars);
            if (!map.containsKey(str)){
                map.put(str, new ArrayList<>());
            }
            map.get(str).add(i);
        }

        return new ArrayList<List<String>>(map.values());
    }
}

代码随想录第四十一天

Posted on 2024-02-04 In 代码随想录

复习

509 斐波那契数

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

70 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

746 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;

        if (n <= 1) return 0;
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < n + 1; i++){
            dp[i] = Math.min(dp[i - 1] +cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
}

62 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

63 不同路径II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

343 拆分整数

动态规划5部曲：

dp[i] 表示，拆分i时最大乘积是多少
递推公式
一种是两个数：j 和 i-j 的乘积
另一种两个数以上：j 和 dp[i-j]的乘积
再算上每次对dp[i]的赋值比较
dp初始化
只考虑dp[2] = 1;

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;

        for (int i = 3; i < n + 1; i++){
            for (int j = 1; j <= i - j; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

96 不同的二叉搜索树

dp[i]表示，有多少不同的二叉搜索树
递推公式
以dp[3]为例：
头节点为1
右子树2个元素 * 左子树有0个搜索树
头节点为2
右子树1个 * 左子树1个
头节点为3
右子树0个 * 左子树2个

2个元素 dp[2]
1个元素 dp[1]
0个元素 dp[0]

dp[3] = dp[2]*dp[0] + dp[1]*dp[1] + dp[0] * dp[2];
dp[4] = 30 21 12 03;

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n +1];

        dp[0] = 1;

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

每日一题 387 First Unique Character in a String:

class Solution {
    public int firstUniqChar(String s) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++){
            record[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++){
            if (record[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }

        return -1;
    }
}

每日一题 49 Group Anagrams

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String i :strs){
            char[] chars = i.toCharArray();
            Arrays.sort(chars);

            String str = new String(chars);
            if (!map.containsKey(str)){
                map.put(str, new ArrayList<String>());
            } 
            map.get(str).add(i);
        }

        return new ArrayList<>(map.values());
    }
}

代码随想录第四十天复习

Posted on 2024-02-03 Edited on 2024-02-04 In 代码随想录

动态规划

509 斐波那契数

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[dp.length - 1];
    }
}

70 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i< dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

746 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n <= 1) return 0;
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < dp.length; i++){
            dp[i] = Math.min(dp[i-1] + cost[i - 1], dp[i-2]+cost[i - 2]);
        }

        return dp[n];
    }
}

62 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m-1][n-1];
    }
}

63 不同路径II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }

        for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j-1];
                }
            }
        }

        return dp[m-1][n-1];
    }
}

每日一题： 76 Minimum Window Substring

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (int i = 0; i < t.length(); i++){
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0;
        int right = 0;
        int start = 0;
        int valid = 0;
        int len = Integer.MAX_VALUE;
        while (right < s.length()){
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }

            while(valid == need.size()){
                if (right - left < len){
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
    }
}

代码随想录第三十九天

Posted on 2024-02-02 Edited on 2024-02-03 In 代码随想录

复习

动态规划五部曲

确定dp数组含义
确定递推公式
确定dp数组初始化
确定遍历顺序
推到dp数组，验证

509 斐波那契数

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[dp.length - 1];
    }
}

70 爬楼梯

考虑一步到还是两步到的情况

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2]; 
        }

        return dp[dp.length - 1];
    }
}

746 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length < 2) return 0;
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < dp.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[dp.length - 1];

    }
}

62 不同路径

思考：

dp[m][n] 是每个格子的步数
递推公式：每个格子的路径个数是由此格子的左格子加上格子
初始化：第一行和第一列都是一，即dp[m][0] 和 dp[n][0]都是1
遍历顺序由上到下，由左到右
模拟

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

63 不同路径II

在上面的题上加入obstacle的条件，如果有obstacle就把数量变成0；

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        //如果在起点或终点出现了障碍，直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }

        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
            }
        }
        return dp[m - 1][n - 1];
    }
}

每日一题 1043 Partition Array for Maximum Sum

代码随想录第三十八天

Posted on 2024-02-02 In 代码随想录

贪心总复习

455 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int indexG = 0;
        int indexS = 0;

        int count = 0;

        while (indexS < s.length){
            if (s[indexS] >= g[indexG]){
                indexS++;
                indexG++;
                count++;
            } else {
                indexS++;
            }

            if (indexG > g.length - 1) return count; 
        }
        return count;
    }
}

376 摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int curDiff = 0;
        int preDiff = 0;
        int count = 1;

        for (int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i - 1];
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){
                preDiff = curDiff;
                count++;
            }
        }

        return count;
    }
}

53 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0 || nums == null) return 0;

        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) sum = 0;
        }

        return maxSum;
    }
}

122 买卖股票的最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int profit = 0;
        int curDiff = 0;

        for (int i = 1; i < prices.length; i++){
            curDiff = prices[i] - prices[i - 1];
            if (curDiff > 0){
                profit += curDiff;
            }
        }

        return profit;
    }
}

55 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) return true;

        int maxLen = 0;

        for (int i = 0; i <= maxLen; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return true;
        }

        return false;
    }
}

45 跳跃游戏II

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;

        int maxLen = 0;
        int count = 0;
        int curLen = 0;
        for (int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return ++count;

            if (i == curLen){
                curLen = maxLen;
                count++;
            }
        }

        return count;
    }
}

1005 K次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        if (nums.length == 0 || nums == null) return 0;

        Arrays.sort(nums);
        int minVal = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (minVal > Math.abs(nums[i])){
                minVal = Math.abs(nums[i]);
                index = i;
            }
            if (k > 0 && nums[i] < 0) {
                k--;
                nums[i] = -nums[i];
            }
        }

        if (k % 2 == 1) nums[index] = -nums[index];
        int sum = 0;
        for (int i : nums){
            sum += i;
        }
        return sum;
        
    }
}

134 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curRest = 0;
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++){
            curRest = gas[i] - cost[i];
            curSum += curRest;
            totalSum += curRest;

            if (curSum < 0){
                curSum = 0;
                index = i + 1;
            }
        }

        if (totalSum < 0) return -1;
        
        return index;
    }
}

135 分发糖果

class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int[] candies = new int[ratings.length];

        for (int i = 1; i < ratings.length; i++){
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }

        for (int i = ratings.length - 2; i >= 0; i--){
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) candies[i] = candies[i + 1] + 1; 
        }
        int sum = ratings.length;
        for (int i : candies){
            sum += i;
        }
        return sum;
    }
}

860 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int i : bills){
            if (i == 5) five++;
            else if (i == 10){
                if (five < 1) return false;
                five--;
                ten++;
            }

            else if (i == 20){
                if (ten > 0 && five > 0){
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five = five - 3;
                } else return false;
            }
        }

        return true;
    }
}

406 根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> result = new LinkedList<>();
        for (int[] i : people){
            result.add(i[1], i);
        }

        return result.toArray(new int[result.size()][]);
    }
}

452 用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;
        for (int i = 1; i < points.length; i++){
            if (points[i][0] > points[i - 1][1]) {
                count++;
            } else {
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }

        return count;
    }
}

435 无重叠区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0],b[0]));

        int count = 1;
        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0] >= intervals[i - 1][1]){
                count++;
            } else {
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
            }
        }

        return intervals.length - count;
    }
}

763 划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int[] index = new int[26];
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++){
            index[chars[i] - 'a'] = i; 
        }

        int maxLen = Integer.MIN_VALUE;
        int last = -1;
        for (int i = 0; i < chars.length; i++){
            maxLen = Math.max(maxLen, index[chars[i] - 'a']);

            if (i == maxLen){
                result.add(i - last);
                last = i;
            }
        }

        return result;
    }
}

56 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();
        int[] path = new int[2];
        path = intervals[0];
        for (int i = 1; i < intervals.length; i++){
            if (path[1] >= intervals[i][0]){
                path[1] = Math.max(path[1], intervals[i][1]);
            } else {
                result.add(path);
                path = intervals[i];
            }
        }

        result.add(path);

        return result.toArray(new int[result.size()][]);
    }
}

738 单调递增的数字

更新index时要变成i+1

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int index = chars.length;
        for (int i = chars.length - 2; i >= 0; i--){
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                index = i + 1;
            }
        }

        for (int i = index; i < chars.length; i++){
            chars[i] = '9';
        }

        return Integer.valueOf(String.valueOf(chars));
    }
}

968 监控二叉树

class Solution {
    int result = 0;
    public int minCameraCover(TreeNode root) {
        if (backTraversal(root) == 0) result++;
        return result;
    }

    /*
        0. no cover
        1. have cam
        2. cover
    */  
    private int backTraversal(TreeNode root){
        if (root == null) return 2;

        int left = backTraversal(root.left);
        int right = backTraversal(root.right);

        if (left == 2 && right == 2) {
            return 0;
        }
        else if (left == 0 || right == 0) {
            result++;
            return 1;
        }
        else return 2;
    }
}

动态规划基础理论

一个问题有很多重叠的子问题
动态规划中的每一状态一定是由上一个状态推导出来的

动态规划五步法：

1.
确定dp数组（dp table）以及下标的含义
2.
确定递推公式
3.
dp数组如何初始化
4.
确定遍历顺序
5.
举例推导dp数组

写代码之前一定要把状态转移在dp数组上具体情况模拟一遍

509 斐波那契数

五部曲：

dp[i] 就是第i个数的斐波那契数值
递推公式 dp[i] = dp[i - 1] + dp[i - 2]
dp初始化 dp[0] = 0 dp[1] = 1
遍历顺序，从前往后遍历
0 1 1 2 3 5 8 13 模拟过程

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[dp.length - 1];
    }
}

70 爬楼梯

五部曲：

dp[i] 就是爬到i层楼梯有dp[i]种方法
递推公式
从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，再一步跳一个台阶就是dp[i]。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，再一步跳两个台阶就是dp[i]。
所以dp[i] = dp[i - 1] + dp[i - 2]
即斐波那契数列，只是初始化不一样
dp初始化 dp[1] = 1 dp[2] = 2
遍历顺序，从前往后遍历
0 1 2 3 5 8 13 模拟过程

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[dp.length - 1];
    }
}

746 使用最小花费爬楼梯

五部曲：

dp[i] 就是爬到i层楼梯使用的dp[i]体力就是最小的
递推公式
dp[i] 要么是dp[i - 1] + cost[i - 1]
或者是dp[i-2] + cost[i - 2];
dp初始化 dp[0] = 0 dp[1] = 0
遍历顺序，从前往后遍历
0 1 2 3 5 8 13 模拟过程

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < dp.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[dp.length - 1];
    }
}

每日一题： 1291 Sequential Digits

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i<= 9; i++){
            int num = i;
            int nextDigit = i + 1;
            while (num <= high && nextDigit <= 9){
                num = num * 10 + nextDigit;
                if (low <= num && num <= high){
                    result.add(num);
                }
                nextDigit++;
            }

            
        }

        result.sort(null);
        return result;
    }
}

代码随想录第三十七天

Posted on 2024-01-31 In 代码随想录

复习

455 分发饼干

while loop 判断s的停止
在while loop里面判断g的停止

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int indexS = 0;
        int indexG = 0;
        int count = 0;

        while (indexS < s.length){
            if (s[indexS] >= g[indexG]) {
                indexS++;
                indexG++;
                count++;
            } else {
                indexS++;
            }
            if (indexG == g.length) return count;
        }

        return count;
    }
}

376 摆动序列

确定边界

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return 1;

        int curDiff = 0;
        int preDiff = 0;

        int count = 1;

        for (int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i - 1];

            if ((curDiff < 0 && preDiff >= 0) || (curDiff > 0 && preDiff <= 0)){
                count++;
                preDiff = curDiff;
            }
        }

        return count;
    }
}

53 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i< nums.length; i++){
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) sum = 0;
        }
        return maxSum;
    }
}

122 买卖股票的最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int sum = 0;
        for (int i = 1; i < prices.length; i++){
            int curDiff = prices[i] - prices[i - 1];

            if (curDiff > 0) sum += curDiff;
        }

        return sum;
    }
}

55 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) return true;

        int maxLen = 0;

        for (int i = 0; i <= maxLen; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return true;

            if (i == maxLen && nums[i] == 0) return false;
        }

        return true;
    }
}

45 跳跃游戏II

class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1|| nums == null) return 0;
        int count = 0;
        int maxLen = 0;
        int curLen = 0;

        for (int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return ++count;
            if (i == curLen){
                count++;
                curLen = maxLen;
            }
        }

        return count;
    }
}

1005 K次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int minVal = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (Math.abs(nums[i]) < minVal){
                index = i;
                minVal = Math.abs(nums[i]);
            }
            if (k > 0 && nums[i] < 0){
                k--;
                nums[i] = -nums[i];
            }
        }

        if (k % 2 == 1) nums[index] = -nums[index];
        int sum = 0;

        for (int i : nums){
            sum += i;
        }
        return sum;
    }
}

134 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int index = 0;
        int curSum = 0;
        int totalSum = 0;
        int rest = 0;
        for (int i = 0; i < gas.length; i++){
            rest = gas[i] - cost[i];
            curSum += rest;
            totalSum += rest;

            if (curSum < 0){
                index = i + 1;
                curSum = 0;
            }
        }

        if (totalSum < 0) return -1;
        return index;
    }
}

135 分发糖果

class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;

        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);

        for (int i = 1; i < ratings.length; i++){
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }

        for (int i = ratings.length - 2; i >= 0; i--){
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) candies[i] = candies[i + 1] + 1;
        }

        int sum = 0;

        for (int i : candies){
            sum += i;
        }

        return sum;
    }
}

860 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        
        for (int i : bills){
            if (i == 5) five++;
            else if (i == 10){
                if (five < 1) return false;
                ten++;
                five--;
            } else {
                if (ten > 0 && five > 0){
                    ten--;
                    five--;
                } else if (five > 2){
                    five = five - 3;
                } else return false;
            }
        }

        return true;
    }
}

406 根据身高重建队列

Integer.compare 用法

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> result = new LinkedList<>();
        for (int[] i : people){
            result.add(i[1], i);
        }

        return result.toArray(new int[people.length][]);
    }
}

452 用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;

        for (int i = 1; i< points.length; i++){
            if (points[i][0] > points[i - 1][1]){
                count++;
            } else {
                points[i][1] = Math.min(points[i][1], points[i - 1][1]);
            }
        }

        return count;
    }
}

435 无重叠区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;
        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0] >= intervals[i - 1][1]){
                count++;
            } else {
                intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
            }
        }

        return intervals.length - count;
    }
}

763 划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] index = new int[26];
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++){
            index[chars[i] - 'a'] = i; 
        }
        List<Integer> result = new ArrayList<>();
        int maxLen = 0;
        int k = -1;
        for (int i = 0; i < chars.length; i++){
            maxLen = Math.max(maxLen, index[chars[i] - 'a']);
            if (i == maxLen){
                result.add(i - k); 
                k = i;
            }
        }

        return result;
    }
}

56 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();

        int[] path = new int[2];
        path = intervals[0];

        for (int i = 1; i < intervals.length; i++){
            if (path[1] < intervals[i][0]){
                result.add(path);
                path = intervals[i];
            } else {
                path[1] = Math.max(intervals[i][1], path[1]);
            }
        }
        result.add(path);
        return result.toArray(new int[result.size()][]);
    }
}

738 单调递增的数字

把int 换成 String 再换成char Array

再对比数字，设置start，start之后全是9

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = chars.length;
        for (int i = s.length() - 2; i >= 0; i--){
            if (chars[i] > chars[i + 1]){
                chars[i]--;
                start = i + 1;
            }
        }

        for (int i = start; i < chars.length; i++){
            chars[i] = '9';
        }

        return Integer.parseInt(String.valueOf(new String(chars)));
    }
}

23 监控二叉树

局部最优是：叶子节点的父节点放摄像头
全局最优: 全摄像头使用最少

从低向上遍历利用后序遍历
更新状态：

节点无覆盖
节点有摄像头
节点有覆盖

关系：

左右节点都有覆盖，中间节点就是无覆盖
左右节点至少有一个无覆盖，则中间节点放摄像头
左右节点至少有一个摄像头，则父节点就是覆盖的状态
头节点没有覆盖，则判断是否需要放摄像头

class Solution {
    int result = 0;
    public int minCameraCover(TreeNode root) {
        if (backTraversal(root) == 0){
            result++;
        }

        return result;
    }

    private int backTraversal(TreeNode root){
        if (root == null) return 2;
        int left = backTraversal(root.left);
        int right = backTraversal(root.right);


        if (left == 2 && right == 2) return 0;
        else if(left == 0 || right == 0) {
            result++;
            return 1;
        } else {
            return 2;
        }
    }

}

每日一题 2966 Divide Arrays Into Arrays With Max Difference

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        int size = nums.length;
        if (size % 3 != 0) return new int[0][];
        Arrays.sort(nums);
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i += 3){
            if (i + 2 < size && nums[i + 2] - nums[i] <= k){
                result.add(new int[]{nums[i], nums[i + 1], nums[i + 2]});
            } else {
                return new int[0][];
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

代码随想录第三十六天

Posted on 2024-01-30 In 代码随想录

复习

455 分发饼干

需要判断两个边界问题
一个是有没有足够的人，一个是有没有足够的饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int count = 0;
        int indexG = 0;
        int indexS = 0;

        while (indexS < s.length){
            if (indexG > g.length - 1) return count; 
            if (s[indexS] >= g[indexG]){
                count++;
                indexS++;
                indexG++;
            } else {
                indexS++;
            }
        }
        return count;
    }
}

376 摆动序列

count从1开始

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length <= 1) return nums.length;

        int curDiff = 0;
        int preDiff = 0;
        int count = 1;

        for (int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i - 1];

            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){
                count++;
                preDiff = curDiff;
            }
        }

        return count;
        
    }
}

53 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i: nums){
            sum += i;
            max = Math.max(max, sum);
            if (sum < 0){
                sum = 0;
            }
        }

        return max;
    }
}

122 买卖股票的最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int sum = 0;
        int curDiff = 0;

        for (int i = 1; i < prices.length; i++){
            curDiff = prices[i] - prices[i - 1];
            if (curDiff > 0) sum += curDiff;
        }

        return sum;
    }
}

55 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length <= 1 || nums == null) return true;

        int maxLen = 0;

        for (int i = 0; i <= maxLen; i++){
            maxLen = Math.max(i + nums[i], maxLen);
            if (maxLen >= nums.length - 1) return true;
        }

        return false;
    }
}

45 跳跃游戏II

判断maxLen超过最后的时间返回count

class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1 || nums == null) return 0;

        int maxLen = Integer.MIN_VALUE;
        int count = 0;
        int curLen = 0;

        for (int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return ++count;
            if (i == curLen){
                count++;
                curLen = maxLen;
            }
        }

        return count;


    }
}

1005 K次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);

        int min = Integer.MAX_VALUE;
        int indexMin = 0;
        for (int i  = 0; i < nums.length; i++){
            if (Math.abs(nums[i]) < min) {
                min = Math.abs(nums[i]);
                indexMin = i;
            }

            if (k > 0 && nums[i] < 0){
                k--;
                nums[i] = -nums[i];
            }
        }

        if (k % 2 == 1) nums[indexMin] = -nums[indexMin];
        int sum = 0;
        for (int i : nums){
            sum += i;
        }
        return sum;
    }
}

134 加油站

找到curSum最后一个大于0的值

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;

        for(int i = 0; i < gas.length; i++){
            int rest = gas[i] - cost[i];

            curSum += rest;
            totalSum += rest;

            if (curSum < 0){
                index = i + 1;
                curSum = 0;
            }
        } 

        if (totalSum < 0) return -1;
        return index;

    }
}

135 分发糖果

分前序和倒序，还要判断当前糖果的数量是否满足条件

class Solution {
    public int candy(int[] ratings) {
        if (ratings == null ||ratings.length == 0) return 0;
        int[] candies = new int[ratings.length];
        
        for (int i = 1; i < ratings.length; i++){
            if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) candies[i] = candies[i - 1] + 1;
        }

        for (int i = ratings.length - 2; i >= 0; i--){
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) candies[i] = candies[i + 1] + 1;
        }
        int sum = 0;
        for (int i : candies){
            sum += i + 1;
        }

        return sum;
    }
}

860 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        
        for (int i : bills){
            if (i == 5) five++;
            else if (i == 10){
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (ten > 0 && five > 0){
                    ten--;
                    five--;
                } else if (five >= 3){
                    five = five - 3;
                } else {
                    return false;
                }
            }
        }

        return true;
    }
}

406 根据身高重建队列

a - b 是顺序小到大
b - a 是倒序大到小
或者利用Integer.compare();
利用LinkedList在index插入

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
            return Integer.compare(b[0], a[0]);
        });

        LinkedList<int[]> result = new LinkedList<>();
        for (int[] i : people){
            result.add(i[1], i);
        }

        return result.toArray(new int[people.length][2]);
    }
}

452 用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int count = 1;

        for (int i = 1; i < points.length; i++){
            if (points[i][0] > points[i - 1][1]){
                count++;
            } else {
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }

        return count;
    }
}

435 无重叠区间

气球的题求的是非交叉区间的数量，此题求的是交叉区间数量，就是length - 非交叉区间数量
判断边界时，要注意

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;
        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0] >= intervals[i-1][1]){
                count++;
            } else {
                intervals[i][1] = Math.min(intervals[i-1][1], intervals[i][1]);
            }
        }

        return intervals.length - count;
    }
}

763 划分字母区间

遍历过程中找每个字母的边界，找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。
统计每个字符最后出现的位置

idx表示最远边界，找到最远边界，更新

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new LinkedList<>();

        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;
        }

        int idx = 0;
        int last = -1;

        for (int i = 0; i < chars.length; i++){
            idx = Math.max(idx, edge[chars[i] - 'a']);
            if (i == idx){
                result.add(i - last);
                last = i;
            }
        }

        return result;
    }
}

56 合并区间

利用path合并所需区间


class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0],b[0]));

        List<int[]> result = new LinkedList<>();
        int[] path = new int[2];
        path = intervals[0];
        int count = 1;

        for (int i = 1; i < intervals.length; i++){
            if (intervals[i][0] <= path[1]){
                path[1] = Math.max(intervals[i][1], path[1]);
            } else {
                result.add(path);
                count++;
                path = intervals[i];
            }
        }
        result.add(path);
        return result.toArray(new int[count][]);
    }
}

代码随想录第三十五天

Posted on 2024-01-29 In 代码随想录

860 柠檬水找零

5， 10 的逻辑好想，在20时，需要考虑贪心
即优先10的找零


class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int i = 0; i < bills.length; i++){
            if (bills[i] == 5){
                five++;
            }

            if (bills[i] == 10){
                if (five == 0) return false;
                ten++;
                five--;
            }

            if (bills[i] == 20){
                if (ten > 0){
                    ten--;
                    five--;
                } else {
                    five -= 3;
                }

                if (five < 0) return false;
            }
        }
        return true;
    }
}

406 根据身高重建队列

此题有两个维度，需要权衡两个维度，像是分发糖果：先从前遍历，确定右边，再从后遍历确定左边

此题先利用身高和k排序，身高越高，k越低的在前面之后再利用k值调整顺序

写法：
array.sort写法，第二个值越小排在前面，身高越大排在前面
linkedlist在index处添加的方法

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0]; 
        });

        LinkedList<int[]> que = new LinkedList<>();
        for (int[] p : people){
            que.add(p[1], p);
        }

        return que.toArray(new int[people.length][]);
    }
}

452 用最少数量的箭引爆气球

先排序，之后对比气球，

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a,b) -> Integer.compare(a[0], b[0]));

        int count = 1;
        for (int i = 1; i < points.length; i++){
            if (points[i][0] > points[i-1][1]){
                count++;
            } else {
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }
        
        return count;


    }
}

代码随想录第三十四天

Posted on 2024-01-28 Edited on 2024-01-29 In 代码随想录

复习

455 分发饼干

把最小的饼干分给最小胃口的孩子，对比寻找


class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int indexG = 0;
        int indexS = 0;
        int count = 0;
        while (indexS < s.length){
            if (indexG < g.length){
                if (s[indexS] >= g[indexG]){
                    count++;
                    indexG++;
                }
                indexS++;
            } else {
                return count;
            }        
        }

        return count;
    }
}

376 摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0 || nums == null) return 0;
        if (nums.length == 1) return 1;

        int curDiff = 0;
        int preDiff = 0;
        int count = 1;

        for (int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i - 1];

            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){
                count++;
                preDiff = curDiff;
            }
        }

        return count;

    }
}

53 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0 || nums == null) return 0;
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxSum = Math.max(sum, maxSum);
            if (sum < 0){
                sum = 0;
            }
        }

        return maxSum;
    }
}

122 买卖股票的最佳时机II

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;

        int sum = 0;
        int curDiff = 0;

        for (int i = 1; i < prices.length; i++){
            curDiff = prices[i] - prices[i - 1];
            if (curDiff > 0) sum += curDiff;
        }

        return sum;
    }
}

55 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) return true;

        int maxLen = 0;

        for (int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return true;
            if (i == maxLen && nums[i] == 0) return false;
        }

        return true;
        
    }
}

45 跳跃游戏II

class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1|| nums == null) return 0;

        int count = 0;
        int maxLen = 0;
        int curLen = 0;

        for (int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen, i + nums[i]);

            if (maxLen >= nums.length - 1) return ++count;

            if (i == curLen){
                count++;
                curLen = maxLen;
            }
        }

        return count;
        
    }
}

1005 K次取反后最大化的数组和

贪心思路
把绝对值最大的负数变成正数，之后反复变换最小值

具体解法把数组通过绝对值由大到小排列，之后找到负数把他变成正数，如果K值还剩单数，则变换绝对值最小的数

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();

        for (int i = 0; i < nums.length; i++){
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1){
            nums[nums.length - 1] = -nums[nums.length - 1];
        }

        return Arrays.stream(nums).sum();
    }
}

直接sortArray，如果有负数，负数的绝对值最大的数就会排在前面，变换负数，记录最小的值，在K值剩余的情况反转最小值

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }

            if (Math.abs(nums[i]) < min){
                min = Math.abs(nums[i]);
                index = i;
            }
        }

        if (k % 2 == 1){
            nums[index] = -nums[index];
        }
        int sum = 0;
        for (int i : nums){
            sum += i;
        }
        return sum;
    }
}

134 加油站

暴力解法就是模拟每一个点都是起点，没有就退出

贪心方法一：

如果gas总和小于cost总和，一定不行
利用剩下的油，从0累加到最后一站，没有负数，就是从0出发的
如果累加的最小值是负数，从后向前，看哪个节点能把负数填平

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < gas.length; i++){
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min){
                min = curSum;
            }
        }

        if (curSum < 0) return -1;
        if (min >= 0) return 0;

        for (int i = gas.length - 1; i >= 0; i--){
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) return i;
        }

        return -1;
    }
}

贪心二：

gas总和小于cost总和一定不行
剩下的油如果累加时出现负值，更新index

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int index = 0;
        int sum = 0;
        for (int i = 0; i < gas.length; i++){
            int rest = gas[i] - cost[i];
            curSum += rest;
            sum += rest;
            if (curSum < 0){
                index = i + 1;
                curSum = 0;
            }
        }
        
        if (sum < 0) return -1;
        return index;

    }
}

135 分发糖果

此题要把左右两边分开比较
先确定右边评分大于左边评分的情况
再确定左边评分大于右边评分的情况

class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        if (ratings.length == 1) return 1;
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);

        for (int i = 1; i < ratings.length; i++){
            if (ratings[i] > ratings[i-1]) candies[i] = candies[i - 1] + 1;

        }

        for (int i = ratings.length - 2;i >= 0; i--){
            if (ratings[i] - ratings[i + 1] > 0 && candies[i] <= candies[i + 1]){
                candies[i] = candies[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int i : candies){
            sum += i;
        }
        return sum;
    }
}

复习

509 斐波那契数

70 爬楼梯

746 使用最小花费爬楼梯

62 不同路径

63 不同路径II

343 拆分整数

96 不同的二叉搜索树

01背包理论基础 二维

动态规划 01背包理论基础（滚动数组）一维

416 分割等和子集

1049 最后一块石头的重量II

494 目标和

474 一和零

每日一题： 451 Sort Characters By Frequency

复习

509 斐波那契数

70 爬楼梯

746 使用最小花费爬楼梯

62 不同路径

63 不同路径II

343 拆分整数

96 不同的二叉搜索树

01背包理论基础 二维

动态规划 01背包理论基础（滚动数组）一维

416 分割等和子集

每日一题: 49 Group Anagrams

复习

509 斐波那契数

70 爬楼梯

746 使用最小花费爬楼梯

62 不同路径

63 不同路径II

343 拆分整数

96 不同的二叉搜索树

每日一题 387 First Unique Character in a String:

每日一题 49 Group Anagrams

动态规划

509 斐波那契数

70 爬楼梯

746 使用最小花费爬楼梯

62 不同路径

63 不同路径II

每日一题： 76 Minimum Window Substring

复习

动态规划五部曲

509 斐波那契数

70 爬楼梯

746 使用最小花费爬楼梯

62 不同路径

63 不同路径II

每日一题 1043 Partition Array for Maximum Sum

贪心总复习

455 分发饼干

376 摆动序列

53 最大子序和

122 买卖股票的最佳时机II

55 跳跃游戏

45 跳跃游戏II

1005 K次取反后最大化的数组和

134 加油站

135 分发糖果

860 柠檬水找零

406 根据身高重建队列

452 用最少数量的箭引爆气球

435 无重叠区间

763 划分字母区间

56 合并区间

738 单调递增的数字

968 监控二叉树

动态规划基础理论

509 斐波那契数

70 爬楼梯

746 使用最小花费爬楼梯

每日一题： 1291 Sequential Digits

复习

455 分发饼干

376 摆动序列

53 最大子序和

122 买卖股票的最佳时机II

01背包理论基础二维

01背包理论基础二维