跳到主要内容

55 篇博文 含有标签「哈希表」

查看所有标签

· 阅读需 4 分钟

1、题干​

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

 

提示：

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

 

注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

题目比较难，没能想到官解那些优秀解法，尝试了暴力解法并两次剪枝优化后，不仅AC还超过82%提交

2、解题思路​

解题关键是：最大异或结果一定是由 二进制位数最多的一个数 与 另一个数 进行异或运算得来。 以 [3,10,5,25,2,8] 为例，用二进制表示是：[11, 1010, 101, 11001, 10, 1000]，其中 二进制位数最多 的只有1个数 25(11001)，接着计算 25 跟其他数的异或结果并取最大值即可。


暴力解法步骤 ：

  • 先对数组进行降序排序
  • 对所有数进行异或运算并取最大值

剪枝优化：

  • 优化1：异或结果的最大可能是：二进制位数最多的数异或之后所有二进制位变成 1，假设为 MAX_NUM。如果运算结果已达到最大可能 MAX_NUM，则直接退出程序。（效果显著）
  • 优化2：异或运算时，第一个数取 二进制位数最多的数 ，第二个数取 二进制位数更少的数 。第一个数不变的情况下，第二个数的二进制位数与其相同则异或会导致最高位变为 0，结果必然小于第二个数的二进制位数更少的情况。

3、代码​

// 优化1
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    let idx = nums.findIndex((n) => n < 1 << c);
    if (idx < 0) idx = nums.length;

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    for (let i = 0; i < idx; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            res = Math.max(res, nums[i] ^ nums[j]);
            if (res === MAX_NUM) return res;
        }
    }

    return res;
};

// 优化1 + 优化2
var findMaximumXOR = function (nums) {
    nums.sort((a, b) => b - a);
    const c = Math.log2(nums[0]) >> 0;
    const idx = nums.findIndex((n) => n < 1 << c);

    const MAX_NUM = (1 << (c + 1)) - 1;
    let res = 0;

    if (idx > -1) {
        for (let i = 0; i < idx; i++) {
            for (let j = idx; j < nums.length; j++) {
                res = Math.max(res, nums[i] ^ nums[j]);
                if (res === MAX_NUM) return res;
            }
        }
    } else {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) res = Math.max(res, nums[i] ^ nums[j]);
        }
    }

    return res;
};

4、复杂度​

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

5、执行结果​

image.png

· 阅读需 6 分钟

1、题干​

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

  • i + 1 需满足：i + 1 < arr.length
  • i - 1 需满足：i - 1 >= 0
  • j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

 

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

 

提示：

  • 1 <= arr.length <= 5 * 104
  • -108 <= arr[i] <= 108

DFS解法写自闭了，简单写下BFS和动态规划的思路和代码

2、解法1-BFS​

BFS解法需要注意各种边界条件以及剪枝优化，不然很可能超时、内存溢出。剪枝的方法有这些：

  • 跳过相邻且值相同的节点，只留头尾，中间部分没有意义
  • 跳过已访问过的节点
  • BFS的当前层级超过到达该节点的最小步数

3、代码​

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引以及最小步数
    const map = new Map();
    for (let i = 0; i < n; i++) {
        if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
    }

    const visited = new Set();
    let queue = [0], level = 0, res = Infinity;

    while (queue.length) {
        const set = new Set();
        if (level >= res) break;
        for (const i of queue) {
            if (visited.has(i)) continue;
            visited.add(i);

            if (i === n - 1) res = Math.min(res, level);
            if (i >= 1) set.add(i - 1);
            if (i <= n - 2) set.add(i + 1);

            const [idxs, min] = map.get(arr[i]);
            if (level + 1 > min) continue;

            map.get(arr[i])[1] = Math.min(min, level + 1);
            for (const x of idxs) {
                if (x !== i) set.add(x);
            }
        }
        queue = [...set];
        level++;
    }

    return res;
};

4、执行结果​

  • 执行用时: 180 ms
  • 内存消耗: 62.3 MB

5、解法2-动态规划​

实际上这道题不能用动态规划，因为违反了无后效性，其实带来的问题就是不能一次性规划出结果，这个问题没啥好办法，多规几次就出来了（两次动态规划结果一致则认为已经是最优解）。

