作者： admin

目标

给定一个包含非负整数的数组 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;
    }
}

性能

目标

电子表格是一个网格，它有 26 列（从 'A' 到 'Z'）和指定数量的 rows。每个单元格可以存储一个 0 到 10^5 之间的整数值。

请你实现一个 Spreadsheet 类：

• Spreadsheet(int rows) 初始化一个具有 26 列（从 'A' 到 'Z'）和指定行数的电子表格。所有单元格最初的值都为 0 。
• void setCell(String cell, int value) 设置指定单元格的值。单元格引用以 "AX" 的格式提供（例如，"A1"，"B10"），其中字母表示列（从 'A' 到 'Z'），数字表示从 1 开始的行号。
• void resetCell(String cell) 重置指定单元格的值为 0 。
• int getValue(String formula) 计算一个公式的值，格式为 "=X+Y"，其中 X 和 Y 要么 是单元格引用，要么非负整数，返回计算的和。

注意： 如果 getValue 引用一个未通过 setCell 明确设置的单元格，则该单元格的值默认为 0 。

示例 1：

输入：
["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"]
[[3], ["=5+7"], ["A1", 10], ["=A1+6"], ["B2", 15], ["=A1+B2"], ["A1"], ["=A1+B2"]]
输出：
[null, 12, null, 16, null, 25, null, 15]
解释
Spreadsheet spreadsheet = new Spreadsheet(3); // 初始化一个具有 3 行和 26 列的电子表格
spreadsheet.getValue("=5+7"); // 返回 12 (5+7)
spreadsheet.setCell("A1", 10); // 设置 A1 为 10
spreadsheet.getValue("=A1+6"); // 返回 16 (10+6)
spreadsheet.setCell("B2", 15); // 设置 B2 为 15
spreadsheet.getValue("=A1+B2"); // 返回 25 (10+15)
spreadsheet.resetCell("A1"); // 重置 A1 为 0
spreadsheet.getValue("=A1+B2"); // 返回 15 (0+15)

说明：

• 1 <= rows <= 10^3
• 0 <= value <= 10^5
• 公式保证采用 "=X+Y" 格式，其中 X 和 Y 要么是有效的单元格引用，要么是小于等于 10^5 的 非负 整数。
• 每个单元格引用由一个大写字母 'A' 到 'Z' 和一个介于 1 和 rows 之间的行号组成。
• 总共 最多会对 setCell、resetCell 和 getValue 调用 10^4 次。

思路

依题意模拟即可。

代码

/**
 * @date 2025-09-19 8:38
 */
public class Spreadsheet {

    private final int[][] data;

    public Spreadsheet(int rows) {
        data = new int[26][rows + 1];
    }

    public void setCell(String cell, int value) {
        int col = cell.charAt(0) - 'A';
        int row = Integer.parseInt(cell.substring(1));
        data[col][row] = value;
    }

    public void resetCell(String cell) {
        int col = cell.charAt(0) - 'A';
        int row = Integer.parseInt(cell.substring(1));
        data[col][row] = 0;
    }

    public int getValue(String formula) {
        String[] params = formula.substring(1).split("\\+");
        int res = 0;
        for (String param : params) {
            if (param.charAt(0) < 'A' || param.charAt(0) > 'Z') {
                res += Integer.parseInt(param);
            } else {
                int col = param.charAt(0) - 'A';
                int row = Integer.parseInt(param.substring(1));
                res += data[col][row];
            }
        }
        return res;
    }
}

性能