算法之夜(002)——學算法到底有什麼用

Urin的自习室
19粉絲
朋友們大家好
又到了這個夜深人未靜的時候
上一集視頻推出之後呢
我收到了大家特別熱情的支持
大家紛紛表示很喜歡這套視頻
那正是大家的支持和喜愛給了我自信
這纔有了咱們今天的第二集視頻
只要大家喜歡這套視頻
喜歡我講的課
那麼我就會一集一集的講下去
那麼上集視頻推出之後呢
很多朋友呢給我留言
提出了很多有意思的問題
你比如說有些朋友問
咱們能不能在視頻裏講一些算法題啊
啊我的回答是呢
如果這道題很經典很有趣的話
我會拿出來講
那麼通過講這些題呢
我們的目的
不是單單的學會幾道算法題
而是呢能夠通過這些算法題呢
提高我們的編程能力和思維技巧
不然的話呢
如果我們在視頻當中
只是爲了刷題而刷題
一味的單純刷題的話
那麼咱們這個節目
就不應該叫算法職業
應該叫刷題職業了
對吧那麼還有些同學呢
就指出上一集視頻的標題是學算法
用什麼編程語言最好
但是呢我只是給大家展示了
那麼幾種編程語言
而並沒有給一個結論
到底應該使用哪門編程語來學習算法
或者說哪門編程語言
是最適合用來學習算法的
那其實呢
我呀已經把這個答案告訴大家了
那這個答案呢
就是我內心的答案
也是我最喜歡的內門編程語言
那麼這門編程語言是什麼呢
我並沒有直說
而是在我們的視頻當中呢
埋了一個小彩蛋
通過這個
小彩蛋呢
我告訴了大家
哪門編程語言是我心中的最愛
大家呢可以在視頻當中找一找
如果你能找到的話
我希望你在視頻後面留言
我來告訴你對還是不對
咱們今天這集視頻要討論的話題
又是一個長久以來十分有爭議的話題
這個話題呢也十分有趣
那就是程序員學習算法到底有用沒用
那針對這個話題呢
其實大家的觀點都是很鮮明的
有一部分人認爲是有用的
有一部分人呢
認爲是沒用的
那麼大致呢
這個論據呢
有這麼幾個啊
認爲有用的同學啊說
那我要不學算法的話
我沒法畢業啊
這是我們這個專業的同學對吧
因爲我們知道計算機專業呢
有一門非常重要的課
就是數據結構與算法
這是必修課
如果你成績考不好的話
那是非常麻煩的
所以說必須要把它學好
那麼持這個必須要學好的
這個觀點同學呢
還有一個論句
那就是現在呃
公司在面試程序員的時候
多多少少呢都會考一些算法題
也叫編程題
特別是大型的公司
你比如說在美國這邊啊
像Facebook啊
谷歌呀Amazon啊
微軟啊LinkedIn啊這些大型的公司
還有Uber啊等等這些公司
那麼你面試的時候呢
基本上都是在考你算法題
也是難度最大的一部分
所以說呢
不學好算法的話
你想進大公司是比較困難的
所以說呢
這是持正方觀點的同學們的論句
那麼也有我們的反方同學
認爲學算法沒什麼用
他們的論句是
什麼呢那這些同學呢
就會說說
你看我寫了這麼多年程序
也沒在程序當中
遇到需要直接使算法的地方啊
啊這是一種觀點
那這種觀點對不對呢
其實挺對的
我平時寫程序的時候呢
也很少遇到說
必須要用某幾種特殊的算法
才能解決的問題啊
大部分情況下都是平鋪直敘
在描述我們的業務邏輯
那持反方觀點的同學呢
還有一個論句
那就是這個算法啊
它是編程當中的一個局部
那當我們的程序
必須要用到一些高深
複雜的算法的時候
那不是由我們的算法工程師嗎
讓他們把這些算法研究開發出來
然後呢把它封裝成函數也好
類也好讓我們來調用
不就可以了嗎
我們大多數程序員
也沒必要非得把算法學的那麼精通嘛
對不對所以說
你看既有正方觀點
也有反方觀點
那麼很多同學呢
可能就會想
是不是今天這集視頻
我就要來給大家當一個裁判
告訴大家到底是正方勝還是反方勝呢
其實呢以我這麼膚淺的學問
我根本就沒有資格對這樣的問題呢
進行裁決
那在這集視頻裏呢
我只是想向大家展現一下
算法的幾個側面
或者說算法的一些用處
然後呢
也抒發一下我對算法學習的感覺
當你看到這些算法的各個側面
看到它的用處之後呢
至於學還是不學算法
希望大家呢
自己能夠有一個判斷
那麼讓我們回到今天的話題
學習算法到底有沒有用呢
讓我們從幾支鋼琴曲開始
那大家呢
看到我的屏幕上一直停着這張截圖
那可能會感覺
我們要從這支鋼琴曲開始
對吧嗯
其實不是啊
爲什麼用這張截圖呢
是因爲上一集出來之後呢
我們老闆啊
看了說哎呀
這個內容不錯啊
就是你一開始那個桌面太單調啊
哪個桌面
就這個桌面對吧
你太單調了
然後你能不能這個
換一個稍微漂亮點的桌面啊
然後呢這不白天忙工作嗎
也沒有找到漂亮的桌面
然後呢我想
那就不讓大家看那個桌面了好不好
然後我就直接把這個截圖擱在這
反正給大家一點遐想的算了
對吧那好
我們的第一隻鋼琴曲是什麼呢
這呢有個小故事啊
這個學鋼琴的同學呢
你可能聽說過一些練習曲
你比如說有299啊
599啊這些
其中呢有一套練習曲
那真是練琴的同學聽到就會頭疼
它叫什麼呢
它叫做哈農
注意啊它叫哈農
全稱呢也叫哈農練指法
專門練指法的啊
練這個彈琴的技巧的
那麼有些同學呢
如果你不是專業的
可能會把哈農呢聽成卡農
我們就從這兩支曲子開始啊
卡農呢是非常簡單
非常優美
非常優雅的曲子
這個大家都聽過啊
咱們聽一下
呃我們經常聽的那個卡農呢
就是這個
呃Canon in d major
d就是d調啦
major就是大調
那d major呢
就是d大調
我們知道大調呢
這個曲子呢
聽起來是非常的明亮明朗的
是吧我們聽一聽啊
好的
卡農這首曲子我們就
先聽到這個地方
我們看到了非常的舒緩
非常的簡單
那麼我們去看一下哈農是什麼
呃這個看字母呢
就差一個啊
c變成h
然後呢哈農就比較啊讓人頭疼了
聽聽
好的我們就先聽這兩段啊
大家看到了
我們這個哈農啊
明顯比卡農聽起來要枯燥乏味一些
而且呢他呢
練習的就是單純的
我們手指彈琴的時候的技巧
像這幾條還算是比較簡單的
只是讓我們練這個音階啊
大調的小調的音階
然後呢音階後邊接幾個和絃
然後呢讓我們的這個手指呢
能夠充分的鍛鍊到各種各樣的技巧
那這個呢就是哈農
那這個哈儂練習曲啊
或者說練指法啊
其實呢
就跟我們這個學算法道理差不多
你看這些音階呢
就像我們平時練的單循環啊
雙循環啊
雖然我們在練各種各樣的循環
練地規的時候非常的枯燥
但是呢那正是這些枯燥的技巧
能夠呢讓我們有一天面對複雜的
具體的問題的時候
我們能夠拿這些編程能力呢
解決這些複雜的具體的問題
那麼什麼算是複雜的具體的問題呢
這時候呢
我們就要請出
咱們剛纔看的第三支曲子了
第三支曲子是什麼呀
看這標題就知道
這是李斯特的匈牙利狂想曲2號啊
簡稱爲狂二啊
說到狂2這個詞的話呢
這個有的時候我做算法題的時候
真的是這個題裏邊寫了一堆bug啊
就就狂2
然後所以說呢
就是形容自己那個狀態是非常貼切的
啊非常的2
那我們聽聽這個狂2是什麼樣的
這是截取了當中一段
呃很需要技巧的
而且整整個曲子都非常需要技巧啊
那如果沒有前面的這種紮實的基本功
作爲功底的話
呃那是不可能演奏這麼複雜的曲子
我們聽一下
好的
我們的狂二就先欣賞到這個地方
那我們再回到我們的這個哈農
哈農呢他全稱是練指法對吧
那實際上呢
我們平時學習算法
或者說是刷題的時候練的那個基本功
就跟鋼琴的指法一樣
彈複雜的曲子
最重要的一點就是
你能夠有很正確的指法
正是這些正確的指法
能給你帶來彈曲子的時候的
正確的感覺
那我們學習算法
就是爲了讓大家養成這個
正確的思考問題
或者編程的基本功
在面對複雜問題的時候呢
我們的編程呢
不走樣而且呢
在面對一些有趣的問題的時候呢
我們能夠體驗到編程的這個真味道
那麼這個呢
就是修習算法的第一個用處啊
紮實大家的基本功
然後呢
讓大家能夠體驗到編程的真滋味
那回到我們剛纔的這個匈牙利狂想曲
這個地方
那如果把這個匈牙利狂想曲
比作是我們現實當中的程序的話
那麼旋律狂想曲呢
它用到很多複雜的指法
那麼有沒有哪些現實當中的程序
也需要我們調用到我們學習的算法呢
有給大家看一個啊
平時呢大家經常會說啊
說我寫程序的時候
也用不着這個算法呀
現在給大家看一個
我們呢這有
一個帶界面的這樣一個桌面程序
這個程序呢
如果你仔細觀察一下
它呢裏邊是一個可以展開的
這樣一個豎狀結構
這種結構的話
我們大家見得很多對不對
那現在的話呢
我們只能一個一個的
去把它的這個checkbox啊
給它勾選上
或者呢給它取消掉
這個效率啊
非常的低
然後呢用戶就要求了
說你能不能給我準備一個按鈕
我能夠的
點一下把它就全選上
再點一下
把它就全取消
那就像這個按鈕一樣
你看
點一下全寫上
點一下全取消
那這個功能應該怎麼實現
如果你不會算法的話
這個功能
單純的依靠我們的這個界面空間
你是做不到的
那個界面空間呢
我們看一下
我們看嗯
這個界面程序的話呢
在一個grade裏邊
我放了一個Triview
triview裏邊呢
它有triview item
然後呢一個一個的item
那個item裏邊呢
又有子級的item
然後呢
這個item裏邊還有checkbox這樣一個結構
那實際上呢
它是一個豎狀的結構
如果之前沒有認真修習過算法的同學
可能很難處理這樣的程序
那麼就只能把這樣的程序呢
交給熟悉算法的同學去寫
那麼要實現剛纔這個功能的話
大家想想應該用什麼樣的算法呢
其實呢
兩種算法都可以解決這個問題
一種呢就是深度優先便利
一種呢就是廣度優先便利
我們呢把這些啊
triview啊triview item啊
還有checkbox啊
看作是這個一棵樹上的節點
然後呢我
們用深度優先便利
或者廣度優先便利去訪問這些節點
如果發現這個節點是一個check box
就把它的狀態反轉一下
我們來看一下這代碼
這代碼呢
我就不給大家一步一步手敲了
我已經給大家寫好了
大家看一下啊
顯然呢
今天我們用的是廣度優先便利
廣東有些便利呢
我們一定要需要一個
這個q就是隊列對吧
上來之後呢
我們把這個triview傳進來
然後呢生成一個q
然後呢
我們先用一個voyage循環疊在一下
把第一層我們的這個triview item
先給它加到我們的q裏邊去
然後呢
就開始我們標準的廣東一天便利啊
當我們這個q呢
它不爲空的時候
我們呢每次從這q裏邊這個拉出一個
這個trivial item來
然後呢
看一看這個trivial item裏邊有沒有check box
如果有check box反轉這個check box的狀態
如果裏邊有這個子級的這個trivial item
那就把這個trivial item
加到我們的q裏邊去
這樣的話呢
我們就可以完成用戶的需求啊
全部選中或者全部給它取消
再看一下
所以說大家未來呢
不要再說算法在編程的時候沒有用
那很多時候呢
是因爲我們很多同學呢
沒有掌握算法
所以說呢
當遇到
可以用算法解決的問題的時候呢
他要麼就是把這個問題呢
交給別的同學去解決了
要麼呢乾脆就不解決他了
總之呢就是逃避開了
那提醒大家注
意啊
我們不要犯那個因果顛倒的錯誤
不是程序當中沒有算法
而是因爲我們不會算法
所以說呢
程序當中該用算法的地方
我們沒有識別出來
那這時候呢
有些同學呢
就會問了
說我的確想把編程學好
我願意吃些苦
像練習這個哈農指法一樣
來學習基本的算法
我應該怎麼來練習呢
那下面呢
我給大家展示幾個例子啊
嗯這呢是我們的拍檔開發環境
每種編程語言呢
都有它表達算法的強項
所以說呢
以後我不會固定到某個編程語言
而是呢
哪個編程語言在這個時間點上最合適
我就拿出來用
這個編程語言
那麼大家會說呢
說哎呀
我只會一門編程語言啊
那怎麼辦呀
哎
這正是咱們這套課程的另一個好處
如果你喜歡這套視頻
你想把我講給你的東西學會的話
那麼這套視頻呢
就相當於逼着你多學幾門編程語言
請大家注意啊
一個心態成熟的程序員的話
永遠不會只抱定一門編程語言
動不動就說我是Java程序員啊
我是C++程序員
我是排放程序員
那如果你抱有這樣的心態的話
那我可以十分坦誠的告訴你
你
永遠也不可能成爲一個優秀的程序員
那好的現在我們來看一下
爲什麼這道練習題我要用Python來做呢
是因爲Python呢
在打印二維數組的時候特別方便
我們想打印二維數組的時候
只要用一個print就可以
如果在別的編程語言裏邊
打印二維數組的話
我還得用
一個循環來打
所以說呢
我在這直接用Python讀機運行
現在呢我們看到了
我這呢創建了一個
這叫四行五列的這樣一個二維數組
或者說呢
這個四行五列二維數組
是由四個子數組構成的
每個子數組裏邊有5個元素
現在呢他們填充的都是0
那麼就像剛纔我們的這個哈農練之法
他練的呢都是這個音階一樣
那麼音階對應到我們的編程語言裏
就是我們的循環啊
單循環雙循環等等這些東西
那我們來練兩個雙循環吧
現在呢
我想讓大家填充這個二維數組啊
第一個數填一二三四五六七八九十
也就是什麼逐行掃描
或者說是逐行填充
那這就是一個非常非常標準的
基本算法
練習題嘛
那我們應該怎麼寫啊
four哎很多同學呢
上來就說哎
我呢建議大家
你迭代行的時候就用肉
你迭代列的時候就用column
在變量命名的時候就養成好習慣
我們哈農不就是練直法嗎
我們學算法不就是練編程的基本功嗎
那基本功
就是要紮實到細節上纔可以啊
for row in range
我們知道一共有幾行啊
4行對不對
for CO與range 05對不對
那下面的話呢
我們的這個Matrix是吧
我們的永遠記着先行後列對吧
等於什麼呢
那這時候呢
我們要動動腦筋
這有一個映射的公式對不對
那麼這個公式應該是什麼
應該是raw乘以我們的column count對吧
然後呢加上我們的哎
當前那個
扣你別忘了還得加一
不加一的話呢
就是從0開始填充了
好看一下
12345 哎
這個就相當於一小段哈農煉脂法
練完它之後
那哈農煉脂法呢
它基本上就是讓你的手指呢
折騰來折騰去啊
反正折騰正着折騰
那現在的話呢
我們學會了竹行掃描
你來個竹列掃描啊
竹列掃描其實呢
也很簡單
你可以就說把這段代碼改一改
當然了我更建議大家呢
自己重新動手寫一遍
for row進入我們的range 05
la for row進入我們的range 04
這回呢我們的公式呢
就稍微有一點點改變了
改成了什麼呢
改成了我們的M
仍然是別忘了還是先行後列
這個是永遠變不了的
但是呢它就變成了
我們的column乘以我們的roll con
加上我們的roll加
好的
12345678 現在呢
變成了逐列掃描
那這個有什麼用呢
就跟我們上臺之前啊
上臺演奏鋼琴曲之前
先要來幾段練習曲熱熱身
熱熱手一樣
當我們刷題之前
當我們要上陣去面試之前
也要拿這些小的代碼片段
先讓自己熱熱身
避免自己呢
臨陣犯一些很愚蠢的錯誤啊
避免自己在面試的時候狂二
好吧好
這是拿這個拍檔語言練了一小段
然後呢請大家注意啊
這個不同的編程語言
它能夠鍛鍊你不同的算法技巧
你比如說在拍檔語言裏
你就很難能夠練到這個
自增自減這兩個操作符
比如說加加呀和減減
爲什麼呢
因爲咱們拍檔語言當中呢
就根本就沒有加加和減減
這兩個操作符啊
然後呢但是呢
他有加等於和減等於吧
但是這個加等於和減等於呢
也取代不了咱們這個加加減減
這兩個技巧
所以說呢
如果想練習這個技巧的話
我們呢要麼去這個加到裏邊
要麼去C++裏邊
要麼去c sharp裏邊
好下面呢
我們用c sharp來做一個練習題啊
專門練加加減減
那這個練習題呢是幹什麼呢
是讓我們把這個數組呢
給它調個個反轉一下
現在是123456789
然後呢我把它反轉成98765321
這個怎麼做呢
很顯然呢
你不能夠啊
有些同學呢
就會說我上來之後
我能不能調上這個reverse這個方法呀
reverse這個方法呀
那如果面試的時候你問這個問題的話
那面試官呢
直接就恨不得把你趕出去了啊
好的肯定是不能這樣做的
那麼我們應該怎麼做呢
來手動寫吧
一般情況下呢
我們都是用一個左邊的index
加上右邊的index
然後呢給它進行逐一的對調
對吧這樣一個東西
那好現在呢
我們先寫啊
說這個LI
那有些同學說LI
這是不是姓李的同學啊
那肯定不是姓李的同學
LI是一個約定俗成的縮寫
是lower index的縮寫啊
lower左邊低嘛
右邊高嘛
所以說lower index
嗯好的
lower index那我們處理化成0好不好啊
然後呢h i這也不讀high啊
這是higher index
的意思右邊的index
我們等於什麼呢
等於AR它的論詞簡易
那這時候
大家可以在腦子裏面腦補一下
這個lower index
實際上是指在這個 1這個元素上的
HIGHER index呢
它實際是指在9這個元素上的
那下面呢
我們就用一個well循環對吧
well well什麼呢
well我們的Li
它仍然還小於我們的HI
的時候我們要做什麼呢
我們就開始對調
對調上節課學過了
我們來一個temper
等於我們的ARR lower index
AR lower index等於AR higher index
然後呢
讓我們的ARR higher index等於我們的temp
好這時候呢
我們的加加減減就要登場了
我們的左邊的lower index
加加右邊的higher index
注意啊一定是減減
你不能寫加加啊
這個時候已經程序
98765421 這個數組呢
就反轉過來了
這個算法寫完了沒有啊
當然沒有啊
如果要是我們練習基本功的話
那麼每段基本功呢
我們叫練到極致
那什麼算練到極致呢
你比如說我們就要讓算法呢
儘可能的短
儘可能的精確
那儘可能短的話
有些同學想了說
能不能把這兩行去掉呢
把這個加加和減減並在這個地方來
那好如果你把加加併到這
減減寫到這的話
那肯定這個程序是錯了
對不對爲什麼錯呢
對不對想一想爲什麼會錯呢
因爲這個加加減減
它們的特性是什麼
對吧後置加加
這個和後置剪剪是什麼樣
你看這不對了
對不對它只有中間這段調過來了
一和9沒調過來
爲什麼呢
以後呢我們來深究這些問題
那有同學說
那既然呃
你不能這樣用夾夾擱前邊
剪剪擱前邊行不行啊運行線
還是不行
對不對那應該怎麼做呢
那實際上的話
如果我們想省掉這兩行代碼的話
在這呢我們需要給他把lower index設爲-1
higher index呢
不要減這個一啊
留出一個餘量來
那這時候呢
運行的話
這程序呢
就又對了
那我們在這呢
改變了兩個起始值
初始值然後呢
把加加減減
併成了前置加加和前置減減
那麼我們的代碼呢
又少了兩行
這樣的話呢
我們的算法呢
就更加的精緻一些了
這個呢
纔是真正的在鍛鍊我們的算法
鍛鍊我們的基本功
那正是這些基本功呢
他穩定下來
沉澱下來
形成我們手上的功夫之後呢
等我們在編程的時候
才能夠編的又快又好
而且呢還不會出錯
那這個呢
就是對我們平時寫程序的
一個潛移默化的貢獻
這樣的那除了這些技巧之外呢
還有很多很多的技巧啊
你比如說我想想啊
鋼琴啊大家學彈琴的時候
老師可能教你第一個概念就說哎
找到那個中央c啊
中央c c就是我說那個唱那個do嘛
對吧鋼琴的鍵盤很長啊
它在靠近中央的地方
那有一個do啊
那叫中央c
那麼找中央c呢
就好像我們找這個數組的這個
所謂中間的那個index一樣啊
middle index middle
index呢它也有一個公式啊
那middle index應該怎麼算呢
好我們現在有lower index
我們設爲0
higher index我們設爲最後一個元素
那麼middle index應該是什麼呢
int m i它呢有兩個公式
一個公式呢是我們的low i加high i除以2
這是一個特別簡單特別好記的公式
但是呢這個公式呢
有很大的侷限性
爲什麼呢
因爲有的時候啊
我們找middle index這個操作呢
它並不一定是發生在
我們找整個的這個數組的middle index
而是呢可能找某一段數組的middle index
你比如說我選中的這段
它的middle index
就是指到6這個地方的index
那麼這個時候大家想想
如果我的lower index和higher index啊
它們兩個值
都大於
整數能容納的最大值的一半的話
那會出現什麼情況
那
lower index它大於整數的最大值的一半
higher index也大於整數的最大值的一半
那這倆值加起來的話
一定就大於整數的最大值
那這時候的話就會產生溢出
那一旦產生溢出的話呢
我們可能會面對兩種不想見到的結果
第一種呢
是它悄悄的溢出了
那我們知道整數一旦溢出的話
溢出最大值的話
它可能會得到一個負數值
那這時候的話呢
我們的負數值除以2的話
它還是個負數值
那麼我們的middle index
就成爲一個負數值
而我們知道像c系的語言
這個index的邊界最小就是0了
你這來一個複數的middle index
那麼下一步操作肯定就要出錯了
這是第一種情況
第二種情況呢
就是我這門編程語言呢
它有溢出檢驗機制
還沒等你除二呢
這一加就已經溢出了
馬上給你拋個異常
你程序呢就當下崩潰了
也就是說當我們採用這個公式的時候
如果我們的lower index
和海爾index足夠大的話
我們得到的結果只有一個
就是程序崩潰
那麼另一個公式是什麼呢
另一個公式呢是非常通用的
就是lower index加上我們的higher index
減去lower index除以2
那這個公式呢
大家才應該把它牢牢的記住
因爲這個公式呢
它不會產生溢出
爲什麼呢
我們來看
首先呢
在這我們的higher index減去lower index
這個地方是不可能產生溢出的
對吧
然後呢
除以2之後再加上我們的lower index
lower index本身它小於HIGHER index
然後呢HIGHER index自己都沒有溢出
然後呢
你這加了一個他們倆之間的差距的1/2
那不可能達到higher index這麼高對不對
所以說也不會產生溢出
總之呢這個公式
就是需要大家記住的一個公式
所以說呢
大家注意到了吧
學習算法
特別是基本算法
它呢最重要的一點就是注意細節
只有注意到這些細節
把這些細節轉化爲自己編程的功夫
甚至是轉化爲自己的肌肉記憶之後呢
我們才能夠成爲真正的
高質量的程序員
那好的我已經呢
把我想給大家展現的算
法的幾個方面呢
展現給大家了
回到我們今天視頻的那個話題
學習算法到底有用沒用
那麼我可以告訴大家
如果呢你只是想做一個非常
非常普通的程序員啊
寫一些非常非常簡單直白的程序
就像我們剛纔看的那個卡農一樣的
那個級別的程序的話
算法的確是一點用都沒有
那當這樣的程序員
遇到那些
需要用算法才能解決的問題的時候呢
他們可以把這些問題交給別人去解決
也可以乾脆不去解決
而我堅信
今天無論是坐在那裏還是躺在那裏
你能夠把視頻看到這個時間點的
朋友們
你們一定是想成爲一個真正的
高級的程序員
成爲編程的高手
那麼算法對你有用沒用
這個答案已經不言自明瞭
好的這就是我今天
想向大家講述的全部內容
以學習喚醒靈魂
我是Tim咱們下集視頻再見
