13 篇博文 含有标签「计数」

1、题干​

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

提示：

• 1 <= croakOfFrogs.length <= 105
• 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

2、思路​

• 遍历给定字符串，记录正在叫的青蛙数量及其最大值
• 蛙叫声需按顺序输出，因此每个字符必须有可用的前一个字符，如果没有则返回-1
• 最后如果还有在叫的青蛙则返回-1，否则返回青蛙数量最大值

3、代码​

function minNumberOfFrogs(chars: string): number {
    const L = 5;
    if (chars.length % L) return -1;

    let ans = 0, used = 0;
    const counts = new Array(L).fill(0), dict = { c: 0, r: 1, o: 2, a: 3, k: 4 };

    for (let i = 0; i < chars.length; i++) {
        const j = dict[chars[i]];
        counts[j]++;

        if (j === 0) {
            used++;
        } else {
            if (counts[j - 1] < 1) return -1;
            if (j === L - 1) used--;
            counts[j - 1]--;
        }

        ans = Math.max(ans, used);
    }

    return used > 0 ? -1 : ans;
};

4、复杂度​

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

1、题干​

给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌，第 i 张牌大小为 ranks[i] ，花色为 suits[i] 。

下述是从好到坏你可能持有的 手牌类型 ：

1. "Flush"：同花，五张相同花色的扑克牌。
2. "Three of a Kind"：三条，有 3 张大小相同的扑克牌。
3. "Pair"：对子，两张大小一样的扑克牌。
4. "High Card"：高牌，五张大小互不相同的扑克牌。

请你返回一个字符串，表示给定的 5 张牌中，你能组成的 最好手牌类型 。

注意：返回的字符串 大小写 需与题目描述相同。

示例 1：

输入：ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]
输出："Flush"
解释：5 张扑克牌的花色相同，所以返回 "Flush" 。

示例 2：

输入：ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"]
输出："Three of a Kind"
解释：第一、二和四张牌组成三张相同大小的扑克牌，所以得到 "Three of a Kind" 。
注意我们也可以得到 "Pair" ，但是 "Three of a Kind" 是更好的手牌类型。
有其他的 3 张牌也可以组成 "Three of a Kind" 手牌类型。

示例 3：

输入：ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"]
输出："Pair"
解释：第一和第二张牌大小相同，所以得到 "Pair" 。
我们无法得到 "Flush" 或者 "Three of a Kind" 。

提示：

• ranks.length == suits.length == 5
• 1 <= ranks[i] <= 13
• 'a' <= suits[i] <= 'd'
• 任意两张扑克牌不会同时有相同的大小和花色。

2、思路​

结果总共4种情况，可以分类讨论：

• 首先判断花色，全部相同则为同花 Flush
• 对 ranks 排序，遍历检查 ranks 属于其他哪种情况
• 若大小全不同，则为高牌 High Card
• 若有3张相同，则为三条 Three of a Kind
• 最后只剩对子 Pair 这一种可能

3、代码​

