1、题干​

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

返回整数数组 answer ，其中 answer = [even, odd] 。

示例 1：

输入：n = 17
输出：[2,0]
解释：17 的二进制形式是 10001 。 
下标 0 和 下标 4 对应的值为 1 。 
共有 2 个偶数下标，0 个奇数下标。

示例 2：

输入：n = 2
输出：[0,1]
解释：2 的二进制形式是 10 。 
下标 1 对应的值为 1 。 
共有 0 个偶数下标，1 个奇数下标。

提示：

• 1 <= n <= 1000

2、思路​

模拟，转二进制字符串并翻转高低位，再遍历计数

有空还是位运算吧

3、代码​

function evenOddBit(n: number): number[] {
    const bits = [...n.toString(2)].reverse();
    let n1 = 0, n2 = 0;

    for (let i = 0; i < bits.length; i++) {
        if (bits[i] === '0') continue;
        i % 2 ? n1++ : n2++;
    }

    return [n2, n1];
};

4、复杂度​

• 时间复杂度：$O(\log{n})$
• 空间复杂度：$O(\log{n})$

5、执行结果​

1、题干​

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.length
• nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

示例 1：

输入：nums = [2,1,3]
输出：12
解释：可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 216

先暴力打个卡睡觉

2、思路​

本题可以用三数之和的思路暴力解题。先用哈希表 map 存储所有二元组按位与的结果与出现次数，再枚举数组 nums 与 map 所有的键，如果二者位与结果为 0 就累计其次数

这种暴力思路会超时吗？可以稍微分析下时间复杂度：

• 第一个嵌套循环的时间复杂度为 $O(n^2)$，其中 $n$ 为数组 nums 长度，由于 $n <= 1000$，整体量级最多为 $10^6$，基本不会超时；
• 第二个嵌套循环的时间复杂度为 $O(nm)$，其中 $m$ 为哈希表键的个数，由于 nums[i] 小于 $2^{16}$，所以二元组按位与的结果个数不会超过 $2^{16}$，即哈希表的键数 $m<=65536$，整体量级最多为 $6*10^7$，大概率能过

3、代码​

function countTriplets(nums: number[]): number {
    const map = new Map();
    for (const x of nums) {
        for (const y of nums) {
            const z = x & y;
            map.set(z, (map.get(z) || 0) + 1);
        }
    }

    let ans = 0;
    for (const x of nums) {
        for (const [y, c] of map) {
            if (!(x & y)) ans += c;
        }
    }

    return ans;
};

4、复杂度​

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

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

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

• 玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
• 可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
• 单词表 words 中每个单词只能计分（使用）一次。
• 根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
• 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

提示：

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i] 和 letters[i] 只包含小写的英文字母。

2、思路​

回溯，枚举所有情况计算最高得分。未优化，存在重复计算，效率不高。

3、代码​

function maxScoreWords(words: string[], letters: string[], score: number[]): number {
    const wordScore = new Array(words.length).fill(0);
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words[i].length; j++) {
            wordScore[i] += score[words[i][j].charCodeAt(0) - 97];
        }
    }

    const letterDict = new Array(26).fill(0);
    for (let i = 0; i < letters.length; i++) {
        letterDict[letters[i].charCodeAt(0) - 97] += 1;
    }

    let ans = 0;
    function dfs(sc: number, visited: Set<number>) {
        for (let i = 0; i < words.length; i++) {
            if (visited.has(i)) continue;

            let valid = true;
            for (let j = 0; j < words[i].length; j++) {
                const c = words[i][j].charCodeAt(0) - 97;
                letterDict[c]--;
                if (letterDict[c] < 0) valid = false;
            }

            if (valid) {
                ans = Math.max(ans, sc + wordScore[i]);

                visited.add(i);
                dfs(sc + wordScore[i], visited);
                visited.delete(i);
            }

            for (let j = 0; j < words[i].length; j++) {
                letterDict[words[i][j].charCodeAt(0) - 97]++;
            }
        }
    }

    return dfs(0, new Set()), ans;
};

4、执行结果​

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

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间
• '#' 代表一堵墙
• '@' 是起点
• 小写字母代表钥匙
• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

