跳到主要内容

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

查看所有标签

· 阅读需 2 分钟

1、题干​

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

  • 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。

给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

 

示例 1：

输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：

输入：s = "aabcbaa"
输出：17

 

提示：

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

Problem: 1781. 所有子字符串美丽值之和

2、思路​

枚举所有子串，累计所有美丽值

没想到官解也是暴力枚举，甚至没有优化

3、Code​

function beautySum(s: string): number {
    let ans = 0, chars = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        chars[s.charCodeAt(i) - 97] += 1;

        const counts = [...chars];
        for (let j = 0; j < i - 1; j++) {
            let max = 1, min = s.length;
            for (const c of counts) {
                if (c > max) max = c;
                if (c && c < min) min = c;
            }
            ans += max - min;
            counts[s.charCodeAt(j) - 97] -= 1;
        }
    }

    return ans;
}

4、复杂度​

  • 时间复杂度：O(C∗n2)O(C*n^2)，C=26C=26
  • 空间复杂度：O(C)O(C)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

 

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

 

提示：

  • 1 <= nums1.length, nums2.length <= 105
  • 1 <= nums1[i], nums2[i] <= 6

Problem: 1775. 通过最少操作次数使数组的和相等

2、思路​

题目要求使数组的和相等的最少操作次数，可以使用贪心算法。假设 nums1 的和较小，升序地将 nums1 中的数尽量变大（最大为 6），降序地将 nums2 中的数尽量变小（最小为 1），直到两个数组的和相等。

操作时需要同时处理 nums1 中的数 n 和 nums2 中的数 7-n。

3、Code​

function minOperations(nums1: number[], nums2: number[]): number {
    const n1 = nums1.length, n2 = nums2.length;
    if (n1 < n2 && 6 * n1 < n2 || (n2 < n1 && 6 * n2 < n1)) return -1;

    let sum1 = nums1.reduce((a, c) => a + c, 0);
    let sum2 = nums2.reduce((a, c) => a + c, 0);

    if (sum1 === sum2) return 0;
    if (sum1 > sum2) [sum1, sum2, nums1, nums2] = [sum2, sum1, nums2, nums1];

    const diffList = new Array(6).fill(0);
    for (let i = 0; i < Math.max(n1, n2); i++) {
        if (nums1[i]) diffList[6 - nums1[i]] += 1;
        if (nums2[i]) diffList[nums2[i] - 1] += 1;
    }

    let ans = 0, diff = sum2 - sum1;

    for (let d = 5; d > 0 && diff > 0; d--) {
        const u = Math.min(diffList[d], Math.ceil(diff / d));
        diff -= d * u;
        ans += u;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

image.png

· 阅读需 3 分钟

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*logn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png

· 阅读需 2 分钟

1、题干​

给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回 满足这个性质的 s 的任意一种排列 。

 

示例 1:

输入: order = "cba", s = "abcd"
输出: "cbad"
解释: 
“a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。

示例 2:

输入: order = "cbafg", s = "abcd"
输出: "cbad"

 

提示:

  • 1 <= order.length <= 26
  • 1 <= s.length <= 200
  • order 和 s 由小写英文字母组成
  • order 中的所有字符都 不同

Problem: 791. 自定义字符串排序

2、思路​

数量级比较小 order.length <= 26，s.length <= 200，用 Array.sort 实现就行

3、Code​

function customSortString(o: string, s: string): string {
    return [...s].sort((a, b) => o.indexOf(a) - o.indexOf(b)).join('');
};

4、复杂度​

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

5、执行结果​

image.png

· 阅读需 2 分钟

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;
};

image.png

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);
};

image.png

· 阅读需 6 分钟

1、题干​

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

 

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

 

提示：

  • 1 <= n <= 109
  • 0 <= lamps.length <= 20000
  • 0 <= queries.length <= 20000
  • lamps[i].length == 2
  • 0 <= rowi, coli < n
  • queries[j].length == 2
  • 0 <= rowj, colj < n

今天题目挺简单的，感觉会写CRUD就能AC，只需要按照题目意思存储、查询以及修改亮灯状态就行

5b4f2239f899f748dd1fd07a8d78a201.gif


2、解题思路​

  • 由于网格行列的最大值是 10910^9，要遍历网格进行状态查改是不太可能了
  • 本题关键点是使用多个哈希表存储亮灯状态，另外要注意灯的状态实际有3种：关闭、打开、被照亮
    • 使用哈希集合存储打开的灯，记为 lightSet，其中键为行列号拼接成的字符串，形如 i-j
    • 使用哈希映射存储被照亮的行和列，分别记为 rowMap 和 colMap，其中键为行号或列号，值为亮灯数量
    • 使用哈希映射存储被照亮的两条对角线 y−x=dy-x=d 和 y+x=dy+x=d，分别记为 dglMap1 和 dglMap2，其中键为行列号的差或和，值为亮灯数量
  • 接着根据题意模拟即可
    • 将初始亮灯状态 lamps 存入各哈希表中
    • 遍历查询数组 queries ，查询亮灯状态并记录到结果数组 ans，查询时注意：只要行列或对角线上亮灯数量大于0，亮灯状态就是 1
    • 每次查询后关闭九宫格内的灯，关灯时注意：打开的灯才需要关闭，被照亮的灯无法关闭