function bestHand(ranks: number[], suits: string[]): string {
    if (suits.every(s => s === suits[0])) return 'Flush';

    ranks.sort((a, b) => a - b);
    if (ranks.every((r, i) => r !== ranks[i - 1])) return 'High Card';

    if (ranks.some((r, i) => r === ranks[i - 1] && r === ranks[i + 1])) return 'Three of a Kind';

    return 'Pair';
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

• 从 nums 选出 两个 相等的 整数
• 从 nums 中移除这两个整数，形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：

输入：nums = [1,3,2,1,3,2,2]
输出：[3,1]
解释：
nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。

示例 2：

输入：nums = [1,1]
输出：[1,0]
解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。

示例 3：

输入：nums = [0]
输出：[0,1]
解释：无法形成数对，nums 中剩下 1 个数字。

提示：

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

2、思路​

假设所求结果为数组 ans，ans[0] 表示数对数目，ans[1] 表示剩下的整数数目。

遍历 nums 数组并对每个整数计数，当某个整数个数为奇数时 ans[1]+=1，反之 ans[1]-=1 且 ans[0]+=1。

3、代码​

function numberOfPairs(nums: number[]): number[] {
    const ans = [0, 0], bucket = new Array(101).fill(0);

    for (let i = 0; i < nums.length; i++) {
        bucket[nums[i]] += 1;
        ans[0] += bucket[nums[i]] % 2 ? 0 : 1;
        ans[1] += bucket[nums[i]] % 2 ? 1 : -1;
    }

    return ans;
};

4、复杂度​

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

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、执行结果​

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、题干​

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。

从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。

示例 1：

输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。

示例 2：

输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。

示例 3：

输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。

提示：

• 1 <= s.length <= 100
• 1 <= target.length <= 10
• s 和 target 由小写英文字母组成

2、思路1​

枚举计数

3、代码​

function rearrangeCharacters(s: string, target: string): number {
    let ans = Infinity;

    for (const t of target) {
        const c1 = [...s].filter(c => c === t).length;
        const c2 = [...target].filter(c => c === t).length;
        ans = Math.min(ans, c1 / c2 >> 0);
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

哈希计数

7、代码​

function rearrangeCharacters(s: string, target: string): number {
    const dict1 = {};
    for (const c of target) dict1[c] = (dict1[c] || 0) + 1;

    const dict2 = {};
    for (const c of s) dict2[c] = (dict2[c] || 0) + 1;

    let ans = Infinity;
    for (const k of Object.keys(dict1)) {
        ans = Math.min(ans, (dict2[k] || 0) / dict1[k] >> 0);
    }

    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

给你一个下标从 0 开始长度为 n 的字符串 num ，它只包含数字。

如果对于 每个 0 <= i < n 的下标 i ，都满足数位 i 在 num 中出现了 num[i]次，那么请你返回 true ，否则返回 false 。

示例 1：

输入：num = "1210"
输出：true
解释：
num[0] = '1' 。数字 0 在 num 中出现了一次。
num[1] = '2' 。数字 1 在 num 中出现了两次。
num[2] = '1' 。数字 2 在 num 中出现了一次。
num[3] = '0' 。数字 3 在 num 中出现了零次。
"1210" 满足题目要求条件，所以返回 true 。

示例 2：

输入：num = "030"
输出：false
解释：
num[0] = '0' 。数字 0 应该出现 0 次，但是在 num 中出现了两次。
num[1] = '3' 。数字 1 应该出现 3 次，但是在 num 中出现了零次。
num[2] = '0' 。数字 2 在 num 中出现了 0 次。
下标 0 和 1 都违反了题目要求，所以返回 false 。

提示：

• n == num.length
• 1 <= n <= 10
• num 只包含数字。

2、思路​

模拟

3、代码​

function digitCount(num: string): boolean {
    for (let i = 0; i < 10; i++) {
        let c = +num[i] || 0;
        for (const n of num) {
            if (+n === i) c--;
        }
        if (c) return false;
    }

    return true;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。

注意：

• 如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
• s 包含至少一个出现两次的字母。

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以返回 'd' 。

提示：

• 2 <= s.length <= 100
• s 由小写英文字母组成
• s 包含至少一个重复字母

2、思路​

记录字符出现次数，首次重复出现则返回

3、代码​

function repeatedCharacter(s: string): string {
    const dict = {};
    for (const c of s) {
        if (dict[c]) return c;
        dict[c] = 1;
    }
};

4、复杂度​

• 时间复杂度：$O(C)$，其中 $C<=26$
• 空间复杂度：$O(C)$，其中 $C<=26$

1、题干​

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

• 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。

给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

示例 1：

输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：

输入：s = "aabcbaa"
输出：17

提示：

• 1 <= s.length <= 500
• s 只包含小写英文字母。

Problem: 1781. 所有子字符串美丽值之和

2、思路​

枚举所有子串，累计所有美丽值

没想到官解也是暴力枚举，甚至没有优化

3、Code​

function beautySum(s: string): number {
    let ans = 0, chars = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        chars[s.charCodeAt(i) - 97] += 1;

        const counts = [...chars];
        for (let j = 0; j < i - 1; j++) {
            let max = 1, min = s.length;
            for (const c of counts) {
                if (c > max) max = c;
                if (c && c < min) min = c;
            }
            ans += max - min;
            counts[s.charCodeAt(j) - 97] -= 1;
        }
    }

    return ans;
}

4、复杂度​

• 时间复杂度：$O(C*n^2)$，$C=26$
• 空间复杂度：$O(C)$

5、执行结果​

1、题干​

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

提示：

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[i] <= 6

Problem: 1775. 通过最少操作次数使数组的和相等

2、思路​

题目要求使数组的和相等的最少操作次数，可以使用贪心算法。假设 nums1 的和较小，升序地将 nums1 中的数尽量变大（最大为 6），降序地将 nums2 中的数尽量变小（最小为 1），直到两个数组的和相等。

操作时需要同时处理 nums1 中的数 n 和 nums2 中的数 7-n。

3、Code​

function minOperations(nums1: number[], nums2: number[]): number {
    const n1 = nums1.length, n2 = nums2.length;
    if (n1 < n2 && 6 * n1 < n2 || (n2 < n1 && 6 * n2 < n1)) return -1;

    let sum1 = nums1.reduce((a, c) => a + c, 0);
    let sum2 = nums2.reduce((a, c) => a + c, 0);

    if (sum1 === sum2) return 0;
    if (sum1 > sum2) [sum1, sum2, nums1, nums2] = [sum2, sum1, nums2, nums1];

    const diffList = new Array(6).fill(0);
    for (let i = 0; i < Math.max(n1, n2); i++) {
        if (nums1[i]) diffList[6 - nums1[i]] += 1;
        if (nums2[i]) diffList[nums2[i] - 1] += 1;
    }

    let ans = 0, diff = sum2 - sum1;

    for (let d = 5; d > 0 && diff > 0; d--) {
        const u = Math.min(diffList[d], Math.ceil(diff / d));
        diff -= d * u;
        ans += u;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​