2019 iOS面试题大全---全方面剖析面试
2018 iOS面试题---算法相关
1、七种常见的数组排序算法整理(C语言版本)
2、2019 算法面试相关(leetcode)--数组和链表
3、2019 算法面试相关(leetcode)--字符串
4、2019 算法面试相关(leetcode)--栈和队列
5、2019 算法面试相关(leetcode)--优先队列
6、2019 算法面试相关(leetcode)--哈希表
7、2019 算法面试相关(leetcode)--树、二叉树、二叉搜索树
8、2019 算法面试相关(leetcode)--递归与分治
9、2019 算法面试相关(leetcode)--贪心算法
10、2019 算法面试相关(leetcode)--动态规划(Dynamic Programming)
11、2019 算法面试相关(leetcode)--动态规划之背包问题
哈希表相关的原理可以参考下：
浅谈哈希表(HashTable)
深入理解哈希表
哈希表的理解
理解HashSet及使用
哈希表最突出的优点就是查找时间复杂度是o(1)，所以其应用场景多数为查找
哈希表和集合另一个特性是无重复，可以用来计数
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这道题目也是leetcode第一题,我们可以利用哈希表，在哈希表中查找是否有target-nums[i]，存在则返回，否则将nums[i]存入哈希表中
var twoSum = function(nums, target) {
let dict = {}
for (let i = 0; i < nums.length; i++) {
if ((target - nums[i]) in dict) return [dict[target-nums[i]], i]
dict[nums[i]] = i
}
};
2. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
题目意思很简单，判断两个字符串是否有同样的字符，字符以及字符的数量都要相同。
我们同样可以用哈希表来解决，现将第一个字符串的字符及数量保存到哈希表中，然后去和第二个字符串对比，完全一致则返回true否则返回false。
- 计数也是哈希表一个比较常见的使用场景
var isAnagram = function(s, t) {
let dic = {}
for (const c of s) {
dic[c] = (dic[c] || 0) + 1
}
for (const c of t) {
if(c in dic) dic[c]--
else return false
}
for (const key in dic) {
if(dic[key] != 0) return false
}
return true
};
还有一种比较简单的写法，就是分别对两个字符串分别排序然后判断是否相同,不过只是写起来简单，实际时间复杂度是o(logn)，比上边的方法效率要差一些，不建议这样写哈。
var isAnagram = function(s, t) {
return s.split('').sort().join('') == t.split('').sort().join('')
};
3. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
1.首先如果我们用暴力法的话，就是三层嵌套循环，时间复杂度为o(n^3),效率很低,leetcode执行超时
2.我们可以将a+b+c = 0转化成a + b = -c，这样就转化成了第一题两数之和了。这里同样可以用hashSet查找来去重
var threeSum = function(nums) {
nums.sort((a,b) => a - b)
let result = []
let resSet = new Set()
for (let i = 0; i < nums.length - 2; i++) {
let set = new Set()
for(let j = i + 1; j < nums.length; j++){
let target = 0-(nums[i] + nums[j])
if(set.has(target)){
let arr = [nums[i],nums[j],target]
let tmp = arr
tmp = tmp.sort().join(',')
if(!resSet.has(tmp)){
result.push(arr)
resSet.add(tmp)
}
}else set.add(nums[j])
}
}
return result
};
这种方法的时间复杂度是o(n^2),效率还是挺低。
- 3.这里可以使用双指针法。首先将数组排序(排序是为了后续方便)，遍历数组，target就是-nums[i]了，由于数组是排好序的，所以如果target小于0，就可以跳出循环了，另外由于题目要求不能有重复三元组，所以遇到相同的就不处理，继续向后循环。
然后再利用左右双指针去遍历数组，由于数组是有序的，就可以根据两个指针对应元素值与-nums[i]值相比是大还是小来决定循环的方向，循环过程中同样要跳过相同的元素，直到等于-nums[i]
var threeSum = function(nums) {
nums.sort((a,b)=>a-b)
let result = []
for (let i = 0; i < nums.length; i++) {
let target = -nums[i];
if(target < 0) break;
if(i>0 && nums[i]==nums[i-1]) continue;
let j = i + 1,k = nums.length - 1
while(j < k){
if(nums[j] + nums[k] == target){
while(j<k && nums[j] === nums[j+1])
++j;
while(j<k && nums[k] === nums[k-1])
--k;
let pushArr = [nums[i], nums[j++],nums[k--]]
result.push(pushArr)
}else if (nums[j] + nums[k] < target) {
j++;
}else {
k--;
}
}
}
return result
};
这种方法的时间复杂度同样是o(n^2),但不再需要用到set去保存，空间复杂度有优化。另外先排序的情况下会规避掉很多不必要的操作，也不需要再用set去去重，在测试用例不是特别大的情况下，实际运行起来要比上边的快不少
