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

1、题干​

给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

• 例如，序列 [4,6,16] 的最大公约数是 2 。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

• 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

示例 2：

输入：nums = [5,15,40,5,6]
输出：7

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 2 * 105

题目太难，看了题解才写出来。

2、思路​

所有最大公约数都处于 $[1,max(nums)]$ 范围内，因此可以枚举该范围内的所有数字 i，判断该数字是否属于 nums 子序列的最大公约数。

具体判断时对 i 倍乘，若倍乘的数同时属于 nums 则求其最大公约数 g，g === i 则结果累加1。

3、代码​

function countDifferentSubsequenceGCDs(nums: number[]): number {
    let max = 0;
    for (const n of nums) max = n > max ? n : max;

    const set = new Array(max + 1);
    for (const n of nums) set[n] = 1;

    const gcd = (x: number, y: number) => y ? gcd(y, x % y) : x;

    let ans = 0;
    for (let i = 1; i <= max; i++) {
        if (set[i]) {
            ans++;
            continue;
        }

        let g = 0;
        for (let j = 2 * i; j <= max && g !== i; j += i) {
            if (set[j]) g = gcd(j, g);
        }

        if (g === i) ans++;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个偶数 n​​​​​​ ，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i​（下标 从 0 开始 计数）。

一步操作中，你将创建一个新数组 arr ，对于每个 i ：

• 如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
• 如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]

然后将 arr​​ 赋值​​给 perm 。

要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。

示例 1：

输入：n = 2
输出：1
解释：最初，perm = [0,1]
第 1 步操作后，perm = [0,1]
所以，仅需执行 1 步操作

示例 2：

输入：n = 4
输出：2
解释：最初，perm = [0,1,2,3]
第 1 步操作后，perm = [0,2,1,3]
第 2 步操作后，perm = [0,1,2,3]
所以，仅需执行 2 步操作

示例 3：

输入：n = 6
输出：4

提示：

• 2 <= n <= 1000
• n​​​​​​ 是一个偶数

2、思路1​

根据题意模拟

3、代码​

function reinitializePermutation(n: number): number {
    let perm = new Array(n).fill(0).map((v, i) => i);

    for (let ans = 1; ans; ans++) {
        let valid = true, arr = new Array(n).fill(0);

        for (let i = 0; i < n; i++) {
            if (i % 2 === 0) arr[i] = perm[i / 2];
            else arr[i] = perm[n / 2 + (i - 1) / 2];

            if (arr[i] !== i) valid = false;
        }
        
        perm = arr;
        if (valid) return ans;
    }

    return -1;
};

4、复杂度​

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

5、执行结果​

6、思路2​

数据量不大，不打表可惜了

7、代码​

function reinitializePermutation(n: number): number {
    const nums = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28, 42, 148, 15, 24, 20, 52, 52, 33, 162, 20, 83, 156, 18, 172, 60, 58, 178, 180, 60, 36, 40, 18, 95, 96, 12, 196, 99, 66, 84, 20, 66, 90, 210, 70, 28, 15, 18, 24, 37, 60, 226, 76, 30, 29, 92, 78, 119, 24, 162, 84, 36, 82, 50, 110, 8, 16, 36, 84, 131, 52, 22, 268, 135, 12, 20, 92, 30, 70, 94, 36, 60, 136, 48, 292, 116, 90, 132, 42, 100, 60, 102, 102, 155, 156, 12, 316, 140, 106, 72, 60, 36, 69, 30, 36, 132, 21, 28, 10, 147, 44, 346, 348, 36, 88, 140, 24, 179, 342, 110, 36, 183, 60, 156, 372, 100, 84, 378, 14, 191, 60, 42, 388, 88, 130, 156, 44, 18, 200, 60, 108, 180, 204, 68, 174, 164, 138, 418, 420, 138, 40, 60, 60, 43, 72, 28, 198, 73, 42, 442, 44, 148, 224, 20, 30, 12, 76, 72, 460, 231, 20, 466, 66, 52, 70, 180, 156, 239, 36, 66, 48, 243, 162, 490, 56, 60, 105, 166, 166, 251, 100, 156, 508, 9, 18, 204, 230, 172, 260, 522, 60, 40, 253, 174, 60, 212, 178, 210, 540, 180, 36, 546, 60, 252, 39, 36, 556, 84, 40, 562, 28, 54, 284, 114, 190, 220, 144, 96, 246, 260, 12, 586, 90, 196, 148, 24, 198, 299, 25, 66, 220, 303, 84, 276, 612, 20, 154, 618, 198, 33, 500, 90, 72, 45, 210, 28, 84, 210, 64, 214, 28, 323, 290, 30, 652, 260, 18, 658, 660, 24, 36, 308, 74, 60, 48, 180, 676, 48, 226, 22, 68, 76, 156, 230, 30, 276, 40, 58, 700, 36, 92, 300, 708, 78, 55, 60, 238, 359, 51, 24, 140, 121, 486, 56, 244, 84, 330, 246, 36, 371, 148, 246, 318, 375, 50, 60, 756, 110, 380, 36, 24, 348, 384, 16, 772, 20, 36, 180, 70, 252, 52, 786, 262, 84, 60, 52, 796, 184, 66, 90, 132, 268, 404, 270, 270, 324, 126, 12, 820, 411, 20, 826, 828, 92, 168, 332, 90, 419, 812, 70, 156, 330, 94, 396, 852, 36, 428, 858, 60, 431, 172, 136, 390, 132, 48, 300, 876, 292, 55, 882, 116, 443, 21, 270, 414, 356, 132, 140, 104, 42, 180, 906, 300, 91, 410, 60, 390, 153, 102, 420, 180, 102, 464, 126, 310, 40, 117, 156, 940, 220, 36, 946, 36, 316, 68, 380, 140, 204, 155, 318, 96, 483, 72, 194, 138, 60, 488, 110, 36, 491, 196, 138, 154, 495, 30, 396, 332, 36];
    return nums[n / 2 - 1];
}