输入：grid = ["@.a..","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。

示例 2：

输入：grid = ["@..aA","..B#.","....b"]
输出：6

示例 3:

输入: grid = ["@Aa"]
输出: -1

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'
• 钥匙的数目范围是 [1, 6] 
• 每个钥匙都对应一个 不同 的字母
• 每个钥匙正好打开一个对应的锁

Problem: 864. 获取所有钥匙的最短路径

2、思路​

写过最长的代码，心态崩了

思路：

• 回溯，对所有钥匙进行排列组合，得到所有路径（不校验路径是否连通）
• 遍历所有路径，累计从起点经过所有钥匙需要的步数，结果取最小步数
• 广搜计算两把钥匙之间的最短路径（需要校验路径是否连通）

3、Code​

function shortestPathAllKeys(grid: string[]): number {
    const m = grid.length, n = grid[0].length;

    const M = 10007;
    const encode = (i: number, j: number) => i * M + j;
    const decode = (d: number) => [(d / M) >> 0, d % M];

    let start = 0;
    const keys: number[] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === "@") start = encode(i, j);
            if (grid[i][j] >= "a" && grid[i][j] <= "f") keys.push(encode(i, j));
        }
    }

    // 寻找两把钥匙之间的最短路径
    function bfs(source: number, target: number, visited: Set<number>, foundKeys: Set<string>): number {
        let queue = [source];
        const [ti, tj] = decode(target);

        let step = 1;
        while (queue.length) {
            const nextQueue = new Set<number>();

            for (const q of queue) {
                if (visited.has(q)) continue;
                visited.add(q);

                const [qi, qj] = decode(q);
                const dirs = [[qi, qj + 1], [qi, qj - 1], [qi + 1, qj], [qi - 1, qj],];

                for (const [i, j] of dirs) {
                    if (!grid[i] || !grid[i][j] || grid[i][j] === "#") continue;
                    if (grid[i][j] >= "A" && grid[i][j] <= "F" && !foundKeys.has(grid[i][j].toLowerCase())) continue;
                    if (i === ti && j === tj) return step;

                    nextQueue.add(encode(i, j));
                }
            }

            step++;
            queue = [...nextQueue];
        }

        return 0;
    }

    // 遍历所有路径，累计从起点经过所有钥匙需要的步数，结果取最小步数
    let res = Infinity;
    function calcSteps(path: Set<number>) {
        let step = 0, source = start, foundKeys = new Set<string>();

        for (const p of path) {
            const st = bfs(source, p, new Set(), foundKeys);
            step += st;
            if (!st || step >= res) return;

            const [pi, pj] = decode(p);
            foundKeys.add(grid[pi][pj]);
            source = p;
        }

        if (step < res) res = step;
    }

    // 对钥匙进行排列组合
    function dfs(path: Set<number>) {
        for (const k of keys) {
            if (path.has(k)) continue;
            path.add(k);
            dfs(path);
            if (path.size === keys.length) calcSteps(path);
            path.delete(k);
        }
    }

    dfs(new Set());

    return res === Infinity ? -1 : res;
}

4、复杂度​

• 时间复杂度：$O(k!*mn)$
• 空间复杂度：$O(mn)$

5、执行结果​

1、题干​

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。

请你返回 words 数组中 一致字符串 的数目。

示例 1：

输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。

示例 2：

输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出：7
解释：所有字符串都是一致的。

示例 3：

输入：allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
输出：4
解释：字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。

提示：

• 1 <= words.length <= 104
• 1 <= allowed.length <= 26
• 1 <= words[i].length <= 10
• allowed 中的字符 互不相同 。
• words[i] 和 allowed 只包含小写英文字母。

Problem: 1684. 统计一致字符串的数目

[TOC]

思路

reduce 跟 for of 耗费的时间空间差距还挺大

Code - for of

function countConsistentStrings(allowed: string, words: string[]): number {
    const dict = new Set(allowed);
    let res = 0;
    loop: for (const s of words) {
        for (const c of s) {
            if (!dict.has(c)) continue loop;
        }
        res++;
    }
    return res;
};

Code - reduce

function countConsistentStrings(allowed: string, words: string[]): number {
    const dict = new Set(allowed);
    return words.reduce((a, s) => a + +([].every.call(s, (c) => dict.has(c))), 0);
};

1、题干​

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。

给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。

一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。

请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

示例 1：

输入：n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出：5
解释：请求列表如下：
从楼 0 离开的员工为 x 和 y ，且他们都想要搬到楼 1 。
从楼 1 离开的员工为 a 和 b ，且他们分别想要搬到楼 2 和 0 。
从楼 2 离开的员工为 z ，且他想要搬到楼 0 。
从楼 3 离开的员工为 c ，且他想要搬到楼 4 。
没有员工从楼 4 离开。
我们可以让 x 和 b 交换他们的楼，以满足他们的请求。
我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。
所以最多可以满足 5 个请求。

示例 2：

输入：n = 3, requests = [[0,0],[1,2],[2,1]]
输出：3
解释：请求列表如下：
从楼 0 离开的员工为 x ，且他想要回到原来的楼 0 。
从楼 1 离开的员工为 y ，且他想要搬到楼 2 。
从楼 2 离开的员工为 z ，且他想要搬到楼 1 。
我们可以满足所有的请求。

示例 3：

输入：n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出：4

提示：

• 1 <= n <= 20
• 1 <= requests.length <= 16
• requests[i].length == 2
• 0 <= fromi, toi < n

2、解法1-回溯​

回溯枚举 requests 所有子集，如果所有节点的出度和入度都为0则属于可行的请求列表，取所有可行请求列表的最大长度作为返回结果

