月度归档： 2025 年 9 月

目标

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

1. nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3. 将 newNums 替换 数组 nums 。
4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。

示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。

说明：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

思路

有一个长度为 n 的数组，将 nums[i] 替换为 (nums[i] + nums[i + 1]) % 10，得到一个长度为 n - 1 的数组，反复执行这一过程，最终得到数组的三角和。

定义 dp[i] 表示 [i, n) 的三角和， 状态转移方程为 dp[i] = (dp[i] + dp[i + 1]) % 10。

代码

/**
 * @date 2025-09-30 8:44
 */
public class TriangularSum2221 {

    public int triangularSum(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                nums[j] = (nums[j] + nums[j + 1]) % 10;
            }
        }
        return nums[0];
    }
}

性能

目标

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

说明:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路

有一个非负整数的数组，返回其中可以组成三角形的三元组。

可以先排序，然后使用二重循环，二分查找满足条件的第三边。

代码

/**
 * @date 2025-09-26 8:52
 */
public class TriangleNumber611 {

    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int t = nums[i] + nums[j];
                int index = bs(nums, j, t);
                res += Math.max(0, index - j);
            }
        }
        return res;
    }

    public int bs(int[] nums, int l, int target) {
        int r = nums.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给定一个三角形 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
• -10^4 <= triangle[i][j] <= 10^4

进阶：

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

思路

有一个由多行数字排列组成的三角形，每一行比上一行多一个数字，当前数字可以到达下一行下标相同或者下标 +1 的两个数字，求从第一行到最后一行的路径中数字和的最小值。

定义 dp[i][j] 表示从第 i 行 j 列到达底部的最小路径和。dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row[i][j]。

代码

/**
 * @date 2024-08-06 15:42
 */
public class MinimumTotal120 {

    public int minimumTotal_new(List<List<Integer>> triangle) {
        int n = triangle.size();
        int m = triangle.get(n - 1).size();
        int[] dp = new int[m];
        for (int i = 0; i < m; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            List<Integer> row = triangle.get(i);
            int l = row.size();
            for (int j = 0; j < l; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + row.get(j);
            }
        }
        return dp[0];
    }

}

性能

目标

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 10^4 。

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 4, denominator = 333
输出："0.(012)"

说明：

• -2^31 <= numerator, denominator <= 2^31 - 1
• denominator != 0

思路

有一个分数，分子分母均为整数，以字符串的形式返回小数，如果是循环小数，将循环部分括在括号内。

关键是如何确定从哪里开始循环？记录余数对应的商的下标，如果余数重复出现说明进入了循环节，根据下标来找出循环节。

代码

/**
 * @date 2025-09-24 9:13
 */
public class FractionToDecimal166 {

    public String fractionToDecimal_v1(int numerator, int denominator) {
        long a = numerator;
        long b = denominator;
        if (a % b == 0) {
            return String.valueOf(a / b);
        }
        StringBuilder sb = new StringBuilder();
        if (a * b < 0) {
            sb.append("-");
        }
        a = Math.abs(a);
        b = Math.abs(b);
        long d = a / b;
        sb.append(d);
        long rem = a % b;
        sb.append(".");
        StringBuilder fraction = new StringBuilder();
        Map<Long, Integer> map = new HashMap<>();
        int i = 0;
        while (rem != 0) {
            if (map.get(rem) != null) {
                return sb.append(fraction.substring(0, map.get(rem)))
                        .append("(")
                        .append(fraction.substring(map.get(rem)))
                        .append(")").toString();
            }
            map.put(rem, i);
            rem *= 10;
            if (rem < b) {
                fraction.append(0);
            } else {
                d = rem / b;
                fraction.append(d);
                rem = rem % b;
            }
            i++;
        }
        return sb.append(fraction).toString();
    }

}

性能

目标

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

• 如果 version1 < version2 返回 -1，
• 如果 version1 > version2 返回 1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.2", version2 = "1.10"
输出：-1
解释：
version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。

示例 2：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：
忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。

示例 3：

输入：version1 = "1.0", version2 = "1.0.0.0"
输出：0
解释：
version1 有更少的修订号，每个缺失的修订号按 "0" 处理。

说明：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 '.'
• version1 和 version2 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

思路

比较两个由 . 分隔的版本号，每个由 . 隔开的部分称为修订号，从左到右分别比较对应的修订号，如果修订号缺失可认为是 0。如果 version1 > version2 返回 1，version1 < version2 返回 -1，否则返回 0。

使用 split 函数获取修订号，取二者修订号个数的最大值，初始化修订号为 0，如果修订号没有缺失则解析修订号，如果修订号不相等直接返回比较结果，否则继续比较下一个修订号。

代码

/**
 * @date 2025-09-23 8:49
 */
public class CompareVersion165 {

    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int n = Math.max(v1.length, v2.length);
        for (int i = 0; i < n; i++) {
            int i1 = 0;
            int i2 = 0;
            if (i < v1.length) {
                i1 = Integer.parseInt(v1[i]);
            }
            if (i < v2.length) {
                i2 = Integer.parseInt(v2[i]);
            }
            if (i1 > i2) {
                return 1;
            } else if (i1 < i2) {
                return -1;
            }
        }
        return 0;
    }
}

性能