“不積跬步审磁，無以至千里谈飒；不積小流，無以成江毫ν迹”
算法的重要性我就不說了，不論是平時(shí)的項(xiàng)目中還是找工作的面試過程中掺逼，算法都是必不可少的吃媒，同時(shí)算法可以鍛煉我們的思維邏輯能力以及解決問題的能力。
今天開始我就會(huì)從各類書籍以及博客等挑選出優(yōu)質(zhì)的算法題與大家分享，從簡到難赘那，在練習(xí)算法的同時(shí)刑桑，我也會(huì)對算法中運(yùn)用的知識點(diǎn)進(jìn)行整理，與大家共同學(xué)習(xí)成長募舟，只要我們每天抽出半個(gè)小時(shí)到一個(gè)小時(shí)的時(shí)間去學(xué)習(xí)祠斧、整理、以及反思拱礁，我相信一段時(shí)間過后你會(huì)成長很多琢锋。
目錄
1. 給出一個(gè)整形數(shù)組和一個(gè)目標(biāo)值，判斷數(shù)組中是否有兩個(gè)數(shù)之和等于目標(biāo)值呢灶。
2. 利用遞歸算法求1到n的和
3. 不借用第三個(gè)變量吴超，如何交換兩個(gè)變量的值？（變量a鸯乃，b）
1. 給出一個(gè)整形數(shù)組和一個(gè)目標(biāo)值鲸阻，判斷數(shù)組中是否有兩個(gè)數(shù)之和等于目標(biāo)值。
法一：很多人可能搭眼一看就能想到每次選中一個(gè)數(shù)缨睡，然后遍歷整個(gè)數(shù)組判斷有沒有一個(gè)數(shù)相加之和等于目標(biāo)值鸟悴。但是這種方法的時(shí)間復(fù)雜度為O(n2)，太復(fù)雜奖年，所以我們需要找到更好的方法優(yōu)化時(shí)間復(fù)雜度细诸。
法二：我們可以利用集合處理這次問題，在遍歷數(shù)組的過程中拾并，我們利用字典保存當(dāng)前值揍堰，假如字典中存在一個(gè)數(shù)等于目標(biāo)值減去當(dāng)前值，那么可以證明整個(gè)遍歷中一定有兩個(gè)數(shù)之和等于目標(biāo)值嗅义。你可以這種方法的時(shí)間復(fù)雜度為O(n)屏歹。
代碼：
func judgeTwoNums(numsArr: [Int], targetValue: Int) -> Bool {
var set = Set<Int>()
for num in numsArr {
if set.contains(targetValue - num) {
return true
}
set.insert(num)
print("有兩個(gè)數(shù)之和等于目標(biāo)值")
}
return false
}
拓展：
給定一個(gè)整形數(shù)組中有且僅有兩個(gè)數(shù)之和等于目標(biāo)值，求這兩個(gè)數(shù)在數(shù)組中的序號之碗。
此題的思路跟上面題的思路基本相似蝙眶，不同之處是此題需要得到兩個(gè)數(shù)在數(shù)組中的序號，所以不能使用集合(排列無序)來解決這個(gè)問題褪那，為了方便得到序列號幽纷，我們使用字典來解決這個(gè)問題。時(shí)間的復(fù)雜度為O(n)博敬。
func judgeTwoNum(numsArr: [Int], targetValue: Int) -> [Int] {
var dict = [Int: Int]()
for (i, num) in numsArr.enumerated() {
if let index = dict[targetValue - num] {
return [index, i]
} else {
dict[num] = i
}
}
return []
}
知識點(diǎn)：
集合(set)：用來存儲(chǔ)沒有固定順序友浸、類型相同且不重復(fù)的值。
2. 利用遞歸算法求1到n的和
所謂遞歸偏窝，簡單點(diǎn)來說收恢，就是一個(gè)函數(shù)直接或間接調(diào)用自身的一種方法武学，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。
// MARK: 遞歸算法
func sum(n: Int) -> Int {
var result: Int
if n == 0 {
return 0
} else if n == 1 {
return 1
} else {
result = sum(n: (n - 1)) + n
return result
}
}
3. 不借用第三個(gè)變量伦意，如何交換兩個(gè)變量的值火窒？（變量a，b）
法一：
a = a + b
b = a- b --> b = (a + b) - b --> b = a
a= a- b --> a = (a + b) - b(此時(shí)b=a) --> a = b
a = a - b
b = a + b --> (a - b) + b --> b = a
a = a + b --> (a - b) + b(此時(shí)b=a) --> a= b
法二（按位異或）：
參加運(yùn)算的兩個(gè)數(shù)驮肉，換算為二進(jìn)制(0熏矿、1)后，進(jìn)行異或運(yùn)算离钝。只有當(dāng)相應(yīng)位上的數(shù)字不相同時(shí)票编，該為才取1，若相同奈辰，即為0栏妖。任何數(shù)與0異或，結(jié)果都是其本身奖恰。
a = a ^ b
b = b ^ a
a = a ^ b