6、代码​

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引
    const map = new Map();
    for (let i = 0; i < n; i++) {
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
    }

    // DP处理
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;

    function updateSame(i) {
        const [idxs, min] = map.get(arr[i]);
        if (idxs.length < 2 || dp[i] >= min) return;
        map.get(arr[i])[1] = dp[i];
        for (let j = 0; j < idxs.length; j++) {
            dp[idxs[j]] = Math.min(dp[i] + 1, dp[idxs[j]]);
        }
    }

    function runDp() {
        for (let i = 0; i < n; i++) {
            if (i > 0) dp[i - 1] = Math.min(dp[i] + 1, dp[i - 1]), updateSame(i - 1);
            if (i < n - 1) dp[i + 1] = Math.min(dp[i] + 1, dp[i + 1]), updateSame(i + 1);

            updateSame(i);
        }
    }

    while (1) {
        runDp();
        const r1 = dp.toString();
        runDp();
        const r2 = dp.toString();
        if (r1 === r2) return dp[n - 1];
    }
};

7、执行结果​

  • 执行用时: 380 ms
  • 内存消耗: 65.1 MB

8、解法3-DFS​

各种处理和优化，最终还是没能AC，直接贴代码吧，如果有大神看到希望指点下🙏

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引以及最小步数
    const map = new Map();
    for (let i = 0; i < n; i++) {
        if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [
            [i], Infinity
        ]);
    }

    let res = Infinity;

    function dfs(i, path) {
        if (i === n - 1) return res = Math.min(res, path.size);
        if (i < 0 || i > n - 1 || path.has(i)) return;

        const [idxs, min] = map.get(arr[i]);
        if (path.size >= min || path.size + 1 >= res) return;

        path.add(i);

        for (let j = 0; idxs.length > 1 && j < idxs.length; j++) {
            if (i !== idxs[j]) dfs(idxs[j], path);
        }

        dfs(i - 1, path);
        dfs(i + 1, path);

        map.get(arr[i])[1] = Math.min(map.get(arr[i])[1], path.size);
        path.delete(i);
    }

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

· 阅读需 4 分钟

1、题干​

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

 

 

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

2、解法1-哈希映射​

遍历数组所有元素，并将当前数字和索引作为键值存入哈希映射 map 中，如果当前数字 nums[i] 已存在于 map 中且其索引与当前索引的差值不大于 k 则返回 true，遍历结束仍未找到符合条件的数字则返回 false


3、复杂度​

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

4、代码​

var containsNearbyDuplicate = function (nums, k) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i]) && i - map.get(nums[i]) <= k) return true;
        map.set(nums[i], i);
    }
    return false;
};
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        map = {}
        for i in range(len(nums)):
            if(nums[i] in map and i - map[nums[i]] <= k):
                return True
            map[nums[i]] = i
        return False

5、解法2-滑动窗口+哈希集合​

遍历数组所有元素，使用哈希集合 set 作为滑动窗口容器存储数组中连续的 k 个元素，索引 i 大于 k 之后需要剔除滑动窗口容器的首个元素 nums[i - k - 1] 以保证其长度不超过 k，如果当前元素已存在于哈希集合则说明二者索引差值不大于 k 应返回 true，遍历结束仍未找到符合条件的数字则返回 false

解法1的优势在于更容易想到和理解。解法2的优势在于只需要存储值而不需要存储键值对，因此空间占用会更少；另外当 k 比 nums.length 小的情况下，解法2的空间复杂度会更小且不受 nums.length 变大而影响。


6、复杂度​

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

7、代码​

var containsNearbyDuplicate = function (nums, k) {
    const set = new Set();
    for (let i = 0; i < nums.length; i++) {
        if (i > k) set.delete(nums[i - k - 1]);
        if (set.has(nums[i])) return true;
        set.add(nums[i]);
    }
    return false;
};
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        s = set()
        for i in range(len(nums)):
            if(i > k):
                s.remove(nums[i - k - 1])
            if(nums[i] in s):
                return True
            s.add(nums[i])
        return False

· 阅读需 3 分钟

1、题干​

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

 

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

进阶：所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

 

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序​

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字


