标签： easy

目标

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
加 1 后得到 4321 + 1 = 4322。
因此，结果应该是 [4,3,2,2]。

示例 3：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

说明：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits 不包含任何前导 0。

思路

数组 digits 表示一个数字，高位在前低位在后，不含前导零，将该数字加一后返回。

由于存在进位，数组长度可能增加 1 位。仔细想想，第一位是 1 后面全是 0。

从后向前遍历，如数字不是 9，将数字加一直接返回，否则，将当前位置零，继续向前进位。如果遍历结束还没有返回，说明数组长度不够，新建数组，将第一位置 1 即可。

代码

/**
 * @date 2024-06-27 0:40
 */
public class PlusOne66 {

    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            int sum = digits[i] + 1;
            if (sum == 10) {
                digits[i] = 0;
            } else {
                digits[i] = sum;
                return digits;
            }
        }
        int[] res = new int[n + 1];
        res[0] = 1;
        return res;
    }

}

性能

目标

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

思路

有一个 m x n 矩阵 grid，按行按列非严格递减，统计其中的负数个数，要求时间复杂度为 O(m + n)。

暴力做法的复杂度为 O(m x n)。根据矩阵有序的性质，如果 grid[i][j] < 0，那么 grid[i + k][j] < 0，对于 i + k 行，只需继续向前判断，累加当前行的负数个数即可。

代码

/**
 * @date 2025-12-30 11:26
 */
public class CountNegatives1351 {

    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int i = 0, j = n - 1;
        int res = 0;
        while (i < m) {
            while (j >= 0 && grid[i][j] < 0) {
                j--;
            }
            res += n - j - 1;
            i++;
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

说明：

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• 输入数据保证可以将包裹中的苹果重新分装到箱子中。

思路

apple[i] 表示第 i 个包裹中苹果的数量，capacity[i] 表示第 i 个箱子的容量，现在需要将包裹中的苹果分装到箱子中，求所需箱子的最小数量。

累加所有苹果的数量，优先选择容量大的箱子装箱，记录箱子个数。

代码

/**
 * @date 2025-12-24 8:44
 */
public class MinimumBoxes3074 {

    public int minimumBoxes(int[] apple, int[] capacity) {
        int sum = 0;
        for (int num : apple) {
            sum += num;
        }
        Arrays.sort(capacity);
        int res = 0;
        for (int i = capacity.length - 1; i >= 0; i--) {
            if (sum <= 0) {
                break;
            }
            sum -= capacity[i];
            res++;
        }
        return res;
    }
}

性能

目标

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：

abc
bce
cae

你需要找出并删除 不是按字典序非严格递增排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按字典序非严格递增排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = ["cba","daf","ghi"]
输出：1
解释：网格示意如下：
  cba
  daf
  ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格示意如下：
  a
  b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：网格示意如下：
  zyx
  wvu
  tsr
所有 3 列都是非升序排列的，所以都要删除。

说明：

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] 由小写英文字母组成

思路

有一个元素长度相同的字符串数组 strs，删掉其中不是非严格递增的列，返回删除的列数。

枚举每一列，判断是否非严格递增。

代码

/**
 * @date 2025-12-21 20:11
 */
public class MinDeletionSize944 {

    public int minDeletionSize(String[] strs) {
        int m = strs[0].length();
        int res = 0;
        for (int i = 0; i < m; i++) {
            char prev = 0;
            for (String str : strs) {
                char cur = str.charAt(i);
                if (cur < prev) {
                    res++;
                    break;
                }
                prev = cur;
            }
        }
        return res;
    }
}

性能

目标

一个 平方和三元组 (a,b,c) 指的是满足 a² + b² = c² 的 整数 三元组 a，b 和 c 。

给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

示例 1：

输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。

示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。

说明：

• 1 <= n <= 250

思路

统计满足 a² + b² = c²，且 1 <= a,b,c <= n 的三元组个数。

暴力枚举 a b，判断平方和是否小于 n²，同时判断开根号之后是否是整数。

代码

/**
 * @date 2025-12-08 8:55
 */
public class CountTriples1925 {

    public int countTriples(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i && i * i + j * j <= n * n; j++) {
                int s = i * i + j * j;
                int k = (int) Math.sqrt(s);
                if (s == k * k){
                    res++;
                }
            }
        }
        return res * 2;
    }

}

性能

目标

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。

示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

说明：

• 0 <= low <= high <= 10^9

思路

返回 low 到 high 之间的奇数数目。

