2019 iOS面試題大全---全方面剖析面試
2018 iOS面試題---算法相關(guān)
1、七種常見的數(shù)組排序算法整理(C語言版本)
2、2019 算法面試相關(guān)(leetcode)--數(shù)組和鏈表
3、2019 算法面試相關(guān)(leetcode)--字符串
4、2019 算法面試相關(guān)(leetcode)--棧和隊(duì)列
5、2019 算法面試相關(guān)(leetcode)--優(yōu)先隊(duì)列
6、2019 算法面試相關(guān)(leetcode)--哈希表
7、2019 算法面試相關(guān)(leetcode)--樹、二叉樹、二叉搜索樹
8、2019 算法面試相關(guān)(leetcode)--遞歸與分治
9、2019 算法面試相關(guān)(leetcode)--貪心算法
10、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃(Dynamic Programming)
11、2019 算法面試相關(guān)(leetcode)--動(dòng)態(tài)規(guī)劃之背包問題
哈希表相關(guān)的原理可以參考下：
淺談哈希表(HashTable)
深入理解哈希表
哈希表的理解
理解HashSet及使用
哈希表最突出的優(yōu)點(diǎn)就是查找時(shí)間復(fù)雜度是o(1)，所以其應(yīng)用場(chǎng)景多數(shù)為查找
哈希表和集合另一個(gè)特性是無重復(fù)，可以用來計(jì)數(shù)
1. 兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?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. 有效的字母異位詞
給定兩個(gè)字符串 s 和 t ，編寫一個(gè)函數(shù)來判斷 t 是否是 s 的一個(gè)字母異位詞。
示例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:
輸入: s = "rat", t = "car"
輸出: false
說明:
你可以假設(shè)字符串只包含小寫字母。
進(jìn)階:
如果輸入字符串包含 unicode 字符怎么辦？你能否調(diào)整你的解法來應(yīng)對(duì)這種情況？
題目意思很簡(jiǎn)單，判斷兩個(gè)字符串是否有同樣的字符，字符以及字符的數(shù)量都要相同。
我們同樣可以用哈希表來解決，現(xiàn)將第一個(gè)字符串的字符及數(shù)量保存到哈希表中，然后去和第二個(gè)字符串對(duì)比，完全一致則返回true否則返回false。
- 計(jì)數(shù)也是哈希表一個(gè)比較常見的使用場(chǎng)景
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
};
還有一種比較簡(jiǎn)單的寫法，就是分別對(duì)兩個(gè)字符串分別排序然后判斷是否相同,不過只是寫起來簡(jiǎn)單，實(shí)際時(shí)間復(fù)雜度是o(logn)，比上邊的方法效率要差一些，不建議這樣寫哈。
var isAnagram = function(s, t) {
return s.split('').sort().join('') == t.split('').sort().join('')
};
3. 三數(shù)之和
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
1.首先如果我們用暴力法的話，就是三層嵌套循環(huán)，時(shí)間復(fù)雜度為o(n^3),效率很低,leetcode執(zhí)行超時(shí)
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
};
這種方法的時(shí)間復(fù)雜度是o(n^2),效率還是挺低。
- 3.這里可以使用雙指針法。首先將數(shù)組排序(排序是為了后續(xù)方便)，遍歷數(shù)組，target就是-nums[i]了，由于數(shù)組是排好序的，所以如果target小于0，就可以跳出循環(huán)了，另外由于題目要求不能有重復(fù)三元組，所以遇到相同的就不處理，繼續(xù)向后循環(huán)。
然后再利用左右雙指針去遍歷數(shù)組，由于數(shù)組是有序的，就可以根據(jù)兩個(gè)指針對(duì)應(yīng)元素值與-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
};
這種方法的時(shí)間復(fù)雜度同樣是o(n^2),但不再需要用到set去保存，空間復(fù)雜度有優(yōu)化。另外先排序的情況下會(huì)規(guī)避掉很多不必要的操作，也不需要再用set去去重，在測(cè)試用例不是特別大的情況下，實(shí)際運(yùn)行起來要比上邊的快不少
