1、题干​

给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。

最好 英文字母的大写和小写形式必须 都 在 s 中出现。

英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。

示例 1：

输入：s = "lEeTcOdE"
输出："E"
解释：
字母 'E' 是唯一一个大写和小写形式都出现的字母。

示例 2：

输入：s = "arRAzFif"
输出："R"
解释：
字母 'R' 是大写和小写形式都出现的最好英文字母。
注意 'A' 和 'F' 的大写和小写形式也都出现了，但是 'R' 比 'F' 和 'A' 更好。

示例 3：

输入：s = "AbCdEfGhIjK"
输出：""
解释：
不存在大写和小写形式都出现的字母。

提示：

• 1 <= s.length <= 1000
• s 由小写和大写英文字母组成

2、思路1​

哈希表模拟

3、代码​

function greatestLetter(s: string): string {
    const dict = new Set();
    let ans = '';

    for (const c of s) {
        dict.add(c);
        const l = c.toLowerCase(), L = c.toUpperCase();
        if (L > ans && dict.has(l) && dict.has(L)) ans = L;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

倒序枚举字母表

7、代码​

function greatestLetter(s: string): string {
    for (let i = 90; i >= 65; i--) {
        const C = String.fromCharCode(i), c = C.toLowerCase();
        if (s.includes(C) && s.includes(c)) return C;
    }

    return '';
};

8、复杂度​

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

9、执行结果​

1、题干​

我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

示例 1:
输入: "(123)"
输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

示例 2:
输入: "(00011)"
输出:  ["(0.001, 1)", "(0, 0.011)"]
解释: 
0.0, 00, 0001 或 00.01 是不被允许的。

示例 3:
输入: "(0123)"
输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

示例 4:
输入: "(100)"
输出: [(10, 0)]
解释: 
1.0 是不被允许的。

提示:

• 4 <= S.length <= 12.
• S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。

Problem: 816. 模糊坐标

[TOC]

思路

• 剔除原始字符串 s 中的括号
• 将 s 拆分成两个字符串 s1、s2
• 分别对 s1、s2 添加小数点，得到两个字符串数组 nums1、nums2
• 组合 nums1、nums2 中的字符串得到最终结果

复杂度

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

Code

function ambiguousCoordinates(s: string): string[] {
    s = s.slice(1, s.length - 1);

    const res = [];

    function insertDot(str: string) {
        const nums = /^0\d/.test(str) ? [] : [str];

        for (let j = 1; j < str.length; j++) {
            const ns = str.slice(0, j) + '.' + str.slice(j);
            if (!/^0\d|0$/.test(ns)) nums.push(ns);
        }

        return nums;
    }

    for (let i = 1; i < s.length; i++) {
        const s1 = s.slice(0, i), s2 = s.slice(i);
        const nums1 = insertDot(s1), nums2 = insertDot(s2);

        for (const ns1 of nums1) {
            for (const ns2 of nums2) {
                res.push(`(${ns1}, ${ns2})`);
            }
        }
    }

    return res;
}

1、题干​

给你一个数组 towers 和一个整数 radius 。

数组  towers  中包含一些网络信号塔，其中 towers[i] = [xi, yi, qi] 表示第 i 个网络信号塔的坐标是 (xi, yi) 且信号强度参数为 qi 。所有坐标都是在  X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。

整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。

如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊qi / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。

请你返回数组 [cx, cy] ，表示 信号强度 最大的 整数 坐标点 (cx, cy) 。如果有多个坐标网络信号一样大，请你返回字典序最小的 非负 坐标。

注意：

• 坐标 (x1, y1) 字典序比另一个坐标 (x2, y2) 小，需满足以下条件之一：
  • 要么 x1 < x2 ，
  • 要么 x1 == x2 且 y1 < y2 。
• ⌊val⌋ 表示小于等于 val 的最大整数（向下取整函数）。

示例 1：

输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
输出：[2,1]
解释：
坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。

示例 2：

输入：towers = [[23,11,21]], radius = 9
输出：[23,11]
解释：由于仅存在一座信号塔，所以塔的位置信号强度最大。

示例 3：

输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
输出：[1,2]
解释：坐标 (1, 2) 的信号强度最大。

提示：

• 1 <= towers.length <= 50
• towers[i].length == 3
• 0 <= xi, yi, qi <= 50
• 1 <= radius <= 50

2、解题思路​

题目不难，难的是阅读理解。

根据题意和数据范围，问题可以简化为：给定数组 towers、整数 radius，求在矩形 rect = [[0,0],[0,100],[100,0],[100,100]] 中信号最强的坐标。这不是最优解，但是相对容易理解。

3、代码​

function bestCoordinate(towers: number[][], radius: number): number[] {
    let [rx, ry, rq] = [0, 0, 0];

    for (let x = 0; x <= 100; x++) {
        for (let y = 0; y <= 100; y++) {
            let q = 0;

            for (const [xt, yt, qt] of towers) {
                const d = Math.sqrt((x - xt) ** 2 + (y - yt) ** 2);
                if (d <= radius) q += Math.floor(qt / (1 + d));
            }

            if (q > rq) [rx, ry, rq] = [x, y, q];
        }
    }

    return [rx, ry];
}

4、复杂度​

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

5、执行结果​

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

给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：

• nums[a] + nums[b] + nums[c] == nums[d] ，且
• a < b < c < d

示例 1：

输入：nums = [1,2,3,6]
输出：1
解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

示例 2：

输入：nums = [3,3,6,4,5]
输出：0
解释：[3,3,6,4,5] 中不存在满足要求的四元组。

示例 3：

输入：nums = [1,1,1,3,5]
输出：4
解释：满足要求的 4 个四元组如下：
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

提示：

• 4 <= nums.length <= 50
• 1 <= nums[i] <= 100

2、解题思路​

等式可转换成nums[a] + nums[b] == nums[d] - nums[c]，先用哈希表存储一边的结果，再遍历计算另一边的结果是否存在于哈希表。

3、代码​

var countQuadruplets = function (nums) {
    const dict = new Map();
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (!dict.has(nums[i] + nums[j])) dict.set(nums[i] + nums[j], []);
            dict.get(nums[i] + nums[j]).push(j);
        }
    }

    let res = 0;
    for (let i = 2; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (!dict.has(nums[j] - nums[i])) continue;
            res += dict.get(nums[j] - nums[i]).reduce((acc, cur) => cur < i ? acc + 1 : acc, 0);
        }
    }

    return res;
};

4、执行结果​