前言
道長(zhǎng)和唐巧的面試之道,剛出來第一時(shí)間就入手了,也是趁著公司目前不是很忙,能好好靜下心來細(xì)讀這本書.筆者認(rèn)為這本書的最大亮點(diǎn)就在第二章的算法基礎(chǔ),所以想通過筆記的形式來記錄算法的學(xué)習(xí)過程,同時(shí)在忘記的時(shí)候也能第一時(shí)間翻閱查看.
這部分代碼都是通過Swift來講解的,所以對(duì)于想學(xué)習(xí)Swift的初學(xué)者來說也是不錯(cuò)的.在本章算法題筆者簡(jiǎn)單的分析了下,需要看詳細(xì)的大家可以選擇購買原書學(xué)習(xí).
1 字典和集合:給出一個(gè)整型數(shù)組和一個(gè)目標(biāo)值,判斷數(shù)組中是否有兩個(gè)數(shù)之和等于目標(biāo)值.
這種題是LeetCode上比較基礎(chǔ)的題,書上關(guān)于這題swift的代碼也是比較簡(jiǎn)單.
func twoSum (nums: [Int], _ target: Int) -> Bool {
//初始化集合
var set = Set<Int>()
//遍歷整型數(shù)組
for num in nums {
//判斷集合中是否包含目標(biāo)值減去當(dāng)前值的結(jié)果
if set.contains(target - num) {
//包含 返回true
return true
}
//不包含 將當(dāng)前值存進(jìn)集合 用作下次判斷
set.insert(num)
}
//都不包含 返回fasle
return false
}
這種方法的時(shí)間復(fù)雜度為O(n),較選中一個(gè)數(shù)然后遍歷整個(gè)數(shù)組這種復(fù)雜度為O(n^2)的方法要好很多.
1.2:在這道題的基礎(chǔ)上做修改:給定一個(gè)整型數(shù)組中有且僅有 兩個(gè)數(shù)之和等于目標(biāo)值,求這兩個(gè)數(shù)在數(shù)組中的序號(hào).
書中的方法為了方便得到序列號(hào),使用了字典,看代碼
func twoSum (nums: [Int], _ target: Int) -> [Int] {
//初始化字典
var dict = [Int: Int]()
//通過索引i 和對(duì)應(yīng)的num進(jìn)行判斷
for (i,num) in nums.enumerated() {
//從dict字典中取出之前保存的索引,判斷是否存在索引值
if let lastIndex = dict[target - num] {
//返回之前存的索引和當(dāng)前索引
return [lastIndex, i]
}else {
//保存當(dāng)前索引,用于后續(xù)判斷
dict[num] = i
}
}
//致命錯(cuò)誤來中止程序
fatalError("No valid output!")
}
巧妙的用到了字典的特性,用key表示數(shù)組的值,通過判斷字典中是否含有目標(biāo)值的key來取出索引.
2 字符串:給出一個(gè)字符串,要求將其按照單詞順序進(jìn)行反轉(zhuǎn).
eg:如果是"hello world",那么反轉(zhuǎn)后的結(jié)果就是"world hello",這個(gè)題比較常規(guī)了,但是要注意空格的特殊處理.看代碼:
fileprivate func _reverse<T>(_ chars: inout[T], _ start: Int, _ end: Int) {
//接收字符串反轉(zhuǎn)起始,結(jié)束位置
var start = start, end = end
//判斷反轉(zhuǎn)字符串的位置
while start < end {
//start end位置 字符互換
swap(&chars, start, end)
//往中間位置靠攏
start += 1
end -= 1
}
}
fileprivate func swap<T>(_ chars: inout[T], _ p: Int, _ q: Int){
//將p,q字符 位置進(jìn)行互換 這種寫法也是swift里的一大亮點(diǎn)
(chars[p], chars[q]) = (chars[q], chars[p])
}
上面方法是實(shí)現(xiàn)了字符串的反轉(zhuǎn),再來看下每個(gè)單詞的單獨(dú)反轉(zhuǎn).需要注意的是單詞的反轉(zhuǎn)需要對(duì)空格進(jìn)行判斷,來看完整實(shí)現(xiàn)代碼.
func reverseWords(s: String?) -> String? {
//判斷入?yún)是否有值
guard let s = s else {
return nil
}
//將字符串s分割成字符數(shù)組
var chars = Array(s.characters), start = 0
//反轉(zhuǎn)chars字符數(shù)組
_reverse(&chars, start, chars.count - 1)
for i in 0 ..< chars.count {
//當(dāng)i等于 數(shù)組最后一位 或者 遇到空格時(shí)反轉(zhuǎn)字符串
if i == chars.count - 1 || chars[i + 1] == " " {
//將每個(gè)單獨(dú)的單詞進(jìn)行反轉(zhuǎn)
_reverse(&chars, start, i)
//更新start位置
start = i + 2
}
}
return String(chars)
}
注解:
1:以輸入字符串為"Hello World"為例,首先將該字符串分割成一個(gè)個(gè)的小字符數(shù)組,然后反轉(zhuǎn)成 "dlroW olleH".
2“接著我們通過判斷字符數(shù)組中的空格位和最后一位字符,對(duì)單一的單詞進(jìn)行分段反轉(zhuǎn),更新start位置.
3:最后輸出我們需要的結(jié)果"World Hello"
其實(shí)字符串反轉(zhuǎn)蘋果已經(jīng)為我們提供了方法來實(shí)現(xiàn)這個(gè)操作.
func reverseWords(s: String) -> String? {
//用空格劃分字符串
let chars = s.components(separatedBy:" ")
//將字符串?dāng)?shù)組 反轉(zhuǎn) 并通過空格重新組合
let reverseString = chars.reversed().joined(separator:" ")
return reverseString
}
寫法非常的簡(jiǎn)單,就不贅述了.但是components和joined的時(shí)間復(fù)雜度是高于上面的寫法的,需要注意.
拓展
如果說把上面的字符串換成整數(shù),又該如何進(jìn)行反轉(zhuǎn)呢?
例題:給定一個(gè)16位有符號(hào)整數(shù)钞钙,要求將其反轉(zhuǎn)后輸出(eg:輸入:1234淹朋,輸出:4321)兵多。來看代碼:
func reverse(x:Int) -> Int {
var i = 0
var t = x
//支持正數(shù) 負(fù)數(shù)
while t != 0 {
i = 10*i + t%10
t = t/10
}
if i < INT16_MIN || i > INT16_MAX {
//超出 16位符號(hào)整型 輸出0
return 0
}
return i
}
這道題也是LeetCode比較基礎(chǔ)的算法題:整數(shù)反轉(zhuǎn)辨萍。非常簡(jiǎn)單,但是一定要注意邊界條件的判斷竭业。
3 鏈表
筆者理解的鏈表是一串在存儲(chǔ)空間上非連續(xù)性嘱兼、順序的存儲(chǔ)結(jié)構(gòu).由節(jié)點(diǎn)進(jìn)行頭尾依次連接而形成鏈表.每個(gè)結(jié)點(diǎn)有包括兩個(gè)部分:數(shù)據(jù)域和下個(gè)節(jié)點(diǎn)的指針域.
接下來看下書中在swift里如何實(shí)現(xiàn)一個(gè)鏈表
1:生成節(jié)點(diǎn)
class ListNode {
//數(shù)據(jù)域
var val: Int
//指針域
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
2:實(shí)現(xiàn)頭插法和尾插法
頭插法:當(dāng)前節(jié)點(diǎn)插到第一個(gè)節(jié)點(diǎn)之前冯丙,
尾插法:當(dāng)前節(jié)點(diǎn)插入到鏈表最后一個(gè)節(jié)點(diǎn)之后。
class List {
var head: ListNode?
var tail: ListNode?
//頭插法
func appendToHead(_ val: Int) {
if head == nil {
//創(chuàng)建頭節(jié)點(diǎn)
head = ListNode(val)
tail = head
} else {
let temp = ListNode(val)
//把當(dāng)前head地址賦給temp的指針域
temp.next = head
head = temp
}
}
//尾插法實(shí)現(xiàn)同上
func appendToTail(_ val: Int) {
if tail == nil {
tail = ListNode(val)
head = tail
} else {
tail!.next = ListNode(val)
tail = tail!.next
}
}
}
例題: 1 ->3 ->5 ->2 ->4 ->2,當(dāng)給定x=3時(shí),要求返回 1 ->2 ->2 ->3 ->5 ->4.
書上給出的解題思路,將完整的鏈表通過條件判斷(入?yún))分割成2個(gè)新的鏈表遭京,然后再將2個(gè)新鏈表拼接成完整的鏈表,看下代碼.
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
//創(chuàng)建2個(gè)Dummy節(jié)點(diǎn)
let prevDummy = ListNode(0), postDummy = ListNode(0)
var prev = prevDummy, post = postDummy
var node = head
//判斷是否存在node
while node != nil {
//判斷數(shù)據(jù)是否小于x
if node!.val < x {
//小于x prev.next指針域指向node
prev.next = node
prev = node!
} else
{
//同上 大于等于x 構(gòu)建新的鏈表
post.next = node
post = node!
}
//判斷下個(gè)節(jié)點(diǎn)
node = node!.next
}
//將尾節(jié)點(diǎn)next置為nil,防止構(gòu)成環(huán)
post.next = nil
//左右拼接(左邊尾節(jié)點(diǎn)指向右邊頭節(jié)點(diǎn))
prev.next = postDummy.next
return prevDummy.next
}
關(guān)于Dummy節(jié)點(diǎn),書中給出了詳細(xì)介紹.
上面代碼引入了Dummy節(jié)點(diǎn),它的作用就是作為一個(gè)虛擬的頭前結(jié)點(diǎn)泞莉。我們引入它的原因是我們不知道要返回的新鏈表的頭結(jié)點(diǎn)是哪一個(gè)哪雕,它有可能是原鏈表的第一個(gè)節(jié)點(diǎn),可能在原鏈表的中間鲫趁,也可能在最后斯嚎,甚至可能不存在(nil)。而Dummy節(jié)點(diǎn)的引入可以巧妙的涵蓋所有以上情況挨厚,我們可以用dummy.next方便得返回最終需要的頭結(jié)點(diǎn)堡僻。
注解:
1:首先創(chuàng)建左右兩個(gè)Dummy節(jié)點(diǎn),然后通過while判斷node是否存在.
2:若存在再判斷節(jié)點(diǎn)的數(shù)據(jù)val和判斷條件x的關(guān)系,小于x則被鏈到左邊鏈表上,大于x被鏈到右邊鏈表.
3:執(zhí)行完while,此時(shí)我們已經(jīng)拿到左右兩個(gè)新的鏈表.最后把左邊的尾節(jié)點(diǎn)指向右邊的頭節(jié)點(diǎn)就完成了完整鏈表的拼接.
注意:需要將右鏈表的尾節(jié)點(diǎn)置nil,防止構(gòu)成環(huán).
關(guān)于檢測(cè)鏈表中是否有環(huán),可以通過快行指針來檢測(cè),若快指針和慢指針變成相等的了,就代表該鏈表有環(huán),具體的就不在這里介紹了,比較簡(jiǎn)單.
4 棧和隊(duì)列
先來了解下棧和隊(duì)列的基本概念
棧:先進(jìn)后出(First In Last Out)的結(jié)構(gòu),又叫FILO.可以理解為我們小時(shí)候完的疊羅漢,最下面的人是第一躺下而最后一個(gè)起來的.
隊(duì)列:先進(jìn)先出(First In First Out)的結(jié)構(gòu),又叫(FIFO).這個(gè)字面上理解就行,就像排隊(duì)買票一樣,先來的人先買到票.
了解了棧和堆的概念,來看下Swift怎么來寫出個(gè)棧和隊(duì)列.
protocol Stack {
//associatedtype:關(guān)聯(lián)類型 相當(dāng)于范型 在調(diào)用的時(shí)候可以根據(jù)associatedtype指定的Element來設(shè)置類型
associatedtype Element
//判斷棧是否為空
var isEmpty: Bool {get}
//棧的大小
var size: Int {get}
//棧頂元素
var peek: Element? {get}
//mutating:當(dāng)需要在協(xié)議(結(jié)構(gòu)體,枚舉)的實(shí)例方法中,修改協(xié)議(結(jié)構(gòu)體,枚舉)的實(shí)例屬性,需要用到mutating對(duì)實(shí)例方法進(jìn)行修飾,不然會(huì)報(bào)錯(cuò).
//進(jìn)棧
mutating func push(_ newElement: Element)
//出棧
mutating func pop() -> Element?
}
實(shí)現(xiàn)協(xié)議方法
struct IntegerStack: Stack {
//typealias:類型別名 指定協(xié)議關(guān)聯(lián)類型的具體類型 和associatedtype成對(duì)出現(xiàn)的
typealias Element = Int
var isEmpty: Bool {return stack.isEmpty}
var size: Int {return stack.count}
//取出stack棧頂元素
var peek: Element? {return stack.last}
private var stack = [Element]()
//push 加入stack數(shù)組中
mutating func push(_ newElement: Element) {
return stack.append(newElement)
}
//pop 刪除stack中最后一個(gè)元素
mutating func pop() -> Element? {
return stack.popLast()
}
}
注解:利用協(xié)議申明了棧的屬性和方法,并在結(jié)構(gòu)體中聲明數(shù)組stack,對(duì)數(shù)組數(shù)據(jù)進(jìn)行append和poplLast操作,完成入棧出棧操作,比較簡(jiǎn)單.
再來看下隊(duì)列的實(shí)現(xiàn):
protocol Queue {
associatedtype Element
//隊(duì)列是否為空
var isEmpty: Bool {get}
//隊(duì)列大小
var size: Int {get}
//隊(duì)列首元素
var peek: Element? {get}
//入列
mutating func enqueue(_ newElement: Element)
//出列
mutating func dequeue() -> Element?
}
實(shí)現(xiàn)協(xié)議方法
struct IntegerQueue: Queue {
typealias Element = Int
var isEmpty: Bool {return left.isEmpty && right.isEmpty}
var size: Int {return left.count + right.count}
var peek: Element? {return left.isEmpty ? right.first : left.last}
//聲明左右2個(gè)數(shù)組
private var left = [Element]()
private var right = [Element]()
//在right數(shù)組中添加新元素
mutating func enqueue(_ newElement: Int) {
right.append(newElement)
}
//出隊(duì)列時(shí) 首先判斷l(xiāng)eft是否為空
mutating func dequeue() -> Element? {
if left.isEmpty {
//reversed: 倒序遍歷數(shù)組
left = right.reversed()
//刪除right數(shù)組
right.removeAll()
}
//刪除left數(shù)組的最后一個(gè)元素
return left.popLast()
}
}
注解:上面代碼里面分別用兩個(gè)數(shù)組分別完成入隊(duì)列和出隊(duì)列的操作,用right存儲(chǔ)入隊(duì)列的元素.當(dāng)出隊(duì)列時(shí)會(huì)先判斷l(xiāng)eft是否為空,如果為空left數(shù)組指向倒序后的right數(shù)組,這時(shí)執(zhí)行popLast,即實(shí)現(xiàn)了出隊(duì)列的操作.size peek isEmpty屬性也是充分通過左右兩個(gè)數(shù)組來進(jìn)行判斷.
關(guān)于書上用left right兩個(gè)數(shù)組來形成一個(gè)隊(duì)列的寫法筆者自己也不是很清楚,希望有知道的同學(xué)可以給小弟指點(diǎn)一下.
之后書上提到了棧和隊(duì)列互相轉(zhuǎn)換,這塊部分因?yàn)槠蚓筒唤榻B了,不過大致思路是通過兩個(gè)棧/隊(duì)列,配合生成所對(duì)應(yīng)的結(jié)構(gòu),是一種用空間復(fù)雜度換時(shí)間復(fù)雜度的寫法.有興趣的同學(xué)可以購買原書細(xì)讀.
例題:給出路徑 /a/./b/../b/c/,簡(jiǎn)化成/c
首先分析一下這道題,輸入字符串x,輸出字符串y.然后我們通過'/'將輸入的字符串進(jìn)行分割,分割成字符串?dāng)?shù)組,然后遍歷數(shù)組中字符的具體情況("."表示當(dāng)前目錄疫剃,".."表示上一級(jí)目錄)就可以了,看下代碼.
func simplifyPath(path: String) -> String {
//初始化存儲(chǔ)路徑的數(shù)組
var pathStack = [String]()
//通過"/"分割入?yún)ath
let paths = path.components(separatedBy: "/")
//遍歷paths
for path in paths {
// 當(dāng)path為"."時(shí),表示當(dāng)前目錄,所以不做處理
guard path != "." else {
//跳過循環(huán)
continue
}
//當(dāng)path等于".."時(shí),表示返回上級(jí)目錄
if path == ".." {
//這里邊界情況一定要考慮,這也是個(gè)容易出錯(cuò)的地方
if (pathStack.count > 0){
//pathStack有數(shù)據(jù),刪除last元素
pathStack.removeLast()
}
} else if path != "" {
//判斷path不等于""的邊界情況,添加路徑
pathStack.append(path)
}
}
//將pathStack進(jìn)行遍歷拼接,獲得最終結(jié)果res
let res = pathStack.reduce(""){
total, dir in "\(total)/\(dir)"
}
//如果是空路徑 返回 "/"
return res.isEmpty ? "/" : res
}
上面的例題并不是很難,但是想完整寫好卻不是十分容易.需要注意的邊界條件非常的多,如果在面試的時(shí)候只是順著解決問題的方向走而忽視了這些邊界問題,那么給面試官的印象也會(huì)大打折扣.
5 二叉樹
概念:二叉樹中,每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn),一般稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn),并且節(jié)點(diǎn)的順序不能任意顛倒.第一層的節(jié)點(diǎn)稱之為根節(jié)點(diǎn),我們從根節(jié)點(diǎn)開始計(jì)算,到節(jié)點(diǎn)的最大層次為二叉樹的深度.
首先看下書中節(jié)點(diǎn)實(shí)現(xiàn)的代碼:
//public:不同于OC的public swift中不能在override和繼承的extension中訪問
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int){
self.val = val
}
}
一個(gè)完整的二叉樹節(jié)點(diǎn)包含數(shù)據(jù)val,左子節(jié)點(diǎn)和右子節(jié)點(diǎn).
有了節(jié)點(diǎn)我們?cè)倏聪氯绾吻蠖鏄涞纳疃?/p>
func treeMaxDepth(root: TreeNode?) -> Int {
guard let root = root else {
return 0;//root不存在返回0
}
//max函數(shù):比較兩個(gè)入?yún)⒌拇笮∪∽畲笾? return max(treeMaxDepth(root:root.left), treeMaxDepth(root: root.right)) + 1
}
注解:
1:首先判斷入?yún)⒍鏄涔?jié)點(diǎn)是否為nil,若不存在的話返回0,若存在遞歸子節(jié)點(diǎn)取最大值.
2:+1表示每遞歸一層钉疫,二叉樹深度+1.
3:max函數(shù)作用:左右子節(jié)點(diǎn)最大深度比較,取較大值.
二叉查找樹
在二叉樹中有類特別的二叉樹叫做二叉查找樹(Binary Sort Tree),滿足所有左子節(jié)點(diǎn)的值都小于它的根節(jié)點(diǎn)的值,所有右子節(jié)點(diǎn)都大于它的根子節(jié)點(diǎn)的值,那么問題來了我們?cè)趺磁袛嘁活w二叉樹是否為二叉查找樹呢.來看代碼:
func isValidBST(root: TreeNode?) -> Bool {
return _helper(node: root, nil, nil)
}
private func _helper(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
//node不存在 則到了最底層 遞歸結(jié)束.這個(gè)要注意的是第一次傳入的node不能為nil
guard let node = node else {
return true
}
//右子樹的值都必須大于它的根節(jié)點(diǎn)的值
if let min = min, node.val <= min {
return false
}
//左子樹的值都必須小于它的根節(jié)點(diǎn)的值
if let max = max, node.val >= max {
return false
}
//左右子樹同時(shí)遞歸
return _helper(node: node.left, min, node.val) && _helper(node: node.right, node.val, max)
}
注解:
1:這個(gè)地方會(huì)首先判斷當(dāng)前節(jié)點(diǎn)是否存在,若不存在即代表已經(jīng)遞歸到最后一層,返回true.
2:然后判斷右子樹和左子樹的val是否滿足判斷條件,若都滿足條件進(jìn)行下一層的遞歸.
3:左右同時(shí)進(jìn)行遞歸操作.
知道了二叉樹的基本概念和swift的寫法外,再來看下如何實(shí)現(xiàn)二叉樹的遍歷操作.常見的二叉樹遍歷有前序巢价、中序牲阁、后序和層級(jí)遍歷(廣度優(yōu)先遍歷).
給出幾種遍歷方法的規(guī)則:
前序遍歷規(guī)則:
1:訪問根節(jié)點(diǎn)
2:前序遍歷左子樹
3:前序遍歷右子樹
中序遍歷規(guī)則:
1:中序遍歷左子樹
2:訪問根節(jié)點(diǎn)
3:中序遍歷右子樹
后序遍歷規(guī)則:
1:后序遍歷左子樹
2:后序遍歷右子樹
3:訪問根節(jié)點(diǎn)
層級(jí)遍歷規(guī)則:以層為順序,將某一層上的節(jié)點(diǎn)全部遍歷完成后,才向下一層進(jìn)行遍歷,依次類推,至到最后一層.
如果還是不理解可以看下這篇關(guān)于二叉樹遍歷的介紹,講的比較直白易懂.
關(guān)于遍歷部分內(nèi)容因?yàn)楸容^多,筆者摘錄書上隊(duì)列實(shí)現(xiàn)樹來介紹下實(shí)現(xiàn)邏輯,看以下代碼:
func levelOrder(root: TreeNode?) -> [[Int]] {
//初始化 遍歷后返回的res數(shù)組
var res = [[Int]]()
//隊(duì)列數(shù)組
var queue = [TreeNode]()
if let root = root {
//存儲(chǔ)入?yún)oot節(jié)點(diǎn)
queue.append(root)
}
while queue.count > 0 {
//獲取層級(jí)個(gè)數(shù)
let size = queue.count
//每一層 數(shù)據(jù)存儲(chǔ)數(shù)組
var level = [Int]()
for _ in 0 ..< size {
//removeFirst:刪除第一個(gè)元素 并返回被刪除的元素
let node = queue.removeFirst()
//添加數(shù)據(jù)
level.append(node.val)
//判斷是否存在 左右子節(jié)點(diǎn) 并添加到隊(duì)列 順序從左至右
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
//存儲(chǔ)level數(shù)據(jù)數(shù)組
res.append(level)
}
return res
}
注解:
1:首先我們聲明數(shù)組res,用來存儲(chǔ)每一層的val數(shù)組,并聲明隊(duì)列數(shù)組,方便后面判斷.
2:判斷入?yún)oot是否存在,若存在存儲(chǔ)root節(jié)點(diǎn)到queue數(shù)組中.
3:while判斷queue是否有數(shù)據(jù),若有數(shù)據(jù)則取到queue的第一個(gè)數(shù)據(jù),并在queue中刪除.然后判斷下一層的數(shù)據(jù),并再次循環(huán)遍歷.
4:最后把節(jié)點(diǎn)的val數(shù)據(jù)保存到level中,添加到res.
總結(jié)
關(guān)于本書中算法部分的基本數(shù)據(jù)結(jié)構(gòu)就介紹的差不多了,后面會(huì)對(duì)具體的算法實(shí)戰(zhàn)部分進(jìn)行介紹.筆者總體感覺這本書更適合初級(jí)->中級(jí)的同學(xué),對(duì)于想要提高自己的初中級(jí)開發(fā)人員這本書絕對(duì)是不錯(cuò)的選擇.