代码随想录
代码随想录
代码随想录CSDN官方
主要题目
242. 有效的字母异位词
242. 有效的字母异位词
var isAnagram = function (s, t) {
if (s.length !== t.length) return false;
let ss = new Array(26).fill(0);
// base 字母的Unicode编码
let base = 'a'.charCodeAt();
for (let i of s) {
ss[i.charCodeAt() - base]++;
// console.log(i.charCodeAt()-base);
}
for (let i of t) {
ss[i.charCodeAt() - base]--;
// console.log(i.charCodeAt()-base);
}
let flag = 0;
ss.forEach(function (item) {
if (item) {
flag = 1;
}
})
if (flag) return false;
return true;
};
349. 两个数组的交集
349. 两个数组的交集
// 在大的里面找小的,set1大
const setIntersection = function (set1, set2) {
if (set1.length < set2.length) {
return setIntersection(set2, set1);
}
let ans = new Set();
for (let i of set2) {
if (set1.has(i)) {
ans.add(i);
}
}
return Array.from(ans)
}
var intersection = function (nums1, nums2) {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
return setIntersection(set1, set2);
};
202. 快乐数
202. 快乐数
var isHappy = function (n) {
const happy = function (n) {
let ans = 0;
while (n) {
ans += (n % 10) ** 2;
// 要向下取整
n = Math.floor(n / 10);
}
return ans;
}
let set = new Set();
while (n != 1) {
let temp = happy(n);
if (set.has(temp)) return false;
else {
set.add(temp);
n = temp;
}
}
return true;
};
1. 两数之和(经典哈希)
1. 两数之和
var twoSum = function (nums, target) {
// key:值 value:下标
let obj = {};
for (let i = 0; i < nums.length; i++) {
let find = target - nums[i];
if (obj[find] !== undefined) {
return [i, obj[find]];
} else {
obj[nums[i]] = i;
}
}
return [];
};
454. 四数相加 II
454. 四数相加 II
一个map版:
var fourSumCount = function (nums1, nums2, nums3, nums4) {
let map1 = new Map();
for (let i of nums1) {
for (let j of nums2) {
let k = i + j;
let kk = map1.get(k) ? map1.get(k) : 0;
kk++;
map1.set(k, kk);
}
}
let ans = 0;
for (let i of nums3) {
for (let j of nums4) {
let k = i + j;
let find = 0 - k;
let temp = map1.get(find) ? map1.get(find) : 0;
ans += temp;
}
}
return ans;
};
两个map和forEach版:注意,forEach参数(value,key)
var fourSumCount = function (nums1, nums2, nums3, nums4) {
let map1 = new Map();
let map2 = new Map();
for (let i of nums1) {
for (let j of nums2) {
let k = i + j;
let kk = map1.get(k) ? map1.get(k) : 0;
kk++;
map1.set(k, kk);
}
}
for (let i of nums3) {
for (let j of nums4) {
let k = i + j;
let kk = map2.get(k) ? map2.get(k) : 0;
kk++;
map2.set(k, kk);
}
}
let ans = 0;
// 参数:先value后key
map1.forEach((value, key) => {
// value表示key出现的次数
let find = 0 - key;
if (map2.has(find)) {
ans += value * map2.get(find);
}
})
return ans;
};
15. 三数之和(双指针)
15. 三数之和
思路:来自代码随想录
var threeSum = function (nums) {
let ans = [];
// 从小到大
nums.sort((a, b) => a - b);
if (nums[0] > 0) return ans;
for (let i = 0; i < nums.length; i++) {
let l = i + 1, r = nums.length - 1;
if (i && nums[i] === nums[i - 1]) continue;
while (l < r) {
let sum = nums[i] + nums[l] + nums[r];
if (sum > 0) r--;
else if (sum < 0) l++;
else {
ans.push([nums[i], nums[l], nums[r]]);
// 去重
while (l < r && nums[l] === nums[l + 1]) {
l++;
}
while (l < r && nums[r] === nums[r - 1]) {
r--;
}
l++, r--;
}
}
}
return ans;
};
18. 四数之和(双指针)
18. 四数之和
var fourSum = function (nums, target) {
let ans = [];
const len = nums.length;
if (len < 4) return ans;
nums.sort((a, b) => a - b);
for (let i = 0; i < len - 3; i++) {
if (i && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < len - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let l = j + 1, r = len - 1;
while (l < r) {
let sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum < target) {
l++;
} else if (sum > target) {
r--;
} else {
ans.push([nums[i], nums[j], nums[l], nums[r]]);
// 去重
while (l < r && nums[l] === nums[l + 1]) {
l++;
}
while (l < r && nums[r] === nums[r - 1]) {
r--;
}
l++; r--;
}
}
}
}
return ans;
};
相关题目
是和主要题目类似的题目。
383. 赎金信
383. 赎金信
var canConstruct = function(ransomNote, magazine) {
// 如果magazine>=ransomNote true
let array=new Array(26).fill(0);
let base='a'.charCodeAt();
// magazine
for(let i of magazine){
let num=i.charCodeAt()-base;
array[num]++;
}
// ransomNote
for(let i of ransomNote){
let num=i.charCodeAt()-base;
array[num]--;
}
let flag=0;
array.forEach(function(item){
if(item<0){
flag=1;
}
})
if(flag) return false;
return true;
};
49. 字母异位词分组(Array,Map的运用)
49. 字母异位词分组
- 把每个字符串str转换为数组(
Array.from
)
- 数组排序,得到唯一的key
- 找到对应的value,添加当前的str
- 把最后的map转换为array
- 要熟练运用Array和Map
var groupAnagrams = function (strs) {
const map = new Map();
for (let str of strs) {
// 把str字符串变成数组
let array = Array.from(str);
array.sort();
// key:String
let key = array.toString();
// value:Array
let value = map.get(key) ? map.get(key) : new Array();
value.push(str);
map.set(key, value);
}
return Array.from(map.values());
};
438. 找到字符串中所有字母异位词(滑动窗口)
438. 找到字符串中所有字母异位词
var findAnagrams = function (s, p) {
if (s.length < p.length) return [];
var compare = function (ss, pp) {
for (let i = 0; i < 26; i++) {
if (ss[i] != pp[i]) {
return false;
}
}
return true;
}
// s长p短
let pp = new Array(26).fill(0);
let ss = new Array(26).fill(0);
let ans = new Array();
// j 慢指针
let j = 0;
// 计算p
for (let char of p) {
pp[char.charCodeAt() - 'a'.charCodeAt()]++;
}
const sl = s.length, pl = p.length;
for (let i = 0; i < pl; i++) {
let char = s[i];
ss[char.charCodeAt() - 'a'.charCodeAt()]++;
}
if (compare(ss, pp)) {
ans.push(0);
}
for (let i = pl; i < sl; i++, j++) {
let char = s[i];
ss[char.charCodeAt() - 'a'.charCodeAt()]++;
char = s[j];
ss[char.charCodeAt() - 'a'.charCodeAt()]--;
if (compare(ss, pp)) {
ans.push(j + 1);
}
}
return ans;
};
350. 两个数组的交集 II
350. 两个数组的交集 II
var intersect = function (nums1, nums2) {
let a1 = new Array(1001).fill(0);
let a2 = new Array(1001).fill(0);
for (let i = 0; i < nums1.length; i++) {
a1[nums1[i]]++;
}
for (let i = 0; i < nums2.length; i++) {
a2[nums2[i]]++;
}
let ans = new Array();
for (let i = 0; i <= 1000; i++) {
if (a1[i] && a2[i]) {
let num = Math.min(a1[i], a2[i]);
for (let j = 0; j < num; j++) {
ans.push(i);
}
}
}
return ans;
};