标签： 数学

812.最大三角形面积

目标

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10^-5 内的答案将会视为正确答案。

示例 1：

输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：输入中的 5 个点如上图所示，红色的三角形面积最大。

示例 2：

输入：points = [[1,0],[0,0],[0,1]]
输出：0.50000

提示：

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • 给出的所有点 互不相同

思路

暴力解，三层循环，三角形面积可以使用向量的叉积计算。

向量的叉积表示这两个向量构成的平行四边形面积，除以 2 就是三角形的面积。

向量 (x1, y1) 与 (x2, y2) 的叉积等于 |x1 * y2 - x2 * y1|。

代码


/**
 * @date 2025-09-27 21:35
 */
public class LargestTriangleArea812 {

    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double res = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int p1 = points[i][0];
                    int q1 = points[i][1];
                    int p2 = points[j][0];
                    int q2 = points[j][1];
                    int p3 = points[k][0];
                    int q3 = points[k][1];
                    res = Math.max(res, Math.abs((p2 - p1) * (q3 - q1) - (p3 - p1) * (q2 - q1)));
                }
            }
        }
        return res / 2;
    }
}

性能

166.分数到小数

目标

给定两个整数，分别表示分数的分子 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();
    }

}

性能

2197.替换数组中的非互质数

目标

给你一个整数数组 nums 。请你对数组执行下述操作：

  1. 从 nums 中找出 任意 两个 相邻 的 非互质 数。
  2. 如果不存在这样的数，终止 这一过程。
  3. 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
  4. 只要还能找出两个相邻的非互质数就继续 重复 这一过程。

返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

示例 1 ：

输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。

示例 2 ：

输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。

思路

将数组 nums 中相邻的非互质的数用它们的最小公倍数替换，一直重复这一过程，返回最终的数组。

遍历数组，针对每一个 num 判断它与其左侧已处理的最后一个值（即 list 的最后一个元素）是否互质，如果不互质，将 num 替换为它们的最小公倍数，同时删除 list 最后一个元素，重复该过程，直到互质为止，最后将 num 加入 list。

代码


/**
 * @date 2025-09-16 8:45
 */
public class ReplaceNonCoprimes2197 {

    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int a : nums) {
            while (!list.isEmpty()) {
                int b = list.get(list.size() - 1);
                int g = gcd(a, b);
                if (g <= 1) {
                    break;
                }
                a = a / g * b;
                list.remove(list.size() - 1);
            }
            list.add(a);
        }
        return list;
    }

}

性能

3021.Alice和Bob玩鲜花游戏

目标

Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花，Alice 到 Bob 之间顺时针有 x 朵鲜花，逆时针有 y 朵鲜花。

游戏过程如下：

  1. Alice 先行动。
  2. 每一次行动中，当前玩家必须选择顺时针或者逆时针，然后在这个方向上摘一朵鲜花。
  3. 一次行动结束后，如果所有鲜花都被摘完了，那么 当前 玩家抓住对手并赢得游戏的胜利。

给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：

  • 按照上述规则，Alice 必须赢得游戏。
  • Alice 顺时针方向上的鲜花数目 x 必须在区间 [1,n] 之间。
  • Alice 逆时针方向上的鲜花数目 y 必须在区间 [1,m] 之间。

请你返回满足题目描述的数对 (x, y) 的数目。

示例 1：

输入：n = 3, m = 2
输出：3
解释：以下数对满足题目要求：(1,2) ，(3,2) ，(2,1) 。

示例 2：

输入：n = 1, m = 1
输出：0
解释：没有数对满足题目要求。

说明：

1 <= n, m <= 10^5

思路

代码

性能

2348.全0子数组的数目

目标

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

说明：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

思路

返回数组的全 0 子数组个数。

长度为 k 的子数组个数为 (1 + k) * k / 2。可以使用贪心策略，如果当前元素是 0 找到以它为起点的最长连续 0 数组，计算子数组个数。

代码


/**
 * @date 2025-08-19 8:54
 */
public class ZeroFilledSubarray2348 {

    public long zeroFilledSubarray(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int i = 0;
        while (i < n){
            if (nums[i] != 0){
                i++;
                continue;
            }
            int start = i;
            while (i < n && nums[i] == 0){
                i++;
            }
            int cnt = i - start;
            res += (1L + cnt) * cnt / 2;
        }

        return res;
    }
}

性能

342.4的幂

目标

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

说明：

  • -2^31 <= n <= 2^31 - 1

进阶：你能不使用循环或者递归来完成本题吗？

思路

判断一个整数是否是 4 的幂。

参考 231.2的幂。

负数的二进制表示中前导零的个数为 0，而 4 的幂的前导零个数为奇数，恰好排除掉了负数。

代码


/**
 * @date 2025-08-15 8:43
 */
public class IsPowerOfFour342 {

    public boolean isPowerOfFour(int n) {
        return (n & (n - 1)) == 0 && Integer.numberOfLeadingZeros(n) % 2 == 1;
    }

}

性能

1780.判断一个数字是否可以表示成三的幂的和

目标

给你一个整数 n ，如果你可以将 n 表示成若干个 不同的 三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：

输入：n = 21
输出：false

提示：

  • 1 <= n <= 10^7

思路

判断一个整数 n 能否用若干个 不同的 3 的幂之和表示。

直接的想法是使用 dfs 从小到大判断 3 的幂选或者不选。

从数学的角度考虑，如果 n 的三进制表示中包含 2 那么就无法用不同的三的幂之和表示。

代码


/**
 * @date 2025-08-14 9:54
 */
public class CheckPowersOfThree1780 {

    class Solution {
        public boolean checkPowersOfThree(int n) {
            while (n > 0) {
                if (n % 3 == 2) {
                    return false;
                }
                n /= 3;
            }
            return true;
        }
    }

