代码随想录

代码随想录
代码随想录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后keymap1.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 truelet array=new Array(26).fill(0);let base='a'.charCodeAt();// magazinefor(let i of magazine){let num=i.charCodeAt()-base;array[num]++;}// ransomNotefor(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:Stringlet key = array.toString();// value:Arraylet 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;// 计算pfor (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;
};