8、复杂度​

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

9、执行结果​

10、思路3​

基于 n 是偶数的前提可以尝试寻找操作规律。每次操作都是按固定规则分别整体移动偶数下标和奇数下标的数字，假设一次操作为一个周期，可以猜测，复原时所有数字经过的操作周期相同，因此可以只考察数字 1 复原所需的步数。（仅猜测，不会证明）

实际编码则是根据题中所给操作规则 arr[i] = perm[i / 2]、arr[i] = perm[n / 2 + (i - 1) / 2] 推断数字 1 的变化。假设 j 为数字 1 当前所处位置，则 j 下一次所处位置存在以下2种情况：

• 当 2 * j < n - 1 时 j = 2 * j
• 当 2 * j >= n - 1 时 j = 2 * j - n + 1

11、代码​

function reinitializePermutation(n: number): number {
    let ans = 0;

    for (let j = 1; !(ans && j === 1); ans++) {
        if (2 * j >= n - 1) j = 2 * j - n + 1;
        else j = 2 * j;
    }

    return ans;
}

12、复杂度​

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

13、执行结果​

1、题干​

给你一个正整数 num ，请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。

正整数的 各位数字之和 是其所有位上的对应数字相加的结果。

示例 1：

输入：num = 4
输出：2
解释：
只有 2 和 4 满足小于等于 4 且各位数字之和为偶数。    

示例 2：

输入：num = 30
输出：14
解释：
只有 14 个整数满足小于等于 30 且各位数字之和为偶数，分别是： 
2、4、6、8、11、13、15、17、19、20、22、24、26 和 28 。

提示：

• 1 <= num <= 1000

2、思路​

根据题意模拟

3、代码​

