跳到主要内容

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

查看所有标签

· 阅读需 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;
};

· 阅读需 2 分钟

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 是数组大小。

解题思路​

  • 创建哈希映射map，用于统计数字出现次数，key为数字，value为出现次数
  • 创建数组arr，用于统计每个出现次数对应的数字集合，数组下标代表数字出现次数，值为出现次数与之相等的数字的集合
  • 倒序遍历数组arr，提取前出现频率前 k 高的数字

代码​

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        map[nums[i]] = (map[nums[i]] || 0) + 1;
    }

    const matrix = Object.entries(map);
    const arr = [];
    for (let i = 0; i < matrix.length; i++) {
        const [n, c] = matrix[i];
        if (!arr[c]) arr[c] = [];
        arr[c].push(+n);
    }

    const res = [];
    for (let i = arr.length - 1; i > -1; i--) {
        if (arr[i] && res.length < k) {
            res.push(...arr[i].slice(0, k - res.length));
        }
    }

    return res;
};

· 阅读需 2 分钟

1、题干​

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

 

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

 

提示：

  • 1 <= arr.length <= 105
  • -104 <= arr[i], difference <= 104

头回见到用哈希表做dp table，记录下。

代码​

/**
 * @param {number[]} arr
 * @param {number} d
 * @return {number}
 */
var longestSubsequence = function (arr, d) {
    let max = 1;
    const dp = {};
    for (let n of arr) {
        dp[n] = (dp[n - d] || 0) + 1;
        max = Math.max(max,dp[n]);
    }

    return max;
};

· 阅读需 2 分钟

1、题干​

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。

 

示例 1：

输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。

示例 2：

输入：candyType = [1,1,2,3]
输出：2
解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。

示例 3：

输入：candyType = [6,6,6,6]
输出：1
解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。

 

提示：

  • n == candyType.length
  • 2 <= n <= 104
  • n 是一个偶数
  • -105 <= candyType[i] <= 105

代码​

/**
 * @param {number[]} candyType
 * @return {number}
 */
var distributeCandies = function (candyType) {
    return Math.min(new Set(candyType).size, candyType.length / 2);
};

· 阅读需 4 分钟

1、题干​

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例 1:

输入: k = 5

输出: 9

1、解题思路​

一开始没想到动态规划、三指针、步进法这些方案，看了题解还是觉得这些规律或方案有点难想到。我的第一反应是：这个问题好像可以用BFS+Set去重来解决。

1.1、转换思路​

根据这个方向，实际上可以把问题转换成：已知一棵树的根是1，第一层节点是根节点与 3、5、7相乘的结果，第二层节点是第一层节点与 3、5、7相乘的结果，以此类推； 求这棵树中按广度遍历的第k个子节点的值。于是写下了这段代码：

var getKthMagicNumber = function(k) {
    let nums = [1];

    while (nums.length) {
        const set = new Set();

        for (let i = 0; i < nums.length; i++) {
            k--;
            if (!k) return nums[i];
            set.add(3 * nums[i]);
            set.add(5 * nums[i]);
            set.add(7 * nums[i]);
        }

        nums = [...set];
    }
};

1.2、测试出错​

写完之后测试出错，是因为忽略了一个很重要的条件：按顺序排列。在上述代码中用于遍历树的 nums 代表的是每一层节点，它始终是单调递增的。虽然每一层节点都单调递增，但是随着层数增加，下一层的节点却有可能小于上一层节点。

1.3、解决问题​

要解决这个问题也不难，只要把所有节点都放入 nums 中，并且保证它的单调性就OK了。

1.4、整体方案​

因此，使用BFS + Set去重 + 单调栈的方式就能解出这道题，问题的关键点有以下3个：

  • 使用非递归的BFS方式进行遍历
  • 使用Set去除重复的数字
  • 使用单调栈保证数字升序排列

2、代码​

var getKthMagicNumber = function (k) {
    const nums = [1];
    const set = new Set();

    for (let i = 0; i < k; i++) {
        if (i + 1 === k) return nums[i];
        const arr = [3 * nums[i], 5 * nums[i], 7 * nums[i]];

        arr.forEach(n => {
            if (set.has(n)) return;
            set.add(n);

            if (n >= nums[nums.length - 1]) return nums.push(n);

            // 以上代码是常规逻辑：BFS + Set去重 
            // 以下代码是为了保证 nums 的单调性
            const arr = [];
            while (n < nums[nums.length - 1]) {
                arr.unshift(nums.pop());
            }
            nums.push(n, ...arr);
        });
    }
};