3、代码​

var gridIllumination = function (n, lamps, queries) {
    // 亮灯哈希集合
    const lightSet = new Set();
    // 亮灯行、亮灯列
    const rowMap = new Map(), colMap = new Map();
    // 亮灯对角线1：y-x=d、亮灯对角线2：y+x=d
    const dglMap1 = new Map(), dglMap2 = new Map();
    
    // 将初始亮灯状态存入各哈希表中
    for (const [i, j] of lamps) {
        if (lightSet.has(`${i}-${j}`)) continue;
        lightSet.add(`${i}-${j}`);
        rowMap.set(i, (rowMap.get(i) || 0) + 1);
        colMap.set(j, (colMap.get(j) || 0) + 1);
        const d1 = j - i, d2 = j + i;
        dglMap1.set(d1, (dglMap1.get(d1) || 0) + 1);
        dglMap2.set(d2, (dglMap2.get(d2) || 0) + 1);
    }

    // 关灯函数：关闭九宫格内的灯
    function turnOff(fi, fj) {
        for (let di = -1; di < 2; di++) {
            for (let dj = -1; dj < 2; dj++) {
                const i = fi + di, j = fj + dj;
                if (!lightSet.has(`${i}-${j}`)) continue;
                lightSet.delete(`${i}-${j}`);
                rowMap.set(i, (rowMap.get(i) || 0) - 1);
                colMap.set(j, (colMap.get(j) || 0) - 1);
                const d1 = j - i, d2 = j + i;
                dglMap1.set(d1, (dglMap1.get(d1) || 0) - 1);
                dglMap2.set(d2, (dglMap2.get(d2) || 0) - 1);
            }
        }
    }

    // 遍历查询数组，计算亮灯状态后进行关灯操作
    const ans = queries.map(() => 0);
    for (let qi = 0; qi < queries.length; qi++) {
        const [i, j] = queries[qi];
        const d1 = j - i, d2 = j + i;
        if (lightSet.has(`${i}-${j}`) || rowMap.get(i) || colMap.get(j) || dglMap1.get(d1) || dglMap2.get(d2)) ans[qi] = 1;
        turnOff(i, j);
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

image.png

· 阅读需 3 分钟

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、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

 

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

 

提示：

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

 

注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-dictionary/

2、解法1-字符串比较​

数组存储字典，查找时直接进行字符串比较，如果不匹配的字符数量为1返回true，否则继续查找直至结束返回false

3、代码​

var MagicDictionary = function () {
    this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }

    return false;
};

4、执行结果​

image.png

5、解法2-哈希表​

哈希表存储字典，查找时对源字符串的每一位做替换，若替换后哈希表存在该字符串则返回true，否则继续查找直至结束返回false

6、代码​

var MagicDictionary = function () {
    this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < searchWord.length; i++) {
        const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
        for (let j = 97; j < 123; j++) {
            const c = String.fromCharCode(j);
            if (c === searchWord[i]) continue;
            if (this.dict.has(pre + c + post)) return true;
        }
    }

    return false;
};

7、执行结果​

  • 执行用时: 860 ms
  • 内存消耗: 48.3 MB

· 阅读需 4 分钟

1、题干​

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

 

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

 

提示：

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

 

注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-dictionary/

2、解法1-字符串比较​

数组存储字典，查找时直接进行字符串比较，如果不匹配的字符数量为1返回true，否则继续查找直至结束返回false

3、代码​

var MagicDictionary = function () {
    this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }

    return false;
};

4、执行结果​

image.png

5、解法2-哈希表​

哈希表存储字典，查找时对源字符串的每一位做替换，若替换后哈希表存在该字符串则返回true，否则继续查找直至结束返回false

6、代码​

var MagicDictionary = function () {
    this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < searchWord.length; i++) {
        const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
        for (let j = 97; j < 123; j++) {
            const c = String.fromCharCode(j);
            if (c === searchWord[i]) continue;
            if (this.dict.has(pre + c + post)) return true;
        }
    }

    return false;
};

7、执行结果​

  • 执行用时: 860 ms
  • 内存消耗: 48.3 MB

· 阅读需 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 = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

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

 

提示：

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

 

进阶：你可以在 O(n) 的时间解决这个问题吗？

 

注意：本题与主站 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