1、哈希表+计数类型

1.1、判断是否存在重复元素

给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

解决思路
遍历数组时，经过数组中的每一项就往 map 中添加，比如 [1, 2, 3, 1]。
第一项：遍历到第一个1时，对象返回 { 1: 1 }，代表 1 出现 1 次。
第二项：遍历到 2 时，返回 { 1: 1, 2: 1 }。
第三项：遍历到 3 时，返回 { 1: 1, 2: 1, 3: 1 }。
第四项：遍历到第二个 1 时，发现原来的对象里已经有 1 了，返回 false。

const containsDuplicate = function(nums) {	let map = new Map();    for (let i of nums) {		if (map.has(i)) {			return true;        } else {            map.set(i, 1);        }    }    return false;};console.log(containsDuplicate([2, 6, 3, 9, 3])); // trueconsole.log(containsDuplicate([2, 6, 3, 9, 7])); // false

1.2、字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

解决思路
遍历字符串，用一个对象 {} 来记数，出现过一次就 +1，遍历完毕，再次遍历字符串，看它们在之前记录的对象里的值，是否是 1，是就返回下标，不是返回 -1。

var firstUniqChar = function(str) {	const map = {};	for (let v of str) map[v] = (map[v] || 0) + 1;	for (let i = 0; i < str.length; i++) if (map[str[i]] === 1) return i;	return -1;};console.log(firstUniqChar("leetcode")); // 0console.log(firstUniqChar("loveleetcode")); // 2

1.3、有效的字母异位词

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

解决思路
声明计数器，一个对象 const obj = {}。遍历 s 字符串，如果遍历到字符串的 ‘a’ 字母，去看 obj[a] 是否存在，不存在说明第一次遍历到 a 字母，那么初始化 obj[a] = 1，如果存在则 obj[a] += 1。t 字符串同理，它每次减 1，遍历完 s 字符串后，遍历 obj 对象，看它的每一对 key: value，是否 value 都是 0。

var isAnagram = function (s, t) {	const sLen = s.length;	const tLen = t.length;	if (sLen !== tLen ) {		return false;	}	const obj = {};	for (let i = 0 ; i < sLen ; i++) {		const currentS = s[i];		const currentT = t[i];		obj[currentS] ? obj[currentS]++ : obj[currentS] = 1;		obj[currentT] ? obj[currentT]-- : obj[currentT] = -1;	}	return Object.values(obj).every(v => v === 0);};console.log(isAnagram("anagram", "nagaram")); // trueconsole.log(isAnagram("rat", "car")); // false

1.4、多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 n/2 的元素。可以假设数组是非空的，并且给定的数组总是存在多数元素。

解决思路
1、声明一个计数器，也就是一个对象 const map = {}。
2、遍历字符串，开始记数，如果字符串的字母第一次碰见，map[第一次碰见的字母] = 1。
3、如果 map 已经记录过这个字母，则 map[记录过的的字母] += 1。
4、在遍历的过程中，看 map[记录过的的字母] 是否大于数组总长度/2。

var majorityElement = function (nums) {	const map = {};	const n = nums.length >> 1; // >>右移运算符，意思是除以2	for (let i = 0; i < nums.length; i++) {		map[nums[i]] = map[nums[i]] !== undefined ? map[nums[i]] + 1 : 1;		if(map[nums[i]] > n) return nums[i];	}};console.log(majorityElement([3, 2, 3])); // 3console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2

1.5、只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。

算法应该具有线性时间复杂度，可以不使用额外空间来实现。

解决思路一
用 map 记录一遍，类似这样的代码，最后再遍历一次 countMap，然后看谁的次数是 1，就解决了。

const countMap = {};array.forEach((item) => { 	countMap[item] ? countMap[item] += 1 : countMap[item] = 1;});

解决思路二
用异或运算符，先看异或运算符有啥用，异或运算符 ^，了解一下这个运算符的功能。
1、任何数和自己做异或运算，结果为 0，即 a^a = 0。
2、任何数和 0 做异或运算，结果还是自己，即 a^0 = a。
3、异或运算中，满足交换律和结合律，也就是 a^b^a = b^a^a = b^(a^a) = b^0 = b。

var singleNumber = function (nums) {	let init = nums[0],		i = 1;	for (; i < nums.length; i++) {		init ^=  nums[i];	}	return init;};console.log(singleNumber([2, 2, 1])); // 1console.log(singleNumber([4,1,2,1,2])); // 4

1.6、位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 1 的个数（也被称为汉明重量）。

解决思路
计算个数，按照思路，把整个数字转为字符串，类似这样，数字 0001 => String(0001) => ‘0001’ => 遍历看 1 的个数。然后直接遍历计算就可以了。

var hammingWeight = function (n) {	let ret = 0;    while (n) {        n &= (n - 1);        ret++;    }    return ret;};console.log(hammingWeight(00000000000000000000000000001011)); // 3console.log(hammingWeight(00000000000000000000000010000000)); // 1

原理

每执行一次 x = x & (x-1)，会将 x 用二进制表示时最右边的一个 1 变为 0，因为 x-1 会将该位（x 用二进制表示时最右边的一个 1）变为 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的二进制数中的 1 的数目。

2、哈希表+映射功能

哈希表有一个非常常见的功能就是建立映射关系，比如说设计模式里的策略模式，思路是一样的，映射表常常见于后端的枚举类型，typescript 也是一样。

示例

// 后端只会返回 0, 1, 2const TYPE = {	2: "orange",	1: "red",	0: "blue"};// 前端使用 console.log(TYPE[0]); // orangeconsole.log(TYPE[1]); // redconsole.log(TYPE[2]); // blue

2.1、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。可以按任意顺序返回答案。

解决思路
用 hashMap 存储遍历过的元素和对应的索引。每遍历一个元素，看看 hashMap 中是否存在满足要求的目标数字。所有事情在一次遍历中完成（用了空间换取时间）。

var twoSum = function (nums, target) {	const map = new Map();    for (let i = 0, len = nums.length; i < len; i++) {		if (map.get(nums[i]) !== undefined) {			return [map.get(nums[i]), i];        } else {			map.set(target - nums[i], i);        }    }    return [];};console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]console.log(twoSum([3, 2, 4], 6)); // [1, 2]console.log(twoSum([3, 3], 6)); // [0, 1]

