哈希表
127. 单词接龙
题目
字典
wordList中从单词beginWord到endWord的 转换序列 是一个按下述规格形成的序列beginWord -> s(1) -> s(2) -> ... -> s(k)：
每一对相邻的单词只差一个字母。
对于
1 <= i <= k时，每个s(i)都在wordList中。注意，beginWord不需要在wordList中。
s(k) == endWord给你两个单词
beginWord和endWord和一个字典wordList，返回 从beginWord到endWord的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回0。示例 1：
输入： beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] 输出： 5 解释： 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
示例 2：
输入： beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”] 输出： 0 解释： endWord “cog” 不在字典中，所以无法进行转换。提示：
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord和wordList[i]由小写英文字母组成
beginWord != endWord
wordList中的所有字符串 互不相同
题解
/*** @param {string} beginWord* @param {string} endWord* @param {string[]} wordList* @return {number}*/
var ladderLength = function (beginWord, endWord, wordList) {if (beginWord === endWord) return 1let newSetWordList = new Set(wordList);let que = [];que.push([beginWord, 1])//第一次默认值，beginWord，默认长度1while (que.length) {for (var i = 0; i < que.length; i++) {let [newBeginWord, level] = que.shift()if (newBeginWord === endWord) {//相等时，返回长度return level}for (var w = 0; w < newBeginWord.length; w++) {//循环需要转换的字符串for (var j = 97; j <= 122; j++) {// 26个小写字母（ascii码 http://ascii.911cha.com/）let newStr = newBeginWord.slice(0, w) + String.fromCharCode(j) + newBeginWord.slice(w + 1)//hit -》 xit hxt hix x代表26个小写字母 if (newSetWordList.has(newStr)) {que.push([newStr, level + 1]) //把转换后的newStr放到数组中，长度+1newSetWordList.delete(newStr)//匹配到删除}}}}}return 0;
};
140. 单词拆分 II
题目
给定一个字符串
s和一个字符串字典wordDict，在字符串s中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意： 词典中的同一个单词可能在分段中被重复使用多次。示例 1：
输入: s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”] 输出: [“cats and dog”,“cat sand dog”]
示例 2：
输入: s = “pineapplepenapple”, wordDict = [“apple”,“pen”,“applepen”,“pine”,“pineapple”] 输出: [“pine apple pen apple”,“pineapple pen apple”,“pine applepen apple”] 解释: 注意你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”,“dog”,“sand”,“and”,“cat”] 输出: []提示：
1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s和wordDict[i]仅有小写英文字母组成
wordDict中所有字符串都 不同
题解
/*** @param {string} s* @param {string[]} wordDict* @return {string[]}*/
var wordBreak = function (s, wordDict) {const sIndex = s.length;const newWordDict = new Set(wordDict);//set 数据结构有has方法let hash = new Map();//存储循环过的从start截取i对应的数据function drt(start) {if (hash.has(start)) {//hash里有start，直接取对应的数据return hash.get(start);}if (start > sIndex - 1) {//start 最大值就是字符串最后一个索引 sIndex - 1return [[]];}let res = [];for (var i = start + 1; i <= sIndex; i++) {let str = s.slice(start, i);if (newWordDict.has(str)) {const items = drt(i);//循环把剩余字符串在newWordDict进行匹配，返回数组res [[string],]for (let item of items) {res.push([str].concat(item));}}hash.set(start, res);//存储从start开始截取，对应的res数据}return res;}return drt(0).map((item) => item.join(" "));// [[string,string],[string,string]] 变成 ["string string","string string"]
};
383. 赎金信
题目
给你两个字符串：
ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。
如果可以，返回true；否则返回false。
magazine中的每个字符只能在ransomNote中使用一次。示例 1：
输入： ransomNote = “a”, magazine = “b” 输出： false
示例 2：
输入： ransomNote = “aa”, magazine = “ab” 输出： false
示例 3：
输入： ransomNote = “aa”, magazine = “aab” 输出： true提示：
1 <= ransomNote.length, magazine.length <= 10(5)
ransomNote和magazine由小写英文字母组成
题解
/*** @param {string} ransomNote* @param {string} magazine* @return {boolean}*/
var canConstruct = function (ransomNote, magazine) {let wordMap = {}; // magazine字符每个字母出现次数let i = 0,j = 0;// 统计 magazine字符26个字母出现次数while (i < magazine.length) {const key = magazine[i];const wordNum = wordMap[key];wordMap[key] = wordNum ? wordNum + 1 : 1;i++;}// 循环ransomNote字符消耗map里对应字母次数while (j < ransomNote.length) {const ranKey = ransomNote[j];if (wordMap[ranKey] > 0) {wordMap[ranKey] -= 1;} else {return false;}j++;}return true;
};
2103. 环和杆
题目
总计有
n个环，环的颜色可以是红、绿、蓝中的一种。这些环分别穿在 10 根编号为0到9的杆上。
给你一个长度为2n的字符串rings，表示这n个环在杆上的分布。rings中每两个字符形成一个 颜色位置对 ，用于描述每个环：
第
i对中的 第一个 字符表示第i个环的 颜色（'R'、'G'、'B'）。第
i对中的 第二个 字符表示第i个环的 位置，也就是位于哪根杆上（'0'到'9'）。例如，
"R3G2B1"表示：共有n == 3个环，红色的环在编号为 3 的杆上，绿色的环在编号为 2 的杆上，蓝色的环在编号为 1 的杆上。
找出所有集齐 全部三种颜色 环的杆，并返回这种杆的数量。示例 1：
输入： rings = “B0B6G0R6R0R6G9” 输出： 1 解释： - 编号 0 的杆上有 3 个环，集齐全部颜色：红、绿、蓝。 - 编号 6 的杆上有 3 个环，但只有红、蓝两种颜色。 - 编号 9 的杆上只有 1 个绿色环。 因此，集齐全部三种颜色环的杆的数目为 1 。
示例 2：
输入： rings = “B0R0G0R9R0B0G0” 输出： 1 解释： - 编号 0 的杆上有 6 个环，集齐全部颜色：红、绿、蓝。 - 编号 9 的杆上只有 1 个红色环。 因此，集齐全部三种颜色环的杆的数目为 1 。
示例 3：
输入： rings = “G4” 输出： 0 解释： 只给了一个环，因此，不存在集齐全部三种颜色环的杆。提示：
rings.length == 2 * n
1 <= n <= 100如
i是 偶数 ，则rings[i]的值可以取'R'、'G'或'B'（下标从 0 开始计数）如
i是 奇数 ，则rings[i]的值可以取'0'到'9'中的一个数字（下标从 0 开始计数）
题解
/*** @param {string} rings* @return {number}*/
var countPoints = function (rings) {if (rings.length < 6) {return 0;}const arr = new Array(10).fill(30);const colorMaps = {R: 2,G: 3,B: 5,};for (let i = 0; i < rings.length; i = i + 2) {let newStr = rings.substr(i, 2);console.log(newStr);let color = newStr[0];let index = newStr[1];let num = colorMaps[color];if (num && index) {const items = arr[index];if (!(items % num)) {arr[index] = items / num;}}}return arr.filter((item) => item === 1).length;
};
2744. 最大字符串配对数目
题目
给你一个下标从 0 开始的数组
words，数组中包含 互不相同 的字符串。
如果字符串words[i]与字符串words[j]满足以下条件，我们称它们可以匹配：
字符串
words[i]等于words[j]的反转字符串。
0 <= i < j < words.length请你返回数组
words中的 最大 匹配数目。
注意，每个字符串最多匹配一次。示例 1：
输入： words = [“cd”,“ac”,“dc”,“ca”,“zz”] 输出： 2 解释： 在此示例中，我们可以通过以下方式匹配 2 对字符串： - 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 “dc” 并且等于 words[2]。 - 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 “ca” 并且等于 words[3]。 可以证明最多匹配数目是 2 。
示例 2：
输入： words = [“ab”,“ba”,“cc”] 输出： 1 解释： 在此示例中，我们可以通过以下方式匹配 1 对字符串： - 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串 “ab” 与 words[0] 相等。 可以证明最多匹配数目是 1 。
示例 3：
输入： words = [“aa”,“ab”] 输出： 0 解释： 这个例子中，无法匹配任何字符串。提示：
1 <= words.length <= 50
words[i].length == 2
words包含的字符串互不相同。
words[i]只包含小写英文字母。
题解
/*** @param {string[]} words* @return {number}*/
var maximumNumberOfStringPairs = function (words) {const indexMap = {};let sum = 0;for (let i = 0; i < words.length; i++) {if (indexMap[words[i]]) {sum++;} else {const [a, b] = words[i];indexMap[b + a] = true;}}return sum;
};
3158. 求出出现两次数字的 XOR 值
题目
给你一个数组
nums，数组中的数字 要么 出现一次，要么 出现两次。
请你返回数组中所有出现两次数字的按位XOR值，如果没有数字出现过两次，返回 0 。示例 1：
输入： nums = [1,2,1,3]
输出： 1
解释：
nums中唯一出现过两次的数字是 1 。
示例 2：
输入： nums = [1,2,3]
输出： 0
解释：
nums中没有数字出现两次。
示例 3：
输入： nums = [1,2,2,1]
输出： 3
解释：
数字 1 和 2 出现过两次。1 XOR 2 == 3。提示：
1 <= nums.length <= 50
1 <= nums[i] <= 50
nums中每个数字要么出现过一次，要么出现过两次。
题解
/*** @param {number[]} nums* @return {number}*/
var duplicateNumbersXOR = function (nums) {const aryMap = {};for (let i = 0; i < nums.length; i++) {let item = nums[i];if (aryMap[item]) {aryMap[item] += 1;} else {aryMap[item] = 1;}}return Object.entries(aryMap).reduce((prev, cur) => {const [key, value] = cur;return value > 1 ? prev ^ key : prev;}, 0);
};