    public boolean checkPowersOfThree(int n) {
        return dfs(1, 0, n);
    }

    public boolean dfs(int d, int num, int n) {
        if (num == n) {
            return true;
        } else if (num > n || d > n) {
            return false;
        }
        return dfs(d * 3, num, n) || dfs(d * 3, num + d, n);
    }

}

性能

3307.找出第K个字符II

目标

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。

现在 Bob 将要求 Alice 按顺序执行 所有 操作：

  • 如果 operations[i] == 0，将 word 的一份 副本追加 到它自身。
  • 如果 operations[i] == 1，将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行所有操作后，返回 word 中第 k 个字符的值。

注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。

示例 1:

输入：k = 5, operations = [0,0,0]
输出："a"
解释：
最初，word == "a"。Alice 按以下方式执行三次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "aa" 附加到 "aa"，word 变为 "aaaa"。
将 "aaaa" 附加到 "aaaa"，word 变为 "aaaaaaaa"。

示例 2:

输入：k = 10, operations = [0,1,0,1]
输出："b"
解释：
最初，word == "a"。Alice 按以下方式执行四次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "bb" 附加到 "aa"，word 变为 "aabb"。
将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。
将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

说明：

  • 1 <= k <= 10^14
  • 1 <= operations.length <= 100
  • operations[i] 可以是 0 或 1。
  • 输入保证在执行所有操作后，word 至少有 k 个字符。

思路

开始的时候有一个字符 a，根据操作数组 operations 执行以下操作：

  • 当 operations[i] == 0 时，将现有的所有字母拼接到当前字符后面。
  • 当 operations[i] == 1 时，将现有的所有字母替换为它在字母表中的下一个字母（z 的下一个字母为 a），拼接到当前字符后面。

返回执行所有操作之后的第 k 个字母。

计算 tail = ceil(log2(k)) 表示操作次数的上界，如果 k <= 1 << tail，说明在左半边无需操作，否则在右半边，需要操作，它是从左半边的第 k - (1 << tail) 个元素转移而来，需要根据 operations[tail] 来确定字母是否变化。按照这个逻辑递归，直到 tail < 0，返回字母 a。

代码


/**
 * @date 2025-07-04 9:19
 */
public class KthCharacter3307 {

    public char kthCharacter(long k, int[] operations) {
        return kthCharacter(k, operations, 63 - Long.numberOfLeadingZeros(k - 1));
    }

    public char kthCharacter(long k, int[] operations, int tail) {
        if (tail < 0) {
            return 'a';
        }
        long p = 1L << tail;
        if (k <= p) {
            return (char) ('a' + ((kthCharacter(k, operations, tail - 1) - 'a') % 26));
        }
        return (char) ('a' + (kthCharacter(k - p, operations, tail - 1) - 'a' + operations[tail]) % 26);
    }

}

性能

2081.k镜像数字的和

目标

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。

  • 比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
  • 相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。

示例 1：

输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2：

输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3：

输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

说明：

  • 2 <= k <= 9
  • 1 <= n <= 30

思路

核心思想：

  1. 首先枚举 10 进制下的镜像数字
  2. 判断这些镜像数字是否是 k 进制下的镜像数字

代码

//todo

性能

3443.K次修改后的最大曼哈顿距离

目标

给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

  • 'N'：向北移动 1 个单位。
  • 'S'：向南移动 1 个单位。
  • 'E'：向东移动 1 个单位。
  • 'W'：向西移动 1 个单位。

初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

示例 1：

输入：s = "NWSE", k = 1
输出：3
解释：
将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
移动操作 位置 (x, y) 曼哈顿距离 最大值
s[0] == 'N' (0, 1) 0 + 1 = 1 1
s[1] == 'W' (-1, 1) 1 + 1 = 2 2
s[2] == 'N' (-1, 2) 1 + 2 = 3 3
s[3] == 'E' (0, 2) 0 + 2 = 2 3
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

示例 2：

输入：s = "NSWWEW", k = 3
输出：6
解释：
将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

说明：

  • 1 <= s.length <= 10^5
  • 0 <= k <= s.length
  • s 仅由 'N'、'S'、'E' 和 'W' 。

思路

从原点 (0, 0) 出发，根据操作序列 s 朝四个方向移动，最多可以修改序列中 k 个方向，求能够到达的距离原点的最大曼哈顿距离。

遍历过程中记录距离变小的次数，每修改一次可以使得最大距离加 2。

网友指出每走一步可能增大的距离最多为 2 * k，但是不能超过往一个方向一直走的情况，即当前走的步数 i + 1。

代码


/**
 * @date 2025-06-20 21:47
 */
public class MaxDistance3443 {

    private static final Map<Character, int[]> MAP = new HashMap<>();

    static {
        MAP.put('N', new int[]{0, 1});
        MAP.put('S', new int[]{0, -1});
        MAP.put('E', new int[]{1, 0});
        MAP.put('W', new int[]{-1, 0});
    }

    public int maxDistance(String s, int k) {
        int res = 0;
        int d = 0;
        int prev = 0;
        int backCnt = 0;
        int[] curPos = new int[]{0, 0};
        char[] move = s.toCharArray();
        for (char dir : move) {
            prev = d;
            int[] delta = MAP.get(dir);
            int dx = delta[0];
            int dy = delta[1];
            curPos[0] += dx;
            curPos[1] += dy;
            d = Math.abs(curPos[0]) + Math.abs(curPos[1]);
            if (prev > d) {
                backCnt++;
            }
            res = Math.max(res, d + Math.min(backCnt, k) * 2);
        }
        return res;
    }
}

性能