2.2、两数组交集1

给定两个数组，编写一个函数来计算它们的交集。

说明
输出结果中的每个元素一定是唯一的。可以不考虑输出结果的顺序。

解决思路一
可以用 set，很简单，但是空间复杂度和时间复杂度都太高，不太优雅。

var intersection = function (nums1, nums2) {	return result = [...new Set(nums1)].filter(item => new Set(nums2).has(item));};console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [4, 9]

解决思路二
可以用 map 来做，时间和空间复杂度都低很多，用一个 map 去存 nums1 数组里的每一项，类似 map[nums1[i]] = true，然后去遍历 nums2，如果在 map 中已经有的值，类似 map[nums2[i]]，就把它 push 到一个数组里。并且将 map[nums2[i]] 设为 false，后面有相同的值就不 push 到数组里了。

var intersection = function (nums1, nums2) {	const map = {},		ret = [];    for (let i = 0; i < nums1.length; i++) {        map[nums1[i]] = true;    }    for (let i = 0; i < nums2.length; i++) {        if (map[nums2[i]]) {            ret.push(nums2[i]);            map[nums2[i]] = false;        }    }    return ret;};console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [4, 9]

3、找规律题

一般画个图或者稍微分析一下就能得出结果。

3.1、罗马数字转整数

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

解释
L = 50, V= 5, III = 3。

解决思路
这些案例的规律，就是把 map 表里面对应的数字加起来。比如说，LVIII = L（对应 map 表 50）+ V（对应 map 表5）+ I（对应 map 表1）+ I（对应 map 表1）+ I（对应 map 表1），所以，就是遍历数字把对应的值加起来。

var romanToInt = function (s) {	const map = {        I: 1,        V: 5,        IV: 4,        IX: 9,        X: 10,        XL: 40,        XC: 90,        L: 50,        C: 100,        CD: 400,        CM: 900,        D: 500,        M: 1000,    }    let res = 0,    	index = 0,    	len = s.length;    while (index < len) {        if (index + 1 < len && map[s.slice(index, index+2)]) {            res += map[s.slice(index, index+2)];            index += 2;        } else {            res += map[s.slice(index, index+1)];            index += 1;        }    }    return res;};console.log(romanToInt("III")); // 3console.log(romanToInt("IV")); // 4console.log(romanToInt("IX")); // 9console.log(romanToInt("LVIII")); // 58

3.2、最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。

提示
0 <= strs.length <= 200。0 <= strs[i].length <= 200。strs[i] 仅由小写英文字母组成。

解决思路
假如求数组里 3 个元素的最长公共前缀。
1、先拿前两个比较，求出他们两个的最长公共前缀。
2、然后上面求出的结果去跟第三个元素求最长公共前缀。
3、n 个元素就一直这么 reduce 下去。

// 这个是求出两个元素最长公共前缀的方法var longestCommonPrefix = function (strs) {	if (strs.length === 0) return "";	if (strs.length === 1) return strs[0];	return strs.reduce(getSameStr, strs[0]);};function getSameStr
                 

                                                                                                                    
                         idc机房托管
                                             
                         云服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               前端基础js笔试题
                                                                                                           js代码片段
                                                                                                           笔试题
                                                                                                           前端笔试题