3、代码​

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度​

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

5、解法2-桶排序​

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入按数量存入桶中，最后返回前 k 个数字。其时间复杂度为 O(n)O(n)，解决了进阶问题。


6、代码​

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度​

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

· 阅读需 3 分钟

1、题干​

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

 

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

进阶：所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

 

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序​

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字


3、代码​

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度​

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

5、解法2-桶排序​

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入按数量存入桶中，最后返回前 k 个数字。其时间复杂度为 O(n)O(n)，解决了进阶问题。


6、代码​

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度​

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

· 阅读需 7 分钟

1、题干​

在一个 106 x 106 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

 

示例 1：

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

示例 2：

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。

 

提示：

  • 0 <= blocked.length <= 200
  • blocked[i].length == 2
  • 0 <= xi, yi < 106
  • source.length == target.length == 2
  • 0 <= sx, sy, tx, ty < 106
  • source != target
  • 题目数据保证 source 和 target 不在封锁列表内

2、解题思路​

迷宫的封锁列表blocked会形成围栏，假设从起点和终点分别进行深度遍历，遍历过程中设定步数最大值steps为围栏最大面积，若2条路径行进的步数都超过最大步数或者遍历过程中起点和终点都能访问到则表示起止点连通，则表示起止点连通，反之不连通。


注意点

  • 最开始认为围栏的最大面积是(n2)2(\dfrac{n}{2}) ^ 2，是一块正方形区域。实际官解给出的是n(n−1)2\dfrac{n(n-1)}{2}，是一块等腰直角三角形区域，其中n为blocked数组长度。具体实现时没看官解，限制的是n22\dfrac{n^2}{2}，实际上围栏最大面积略偏高不影响结果，因为在不被围的情况下可以走的步数肯定远超这个值。这个最大面积的推导和精确计算可以说有点复杂了，答题时被用例28教育了一番。
  • 遍历过程中如果起止两个点都能访问到则表示起止点连通（用例[[0,3],[1,0],[1,1],[1,2],[1,3]] [0,0] [0,2]）
  • 走过的坐标使用哈希表记录，以免重复遍历导致死循环
  • JS若使用递归实现在执行用例28时会出现栈溢出（本地溢出，力扣判题程序未溢出，后面补充了递归DFS代码）

3、代码-非递归​

var isEscapePossible = function (blocked, source, target) {
    const hash = (x, y) => 1123 * x + y;
    const maxSteps = blocked.length ** 2 / 2, dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const blockSet = blocked.reduce((a, c) => a.add(hash(c[0], c[1])), new Set());

    function move(s, t, steps, visited) {
        const stack = [s];
        while (stack.length) {
            const [x, y] = stack.pop();
            if (x < 0 || x >= 1e6 || y < 0 || y >= 1e6 || blockSet.has(hash(x, y)) || visited.has(hash(x, y))) continue;
            if (--steps <= 0 || (x === t[0] && y === t[1])) return true;
            visited.add(hash(x, y));
            for (const d of dirs) stack.push([x + d[0], y + d[1]]);
        }
        return false;
    }

    return move(source, target, maxSteps, new Set()) && move(target, source, maxSteps, new Set());
};

4、执行结果​

执行用时: 156 ms 内存消耗: 58.8 MB


5、代码-递归​

var isEscapePossible = function (blocked, source, target) {
    const hash = (x, y) => 1123 * x + y;
    const maxSteps = blocked.length ** 2 / 2, dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const blockSet = blocked.reduce((a, c) => a.add(hash(c[0], c[1])), new Set());

    function dfs(x, y, steps, visited, t) {
        if (x < 0 || x >= 1e6 || y < 0 || y >= 1e6 || blockSet.has(hash(x, y)) || visited.has(hash(x, y))) return false;
        if (--steps <= 0 || (x === t[0] && y === t[1])) return true;
        visited.add(hash(x, y));
        return dirs.reduce((a, c) => a || dfs(x + c[0], y + c[1], steps, visited, t), false);
    }

    return dfs(...source, maxSteps, new Set(), target) && dfs(...target, maxSteps, new Set(), source);
};

6、执行结果​

执行用时: 120 ms 内存消耗: 47.8 MB

1.png