function countEven(num: number): number {
    let ans = 0;
    for (let n = 1; n <= num; n++) {
        for (let k = n, sum = 0; k; k = k / 10 >> 0) {
            sum += k % 10;
            if (k < 10 && sum % 2 === 0) ans += 1;
        }
    }
    return ans;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。

同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = "abbcccaa"
输出：13
解释：同构子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：

输入：s = "xy"
输出：2
解释：同构子字符串是 "x" 和 "y" 。

示例 3：

输入：s = "zzzzz"
输出：15

提示：

• 1 <= s.length <= 105
• s 由小写字符串组成

2、思路​

先提取连续且重复的字母组成的单词，再累计每个单词长度的等差数列和

3、代码​

function countHomogenous(s: string): number {
    return s.match(/([a-z])\1*/g).reduce((a, c) => (a + c.length * (c.length + 1) / 2) % (1e9 + 7), 0);
};

4、执行结果​

1、题干​

给你一个字符串 s ，返回 s 中 同质子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。

同质字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：s = "abbcccaa"
输出：13
解释：同质子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：

输入：s = "xy"
输出：2
解释：同质子字符串是 "x" 和 "y" 。

示例 3：

输入：s = "zzzzz"
输出：15

提示：

• 1 <= s.length <= 105
• s 由小写字符串组成。

2、思路​

先提取连续且重复的字母组成的单词，再累计每个单词长度的等差数列和

3、代码​

function countHomogenous(s: string): number {
    return s.match(/([a-z])\1*/g).reduce((a, c) => (a + c.length * (c.length + 1) / 2) % (1e9 + 7), 0);
};

4、执行结果​

1、题干​

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

1. 提供 100ml 的 汤A 和 0ml 的 汤B 。
2. 提供 75ml 的 汤A 和 25ml 的 汤B 。
3. 提供 50ml 的 汤A 和 50ml 的 汤B 。
4. 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意 不存在先分配 100 ml 汤B 的操作。

需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。

示例 1:

输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

示例 2:

输入: n = 100
输出: 0.71875

提示:

• 0 <= n <= 109​​​​​​​

Problem: 808. 分汤

2、思路​

记忆化搜索

3、Code​

function soupServings(n: number): number {
    const operations = [[100, 0], [75, 25], [50, 50], [25, 75]];
    const visited = new Map();

    function serve(ka: number, kb: number) {
        const key = `${ka}-${kb}`;
        if (visited.has(key)) return visited.get(key);

        if (ka <= 0 && kb > 0) return 1;
        else if (ka <= 0 && kb <= 0) return 1 / 2;
        else if (kb <= 0) return 0;

        let r = 0;
        for (const [a, b] of operations) {
            r += 1 / 4 * serve(ka - a, kb - b);
        }

        visited.set(key, r);

        return r;
    }

    return n < 5000 ? serve(n, n) : 1;
};

4、执行结果​

1、题干​

一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例 1：

输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。

示例 2：

输入：nums = [2]
输出：0

提示：

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

Problem: 891. 子序列宽度之和

2、思路​

还得是按官解的排序+计算贡献值的思路去做：

• 对长度为 n 的整数数组 nums 升序排列
• 数组 nums 中第 i 个整数贡献的最小值次数是： $2 ^ {n-i-1} - 1$
• 数组 nums 中第 i 个整数贡献的最大值次数是： $2 ^ i - 1$
• 累计每个元素的贡献值 $nums[i] * (2 ^ i - 1) - nums[i] * (2 ^ {n-i-1} - 1)$

计算贡献次数实际是计算组合数：$C_{n}^{1} + C_{n}^{2} + ... + C_{n}^{n}$

由于数据过大需要取余，第一版用快速幂实现，居然只通过了 20+ 个用例，真是裂开了😳；把快速幂改成打表后过了。。。

3、Code​

function sumSubseqWidths(nums: number[]): number {
    const n = nums.length, MOD = 1e9 + 7;
    nums.sort((a, b) => a - b);
    const pow = new Array(n).fill(1);
    for (let i = 1; i < n; i++) pow[i] = 2 * pow[i - 1] % MOD;

    let res = 0;
    for (let i = 0; i < n; i++) {
        res = (res + nums[i] * (pow[i] - pow[n - i - 1])) % MOD;
    }

    return res;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。

全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：

• 0 <= i < j < n
• nums[i] > nums[j]

局部倒置 的数目等于满足下述条件的下标 i 的数目：

• 0 <= i < n - 1
• nums[i] > nums[i + 1]

当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,0,2]
输出：true
解释：有 1 个全局倒置，和 1 个局部倒置。

示例 2：

输入：nums = [1,2,0]
输出：false
解释：有 2 个全局倒置，和 1 个局部倒置。

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] < n
• nums 中的所有整数 互不相同
• nums 是范围 [0, n - 1] 内所有数字组成的一个排列

Problem: 775. 全局倒置与局部倒置

2、思路1​

根据题意可知，局部倒置是全局倒置，全局倒置不一定是局部倒置，因此全局倒置的数量必然大于等于局部倒置。

