1.比較含倒退的字元串
題目：
給定 S 和 T 兩個字元串，當它們分别被輸入到空白的文本編輯器後，判斷二者是否相等，并傳回結果。 # 代表倒退字元。
注意：如果對空文本輸入倒退字元，文本繼續為空。
思路：分别周遊兩個字元串，分别處理，比較處理之後的結果
/**
* @param {string} S
* @param {string} T
* @return {boolean}
*/
var backspaceCompare = function(S, T) {
let s1 = "";
let s2 = "";
for (const s of S) {
if (s == "#") {
s1 = s1.slice(0, s1.length - 1);
} else {
s1 += s;
}
}
for (const s of T) {
if (s == "#") {
s2 = s2.slice(0, s2.length - 1);
} else {
s2 += s;
}
}
return s1 === s2;
};
優化：雙指針法。可以從後往前周遊，遇到#額外往前一位，，直到消除目前位之後所有的#（倒序，也可以了解成之前 ），然後比較同一輪的兩個字元串的兩個指針對應的字元，直到處理完所有的字元
let i = S.length - 1;
let j = T.length - 1;
let backspaceNumI = 0;
let backspaceNumJ = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] === '#') {
i--;
backspaceNumI++;
} else if (backspaceNumI > 0) {
i--;
backspaceNumI--;
} else {
break;
}
}
while (j >= 0) {
if (T[j] === '#') {
j--;
backspaceNumJ++;
} else if (backspaceNumJ > 0) {
j--;
backspaceNumJ--;
} else {
break;
}
}
if (S[i] !== T[j]) return false;
i--;
j--
}
return true;
2.到最近的人的最大距離
題目：
在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。
至少有一個空座位，且至少有一人坐在座位上。
亞曆克斯希望坐在一個能夠使他與離他最近的人之間的距離達到最大化的座位上。
傳回他到離他最近的人的最大距離。
思路：周遊數組，用一個變量記錄目前的連續0的數量，用一個變量記錄最長的連續0的數量，一個變量記錄左邊的連續0的數量，周遊完之後，第一周遊就等于最右邊連續0的數量，然後比較三個值就行，第二個變量要除以2
/**
* @param {number[]} seats
* @return {number}
*/
var maxDistToClosest = function(seats) {
let length = 0;
let max = 0;
let left;
for (let i = 0, l = seats.length; i < l; i++) {
if (seats[i] == 0) {
length++;
} else {
left = left === undefined ? length : left;
max = length > max ? length : max;
length = 0;
}
}
return Math.max(left, length, Math.ceil(max / 2));
};
3.山脈數組的峰頂索引
題目：
我們把符合下列屬性的數組 A 稱作山脈：
A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
給定一個确定為山脈的數組，傳回任何滿足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。
思路：周遊，如果某個數必後面的數大， 那麼這個數肯定就是峰頂
/**
* @param {number[]} A
* @return {number}
*/
var peakIndexInMountainArray = function(A) {
let i = 1;
while (true) {
if (A[i] > A[i + 1]) return i;
i++;
}
};
4.親密字元串
題目：給定兩個由小寫字母構成的字元串
A
和
B
，隻要我們可以通過交換
A
中的兩個字母得到與
B
相等的結果，就傳回
true
；否則傳回
false
思路：先确定條件。
交換字母，并沒有說是不同字母，是以也可以是相同字母。符合條件的結果是兩種情況（A、B長度相等）：
(1)A和B隻有兩個位置的字元不同，且A[left]=B[right]，A[right]=B[left]；
(2)A和B所有位置字元相同，且A最少有一個字元出現了至少兩次
我們用一個變量left記錄第一個不同字元的位置，right變量記錄第二個不同字元的位置，flag記錄是否有字元出現過至少兩次
/**
* @param {string} A
* @param {string} B
* @return {boolean}
*/
var buddyStrings = function(A, B) {
const l1 = A.length;
if (l1 < 2) return false;
const l2 = B.length;
if (l1 !== l2) return false;
let left, right;
let flag = false;
const set = new Set();
for (let i = 0; i < l1; i++) {
if (A[i] !== B[i]) {
if (left !== undefined && right) {
return false;
} else if (left !== undefined) {
if (A[left] !== B[i] || A[i] !== B[left]) return false;
right = i;
} else {
left = i;
}
}
if (set.has(A[i])) {
flag = true;
} else {
set.add(A[i]);
}
}
return (left!==undefined&&right!==undefined) || (left === undefined && flag);
};
5.檸檬水找零
題目：
在檸檬水攤上，每一杯檸檬水的售價為 5 美元。
顧客排隊購買你的産品，（按賬單 bills 支付的順序）一次購買一杯。
每位顧客隻買一杯檸檬水，然後向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正确找零，也就是說淨交易是每位顧客向你支付 5 美元。
注意，一開始你手頭沒有任何零錢。
如果你能給每位顧客正确找零，傳回 true ，否則傳回 false 。
思路：我們用一個數組記錄目前可以用來找零錢，隻儲存5和10，因為20不可能用來找零。
遇到找零，優先用10找零，然後用5，如果需要找10，隻有一個5，那麼就是false，或者目前數組長度為0，還需要找零，也false
為了友善，把5放到數組開頭，10放到數組末尾
/**
* @param {number[]} bills
* @return {boolean}
*/
var lemonadeChange = function(bills) {
const stack = [];
for (const n of bills) {
let v = n - 5;
if (v && !stack.length) return false;
while (v) {
if (!stack.length) return false;
if (v == stack[stack.length - 1]) {
const v1 = stack.pop();
v -= v1;
} else if (v > stack[stack.length - 1]) {
const v1 = stack.pop();
v -= v1;
} else if (v == stack[0]) {
stack.shift();
v=0;
} else {
return false;
}
}
if (n == 5) {
stack.unshift(n);
} else if (n == 10) {
stack.push(n);
}
}
return true;
};
因為隻有5和10兩種，是以用兩個變量記錄這兩種貨币的數量代替數組，也可以，這種算起來也友善一點
/**
* @param {number[]} bills
* @return {boolean}
*/
var lemonadeChange = function(bills) {
let five = 0;
let ten = 0;
for (const n of bills) {
if (n == 10) {
if (!five) return false;
five--;
ten++;
} else if (n == 20) {
if (five && ten) {
five--;
ten--;
} else {
if (five < 3) return false;
five -= 3;
}
} else {
five++;
}
}
return true;
};