如果数字个数是偶数，返回 (high - low + 1) / 2，否则，取决于 high 是奇数还是偶数，如果是奇数，需要再额外加上 1。

代码

/**
 * @date 2025-12-07 22:22
 */
public class CountOdds1523 {

    public int countOdds(int low, int high) {
        int n = high - low + 1;
        return n / 2 + (n % 2 == 0 ? 0 : high % 2);
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 。

分区 是指将数组按照下标 i （0 <= i < n - 1）划分成两个 非空 子数组，其中：

• 左子数组包含区间 [0, i] 内的所有下标。
• 右子数组包含区间 [i + 1, n - 1] 内的所有下标。

对左子数组和右子数组先求元素 和 再做 差 ，统计并返回差值为 偶数 的 分区 方案数。

示例 1：

输入：nums = [10,10,3,7,6]
输出：4
解释：
共有 4 个满足题意的分区方案：
[10]、[10, 3, 7, 6] 元素和的差值为 10 - 26 = -16 ，是偶数。
[10, 10]、[3, 7, 6] 元素和的差值为 20 - 16 = 4，是偶数。
[10, 10, 3]、[7, 6] 元素和的差值为 23 - 13 = 10，是偶数。
[10, 10, 3, 7]、[6] 元素和的差值为 30 - 6 = 24，是偶数。

示例 2：

输入：nums = [1,2,2]
输出：0
解释：
不存在元素和的差值为偶数的分区方案。

示例 3：

输入：nums = [2,4,6,8]
输出：3
解释：
所有分区方案都满足元素和的差值为偶数。

说明：

• 2 <= n == nums.length <= 100
• 1 <= nums[i] <= 100

思路

将数组 nums 划分为非空的左右两部分，满足左子数组的元素和与右子数组的元素和之差为偶数，返回划分的方案数。

数组所有元素和为 sum，假设左子数组和为 left，那么右子树和为 sum - left，二者之差为 2 * left - sum，只需判断 sum 是否是偶数即可，如果是偶数，有 n - 1 种方案，否则没有满足要求的方案。

代码

/**
 * @date 2025-12-05 9:10
 */
public class CountPartitions3432 {

    public int countPartitions(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % 2 == 0 ? nums.length - 1 : 0;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k。你可以执行以下操作任意次：

• 选择一个下标 i，并将 nums[i] 替换为 nums[i] - 1。

返回使数组元素之和能被 k 整除所需的最小操作次数。

示例 1：

输入： nums = [3,9,7], k = 5
输出： 4
解释：
对 nums[1] = 9 执行 4 次操作。现在 nums = [3, 5, 7]。
数组之和为 15，可以被 5 整除。

示例 2：

输入： nums = [4,1,3], k = 4
输出： 0
解释：
数组之和为 8，已经可以被 4 整除。因此不需要操作。

示例 3：

输入： nums = [3,2], k = 6
输出： 5
解释：
对 nums[0] = 3 执行 3 次操作，对 nums[1] = 2 执行 2 次操作。现在 nums = [0, 0]。
数组之和为 0，可以被 6 整除。

说明：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• 1 <= k <= 100

思路

返回数组元素和模 k 的余数。

代码

/**
 * @date 2025-11-29 21:53
 */
public class MinOperations3512 {

    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % k;
    }
}

性能

目标

给定一个二进制数组 nums ( 索引从0开始 )。

我们将 xi 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。

• 例如，如果 nums =[1,0,1] ，那么 x0 = 1, x1 = 2, 和 x2 = 5。

返回布尔值列表 answer，只有当 xi 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：nums = [0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。

示例 2：

输入：nums = [1,1,1]
输出：[false,false,false]

说明：

• 1 <= nums.length <= 10^5
• nums[i] 仅为 0 或 1

思路

有一个二进制数组 nums，定义 xi 为二进制表示为 子数组 [0, i] 的数字，判断 x0 ~ x_(n-1) 能否被 5 整除。

模拟存在的问题是左移多次会溢出。假设 num = k * 5 + mod，左移 1 位相当于乘以 2，2 * num = k * 10 + 2 * mod，能否被 5 整除只需考虑 2 * mod | nums[i]。

代码

/**
 * @date 2025-11-24 8:52
 */
public class PrefixesDivBy5_1018 {

    public List<Boolean> prefixesDivBy5_v1(int[] nums) {
        List<Boolean> res = new ArrayList<>();
        int mod = 0;
        for (int num : nums) {
            mod = (mod << 1) % 5 + num;
            res.add(mod % 5 == 0);
        }
        return res;
    }

}

性能