哈希表与字符串
1、最长回文串409
给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。
在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
示例 1:
输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
思路: 字符数量为偶数,count+数量;字符数量为奇数,count+数量-1 flag=1;flag代表的是是否有中心节点,最终长度max_length=count+flag.
/**
* @param {string} s
* @return {number}
*/
var longestPalindrome = function(s) {
let map = new Map();
for(let i = 0;i < s.length;i++){
map.set(s[i], (map.get(s[i]) ?? 0) + 1)
}
let count = 0;
let max_length = 0;
let flag = 0;
map.forEach((item,index)=>{
if(item % 2 === 0){
count += item
}else{
count += item - 1;
flag = 1;
}
})
max_length = count+flag;
return max_length;
};
2、单词规律290
给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", s = "dog cat cat dog"
输出: true
思路: 先把字符串str分割成数组,用map映射记录dog->a的映射,若dog没有出现过并且pattern[i]没有被使用过,就保存映射并标记pattern[i],把pattern[i] push到数组used中,用来记录是否使用过。如果map映射中不存在并且pattern[i]被标记了,返回false,如果map映射存在并且map映射对应的值和pattern[i]不相等,返回false。两个数组长度不等也返回false。
/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function(pattern, s) {
let map = new Map();
let used = [];
s = s.split(' ')
if(pattern.length!==s.length){
return false;
}
for(let i = 0;i < s.length;i++){
if(!map.get(s[i])&&!used.includes(pattern[i])){
map.set(s[i],pattern[i]);
used.push(pattern[i]);
}
if(!map.get(s[i])&&used.includes(pattern[i])){
return false;
}
if(map.get(s[i])&&map.get(s[i])!==pattern[i]){
return false;
}
}
return true;
};
3、字母异位词分组49
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
思路: 给字符串排序后,用排序后的作为key,把字符串作为value,用[]数组存储。
var groupAnagrams = function(strs) {
let map = new Map();
let result = [];
for(let i = 0;i < strs.length;i++){
//使用排序后的字符串作为map的键
let sortStr = strs[i].split('').sort().join('');//把字符串按ascii码排序,先转为数组,再排序,再转为字符串
if(!map.get(sortStr)){
map.set(sortStr,[]);
}
map.get(sortStr).push(strs[i])
}
map.forEach((item)=>{
result.push(item)
})
return result
};
4、无重复字符的最长子串3
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
思路: 指针向后扫描每个字符,用map记录字符的数量。如果word中没有出现过该字符,对word进行push,并且检查result的值是否需要更新。如果word中出现过该字符,就向前移动begin指针,更新map中该字符的数量,直到数量为1.更新word字符串,将word赋值为begin到i之间的字符自出子串。
在整个过程中,使用begin和i维护一个窗口,该窗口中的子串满足题目条件(无重复的字符),窗口线性向前滑动,整体时间复杂度为O(n)
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let word = '';//最长子串
let result = 0;//记录最大字符数量
let begin = 0;
let map = new Map();//map用来记录某个字符出现的次数,如果次数大于1,就重复
for(let i = 0;i < s.length;i++){
map.set(s[i],(map.get(s[i])??0)+1);
if(map.get(s[i])===1){
word += s[i];
if(result < word.length){
result = word.length;
}
}else{
while(begin < i&&map.get(s[i]) > 1){
map.set(s[begin],map.get(s[begin])-1);
begin++;
}
word = '';
for(let j = begin;j<=i;j++){
word += s[j];
}
}
}
return result
};