刷題思路:
- 判斷數(shù)據(jù)的合法性, 過(guò)濾掉非法的情況
- 確定循環(huán)跳出條件, 要么找到了(標(biāo)記位置),要么找不到(跳出循環(huán))
- 難點(diǎn)在于邊界的判定,搞清楚邊界條件
題目1:
給定?個(gè)按照升序排列的整數(shù)數(shù)組 nums邪码，和?個(gè)?標(biāo)值 target嗽上，找出給定?標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié) 束位置。如果數(shù)組中不存在?標(biāo)值 target，返回 [-1, -1]奈虾。
示例 1：
輸?：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
示例 2：
輸?：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
解法:
func getNumber(array:[Int], target: Int) ->(Int, Int) {
//不滿足情況 返回
if array.count == 0 ||
array.first! > target ||
array.last! < target {
return (-1, -1)
}
var L = 0, R = array.count - 1, idx = R / 2
while array[idx] != target { //循環(huán)條件
if L + 1 == R { return (-1, -1) }//臨近邊界,找不到的情況
if array[idx] > target {
R = idx
} else {
L = idx
}
idx = (L + R) / 2
}
var tmpIdx = idx//暫存下標(biāo)值
while L < idx - 1 && array[idx - 1] == target {//向左搜索
idx -= 1
}
while R > tmpIdx + 1 && array[tmpIdx + 1] == target {//向右搜索
tmpIdx += 1
}
return (idx, tmpIdx)
}
print(getNumber(array: [5,7,7,8,8,8,10,11,12,12,12,12,12,12,12,13,13,13,13], target: 12))
題目2:
給定有 n 個(gè)元素的升序整型數(shù)組 nums 和?個(gè)?標(biāo)值 target，寫?個(gè)函數(shù)搜索 nums 中的 target笼沥，如果? 標(biāo)值存在返回下標(biāo)铣揉，否則返回 -1。
輸?：nums = [-1,0,3,5,9,12], target = 9
輸出：4
解釋：9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2：
輸?：nums = [-1,0,3,5,9,12], target = 2
輸出：-1
解釋：2 不存在 nums 中因此返回 -1
解法:
func search(array:[Int], target: Int) -> Int {
var L = 0 , R = array.count - 1
while L <= R {
let idx = (L + R) / 2
if target == array[idx] {
return idx
} else if target < array[idx] {
R = idx - 1
} else {//target > array[idx]
L = idx + 1
}
}
return -1
}
print(search(array: [1,3,5,7,9], target: 1))
題目3:
計(jì)算非波拉切數(shù)列
1, 1, 2, 3, 5, 8, 13, 12....
解法:
//計(jì)算非波拉切數(shù)列
//方法1:
func fib(n: Int) -> Int {
//創(chuàng)建一個(gè)數(shù)組保存 n-1之和
var mem = [1,1]
return calc(mem: &mem, n: n)
}
//1, 1, 2, 3, 5, 8, 13, 21
@discardableResult
func calc(mem : inout [Int], n: Int) -> Int {
//濾
if n < 0 { return 0 }
//限
if mem.count > n { return mem[n] }
//定
mem.append( calc(mem: &mem, n: n - 1) + calc(mem: &mem, n: n - 2))//求第 n 項(xiàng)的非波拉切數(shù)列
//查
return mem[n]
}
//方法2: 自底向上推
func fibDp(n: Int) -> Int {
if n < 0 {return 0}
var list = [1, 1]
if n < 2 { return list[n] }
for i in 2...n {
let n = list[i - 1] + list[i - 2]
list.append(n)
}
return list[n]
}
//方法3: 獲取第 n 項(xiàng)的值,其實(shí)只要獲取前兩項(xiàng)的就可以了, 于是創(chuàng)建兩個(gè)變量,分別保存前兩個(gè)的值
func fibProMax(n: Int) -> Int {
if n < 0 {return 0}
var pre_1 = 1, pre_2 = 1
if n < 2 { return 1 }
for _ in 2...n {
let cur = pre_1 + pre_2
pre_2 = pre_1
pre_1 = cur
}
return pre_1
}
//print(fib(n: -1))
//--------------------------
//前 n 項(xiàng)非波拉切數(shù)列之和
func fibSum(n: Int) -> Int {
if n <= 0 {return 0}
var total = 0
for i in 0...n - 1 {
total += fib(n: i)
}
return total
}
print(fibSum(n: 5))
題目4: 湊零錢問(wèn)題
給你 k 種面值的硬幣蛾魄，面值分別為 c1, c2 ... ck虑瀑，每種硬幣的數(shù)量無(wú)限，再給一個(gè)總金額 amount滴须，問(wèn)你最少需要幾枚硬幣湊出這個(gè)金額舌狗，如果不可能湊出，算法返回 -1 描馅。
比如說(shuō) k = 3把夸，面值分別為 1，2铭污，5恋日，總金額 amount = 11。那么最少需要 3 枚硬幣湊出嘹狞，即 11 = 5 + 5 + 1岂膳。
/*
動(dòng)態(tài)規(guī)劃, 尋找最優(yōu)子問(wèn)題
*/
var mem = [Int]()
/// 計(jì)算最少硬幣的個(gè)數(shù)
/// - Parameters:
/// - coins: 不同面值硬幣的數(shù)組
/// - amount: 需要湊出的金額
/// - Returns: 需要最少的硬幣個(gè)數(shù), -1表示湊不出
func coinChange(coins:[UInt], amount:UInt) -> Int {
mem = Array(repeating: -222, count: Int(amount) + 1)
return coinDp(coins: coins, amount: amount)
}
func coinDp(coins:[UInt], amount:UInt) -> Int {
//濾
if amount == 0 {return 0}
if mem[Int(amount)] != -222 {//這個(gè)值已經(jīng)有了不用再算一遍
return mem[Int(amount)]
}
//限
var res = Int.max
coins.forEach({
if amount >= $0 {//因?yàn)閍mount是無(wú)符號(hào)整形, 所以我要保證 amount - $0 是非負(fù)數(shù)
let subProblem = coinDp(coins: coins, amount: amount - $0)
if subProblem != -1 {//找到了的情況
res = Swift.min(res, subProblem + 1)//返回的是最少的硬幣個(gè)數(shù)
}
}
})
mem[Int(amount)] = res == Int.max ? -1 : res
return mem[Int(amount)]
}
//print(coinChange(coins: [3,5,7,9], amount: 13))
快速排序 相當(dāng)于前序遍歷(先遍歷根節(jié)點(diǎn),再遍歷左右節(jié)點(diǎn))
/*
快速排序
*/
func fastSort(array: inout [Int], target: Int) {
sort(array: &array, L: 0, R: array.count - 1)
}
func sort(array: inout [Int], L: Int, R: Int) {
//濾
if L > R {return }
var j = R,i = L, base = array[L]
while i < j {
while i < j && array[j] >= base {
j -= 1
}
while i < j && array[i] <= base {
i += 1
}
if i < j {
array.swapAt(i, j)
}
}
array.swapAt(L, i)//此時(shí) i == j
sort(array: &array, L: L, R: j - 1)
sort(array: &array, L: i + 1, R: R)
}
var tmpArr = [3,2,3,1,2,4,5,5,6]
fastSort(array: &tmpArr, target: 4)
print(tmpArr[tmpArr.count - 4])
