2019 iOS面試題大全---全方面剖析面試
2018 iOS面試題---算法相關
1盛杰、七種常見的數(shù)組排序算法整理(C語言版本)
2飘痛、2019 算法面試相關(leetcode)--數(shù)組和鏈表
3、2019 算法面試相關(leetcode)--字符串
4、2019 算法面試相關(leetcode)--棧和隊列
5、2019 算法面試相關(leetcode)--優(yōu)先隊列
6、2019 算法面試相關(leetcode)--哈希表
7孟辑、2019 算法面試相關(leetcode)--樹、二叉樹蔫敲、二叉搜索樹
8饲嗽、2019 算法面試相關(leetcode)--遞歸與分治
9、2019 算法面試相關(leetcode)--貪心算法
10奈嘿、2019 算法面試相關(leetcode)--動態(tài)規(guī)劃(Dynamic Programming)
11貌虾、2019 算法面試相關(leetcode)--動態(tài)規(guī)劃之背包問題
哈希表相關的原理可以參考下：
淺談哈希表(HashTable)
深入理解哈希表
哈希表的理解
理解HashSet及使用
哈希表最突出的優(yōu)點就是查找時間復雜度是o(1)，所以其應用場景多數(shù)為查找
哈希表和集合另一個特性是無重復裙犹，可以用來計數(shù)
1. 兩數(shù)之和
給定一個整數(shù)數(shù)組 nums 和一個目標值 target尽狠，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)，并返回他們的數(shù)組下標叶圃。
你可以假設每種輸入只會對應一個答案袄膏。但是，你不能重復利用這個數(shù)組中同樣的元素掺冠。
示例:
給定 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 斥黑，編寫一個函數(shù)來判斷 t 是否是 s 的一個字母異位詞揖盘。
示例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:
輸入: s = "rat", t = "car"
輸出: false
說明:
你可以假設字符串只包含小寫字母。
進階:
如果輸入字符串包含 unicode 字符怎么辦锌奴？你能否調(diào)整你的解法來應對這種情況兽狭？
題目意思很簡單，判斷兩個字符串是否有同樣的字符缨叫，字符以及字符的數(shù)量都要相同椭符。
我們同樣可以用哈希表來解決，現(xiàn)將第一個字符串的字符及數(shù)量保存到哈希表中耻姥，然后去和第二個字符串對比，完全一致則返回true否則返回false有咨。
- 計數(shù)也是哈希表一個比較常見的使用場景
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. 三數(shù)之和
給定一個包含 n 個整數(shù)的數(shù)組 nums渣叛，判斷 nums 中是否存在三個元素 a丈秩，b，c 淳衙，使得 a + b + c = 0 蘑秽？找出所有滿足條件且不重復的三元組。
注意：答案中不可以包含重復的三元組箫攀。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]肠牲，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
1.首先如果我們用暴力法的話，就是三層嵌套循環(huán)靴跛，時間復雜度為o(n^3),效率很低,leetcode執(zhí)行超時
2.我們可以將a+b+c = 0轉(zhuǎn)化成a + b = -c缀雳，這樣就轉(zhuǎn)化成了第一題兩數(shù)之和了。這里同樣可以用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.這里可以使用雙指針法肥印。首先將數(shù)組排序(排序是為了后續(xù)方便)，遍歷數(shù)組绝葡，target就是-nums[i]了深碱，由于數(shù)組是排好序的，所以如果target小于0挤牛，就可以跳出循環(huán)了莹痢，另外由于題目要求不能有重復三元組，所以遇到相同的就不處理，繼續(xù)向后循環(huán)竞膳。
然后再利用左右雙指針去遍歷數(shù)組航瞭，由于數(shù)組是有序的，就可以根據(jù)兩個指針對應元素值與-nums[i]值相比是大還是小來決定循環(huán)的方向坦辟，循環(huán)過程中同樣要跳過相同的元素刊侯，直到等于-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去保存，空間復雜度有優(yōu)化锉走。另外先排序的情況下會規(guī)避掉很多不必要的操作滨彻，也不需要再用set去去重，在測試用例不是特別大的情況下挪蹭，實際運行起來要比上邊的快不少