3、代码​

var maximumRequests = function (n, requests) {
    let max = 0;
    function backtrace(i, path) {
        const sums = new Array(n).fill(0);
        for (const [f, t] of path) sums[f]--, sums[t]++;
        if (sums.every(s => !s)) max = Math.max(max, path.length);

        for (let j = i + 1; j < requests.length; j++) {
            path.push(requests[j]);
            backtrace(j, path);
            path.pop();
        }
    }

    for (let i = 0; i < requests.length; i++) backtrace(i, [requests[i]]);

    return max;
};

4、执行结果​

5、解法2-BFS​

BFS 枚举 requests 所有子集，如果所有节点的出度和入度都为0则属于可行的请求列表，取所有可行请求列表的最大长度作为返回结果

6、代码​

var maximumRequests = function (n, requests) {
    let max = 0, queue = requests.map((r) => [r]);
    while (queue.length) {
        const nextQueue = [];
        for (let i = 0; i < queue.length; i++) {
            const reqs = queue[i], sums = new Array(n).fill(0);

            for (const [f, t] of reqs) sums[f]--, sums[t]++;
            if (sums.every((s) => !s)) max = Math.max(max, reqs.length);

            const idx = requests.indexOf(reqs[reqs.length - 1]);
            for (let j = idx + 1; j < requests.length; j++) nextQueue.push([...reqs, requests[j]]);
        }
        queue = nextQueue;
    }
    return max;
};

7、执行结果​

• 执行用时: 924 ms
• 内存消耗: 68 MB

1、题干​

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。

• 比方说，如果 nums = [1, 2, 3, 4] ：
  • [2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
  • [1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。

请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。

nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

示例 1：

输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。

示例 2：

输入：nums = [4,2,3,15]
输出：5
解释：好子集为：
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。

提示：

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

2、解题思路​

• 状态压缩：对数组 nums 使用哈希表计数，所有的键都会集中在 $[1,30]$ 这个区间
• 从哈希表中剔除存在多个相同因子的数，比如4,8,12
• 使用 BFS 思路对符合要求的数字进行好子集组合，第一层为1个数的组合，第二层为2个数的组合，以此类推
• 组合过程中记得剔除掉存在最大公约数不为1的情况，另外注意去重
• 计算每层好子集数量并累加
  • 好子集数量等于子集各元素个数相乘
  • 若子集中存在 $1$，不是乘以 $1$ 的数量 $c1$，而应该乘以 $1$ 的组合总数 $2^{c1}-1$，由于 $c1$ 可能很大直接计算会溢出，可以使用累乘并模 $1e9+7$

这道题最大的坑在于对数字 $1$ 的特殊处理，这个解法和代码都不是最优的，抽空再优化了

3、代码​

var numberOfGoodSubsets = function (nums) {
    const MOD = 1e9 + 7;
    const nMap = nums.reduce((a, c) => a.set(c, (a.get(c) || 0) + 1), new Map());
    const bNums = [4, 9, 16, 25, 8, 27, 16];
    const gNums = [...nMap.keys()].filter(n => bNums.every((b) => n % b)).sort((a, b) => a - b);
    const gcd = (a, b) => (b ? gcd(b, a % b) : a);

    let cn1 = 1;
    for (let c1 = nMap.get(1); c1; c1--) cn1 = 2 * cn1 % MOD;

    let count = 0, queue = gNums.map((n) => [n]);
    while (queue.length) {
        const nextQueue = [];
        for (const arr of queue) {
            for (const g of gNums) {
                if (g <= arr[arr.length - 1] || arr.some((a) => gcd(a, g) > 1)) continue;
                nextQueue.push([...arr, g]);
            }

            if (arr.length === 1 && arr[0] === 1) continue;
            count += arr.reduce((a, c) => {
                const cn = c > 1 ? nMap.get(c) : cn1 - 1;
                return a * cn % MOD;
            }, 1);
            count = count % MOD;
        }
        queue = nextQueue;
    }

    return count;
};

4、执行结果​

• 执行用时: 468 ms
• 内存消耗: 63.9 MB

1、题干​

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：

输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：

输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示：

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

2、解题思路​

由题意可知美好子串中不会单独存在大写或小写字母，因此可以在单独的大写或小写字母处断开字符串，对拆分出来的左右子串进行递归查找，直到子串成为美好子串。

3、代码​

var longestNiceSubstring = function (s) {
    for (let i = 0; i < s.length; i++) {
        const c = s[i].charCodeAt(0) < 91 ? s[i].toLowerCase() : s[i].toUpperCase();
        if (s.includes(c)) continue;
        const s1 = longestNiceSubstring(s.slice(0, i));
        const s2 = longestNiceSubstring(s.slice(i + 1));
        return s1.length >= s2.length ? s1 : s2;
    }
    return s;
};

4、执行结果​