2019 iOS面試題大全---全方面剖析面試
2018 iOS面試題---算法相關
1、七種常見的數(shù)組排序算法整理(C語言版本)
2、2019 算法面試相關(leetcode)--數(shù)組和鏈表
3、2019 算法面試相關(leetcode)--字符串
4、2019 算法面試相關(leetcode)--棧和隊列
5提岔、2019 算法面試相關(leetcode)--優(yōu)先隊列
6、2019 算法面試相關(leetcode)--哈希表
7笋敞、2019 算法面試相關(leetcode)--樹碱蒙、二叉樹、二叉搜索樹
8夯巷、2019 算法面試相關(leetcode)--遞歸與分治
9赛惩、2019 算法面試相關(leetcode)--貪心算法
10、2019 算法面試相關(leetcode)--動態(tài)規(guī)劃(Dynamic Programming)
11趁餐、2019 算法面試相關(leetcode)--動態(tài)規(guī)劃之背包問題
反轉鏈表
兩兩交換鏈表中的節(jié)點
環(huán)形鏈表
環(huán)形鏈表 II
鏈表和數(shù)組作為算法中的兩個基本數(shù)據(jù)結構喷兼，在程序設計過程中經(jīng)常用到。盡管兩種結構都可以用來存儲一系列的數(shù)據(jù)后雷，但又各有各的特點季惯。
數(shù)組的優(yōu)劣勢：可以方便的遍歷查找需要的數(shù)據(jù)，時間復雜度為O(1)臀突。這種時間上的便利性勉抓，是因為數(shù)組在內存中占用了連續(xù)的空間，在進行類似的查找或者遍歷時候学，本質是指針在內存中的定向偏移琳状。然而，當需要對數(shù)組成員進行添加和刪除的操作時盒齿，數(shù)組內完成這類操作的時間復雜度則變成了O(n)
鏈表的優(yōu)劣勢：在某些操作上比數(shù)組更加高效念逞，例如當進行插入和刪除操作時，鏈表操作的時間復雜度僅為O(1)边翁。因為鏈表在內存中不是連續(xù)存儲的翎承，所以可以充分利用內存中的碎片空間。
提到數(shù)組就不得不提到數(shù)組的排序：七種常見的數(shù)組排序算法整理(C語言版本)
- 下面主要針對leetcode上關于鏈表的一些題目符匾，這里我是使用的JavaScript
function ListNode(val) {
this.val = val;
this.next = null;
}
一叨咖、3種方法實現(xiàn)反轉鏈表
反轉一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
-
1、遞歸實現(xiàn)
遞歸的方法其實是非常巧的甸各，它利用遞歸走到鏈表的末端垛贤，然后再更新每一個node的next 值 ，實現(xiàn)鏈表的反轉趣倾。而newhead 的值沒有發(fā)生改變聘惦，為該鏈表的最后一個結點，所以儒恋，反轉后善绎，我們可以得到新鏈表的head。
var reverseList = function(head) {
if (!head || !head.next) return head;
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};
-
2诫尽、新建鏈表禀酱，頭節(jié)點插入法
新建一個頭結點，遍歷原鏈表牧嫉，把每個節(jié)點用頭結點插入到新建鏈表中剂跟。最后，新建的鏈表就是反轉后的鏈表酣藻。
var reverseList = function(head) {
if (!head || !head.next) return head;
let lastNode = new ListNode(head.val), curNode;
let node = head.next;
while (node) {
curNode = new ListNode(node.val);
curNode.next = lastNode;
lastNode = curNode;
node = node.next;
}
return curNode;
};
-
3浩聋、直接反轉
把當前鏈表的下一個節(jié)點指向當前結點，直至循環(huán)結束
var reverseList = function(head) {
if(!head || !head.next) return head
let pre = head, cur, last = head.next;
head.next = null;
while (last) {
cur = last;
last = cur.next;
cur.next = pre;
pre = cur;
}
return cur;
};
二 臊恋、兩兩交換鏈表中的節(jié)點
給定一個鏈表衣洁，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表抖仅。
示例:
給定 1->2->3->4, 你應該返回 2->1->4->3.
說明:
你的算法只能使用常數(shù)的額外空間坊夫。
你不能只是單純的改變節(jié)點內部的值，而是需要實際的進行節(jié)點交換撤卢。
記錄相鄰兩個結點cur和last环凿，以及之前的結點prev，然后去進行反轉相鄰的兩個結點放吩，依次循環(huán)到最后
var swapPairs = function(head) {
if(!head || !head.next) return head
let res = head.next
let cur = head
let prev = last = null
while(cur && cur.next){
last = cur.next
cur.next = last.next
last.next = cur
if(prev) prev.next = last
prev = cur
cur = cur.next
}
return res
};
三智听、環(huán)形鏈表
給定一個鏈表，判斷鏈表中是否有環(huán)渡紫。
為了表示給定鏈表中的環(huán)到推，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1惕澎，則在該鏈表中沒有環(huán)莉测。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點唧喉。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)捣卤，其尾部連接到第一個節(jié)點忍抽。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。
進階：
你能用 O(1)（即董朝，常量）內存解決此問題嗎鸠项？
正常鏈表都是有頭有尾的，而環(huán)形鏈表則是沒有尾的子姜，它的尾會指向其中一個結點pos(不一定是指向頭結點)祟绊，也就是環(huán)形鏈表，該題目就是來判斷一個鏈表是否是環(huán)形鏈表闲询。
正常來說久免，對鏈表進行循環(huán)浅辙，如果存在尾指針扭弧，即某結點指向null，即可證明該鏈表不是環(huán)形鏈表记舆。但如果對環(huán)形鏈表進行循環(huán)的話鸽捻，會造成死循環(huán)，這樣就沒辦法確定是鏈表足夠長還是該鏈表是環(huán)形鏈表泽腮。
- 1御蒲、比較容易想到的就是利用數(shù)組或集合:循環(huán)鏈表，將結點依次保存在集合中诊赊，如果下個結點已經(jīng)在集合中存在厚满，則說明是環(huán)形鏈表。如果循環(huán)到最后指向null碧磅，則非環(huán)形鏈表碘箍。
var hasCycle = function(head) {
let set = new Set()
while(head){
if(set.has(head)) return true
set.add(head)
head = head.next
}
return false
};
但題目有要求讓用o(1)空間復雜度解決，但這種方法空間復雜度很明顯是o(n),不符合要求
- 2鲸郊、還有一種比較巧妙的方法:快慢指針
快慢指針中的快慢指的是移動的步長丰榴，即每次向前移動速度的快慢。例如可以讓快指針每次沿鏈表向前移動2秆撮，慢指針每次向前移動1次四濒。此外還有其他不少巧妙的應用。
這里使用快慢指針职辨，slow每次走一步盗蟆，fast每次走兩步，如果不是環(huán)形鏈表舒裤，則會一直循環(huán)下去姆涩，永遠不會相遇，直至循環(huán)結束惭每。
反之如果這兩個指針相遇骨饿，則說明該鏈表是環(huán)形鏈表亏栈。
var hasCycle = function(head) {
let slow = fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow == fast) return true
}
return false
};
四、 環(huán)形鏈表 II
給定一個鏈表宏赘，返回鏈表開始入環(huán)的第一個節(jié)點绒北。 如果鏈表無環(huán)，則返回 null察署。
為了表示給定鏈表中的環(huán)闷游，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1贴汪，則在該鏈表中沒有環(huán)脐往。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點扳埂。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環(huán)业簿，其尾部連接到第一個節(jié)點。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)阳懂。
說明：不允許修改給定的鏈表梅尤。
題目意思是如果鏈表是環(huán)形鏈表，就返回交點(鏈表尾連接到鏈表中的位置)在該鏈表中的位置岩调，否則返回null
如果是用方法1使用數(shù)組保存結點巷燥，很容易就可以做到，這里不再贅述
快慢指針的話号枕，首先先循環(huán)一次缰揪，判斷是否是環(huán)形鏈表，不是的話直接返回null葱淳。是的話钝腺，則記錄下相遇點。然后head開始跑蛙紫，同時fast指針繼續(xù)從相遇點跑拍屑，則head必然會和fast指針在環(huán)形鏈表交點相遇。
var detectCycle = function(head) {
let slow = fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow == fast) {
while(fast != head){
head = head.next
fast = fast.next
}
return head
}
}
return null
};