当数组 nums 升序排列时不存在倒置情况，若将任意整数 k 置换到位置 i 就会出现倒置，二者差值大于 1 时必然会出现全局倒置的数量大于局部倒置。

3、Code​

function isIdealPermutation(nums: number[]): boolean {
    for (let i = 0; i < nums.length; i++) {
        if (Math.abs(nums[i] - i) > 1) return false;
    }
    return true;
};

4、复杂度​

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

5、执行结果​

6、思路2​

累计局部倒置数量 pc 和全局倒置数量 ac，当 nums[i] > nums[i + 1] 时 pc 加 1，当 nums[i] > i 时 ac 加 nums[i] - i，最后判断二者是否相等。其中有一种特殊情况：出现3个连续递减的数时全局倒置数量必定大于倒置数量。

这个思路正确性没有验证，完全是运气通过

7、Code​

function isIdealPermutation(nums: number[]): boolean {
    let pc = 0, ac = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > nums[i + 1] && nums[i + 1] > nums[i + 2]) return false;

        if (nums[i] > nums[i + 1]) pc++;
        if (nums[i] > i) ac += nums[i] - i;
    }

    return pc === ac;
};

8、复杂度​

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

9、执行结果​

10、思路3​

单调栈，耗时很长

11、Code​

function isIdealPermutation(nums: number[]): boolean {
    let pc = 0, ac = 0, stack = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > nums[i + 1]) pc++;

        if (!stack.length || stack.at(-1) > nums[i]) {
            ac += stack.length;
            stack.push(nums[i]);
        } else {
            const j = stack.findIndex(s => s < nums[i]);
            ac += j;
            stack.splice(j, 0, nums[i]);
        }
    }

    return pc === ac;
};

12、复杂度​

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

13、执行结果​

1、题干​

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

示例 1:

输入: n = "123"
输出: "121"

示例 2:

输入: n = "1"
输出: "0"
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

提示:

• 1 <= n.length <= 18
• n 只由数字组成
• n 不含前导 0
• n 代表在 [1, 1018 - 1] 范围内的整数

2、解题思路​

• 找到中轴并提取中轴前的数字作为前半段，计算前半段数字加1、减1、不变3种情况的结果
• 根据3种计算结果推导3个回文数，对进位导致位数增加、借位导致位数减少、前导0等情况分别进行处理
  • 若进位导致位数增加，求得 10...01 形式的回文数
  • 若借位导致位数减少或出现前导0的情况，求得 99...99 形式的回文数
  • 否则将前半段翻转作为后半段（原数字长度为奇数的需要剔除中轴），求得前后两段拼接而成的回文数
• 在3个回文数中找到与 n 的差值的绝对值最小的数，若存在多个则取较小那个数，最后返回该数

3、代码​

var nearestPalindromic = function (n) {
    const len = n.length, m = Math.floor((len - 1) / 2);
    const s1 = n.slice(0, m + 1);

    const reverse = (s) => [].reduce.call(s, (a, c) => c + a, '');
    const nums = [`${+s1 + 1}`, s1, `${+s1 - 1}`].map((a) => {
        if (a.length > m + 1) return `1${'0'.repeat(len - 1)}1`;
        if (a.length <= m || (a === '0' && len === 2)) return '9'.repeat(len - 1);
        return a + (len % 2 ? reverse(a).slice(1) : reverse(a));
    });
    const diffs = nums.map((d) => BigInt(d) - BigInt(n)).map((d) => (d > 0 ? d : -d));
    const minDiff = diffs.reduce((a, c, i) => (c && c <= a[0] ? [c, i] : a), [Infinity, -1]);
    return nums[minDiff[1]];
};

4、执行结果​

1、题干​

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。

• 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意：你的表达式不应该包含多余的括号。

示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

示例 2:

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

说明:

• 1 <= nums.length <= 10
• 2 <= nums[i] <= 1000
• 对于给定的输入只有一种最优除法。

2、解题思路​

贪心，加括号使得被除数最大、除数最小即可

3、代码​

var optimalDivision = function (nums) {
    return nums.length < 3 ? nums.join('/') : `${nums.shift()}/(${nums.join('/')})`;
};

4、执行结果​