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)--棧和隊列
5、2019 算法面試相關(guān)(leetcode)--優(yōu)先隊列
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)--動態(tài)規(guī)劃(Dynamic Programming)
11矢赁、2019 算法面試相關(guān)(leetcode)--動態(tài)規(guī)劃之背包問題
遞歸算法（英語：recursion algorithm）在計算機(jī)科學(xué)中是指一種通過重復(fù)將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用于解決很多的計算機(jī)科學(xué)問題贬丛，因此它是計算機(jī)科學(xué)中十分重要的一個概念撩银。絕大多數(shù)編程語言支持函數(shù)的自調(diào)用，在這些語言中函數(shù)可以通過調(diào)用自身來進(jìn)行遞歸豺憔。計算理論可以證明遞歸的作用可以完全取代循環(huán)额获，因此在很多函數(shù)編程語言（如Scheme）中習(xí)慣用遞歸來實現(xiàn)循環(huán)。
分治算法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題恭应，這些子問題相互獨立且與原問題性質(zhì)相同抄邀。求出子問題的解，就可得到原問題的解昼榛。即一種分目標(biāo)完成程序算法境肾，簡單問題可用二分法完成。
一胆屿、 Pow(x, n)
實現(xiàn) pow(x, n) 奥喻，即計算 x 的 n 次冪函數(shù)。
示例 1:
輸入: 2.00000, 10
輸出: 1024.00000
示例 2:
輸入: 2.10000, 3
輸出: 9.26100
示例 3:
輸入: 2.00000, -2
輸出: 0.25000
解釋: 2-2 = 1/22 = 1/4 = 0.25
說明:
- -100.0 < x < 100.0
- n 是 32 位有符號整數(shù)非迹，其數(shù)值范圍是 [?231, 231 ? 1] 环鲤。
1、比較容易想的就是循環(huán)累乘
var myPow = function(x, n) {
let res = 1
if(n < 0){
x = 1/x
n = -n
}
if(x == 1) return 1
if(x == -1) return n%2 ? -1 : 1
for(let i = 0; i < n; i++){
res *= x
}
return res
};
效率并不理想彻秆，甚至?xí)瑫r楔绞。
2、我們可以嘗試用分治+遞歸算法
xn = x(n/2) * x(n/2)
var myPow = function(x, n) {
if(n == 0 || x == 1) return 1
if(n < 0) return 1/myPow(x,-n)
if(n % 2) return x*myPow(x,n - 1)
return myPow(x*x,Math.floor(n/2))
};
3唇兑、那么能不能不用遞歸呢？只用分治算法
var myPow = function(x, n) {
if(n < 0){
x = 1.0/x
n = -n
}
let res = 1
while(n){
if(n%2) res *= x
x *= x
n = Math.floor(n/2)
}
return res
};
二桦锄、 求眾數(shù)
給定一個大小為 n 的數(shù)組扎附，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素结耀。
你可以假設(shè)數(shù)組是非空的留夜，并且給定的數(shù)組總是存在眾數(shù)匙铡。
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
同樣是有多種解法
1、首先是暴力法碍粥，就是兩層嵌套鳖眼，效率是O(n2),效率很低，這里不再贅述嚼摩。
2钦讳、我們注意到，題目中有假設(shè)數(shù)組總是存在眾數(shù)
那么可以用排序法,那么數(shù)組中間那個數(shù)就一定是眾數(shù)
var majorityElement = function(nums) {
nums.sort((a,b) => a - b)
return nums[Math.floor(nums.length/2)]
};
排序時間復(fù)雜度是O(nlogn),而且還會改變數(shù)組枕面，這方法并不推薦
3愿卒、既然是計數(shù)，那么很容易想到哈希表去計數(shù)潮秘。
var majorityElement = function(nums) {
let dic = {}
for (const num of nums) {
dic[num] = (dic[num] || 0) + 1
if(dic[num] > nums.length/2) return num
}
};
這種算法時間復(fù)雜度是O(n),但因為引入了哈希表琼开，空間復(fù)雜度也是O(n)
4、摩爾投票法枕荞。既然數(shù)組一定存在眾數(shù)柜候，假設(shè)數(shù)組存在m個數(shù)字，眾數(shù)存在n個躏精，n > m/2渣刷。那么如果數(shù)組去掉一個眾數(shù)，再去掉一個其他數(shù)字玉控，眾數(shù)數(shù)目為n - 1,數(shù)組數(shù)目為m - 2飞主，n - 1 > (m - 2)/2，還是會存在眾數(shù)高诺。同樣碌识，如果我們?nèi)サ鬹個眾數(shù)，同時去掉k個其余數(shù)字虱而，剩下的數(shù)組還是會存在同樣的眾數(shù)筏餐。
var majorityElement = function(nums) {
let count = 1,res = nums[0]
for(let i = 1; i < nums.length; i++){
if(nums[i] == res) count++
else {
count --
if(count == 0){
res = nums[i]
count++
}
}
}
return res
};
該算法同樣用到了分治思想，時間復(fù)雜度O(n),空間復(fù)雜度O(1)
