Algorithm: 每周至少做一個(gè) LeetCode 的算法題
算法題:
1 劍指 offer 24: 翻轉(zhuǎn)鏈表
遞歸法實(shí)現(xiàn)翻轉(zhuǎn)鏈表
鏈表遞歸的基線條件(最簡單情況): 沒有節(jié)點(diǎn)或者只有一個(gè)節(jié)點(diǎn)
基線條件: 什么時(shí)候函數(shù)不再調(diào)用自己
遞歸條件: 什么時(shí)候函數(shù)調(diào)用自己
使用分治法看遞歸翻轉(zhuǎn)鏈表
對數(shù)組元素實(shí)現(xiàn)快速排序時(shí), 分治法的應(yīng)用是將 數(shù)組根據(jù) 中樞 從左到右 拆分為左子數(shù)組, 中樞, 右子數(shù)組.
在分治法翻轉(zhuǎn)鏈表時(shí), 以 5->4->3->2->1 為例, 將鏈表分成 5 和 4->3->2->1 這兩個(gè)鏈表, 即可理解.
ListNode* reverseList(ListNode* head) {
// 基線條件
if (!head || !head->next) {
return head;
}
// 對當(dāng)前節(jié)點(diǎn)的后面的節(jié)點(diǎn)進(jìn)行遞歸翻轉(zhuǎn), 最后得到一個(gè)翻轉(zhuǎn)好的鏈表
ListNode *newNode = reverseList(head->next);
// 組合 5 和 翻轉(zhuǎn)好的 4->3->2->1 這兩個(gè)鏈表
head->next->next = head;
head->next = NULL;
return newNode;
}
總結(jié): 遞歸時(shí), 首要找到基線條件, 然后看怎么將對應(yīng)的情況轉(zhuǎn)化到基線條件上.
檢驗(yàn)方法: 看遞歸的中間狀態(tài)
2 劍指 offer 59-1: 滑動(dòng)窗口最大值
知識(shí)點(diǎn): 單調(diào)遞減隊(duì)列
1 使用 deque 實(shí)現(xiàn)一個(gè)單調(diào)隊(duì)列
2 使用 雙向隊(duì)列實(shí)現(xiàn)對應(yīng)的 滑動(dòng)窗口最大值
每次元素進(jìn)隊(duì)的時(shí)候就保證能形成一個(gè)單調(diào)減的隊(duì)列
類似題目: 實(shí)現(xiàn)含有 min 函數(shù)的棧.
3 劍指 offer 48: 最長不含重復(fù)字符的子字符串長度
1 動(dòng)態(tài)規(guī)劃法: 研究 s[i] s[j] 之間沒有重復(fù)元素的長度關(guān)系.
2 使用哈希表和雙指針法, map 中的鍵值對<char, int> 保存這個(gè) char 最后一次出現(xiàn)的位置.
int lengthOfLongestSubstring(string s) {
int res = 0, leftIndex = -1, n = s.size();
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.count(s[i]) && map[s[i]] > leftIndex) {
leftIndex = map[s[i]];
}
map[s[i]] = i;
res = max(res, i - leftIndex);
}
return res;
}
Review: 閱讀并點(diǎn)評(píng)至少一篇英文技術(shù)文章
1 Swift 中的可選鏈
2 Difference between Swift and Kotlin
Tips: 學(xué)習(xí)至少一個(gè)技術(shù)技巧
Swift 中 SnapKit 代碼添加約束的理解與使用
Share: 分享一篇有觀點(diǎn)和思考的技術(shù)文章
Flutter 不是 the next big thing
還是先不著急上手 flutter 吧. 完成攜程的例子.
