1.環形連結清單
題目:
給定一個連結清單,判斷連結清單中是否有環。
為了表示給定連結清單中的環,我們使用整數
pos
來表示連結清單尾連接配接到連結清單中的位置(索引從 0 開始)。 如果
pos
是
-1
,則在該連結清單中沒有環。
思路:先說最簡單的,用map記錄每個節點,然後依次比較即可
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
var map = new Map();
while (head) {
if (map.has(head)) return true;
map.set(head, 111);
head = head.next;
}
return false;
};
問題:沒什麼大問題,不過需要額外的空間,可以優化
優化方向:追及問題,又或者叫快慢指針。兩個指針,一個跑得快一個跑得慢,如果有環形,那麼肯定會相交的。
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
if (!head || !head.next) {
return false
}
let fast = head
let slow = head
while (slow) {
if (!fast || !fast.next) {
return false
}
fast = fast.next.next
slow = slow.next
if (Object.is(fast, slow)) {
return true
}
}
return false
};
2.最小棧
題目:
設計一個支援 push ,pop ,top 操作,并能在常數時間内檢索到最小元素的棧。
push(x) —— 将元素 x 推入棧中。
pop() —— 删除棧頂的元素。
top() —— 擷取棧頂元素。
getMin() —— 檢索棧中的最小元素。
思路:沒啥說的,其實比較簡單,這裡就放基于數組的實作
var MinStack = function () {
this.data = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.data.push(x);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
if (this.data.length) this.data.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
if (this.data.length) {
return this.data[this.data.length - 1];
} else {
return null;
}
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
if (this.data.length) {
return Math.min(...this.data);
} else {
return null;
}
};
基于連結清單也可以,大同小異
3.相交連結清單
題目:編寫一個程式,找到兩個單連結清單相交的起始節點。
注意:
如果兩個連結清單沒有交點,傳回 null.
在傳回結果後,兩個連結清單仍須保持原有的結構。
可假定整個連結清單結構中沒有循環。
程式盡量滿足 O(n) 時間複雜度,且僅用 O(1) 記憶體。
思路:先還是說最簡單的,用map來比較。先把第一個連結清單的節點存儲,然後周遊第二個連結清單的節點。
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let map = new Map();
while (headA) {
map.set(headA);
headA = headA.next;
}
while (headB) {
if (map.has(headB)) {
return headB;
}
headB = headB.next;
}
return null;
};
問題:需要額外的空間
優化方向:雙指針法。可以用兩個指針同時跑,如果周遊一次之後交換,如果有相交,那麼在第二次周遊的時候一定會在同一個節點結束
。如果不相交,那麼第二次周遊時最後一個節點是null
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let pa = headA;
let pb = headB;
while(pa !==pb){
pa = pa? pa.next : headB;
pb = pb? pb.next : headA;
}
return pa;
};
4.兩數之和 II
題目:
給定一個已按照升序排列 的有序數組,找到兩個數使得它們相加之和等于目标數。
函數應該傳回這兩個下标值 index1 和 index2,其中 index1 必須小于 index2。
說明:
傳回的下标值(index1 和 index2)不是從零開始的。
你可以假設每個輸入隻對應唯一的答案,而且你不可以重複使用相同的元素。
思路:還是用之前的,不過可以優化的是,因為是有序數組,可以根據最大值和最小值優先排除一些元素,這樣可以節省空間
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let l = numbers.length;
let min = target - numbers[l - 1];
let map = {};
for (let i = 1; i <= l; i++) {
if (numbers[i - 1] < min) continue;
if (map[target - numbers[i - 1]]) return [map[target - numbers[i - 1]], i];
map[numbers[i - 1]] = i;
}
};
優化方向:對撞指針。兩個指針一頭一尾,相加,如果大于目标值,則尾部向前+1,如果小于目标值,則頭部向前+1,直到得到結果
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let front=0;end=numbers.length-1;
while(front<end){
const frontNums=numbers[front];
const endNums=numbers[end];
if(frontNums+endNums>target){
end--;
}
if(frontNums+endNums<target){
front++;
}
if(frontNums+endNums===target){
// 答案是從1開始數,程式求出來起始點是0,是以 +1
return [front+1,end+1]
}
}
};
5.Excell表列名稱
題目:
給定一個正整數,傳回它在 Excel 表中相對應的列名稱。
例如,
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
輸入: 1
輸出: "A"
示例 2:
輸入: 28
輸出: "AB"
示例 3:
輸入: 701
輸出: "ZY"
思路:建立字母和數字的映射關系,A=>0,B=>1這樣,然後循環操作數字,每次取26的餘數作為目前,然後除以26的值作為下一輪的值
/**
* @param {number} n
* @return {string}
*/
let map=[ 'A', 'B', 'C', 'D', 'E', 'F', 'G',
'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z']
var convertToTitle = function (n) {
let result = ''
while (n > 0) {
n--
result = map[(n%26)] + result;
n = Math.floor(n / 26);
}
return result;
};