7、优化点​

  • 问题：最开始哈希表保存的坐标是字符串拼接而来，但是字符串消耗空间更多、操作耗时更多，所以执行结果的时长和内存偏高
  • 优化：不用字符串做key，使用质数乘法把坐标转成唯一数字，使用该唯一数字做key
  • 结果：优化后两种代码执行结果用时减半（240ms 到 120ms），内存消耗也大幅减少（57.3 MB 到 47.8 MB），递归DFS代码执行结果破双百

字符串做key比较容易理解和实现且不会冲突，但消耗时间空间较多；而数字做key的好处在于消耗时间空间较少，但麻烦点在于实现时要注意避免key冲突的问题。

· 阅读需 3 分钟

1、题干​

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

 

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

 

提示：

  • 二叉树的节点个数的范围是  [1, 104].
  • -104 <= Node.val <= 104
  • root 为二叉搜索树
  • -105 <= k <= 105

 

注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

2、解法1​

DFS遍历+哈希查找：DFS遍历所有节点node，在哈希表set中查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

3、代码​

var findTarget = function (root, k) {
    const set = new Set();
    function dfs(node) {
        if (!node) return false;
        if (set.has(k - node.val)) return true;
        set.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
};

4、复杂度​

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

5、执行结果​

1.png


6、解法2​

DFS遍历+DFS二分查找：DFS遍历所有节点node，利用BST特性进行DFS二分查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

这里二分搜索的时间复杂度受到二叉树平衡性的影响，最坏情况下二叉树可能退化成链表，导致搜索时间复杂度为O(n)O(n)，总体时间复杂度为O(n2)O(n^2)

7、代码​

var findTarget = function (root, k) {
    function find(node, num) {
        if (!node) return false;
        if (num === node.val) return true;
        return num > node.val ? find(node.right, num) : find(node.left, num);
    }

    function findSum(node, num) {
        if (!node) return false;
        return (num !== 2 * node.val && find(root, num - node.val)) || findSum(node.right, num) || findSum(node.left, num);
    }

    return findSum(root, k);
};

8、复杂度​

时间复杂度：平衡二叉搜索树的情况下为O(nlogn)O(nlogn) ，非平衡二叉搜索树的情况下超过O(nlogn)O(nlogn)，最差为O(n2)O(n^2)

空间复杂度：O(1)O(1)

9、执行结果​

1.png

· 阅读需 4 分钟

1、题干​

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

 

    示例 1：

    输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
    输出：true
    解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

    示例 2：

    输入：hand = [1,2,3,4,5], groupSize = 4
    输出：false
    解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

     

    提示：

    • 1 <= hand.length <= 104
    • 0 <= hand[i] <= 109
    • 1 <= groupSize <= hand.length

     

    注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

    2、解法1​

    先对原数组升序排序，然后进行双指针嵌套遍历，外层遍历找顺子起点，内层遍历找顺子后续元素，被找到的元素置为-1即寻找其他顺子元素时直接略过，若无法找到完整顺子则返回false

    3、代码​

    var isNStraightHand = function (hand, groupSize) {
        hand.sort((a, b) => a - b);
        for (let i = 0; i < hand.length; i++) {
            if (hand[i] < 0) continue;
            let count = 0;
            for (let j = i + 1; j < hand.length && count !== groupSize - 1; j++) {
                if (hand[j] - hand[i] === count + 1) count++, hand[j] = -1;
            }
            if (count !== groupSize - 1) return false;
        }
        return true;
    };

    代码逻辑简要说明

    • 外层遍历：从下标i=0开始遍历数组内的元素，如果当前元素不为负数则作为顺子起点
    • 内层遍历：从下标j=i+1(即顺子起点的下一个元素)开始遍历数组内的元素，寻找顺子后续元素
      • 对已找到的元素计数，计数变量记为count
      • 若当前元素与顺子起点的差值等于count+1，则说明该元素是顺子的后续元素
    • 内层遍历结束，若找到的元素数量不等于groupSize - 1，说明顺子不存在应返回false

    4、执行结果​

    1.png

    5、解法2​

    先对原数组升序排序，然后对数组内数字进行哈希表计数（数字作key数量作value），然后遍历数组所有数字，以数量大于1的数字作为顺子起点，寻找顺子后续元素，若无法找到完整顺子则返回false

    6、代码​

    var isNStraightHand = function (hand, groupSize) {
        hand.sort((a, b) => a - b);
        const map = hand.reduce((acc, n) => acc.set(n, (acc.get(n) || 0) + 1), new Map());
        for (const n of hand) {
            if (!map.get(n)) continue;
            for (let i = 0; i < groupSize; i++) {
                if (!map.get(n + i)) return false;
                else map.set(n + i, map.get(n + i) - 1);
            }
        }
        return true;
    };

    7、执行结果​

    执行用时: 100 ms 内存消耗: 47.1 MB

    · 阅读需 4 分钟

    1、题干​

    某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

    给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

     

    示例 1：

    输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
    输出：true
    解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

    示例 2：

    输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
    输出：false
    解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

    示例 3：

    输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
    输出：false
    解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

     

    提示：

    • 1 <= words.length <= 100
    • 1 <= words[i].length <= 20
    • order.length == 26
    • 在 words[i] 和 order 中的所有字符都是英文小写字母。

    解题思路​

    思路 将words中的所有字符替换为正常字典序的字符，然后使用比较运算符（大于号、小于号等）去比较所有words即可。

    例子 words = ["hl","la"], order = "hlabcdefgijkmnopqrstuvwxyz"

    • 将words中的字符替换为正常字典序的字符，结果为：words = ["ab","bc"]
    • 使用比较运算符比较所有words，"ab"<"bc"结果为true，最终返回true

    步骤

    • 创建哈希映射map，遍历order，获得外星字典序（键）与正常字典序（值）的映射
    • 遍历words中的所有字符串
      • 将words[i]中的字符替换为正常字典序的字符
      • 使用比较运算符比较words[i]与words[i - 1]的大小
      • 如果i && words[i] < words[i - 1]则不符合外星字典序直接返回false
    • 函数运行到结尾，则说明符合外星字典序，返回true

    代码​

    var isAlienSorted = function (words, order) {
        const map = new Map();
        for (let i = 0; i < order.length; i++) map.set(order[i], String.fromCharCode(97 + i));

        for (let i = 0; i < words.length; i++) {
            words[i] = [...words[i]].reduce((a, c) => a + map.get(c), '');
            if (i && words[i] < words[i - 1]) return false;
        }

        return true;
    };

    · 阅读需 4 分钟

    1、题干​

    某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

    给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

     

    示例 1：

    输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
    输出：true
    解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

    示例 2：

    输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
    输出：false
    解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

    示例 3：

    输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
    输出：false
    解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

     

    提示：

    • 1 <= words.length <= 100
    • 1 <= words[i].length <= 20
    • order.length == 26
    • 在 words[i] 和 order 中的所有字符都是英文小写字母。

     

    注意：本题与主站 953 题相同： https://leetcode-cn.com/problems/verifying-an-alien-dictionary/

    解题思路​

    思路 将words中的所有字符替换为正常字典序的字符，然后使用比较运算符（大于号、小于号等）去比较所有words即可。

    例子 words = ["hl","la"], order = "hlabcdefgijkmnopqrstuvwxyz"

    • 将words中的字符替换为正常字典序的字符，结果为：words = ["ab","bc"]
    • 使用比较运算符比较所有words，"ab"<"bc"结果为true，最终返回true

    步骤

    • 创建哈希映射map，遍历order，获得外星字典序（键）与正常字典序（值）的映射
    • 遍历words中的所有字符串
      • 将words[i]中的字符替换为正常字典序的字符
      • 使用比较运算符比较words[i]与words[i - 1]的大小
      • 如果i && words[i] < words[i - 1]则不符合外星字典序直接返回false
    • 函数运行到结尾，则说明符合外星字典序，返回true

    代码​

    var isAlienSorted = function (words, order) {
        const map = new Map();
        for (let i = 0; i < order.length; i++) map.set(order[i], String.fromCharCode(97 + i));

        for (let i = 0; i < words.length; i++) {
            words[i] = [...words[i]].reduce((a, c) => a + map.get(c), '');
            if (i && words[i] < words[i - 1]) return false;
        }

        return true;
    };