月度归档： 2021年9月

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

• 0 <= rowIndex <= 33

进阶：

你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

题解

嗯，依旧明显的动态规划问题，滚动数组实现

class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[][] dp = new int[rowIndex+1][rowIndex+1];
        dp[0][0] = 1;
        int row = 1;
        while (row <= rowIndex){
            for (int i = 0; i <= row; i++) {
                dp[row][i] = i==0?1:dp[row-1][i]+dp[row-1][i-1];
            }
            row++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i : dp[rowIndex]) {
            res.add(i);
        }
        return res;
    }
}

之前的参考LeetCode刷题【118】杨辉三角

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

示例 1：

输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

示例 2：

输入：chalk = [3,4,1,2], k = 25
输出：1
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。

提示：

• chalk.length == n
• 1 <= n <= 105
• 1 <= chalk[i] <= 105
• 1 <= k <= 109

题解

9月10日的每日一题，思路很简单

首先需要知道每个人的时候一共花费了多少粉笔，自然就会想到了前缀和。

再接下来就是按照题面一轮结束，再次从头开始，很自然的就是应该拿总数余上一轮结束总共花费的粉笔数量。

余下的余数则必然会在本轮内消耗完毕，那么就是前面的前缀和数组中找到提问到哪个学生的时候会消耗完毕。那么就是下一个学生来换粉笔了。由于前缀和数组是稳定递增的，所以查找这块的话也自然的想到的是二分查找。

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        long [] preSum = new long[chalk.length];
        preSum[0] = chalk[0];
        //前缀和数组构建，表名了一轮循环下来，第n个学生的时候一共消耗了preSum[n]个粉笔
        for (int i = 1; i < chalk.length; i++) {
            preSum[i] = (long)chalk[i] + preSum[i-1];
        }
        //最后一轮需要换粉笔的时候，这一轮开始还剩余chalkLeft支粉笔
        long chalkLeft = k % preSum[preSum.length-1];
        //拿chalkLeft 用二分法到  preSum 中找到 需要换粉笔的那个学生
        int left = 0,right = preSum.length-1;
        while (left < right){
            int mid = left + ( (right - left) >> 1);
            if (preSum[mid] <= chalkLeft){
                //包含等于的情况，用完的学生不处理，由下一个来的学生发现没有粉笔了处理
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

进阶：

• 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

嗯，动态规划，和上一题区别不大LeetCode刷题【256】粉刷房子

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()+1][triangle.size()+1];
        for (int i = triangle.size()-1; i >= 0 ; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

一样的，dp数组因为只依赖前一次的，空间的使用可以重新调整下，使用两个int[triangle.size()+1]的数组来完成即可。

上面的代码是自下而上的遍历过程，其实也可以自上而下来处理，不过相对的代码有点不一样，每一行需要判断索引0的位置的不能取到上一层的索引为-1的位置的值比较，因为索引-1不存在。

另外一个，遍历到最下一层的时候需要在最后一层中再次遍历下，找到这一层的最小值返回。

另一个一个和本题相似度非常高的题目LeetCode刷题【931】下降路径最小和，基本都非常一致

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]
输出: 2

提示:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

嗯题解，依旧是动态规划，以题目中的示例数组为例讨论分析

当只有一栋房子的时候，只需要判断一下，红蓝绿房子对应的最小价格和costs[0]一致为【17,2,17】

当到第二个房子的时候，刷红色房子的话，那么总费用应当是，当第一个房子是刷蓝色，或者绿色的时候较小值加上当前刷红色房子的费用。刷蓝色房子的话，那么总费用是第一个房子刷红色或者绿色的费用的较小值加当前刷蓝色房子的费用，绿色同理。

即

dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];

代码就很明显了，这样

class Solution {
    public int minCost(int[][] costs) {
        int[][] dp = new int[costs.length+1][3];
        int i = 1;
        while (i < dp.length){
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
            dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];
            i++;
        }
        return Math.min(Math.min(dp[dp.length-1][0],dp[dp.length-1][1]),dp[dp.length-1][2]);
    }
}

当然，这里面也是可以空间优化下的，dp[i]上的值只与dp[i-1]相关，可以把这块空间复用起来实现空间优化

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

 示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

提示：

• cost 的长度范围是 [2, 1000]。
• cost[i] 将会是一个整型数据，范围为 [0, 999] 。

题解

类似于上一题，LeetCode刷题【70】爬楼梯，但是中间多了一些判断逻辑，这样就不在是单纯的滚动数组问题了，而是动态规划了。

本题解题逻辑不复杂，直接见代码，相关详情代码注释里有写出来

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //登上第n级或者顶的最小消耗 = min(第n-1级的最小消耗+第n-1级的消耗 , 第n-2级的最小消耗+第n-2级的最小消耗)
        //如此循环下去，直到终止
        int[] dp = new int[cost.length+1];
        //登上第0或者第一个台阶的花费为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[cost.length];
    }
}

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

题解

本周开始滚动数组，动态规划相关专项练习。本题滚动数组的最明显直接的应用，类似于之前的斐波那契数列那题LeetCode刷题【剑指 Offer 10- I】斐波那契数列

当用户在第n级台阶的时候，可以由n-1级往上走一级到达，也可以由n-2级往上走2级到达当前的n级。这两个状态是用户到达n级的时候的前一个状态。所以到达n级的时候应当是到达n-1和n-2级的两种情况的可能数量之和

代码和斐波那契数列几乎一样

class Solution {
    public int climbStairs(int n) {
        if (n<=3){
            return n;
        }
        int [] arr = new int[n+1];
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;
        int i = 4;
        while (i <=n){
            arr[i] = arr[i-1]+arr[i-2];
            i++;
        }
        return arr[n];

    }
}

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

例如:

输入:
[1,2,3]

输出:
2

说明：
只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

题解

以排序后的数组【1,2,3,3,4,5,6,7,8,9】举例

很明显移动的目标值应该是中位数 ，从最外层开始看，这个移动的目标值应该在 最小值1 和 最大值9 之间，因为如果小于1或者大于9必然会更大。而不管这个值是多少，需要移动的次数应该是 n-1 + 9-n 即 1和9之间的距离。

再往内看一层，2和8的话，同样值在2在8之间，这个区间显然在前面的1-9区间之内，需要移动的次数就是 8到2之间的距离，后面依次同理。

而最后到了最内层，4和5的话，需要的值应该在4和5之间都可以（包含4、5，前面的所有都一样包含边界），而这个范围肯定满足前面的所有范围的要求。即移动一次，在4上面或者5上面。而这个值，具体是4或者5都不影响最终的结果的移动次数。

另外一种情况，最后剩下一个数字，这个就更简单了，这个值就是所有位置上的数字需要移动朝向的值，他自己需要移动0次。

代码：

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int i = 0, j = nums.length - 1, ret = 0;
        while (i < j) {
            ret += nums[j--] - nums[i++];
        }
        return ret;
    }
}