39 篇博文 含有标签「数学」

1、题干​

反转 一个整数意味着倒置它的所有位。

• 例如，反转 2021 得到 1202 。反转 12300 得到 321 ，不保留前导零 。

给你一个整数 num ，反转 num 得到 reversed1 ，接着反转 reversed1 得到 reversed2 。如果 reversed2 等于 num ，返回 true ；否则，返回 false 。

示例 1：

输入：num = 526
输出：true
解释：反转 num 得到 625 ，接着反转 625 得到 526 ，等于 num 。

示例 2：

输入：num = 1800
输出：false
解释：反转 num 得到 81 ，接着反转 81 得到 18 ，不等于 num 。 

示例 3：

输入：num = 0
输出：true
解释：反转 num 得到 0 ，接着反转 0 得到 0 ，等于 num 。

提示：

• 0 <= num <= 106

2、思路​

模拟

3、代码​

impl Solution {
    pub fn is_same_after_reversals(num: i32) -> bool {
            return num == 0 || num % 10 != 0;
    }
}

function isSameAfterReversals(num: number): boolean {
    return num === 0 || num % 10 !== 0;
};

4、复杂度​

• 时间复杂度: $O(1)$
• 空间复杂度: $O(1)$

1、题干​

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21。

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40。

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30。

提示：

• 1 <= n <= 10³

2、思路​

模拟

3、代码​

impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        let mut ans: i32 = 0;

        for i in 1..=n {
            if i % 3 == 0 || i % 5 == 0 || i % 7 == 0 {
                ans += i;
            }
        }

        return ans;
    }
}

function sumOfMultiples(n: number): number {
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        if (i % 3 === 0 || i % 5 === 0 || i % 7 === 0) ans += i;
    }
    return ans;
};

4、复杂度​

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

1、题干​

Alice 和 Bob 计划分别去罗马开会。

给你四个字符串 arriveAlice ，leaveAlice ，arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（日期为闭区间），而 Bob 在日期 arriveBob 到 leaveBob 之间在城市里（日期为闭区间）。每个字符串都包含 5 个字符，格式为 "MM-DD" ，对应着一个日期的月和日。

请你返回 Alice和 Bob 同时在罗马的天数。

