1、题干​

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：

• 必须选择 一种 冰激凌基料。
• 可以添加 一种或多种 配料，也可以不添加任何配料。
• 每种类型的配料 最多两份 。

给你以下三个输入：

• baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
• toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
• target ，一个整数，表示你制作甜点的目标价格。

你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

示例 1：

输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。

示例 2：

输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3：

输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。

示例 4：

输入：baseCosts = [10], toppingCosts = [1], target = 1
输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。

提示：

• n == baseCosts.length
• m == toppingCosts.length
• 1 <= n, m <= 10
• 1 <= baseCosts[i], toppingCosts[i] <= 104
• 1 <= target <= 104

Problem: 1774. 最接近目标价格的甜点成本

2、思路​

暴力搜索，确定基料，枚举配料

3、Code​

function closestCost(baseCosts: number[], toppingCosts: number[], target: number): number {
    let ans = baseCosts[0];

    function dfs(c: number, ti: number) {
        if (c === target) return ans = target;
        else {
            const d1 = Math.abs(c - target), d2 = Math.abs(ans - target);
            if (d1 < d2 || (d1 === d2 && c < ans)) ans = c;
        }

        for (let i = ti; i < toppingCosts.length && c <= target; i++) {
            for (let k = 0; k < 3; k++) dfs(c + k * toppingCosts[i], i + 1);
        }
    }

    for (const b of baseCosts) dfs(b, 0);

    return ans;
};

4、执行结果​

1、题干​

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

示例 1：

输入：boxes = "110"
输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入：boxes = "001011"
输出：[11,8,5,4,3,4]

提示：

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] 为 '0' 或 '1'

Problem: 1769. 移动所有球到每个盒子所需的最小操作数

2、思路1​

双层循环暴力枚举

3、Code​

function minOperations(boxes: string): number[] {
    const ans = new Array(boxes.length).fill(0);
    for (let i = 0; i < ans.length; i++) {
        for (let j = 0; j < boxes.length; j++) {
            if (boxes[j] === '1') ans[i] += Math.abs(i - j);
        }
    }
    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

单层循环累加左右步数

关键点：左半边有 lc 个 1 时，每移动一次左半边步数 ls 需累加 lc，同理右半边步数 rs 需减去 rc

7、Code​

function minOperations(boxes: string): number[] {
    let rc = 0, rs = 0, lc = 0, ls = 0;
    const ans = new Array(boxes.length).fill(0);

    for (let i = 0; i < boxes.length; i++) {
        if (boxes[i] === '1') rc += 1, rs += i;
    }

    for (let i = 0; i < ans.length; i++) {
        ans[i] = ls + rs;
        if (boxes[i] === '1') rc--, lc++;
        rs -= rc, ls += lc;
    }
    
    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 s = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = s。

输入一组查询单词，输出其中可扩张的单词数量。

示例：

输入： 
s = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。

提示：

• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s 和所有在 words 中的单词都只由小写字母组成。

Problem: 809. 情感丰富的文字

2、思路​

总体思路是：先提取字符串 s 的 pattern，然后遍历 words 中每一项是否与 pattern 相匹配。这里使用正则实现。

• 提取字符串 s 的正则
  • 将 s 中连续 3 个以上相同的字符 a 替换为 a{1,a.count}，比如 ooooo 替换为 o{1,5}
  • 替换后的字符串添加首尾标志 ^、$ 并转为正则
• 遍历 words 并与正则匹配，若匹配则结果累计 1

3、Code​

function expressiveWords(s: string, words: string[]): number {
    const r = s.replace(/(\w)\1{2,}/g, (m, a) => `${a}{1,${m.length}}`);
    const reg = new RegExp(`^${r}$`);
    return words.reduce((a, c) => a + +reg.test(c), 0);
};

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

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

提示:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和s 都只由小写字母组成。

Problem: 792. 匹配子序列的单词数

2、思路​

二分查找

• 按字母表顺序把字符串 s 中所有字符的下标升序存入二维数组 idxMatrix
• 判断数组 words 中任意字符串 w 是否 s 的子序列，只需要判断 w 中任意字符 c 比前一个字符 在 s 中的下标更大。其中查找 c 在 s 中的下标时，使用二分查找算法

3、Code​

function numMatchingSubseq(s: string, words: string[]): number {
    const CA = 'a'.charCodeAt(0), idxMatrix = new Array(26).fill(0).map(() => []);

    for (let i = 0; i < s.length; i++) {
        const ci = s[i].charCodeAt(0) - CA;
        idxMatrix[ci].push(i);
    }

    function find(nums: number[] = [], k: number) {
        let l = 0, r = nums.length - 1;

        while (l <= r) {
            const m = ((l + r) / 2) >> 0;
            if (nums[m] > k) {
                if (nums[m - 1] > k) r = m - 1;
                else return nums[m];
            } else {
                l = m + 1;
            }
        }

        return -1;
    }

    let res = 0;
    loop: for (const w of words) {
        let preIdx = -1;
        for (const c of w) {
            const ci = c.charCodeAt(0) - CA;
            const ni = find(idxMatrix[ci], preIdx);
            if (ni < 0) continue loop;
            preIdx = ni;
        }
        res++;
    }

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

给定一个二维网格 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、题干​

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

示例 1：

输入: n = 5, mines = [[4, 2]]
输出: 2
解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

提示：

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• 每一对 (xi, yi) 都 不重复​​​​​​​

Problem: 764. 最大加号标志

2、思路​

• 暴力：遍历矩阵 grid，把每个网格当成中心，计算加号标志的最大阶数 k
• 哈希：把 0 网格的坐标转换成哈希表降低查找时间复杂度
• 剪枝：遍历过程中，通过当前求得的最大阶数 k 进一步缩小遍历范围

3、Code​

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
    const M = 10007, hash = (x: number, y: number) => x * M + y;
    const set = new Set(mines.map(([x, y]) => hash(x, y)));
    
    let k = 0;
    for (let i = 0; i < n - k; i++) {
        for (let j = k; i >= k && j < n - k; j++) {
            for (let l = 0; l < n / 2; l++) {
                if (i < l || j < l || i + l >= n || j + l >= n) break;
                if (set.has(hash(i, j + l)) || set.has(hash(i, j - l)) || set.has(hash(i + l, j)) || set.has(hash(i - l, j))) break;
                k = Math.max(k, l + 1);
            }
        }
    }

    return k;
}

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(m)$，$m=mines.length$

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

给你一个数组 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、执行结果​