你可以假设所有日期都在 同一个 自然年，而且 不是 闰年。每个月份的天数分别为：[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 。

示例 1：

输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
输出：3
解释：Alice 从 8 月 15 号到 8 月 18 号在罗马。Bob 从 8 月 16 号到 8 月 19 号在罗马，他们同时在罗马的日期为 8 月 16、17 和 18 号。所以答案为 3 。

示例 2：

输入：arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
输出：0
解释：Alice 和 Bob 没有同时在罗马的日子，所以我们返回 0 。

提示：

• 所有日期的格式均为 "MM-DD" 。
• Alice 和 Bob 的到达日期都 早于或等于 他们的离开日期。
• 题目测试用例所给出的日期均为 非闰年 的有效日期。

2、思路​

先计算交集起止时间，再把日期转化为天数并求差值，具体步骤：

• 前缀和预处理每月天数
• 通过字典序计算交集的起止时间
• 计算起止时间是该年第几天并求差值

3、代码​

function countDaysTogether(s1: string, e1: string, s2: string, e2: string): number {
    const days = [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365];
    const s = s1 <= s2 ? s2 : s1, e = e1 <= e2 ? e1 : e2;
    if (e < s) return 0;

    const d1 = (days[+s.slice(0, 2) - 2] || 0) + +s.slice(3);
    const d2 = (days[+e.slice(0, 2) - 2] || 0) + +e.slice(3);

    return d2 - d1 + 1;
};

4、复杂度​

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

提示：

• 1 <= nums.length, value <= 105
• -109 <= nums[i] <= 109

2、思路​

• 对 nums 所有元素与 value 取模计数，得到数组 ms
• 遍历区间 [0,nums.length)，消费 ms，直到遍历结束 或 ms 中某个余数被消耗完（ms[i % value] < 1） ，此时的下标 i 即所求结果

3、代码​

function findSmallestInteger(nums: number[], value: number): number {
    const ms = new Array(value).fill(0);
    for (const n of nums) {
        const mod = n % value + (n % value < 0 ? value : 0);
        ms[mod]++;
    }

    let ans = 0;
    for (let i = 0; i < nums.length; i++, ans++) {
        const mod = i % value;
        if (ms[mod] < 1) break;
        ms[mod]--;
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。

示例1:

 输入：0.625
 输出："0.101"

示例2:

 输入：0.1
 输出："ERROR"
 提示：0.1无法被二进制准确表示

提示：

• 32位包括输出中的 "0." 这两位。
• 题目保证输入用例的小数位数最多只有 6 位

2、思路1-数学模拟​

将小数 num 倍乘 2，所得结果的整数部分累加到结果字符串，小数部分赋值给 num，循环上述操作直至 32 次或 num 为 0

3、代码​

function printBin(num: number): string {
    let ans = '0.'
    while (num && ans.length <= 32) {
        num = num * 2;
        const k = num % 2 >> 0;
        ans += k;
        num -= k;
    }
    return ans.length > 32 ? 'ERROR' : ans;
};

4、复杂度​

• 时间复杂度： $O(C)$
• 空间复杂度： $O(1)$

5、执行结果​

6、思路2-API​

调用内置API toString 实现

7、代码​

function printBin(num: number): string {
    const ans = num.toString(2);
    return ans.length > 32 ? 'ERROR' : ans;
};

8、执行结果​

1、题干​

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

示例 1：

输入：s1 = "xx", s2 = "yy"
输出：1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

输入：s1 = "xy", s2 = "yx"
输出：2
解释：
交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

输入：s1 = "xx", s2 = "xy"
输出：-1

提示：

• 1 <= s1.length, s2.length <= 1000
• s1.length == s2.length
• s1, s2 只包含 'x' 或 'y'。

2、思路​

出现不同字符需要交换时有两种情况：$\frac{xx}{yy}$、$\frac{xy}{yx}$

• 情况1 $\frac{xx}{yy}$：只用1次对角线交换
• 情况2 $\frac{xy}{yx}$：需要先上下交换再对角线交换，共计2次交换
• 因此尽量将不同字符组合成情况1就能使交换次数最少

具体实现时，分别统计字符串 s1 中需要交换的 x 与 y，记为 dx、dy

• 若 dx + dy 为奇数，则无法使得两个字符串相同，返回 -1
• 若 dx + dy 为偶数，且 dx 也是偶数，那么不同字符可以全部组合成情况1，最小交换次数为 (dx + dy) / 2
• 若 dx + dy 为偶数，dx 是奇数，那么就会出现1组情况2，最小交换次数为 (dx + dy) / 2 + 1

3、代码​

function minimumSwap(s1: string, s2: string): number {
    let dx = 0, dy = 0;
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] !== s2[i]) s1[i] === 'x' ? dx++ : dy++;
    }

    return (dx + dy) % 2 ? -1 : (dx + dy) / 2 + (dx % 2);
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

• p[0] = start
• p[i] 和 p[i+1] 的二进制表示形式只有一位不同
• p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

示例 1：

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

示例 2：

输入：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

提示：

• 1 <= n <= 16
• 0 <= start < 2^n

2、思路1​

没啥思路先尝试暴力枚举，这里用回溯实现。从整数 start 开始枚举下一个可能的整数，用 $2^0$, $2^1$ ... $2^{n-1}$ 分别与 start 做异或运算即可得到，递归重复这个过程得到结果。

3、代码​

function circularPermutation(n: number, start: number): number[] {
    let ans = [], visited = new Set<number>();

    function dfs(i: number) {
        if (ans.length || visited.size > 2 ** n || visited.has(i)) return;

        visited.add(i);
        if (visited.size === 2 ** n) return ans = [...visited];

        for (let b = 0; b < n; b++) {
            dfs(1 << b ^ i);
        }
        
        visited.delete(i);
    }

    return dfs(start), ans;
};

4、执行结果​

5、思路2​

先生成格雷码，再以 start 为起点偏移得到结果

6、代码​

function circularPermutation(n: number, start: number): number[] {
    const ans = [0, 1];

    for (let h = 1; h < n; h++) {
        for (let i = ans.length - 1; i > -1; i--) {
            ans.push(1 << h | ans[i]);
        }
    }

    const i = ans.indexOf(start);
    if (!i) return ans;

    return [...ans.slice(i), ...ans.slice(0, i)];
};

7、复杂度​

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(n)$

8、执行结果​

1、题干​

给你一个函数  f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知，但它是单调递增函数，也就是说：

• f(x, y) < f(x + 1, y)
• f(x, y) < f(x, y + 1)

函数接口定义如下：

interface CustomFunction {
public:
  // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
  int f(int x, int y);
};

你的解决方案将按如下规则进行评判：

• 判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
• 判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
• 判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
• 如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。

示例 1：

输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5

示例 2：

输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5

提示：

• 1 <= function_id <= 9
• 1 <= z <= 100
• 题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
• 在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

题目不难，难的是阅读理解，这题目看了老半天才懂

2、思路1​

暴力枚举加上剪枝优化，效果还不错

3、代码​

function findSolution(customfunction: CustomFunction, z: number): number[][] {
    let ans = [];

    for (let x = 1; x < 1001; x++) {
        if (customfunction.f(x, 1) > z) break;

        for (let y = 1; y < 1001; y++) {
            if (customfunction.f(x, y) === z) ans.push([x, y]);
            else if (customfunction.f(x, y) > z) break;
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

5、执行结果​

6、思路2​

双指针枚举，两个指针相向步进

7、代码​

function findSolution(customfunction: CustomFunction, z: number): number[][] {
    let ans = [];

    for (let x = 1, y = 1000; x < 1001 && y > 0; x++) {
        while (y && customfunction.f(x, y) > z) y--;

        if (y && customfunction.f(x, y) === z) {
            ans.push([x, y]);
            y--;
        }
    }

    return ans;
};

8、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

9、执行结果​

1、题干​

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

提示：

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

2、思路​

这不是我能写出来的题，看了提示才AC

根据提示，要求所有数字的最大公约数是否等于1。想到的思路是：先升序排序 nums 数组，如果存在相邻数字的最大公约数 gi 等于1，或者 gi 与 gcd(nums[0],nums[1]) 的最大公约数等于1，那么 nums 是一个好数组。虽然过了，但无法证明算法正确性

3、代码​

function isGoodArray(nums: number[]): boolean {
    nums.sort((a, b) => a - b);
    const gcd = (a: number, b: number) => a ? gcd(b % a, a) : b;

    const g1 = gcd(nums[0], nums[1] || 0);

    for (let i = 1; i < nums.length; i++) {
        const gi = gcd(nums[i], nums[i + 1]);
        if (gi === 1 || gcd(g1, gi) === 1) return true;
    }

    return g1 === 1;
};

官解根据裴蜀定理推论和证明，严谨很多，代码也不难。整体思路也是求所有数字的最大公约数是否等于1

function isGoodArray(nums: number[]): boolean {
    let d = nums[0];
    const gcd = (a: number, b: number) => a ? gcd(b % a, a) : b;

    for (let i = 0; i < nums.length && d !== 1; i++) {
        d = gcd(d, nums[i]);
    }

    return d === 1;
};

4、复杂度​

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(logn)$

5、执行结果​

1、题干​

给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：

• 0 <= i < j < nums.length
• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

请你返回好下标对的数目。由于结果可能会很大，请将结果对 109 + 7 取余 后返回。

示例 1：

输入：nums = [42,11,1,97]
输出：2
解释：两个坐标对为：
 - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。

示例 2：

输入：nums = [13,10,35,24,76]
输出：4

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

2、思路​

题中的条件转换为 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，转换后简单很多，遍历所有数字计算 nums[i] - rev(nums[i]) 并使用哈希表计数

3、代码​

function countNicePairs(nums: number[]): number {
    const M = 1e9 + 7, map = new Map();

    let ans = 0;
    for (const n of nums) {
        let cn = n, rn = 0;
        while (cn) {
            rn = 10 * rn + (cn % 10);
            cn = (cn / 10) >> 0;
        }

        const c = map.get(n - rn) || 0;
        ans = (ans + c) % M;
        map.set(n - rn, c + 1);
    }

    return ans;
};

可以使用字符串反转数字，代码更简短，但消耗的时间和内存偏多（时间：204 ms，内存：63.5 MB）。

function countNicePairs(nums: number[]): number {
    const M = 1e9 + 7, map = new Map();

    for (const n of nums) {
        const rn = +[...`${n}`].reverse().join('');
        map.set(n - rn, (map.get(n - rn) || 0) + 1);
    }

    return [...map.values()].reduce((a, c) => (a + (c * c - c) / 2) % M, 0);
};

4、复杂度​

• 时间复杂度：$O(n*logm)$，其中 $n$ 为数组长度，$m$ 为数字值
• 空间复杂度：$O(n)$

5、执行结果​