【算法面試】leetcode最常見的150道前端面試題 --- 中等題

兄弟姐妹們，中等題來了，本篇17道，剩下63道，每周更新10道！

之前簡(jiǎn)單題的鏈接如下：

• 【算法面試】leetcode最常見的150道前端面試題 --- 簡(jiǎn)單題下（44題)
• 【算法面試】leetcode最常見的150道前端面試題 --- 簡(jiǎn)單題上（44題）^[2]

378. 有序矩陣中第 K 小的元素(中等難度)

給你一個(gè) n x n 矩陣 matrix ，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。請(qǐng)注意，它是 排序后 的第 k 小元素，而不是第 k 個(gè) 不同 的元素。

示例 1：

輸入：matrix =?[[1,5,9],[10,11,13],[12,13,15]],?k?=?8
輸出：13
解釋：矩陣中的元素為?[1,5,9,10,11,12,13,13,15]，第?8?小元素是?13
復(fù)制代碼

示例 2：

輸入：matrix =?[[-5]],?k?=?1
輸出：-5
復(fù)制代碼

在刷leetcode時(shí)，我發(fā)現(xiàn)一類問題（Topk問題，只要問你前n個(gè)或者后n個(gè)最大最小值，我們講的方法非常容易解決）可以用優(yōu)先隊(duì)列非常輕松的解決，優(yōu)先隊(duì)列可以用二叉堆這個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。

但是我們javascript沒有這種數(shù)據(jù)結(jié)構(gòu)，所以需要我們手寫一個(gè)。

簡(jiǎn)單介紹一下二叉堆的特點(diǎn)：

• 它是一顆完全的二叉樹，表示樹的每一層都有左側(cè)和右側(cè)子節(jié)點(diǎn)（除了最后一層的葉子節(jié)點(diǎn)），并且最后一層的葉節(jié)點(diǎn)盡可能都是左側(cè)子節(jié)點(diǎn)
• 二叉堆不是最小堆就是最大堆。最小堆允許你快速導(dǎo)出樹的最小值，最大堆允許你快速導(dǎo)出樹的最大值。所有的節(jié)點(diǎn)都大于等于最大堆或小于等于最小堆的每個(gè)它的子節(jié)點(diǎn)

以下是二叉堆示意圖：

我們用數(shù)組來模擬這樣一個(gè)二叉堆。

我們需要一個(gè)前置知識(shí)點(diǎn)，就是數(shù)組如何模擬二叉樹。

對(duì)于給定的位置index的節(jié)點(diǎn)

• 它的左側(cè)子節(jié)點(diǎn)的位置是 2 * index + 1
• 它的右側(cè)子節(jié)點(diǎn)的位置是 2 * index + 2
• 它的父節(jié)點(diǎn)的位置是 (index-1) / 2 如果位置可用

所以接下來，我們就用數(shù)組來寫一個(gè)二叉堆：

以下是一個(gè)比較函數(shù)，比較兩個(gè)數(shù)誰(shuí)大誰(shuí)小

const?COMPARE_NUM?=?{
????less:?-1,
????great:?1,
????equal:?0,
}
function?defaultCompreFn(i,?j){
??if(i?-?j?===?COMPARE_NUM.equal)?return?COMPARE_NUM.equal;
??return?i?>?j???COMPARE_NUM.great?:?COMPARE_NUM.less;
}
復(fù)制代碼

最小堆的數(shù)據(jù)部分，包括堆的數(shù)組表示，heap屬性和比較函數(shù)compareFn

class?MinHeap{
??constructor(compareFn?=?defaultCompreFn){
??????this.heap?=?[];
??????this.compareFn?=?compareFn;
??}
復(fù)制代碼

以下是獲取節(jié)點(diǎn)左右子樹和父節(jié)點(diǎn)下標(biāo)的方法

?getLeftIndex(index){
??????return?2?*?index?+?1;
??}
??
??getRightIndex(index){
??????return?2?*?index?+?2;
??}
??
??getParentIndex(index){
??????if(index?===?0)?return;
??????return?(index?-?1)?>>?1;
??}
復(fù)制代碼

以下是工具方法，用來交換數(shù)據(jù)

?swap(i,?j){
??????[this.heap[i],?this.heap[j]]?=?[this.heap[j],?this.heap[i]];
??}
復(fù)制代碼

以下是插入數(shù)據(jù)的方法

?insert(value){
??????if(value?!==?null){
??????????//?往數(shù)組末尾添加數(shù)據(jù)
??????????this.heap.push(value);
??????????//?添加的數(shù)據(jù)上移到堆合適的位置
??????????this.siftUp(this.heap.length?-?1);
??????????return?true;
??????}
??????return?false;
??}
??
??siftUp(index){
??????let?parentIndex?=?this.getParentIndex(index);
??????//?index?>?0?非常必要，因?yàn)閕ndex等于0就到了小頂堆的頂部了
??????while(index?>?0?&&?this.compareFn(this.heap[index],?this.heap[parentIndex])?===?COMPARE_NUM.less)?{
??????????this.swap(index,?parentIndex);
??????????index?=?parentIndex;
??????????parentIndex?=?this.getParentIndex(parentIndex);
??????}
??}
復(fù)制代碼

取出小頂堆的最小值

?extract(){
??????if(this.heap.length?===?0)?return;
??????if(this.heap.length?===?1)?return?this.heap.shift();
??????const?removedValue?=?this.heap[0];
??????this.heap[0]?=?this.heap.pop();
??????//?下移從最后面放到第一位的元素
??????this.siftDown(0);
??????return?removedValue;
??}
復(fù)制代碼

下移操作，主要思路就是比較葉子節(jié)點(diǎn)和自己誰(shuí)更小，小的就上移

?siftDown(index)?{
?????let?tempIndex?=?index;
?????const?leftIndex?=?this.getLeftIndex(index);
?????const?rightIndex?=?this.getRightIndex(index);
?????if(leftIndex?this.heap.length?&&?this.compareFn(this.heap[leftIndex],?this.heap[tempIndex])?===?COMPARE_NUM.less)?{
?????????tempIndex?=?leftIndex;
?????}
?????if(rightIndex?this.heap.length?&&?this.compareFn(this.heap[rightIndex],this.heap[tempIndex])?===?COMPARE_NUM.less)?{
?????????tempIndex?=?rightIndex;
?????}
?????if(tempIndex?!==?index){
?????????this.swap(tempIndex,?index);
?????????this.siftDown(tempIndex);
?????}
?}
}
復(fù)制代碼

好了，我們用這個(gè)數(shù)據(jù)結(jié)構(gòu)來解題吧，非常好用！

好了，這種題，我們叫做TopK，意思是題目要求我們找矩陣中第k小元素，我們就用一個(gè)小頂堆把所有元素裝進(jìn)來，然后移除k個(gè)，就是答案啦！

下面的代碼是不是很簡(jiǎn)單，這道題中等難度簡(jiǎn)直比簡(jiǎn)單題還簡(jiǎn)單！

var?kthSmallest?=?function(matrix,?k)?{
????let?result;
????const?length?=?matrix.length;
????const?heap?=?new?MinHeap();
????for(let?i?=?0;?i?????????for(let?j?=?0;?j?????????????heap.insert(matrix[i][j])
????????}
????}
????while(k--){
????????result?=?heap.extract();
????}

????return?result;
};
復(fù)制代碼

刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第?n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

進(jìn)階： 你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？

輸入：head = [1,2,3,4,5], n = 2 輸出：[1,2,3,5] 示例 2：

輸入：head = [1], n = 1 輸出：[] 示例 3：

輸入：head = [1,2], n = 1 輸出：[1]

思路：

如何使用快慢指針找到倒數(shù)第n個(gè)節(jié)點(diǎn)？

• 首先設(shè)置快指針先走n步，到達(dá)從頭數(shù)，鏈表第n個(gè)節(jié)點(diǎn)
• 慢指針從頭開始走，跟快指針一起走，快指針到達(dá)鏈表盡頭的時(shí)候，慢指針的下一個(gè)節(jié)點(diǎn)就是第n個(gè)節(jié)點(diǎn)

```javascript
var?removeNthFromEnd?=?function(head,?n)?{
??let?slow?=?slowCopy?=?fast?=?new?ListNode();
??slow.next?=?head;
??while(n--){
??????fast?=?fast.next;
??}
??while(fast.next){
??????slow?=?slow.next;
??????fast?=?fast.next;
??}
??slow.next?=?slow.next.next;
??return?slowCopy.next;
};
復(fù)制代碼

36. 有效的數(shù)獨(dú)

請(qǐng)你判斷一個(gè)?9x9?的數(shù)獨(dú)是否有效。只需要 根據(jù)以下規(guī)則?，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

1. 數(shù)字?1-9?在每一行只能出現(xiàn)一次。
2. 數(shù)字?1-9?在每一列只能出現(xiàn)一次。
3. 數(shù)字?1-9?在每一個(gè)以粗實(shí)線分隔的?3x3?宮內(nèi)只能出現(xiàn)一次。（請(qǐng)參考示例圖）

數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用?'.'?表示。

注意：

• 一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。
• 只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

示例 1：

輸入：board =?
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出：true
復(fù)制代碼

示例 2：

輸入：board =?
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出：false
復(fù)制代碼

解釋：除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無(wú)效的。

思路：這道題就按照題目要求依次檢查就行，橫豎兩個(gè)方向的檢查很容易，就是3x3的格子，需要找到驗(yàn)證規(guī)律，如下圖

3x3的驗(yàn)證關(guān)鍵就是橫向坐標(biāo)和豎直方向坐標(biāo)都 %3 看是否 等于 0， 如果等于0，說明從這個(gè)位置開始，橫向和縱向3x3就是我們要驗(yàn)證的區(qū)域。

var?isExistInMap?=?function(?map,?item)?{
????if(map[item]?&&?item?!==?'.'){
????????return?false;
????}?else?{
????????map[item]?=?item;
????????return?true;
????}
};
var?validateHV?=?function(nums)?{
????const?validateMap?=?{};
????return?nums.every(num?=>?isExistInMap(validateMap,?num));
};

var?validate3x3?=?function(nums)?{
????const?validateMap?=?{};
????return?nums.every(num?=>?isExistInMap(validateMap,?num));
};

var?getVerticalNums?=?function(nums,?row)?{
????const?result?=?[];
????for(let?i?=?0;?i?????return?result;
};

var?get3x3?=?function(nums,?row,?col)?{
????const?result?=?[];
????for(let?i?=?col;?i?3;?i++)?{
????????for(let?j?=?row;?j?3;?j++){
????????????result.push(nums[i][j]);
????????}?
????}
????return?result;
};

var?isValidSudoku?=?function(board)?{
????for(let?i?=?0;?i?9;?i++)?{
????????if(!validateHV(board[i]))?return?false;
????????if(!validateHV(getVerticalNums(board,?i)))?return?false;
????????for(let?j?=?0;?j?9;?j++)?{
????????????if(i?%?3?===?0?&&?j?%?3?===?0?&&?!validateHV(get3x3(board,?i,?j)))?return?false
????????}
????}
????return?true;
};
復(fù)制代碼

38. 外觀數(shù)列

給定一個(gè)正整數(shù)?n?，輸出外觀數(shù)列的第?n?項(xiàng)。

「外觀數(shù)列」是一個(gè)整數(shù)序列，從數(shù)字 1 開始，序列中的每一項(xiàng)都是對(duì)前一項(xiàng)的描述。

你可以將其視作是由遞歸公式定義的數(shù)字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n)?是對(duì)?countAndSay(n-1)?的描述，然后轉(zhuǎn)換成另一個(gè)數(shù)字字符串。

前五項(xiàng)如下：

1.?????1
2.?????11
3.?????21
4.?????1211
5.?????111221
第一項(xiàng)是數(shù)字?1?
描述前一項(xiàng)，這個(gè)數(shù)是?1?即?“?一?個(gè)?1?”，記作?"11"
描述前一項(xiàng)，這個(gè)數(shù)是?11?即?“?二?個(gè)?1?”?，記作?"21"
描述前一項(xiàng)，這個(gè)數(shù)是?21?即?“?一?個(gè)?2?+?一?個(gè)?1?”?，記作?"1211"
描述前一項(xiàng)，這個(gè)數(shù)是?1211?即?“?一?個(gè)?1?+?一?個(gè)?2?+?二?個(gè)?1?”?，記作?"111221"
復(fù)制代碼

這個(gè)題思路主要是如下的generatorCount函數(shù)，這個(gè)函數(shù)的思路就是求任意數(shù)字，如何轉(zhuǎn)化

• 從第一個(gè)字符串開始，遍歷字符串
• 如果前一個(gè)字符和后一個(gè)字符相同，就加在一起，直到后一個(gè)字符和前一個(gè)字符不一樣
• 然后統(tǒng)計(jì)之前相同字符的個(gè)數(shù)，以此類推

var?countAndSay?=?function(n)?{
??if(n?===?1)?return?'1';
??return?generatorCount(countAndSay(n-1));
??
};
function?generatorCount(n){
??let?initStr?=?n[0];
??let?result?=''
??for(let?i?=?0;?i???????if(n[i]?===?n[i+1]){
??????????initStr?+=?n[i+1]
??????}else{
??????????result?+=?initStr.length?+?initStr[0];
??????????initStr?=?n[i+1];
??????}
??}
??return?result;
}
復(fù)制代碼

46. 全排列

給定一個(gè)不含重復(fù)數(shù)字的數(shù)組?nums?，返回其?所有可能的全排列?。你可以?按任意順序?返回答案。

示例 1：

輸入：nums =?[1,2,3]
輸出：?[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
復(fù)制代碼

示例 2：

輸入：nums =?[0,1]
輸出：?[[0,1],[1,0]]
復(fù)制代碼

示例 3：

輸入：nums =?[1]
輸出：?[[1]]
復(fù)制代碼

思路：

這道題是典型的回溯問題，全排列就是把各種組合全部打印出來，但是這個(gè)題需要去重。

主要思路就是按照上圖的畫法

• 回溯中參數(shù)為原始數(shù)組nums，以及當(dāng)前數(shù)組arr
• 回溯的終止條件為，當(dāng)前arr的個(gè)數(shù)已經(jīng)等于原始數(shù)組nums
• 回溯的處理，循環(huán)遍歷原始數(shù)組nums,當(dāng)前值不存在arr中時(shí)，將該值放入arr中，遞歸調(diào)用

var?permute?=?function(nums)?{
??const?result?=?[];
??function?dfs(partialResult){
??????if(partialResult.length?===?nums.length){
??????????result.push(partialResult);
??????????return;
??????}
??????for(let?i?=?0,?len?=?nums.length;?i???????????if(partialResult.includes(nums[i]))?{?continue?};
??????????dfs(partialResult.concat(nums[i]));
??????}
??}
??dfs([]);
??return?result;
};
復(fù)制代碼

旋轉(zhuǎn)圖像

給定一個(gè) n × n 的二維矩陣 matrix 表示一個(gè)圖像。請(qǐng)你將圖像順時(shí)針旋轉(zhuǎn) 90 度。

你必須在 原地 旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要 使用另一個(gè)矩陣來旋轉(zhuǎn)圖像。

示例 1：

輸入：matrix =?[[1,2,3],[4,5,6],[7,8,9]]
輸出：?[[7,4,1],[8,5,2],[9,6,3]]
復(fù)制代碼

示例 2：

輸入：matrix =?[[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
輸出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
復(fù)制代碼

示例 3：

輸入：matrix =?[[1]]
輸出：[[1]]
復(fù)制代碼

示例 4：

輸入：matrix =?[[1,2],[3,4]]
輸出：[[3,1],[4,2]]
復(fù)制代碼

思路

首先輸入

1?2?3
4?5?6
7?8?9
復(fù)制代碼

通過交換matrix[i][j], matrix[j][i] 得到

1?4?7
2?5?8
3?6?9
復(fù)制代碼

最后將得到每組數(shù)組倒序排列即可

7?4?1
8?5?2
9?6?3
復(fù)制代碼

思路：首先將輸入

1?2?3
4?5?6
7?8?9
復(fù)制代碼

通過交換matrix[i][j], matrix[j][i] 得到

1?4?7
2?5?8
3?6?9
復(fù)制代碼

最后將得到每組數(shù)組倒序排列即可

7?4?1
8?5?2
9?6?3
復(fù)制代碼

var?rotate?=?function(matrix)?{
??for(let?i?=?0;?i???????for(let?j?=?i;?j???????????[matrix[i][j],?matrix[j][i]]?=?[matrix[j][i],?matrix[i][j]]
??????}
??}
??return?matrix.map(item?=>?item.reverse());
};

復(fù)制代碼

49. 字母異位詞分組

難度中等804

給定一個(gè)字符串?dāng)?shù)組，將字母異位詞組合在一起?？梢园慈我忭樞蚍祷亟Y(jié)果列表。

字母異位詞指字母相同，但排列不同的字符串。

示例 1:

輸入:?strs?=?["eat",?"tea",?"tan",?"ate",?"nat",?"bat"]
輸出:?[["bat"],["nat","tan"],["ate","eat","tea"]]
復(fù)制代碼

示例 2:

輸入:?strs?=?[""]
輸出:?[[""]]
復(fù)制代碼

示例 3:

輸入:?strs?=?["a"]
輸出:?[["a"]]
復(fù)制代碼

思路：

就是排序的字符串肯定相同，然后用一個(gè)哈希map發(fā)現(xiàn)排序的字符串相同就把他們加進(jìn)去就行了

var?groupAnagrams?=?function(strs)?{
??const?recordMap?=?{};
??const?result?=?[];
??for(let?str?of?strs){
??????const?sortStr?=?str.split('').sort().join('');
??????if(recordMap[sortStr]){
??????????recordMap[sortStr].push(str);
??????}?else?{
??????????recordMap[sortStr]?=?[str];
??????}
??}
??for(let?key?in?recordMap){
??????result.push(recordMap[key])
??}
??return?result;
};
復(fù)制代碼

2. 兩數(shù)相加

給你兩個(gè)?非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照?逆序?的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ)?一位?數(shù)字。

請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0?開頭。

示例 1：

輸入：l1 =?[2,4,3],?l2?=?[5,6,4]
輸出：[7,0,8]
解釋：342?+?465?=?807.
復(fù)制代碼

示例 2：

輸入：l1 =?[0],?l2?=?[0]
輸出：[0]
復(fù)制代碼

示例 3：

輸入：l1 =?[9,9,9,9,9,9,9],?l2?=?[9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]
復(fù)制代碼

這個(gè)兩個(gè)數(shù)相加就跟我們之前簡(jiǎn)單題有一道叫做：加1，算法過程幾乎是一模一樣的.

不過需要注意：做有關(guān)鏈表的題，有個(gè)隱藏技巧：添加一個(gè)虛擬頭結(jié)點(diǎn)（哨兵節(jié)點(diǎn)），幫助簡(jiǎn)化邊界情況的判斷 具體思路。

思路：從最低位至最高位，逐位相加，如果和大于等于 10，則保留個(gè)位數(shù)字，同時(shí)向前一位進(jìn) 1 如果最高位有進(jìn)位，則需在最前面補(bǔ) 1。

var?addTwoNumbers?=?function(l1,?l2)?{
????let?carry=?0;
????let?pre?=?point?=??new?ListNode();
????while(l1?||?l2){
????????point.next?=?new?ListNode();
????????point?=?point.next;
????????let?sum?=?0;
????????if(l1){
????????????sum?+=?l1.val;
????????????l1?=?l1.next;
????????}
????????if(l2){
????????????sum?+=?l2.val;
????????????l2?=?l2.next;
????????}
????????sum?=?sum?+?carry;
????????point.val?=?sum?%?10;
????????carry?=?(sum?/?10)?|?0;
????}
????if(carry)?point.next?=?new?ListNode(carry);
????return?pre.next;
};
復(fù)制代碼

3. 無(wú)重復(fù)字符的最長(zhǎng)子串

題目如下：給定一個(gè)字符串 s ，請(qǐng)你找出其中不含有重復(fù)字符的?最長(zhǎng)子串?的長(zhǎng)度。

示例?1:

輸入:?s?=?"abcabcbb"
輸出:?3?
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"abc"，所以其長(zhǎng)度為?3。
復(fù)制代碼

示例 2:

輸入:?s?=?"bbbbb"
輸出:?1
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"b"，所以其長(zhǎng)度為?1。
復(fù)制代碼

示例 3:

輸入:?s?=?"pwwkew"
輸出:?3
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"wke"，所以其長(zhǎng)度為?3。
?????請(qǐng)注意，你的答案必須是?子串?的長(zhǎng)度，"pwke"?是一個(gè)子序列，不是子串。
復(fù)制代碼

這個(gè)題是典型的滑動(dòng)串口類的題目，我們舉例來說明什么是滑動(dòng)窗口,

如下：比如字符串abcabcbb ，假設(shè)我們已經(jīng)到abc，此時(shí)下一個(gè)是a也就是abca，我們之前維護(hù)了一個(gè)不重復(fù)的字符串序列是abc，現(xiàn)在接著又出現(xiàn)a了，說明不重復(fù)序列需要重新組織了，就編程了abca把第一個(gè)a刪掉，成為bca，然后繼續(xù)向前遍歷，按照我們剛才說的規(guī)律去維護(hù)不重復(fù)的字符串序列，最后看這些序列誰(shuí)最長(zhǎng)。

?┌─┐
??│a│b?c?a?b?c?b?b???#?max?=?0?,?arr.length?=1???取最大得：? max =?1??
??└─┘

??┌───┐
??│a?b│c?a?b?c?b?b???#?max?=?1?,?arr.length?=2???取最大得：? max =?2
??└───┘

??┌─────┐
??│a?b?c│a?b?c?b?b???#?max?=?2?,?arr.length?=3???取最大得：? max =?3
??└─────┘

????┌─────┐
???a│b?c?a│b?c?b?b???#?max?=?3?,?arr.length?=1???取最大得：? max =?3
????└─────┘

??????┌─────┐
???a?b│c?a?b│c?b?b???#?max?=?3?,?arr.length?=1???取最大得：? max =?3
??????└─────┘

????????┌─────┐
???a?b?c│a?b?c│b?b????#?max?=?3?,?arr.length?=1???取最大得：? max =?3
????????└─────┘

????????????┌───┐
???a?b?c?a?b│c?b│b????#?max?=?3?,?arr.length?=1???取最大得：? max =?3
????????????└───┘

????????????????┌─┐
???a?b?c?a?b?c?b│b│???#?max?=?3?,?arr.length?=1???取最大得：? max =?3
復(fù)制代碼

圖解pwwabw

?┌─┐
?│p│w?w?a?b?w
?└─┘

?┌───┐
?│p?w│w?a?b?w
?└───┘

?????┌─┐
??p?w│w│a?b?w
?????└─┘

?????┌───┐
??p?w│w?a│b?w
?????└───┘

?????┌─────┐
??p?w│w?a?b│w
?????└─────┘

???????┌─────┐
??p?w?w│a?b?w│
???????└─────┘
復(fù)制代碼

所以我們的代碼就出來了，解法有很多，我這個(gè)不是最優(yōu)解，但是容易理解：

var?lengthOfLongestSubstring?=?function(s)?{
????if(s.length?===?0)?return?0;
????const?map?=?{};
????//?這個(gè)指針就是指向最新維護(hù)不重復(fù)序列的最開始字母的下標(biāo)
????let?start?=?0;
????let?ret?=?0;
????for(let?i?=?0;?i?????????//?如果map出現(xiàn)了相同的字母，并且之前出現(xiàn)的字母的下標(biāo)大于等于不重復(fù)序列最開始的下標(biāo)就更新下標(biāo)
????????//?這個(gè)是最難理解的地方，我也是想了一段時(shí)間才理解的，剛開始不理解沒關(guān)系
????????if(map[s[i]]?!==?undefined?&&?map[s[i]]?>=?start){
????????????start?=?map[s[i]]?+?1
????????}
????????map[s[i]]?=?i;
????????//?每次都更新結(jié)果，結(jié)果就會(huì)當(dāng)前的下標(biāo)減去最新的不重復(fù)序列的下標(biāo)
????????//?+1是因?yàn)榍箝L(zhǎng)度，比如3到4的長(zhǎng)度是2，就是4?-?3?+?1?=?2
????????ret?=?Math.max(ret,?i?-?start?+?1)
????}
????return?ret
};
復(fù)制代碼

在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

題目如下：

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回?[-1, -1]。

進(jìn)階：

你可以設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(log n)?的算法解決此問題嗎？

示例 1：

輸入：nums =?[5,7,7,8,8,10],?target?=?8
輸出：[3,4]
復(fù)制代碼

示例 2：

輸入：nums =?[5,7,7,8,8,10],?target?=?6
輸出：[-1,-1]
復(fù)制代碼

示例 3：

輸入：nums =?[], target =?0
輸出：[-1,-1]
復(fù)制代碼

這道題，我們可以使用暴力解法：

• 利用數(shù)組有序的特點(diǎn)從頭到尾遍歷一次數(shù)組
• 在遍歷的時(shí)候，用一個(gè)數(shù)組記錄等于target的下標(biāo)，最后取數(shù)組第一個(gè)和最后一個(gè)值

但是題目說如何在?O(log n)?的時(shí)間復(fù)雜度解決問題，這就不得不換個(gè)解法了，我們采用二分法去解決這個(gè)題

在解決這個(gè)題之前我們需要解決一個(gè)問題

• 如何用2分法找到目標(biāo)值target最左邊的值，比如

輸入：nums =?[5,7,7,8,8,10]
復(fù)制代碼

如何找到最左邊的7，

我們需要考慮3種情況

• 
  
1. 如果target是4，也就是在左邊界5左邊，不在數(shù)組中
• 
  
2. 如果target是12，也就是在有邊界的右邊，不在數(shù)組中
• 
  
3. 如果target在數(shù)組中，比如target = 8

這3種情況，我們介紹一種方法，就是二分法一直二分，最后會(huì)有一規(guī)律，

• 如果找數(shù)組中沒有的元素并且小于數(shù)組最左邊的元素，會(huì)返回?cái)?shù)組下標(biāo)0

• 如果找數(shù)組中沒有的元素并且大于數(shù)組最右邊的元素，會(huì)返回?cái)?shù)組長(zhǎng)度-1（也就是最后一個(gè)元素的下標(biāo)）

• 如果找數(shù)組中有的元素，那么會(huì)返回相同元素最左邊的元素

const?findLeftBoundary?=?(nums,?target)?=>?{
????let?left?=?0;
????let?right?=?nums.length?-?1;
????while(left?<=?right){
?????????let?mid?=?Math.floor((left?+?right)?/?2);
????????if(nums[mid]?>=?target){
????????????right?=?mid?-?1;
????????}?else?{
????????????left?=?mid?+?1;
????????}
????}
????return?left;
}

findLeftBoundary([5,7,7,8,8,10],?4)?//?0
findLeftBoundary([5,7,7,8,8,10],?7)??//?1
findLeftBoundary([5,7,7,8,8,10],?12)?//?6
復(fù)制代碼

意思是這種一直二分的函數(shù)，會(huì)讓我們找到左邊界，例如上面

• target = 4，因?yàn)閿?shù)組里沒有4，所以左邊界就是最左邊的元素的下標(biāo)
• target = 7，因?yàn)閿?shù)組里有7，所以左邊界就是7在數(shù)組最左邊元素的下標(biāo)
• target = 12，因?yàn)閿?shù)組沒有6，所以數(shù)組最右邊的下標(biāo)

上面的函數(shù)還有一個(gè)功能就是找右邊界，也就是指

• 如果找9，會(huì)返回下標(biāo)5，因?yàn)?0離9右邊最近
• 如果找7.5，會(huì)返回下標(biāo)3，因?yàn)?離7.5右邊最近

?var?searchRange?=?function?(nums,?target)?{
??????const?findLeft?=?(nums,?target)?=>?{
????????let?left?=?0;
????????let?right?=?nums.length?-?1;
????????while?(left?<=?right)?{
??????????let?mid?=?Math.floor((left?+?right)?/?2);
??????????if?(nums[mid]?>=?target)?{
????????????right?=?mid?-?1;
??????????}?else?{
????????????left?=?mid?+?1;
??????????}
????????}
????????return?left;
??????}
??????if?(nums[findLeft(nums,?target)]?!==?target)
????????return?[-1,?-1]
??????else
????????return?[findLeft(nums,?target),?findLeft(nums,?target?+?1)?-?1]
????};
復(fù)制代碼

5. 最長(zhǎng)回文子串

下面是一道動(dòng)態(tài)規(guī)劃的題（也有其他解法）：

給你一個(gè)字符串?s，找到?s?中最長(zhǎng)的回文子串。

示例 1：

輸入：s =?"babad"
輸出：?"bab"
解釋：?"aba"?同樣是符合題意的答案。
復(fù)制代碼

示例 2：

輸入：s =?"cbbd"
輸出：?"bb"
復(fù)制代碼

示例 3：

輸入：s =?"a"
輸出：?"a"
復(fù)制代碼

示例 4：

輸入：s =?"ac"
輸出：?"a"
復(fù)制代碼

思路：

• 
  
1. 確定DP數(shù)組和下標(biāo)的含義：dp[i][j] 表示 區(qū)間范圍 [i,j]（左閉右閉）的字串是否是回文串，如果是，則 dp[i][j] 為 true；反之，為 false
• 
  
• 如果 s[i] != s[j]，dp[i][j] 為 false
• 如果 s[i] == s[j]，則有三種情況：
• 當(dāng) 下標(biāo)i與 下標(biāo) j 相同，則 s[i] 和 s[j] 是同一個(gè)字符，例如 a，這是回文串
• 當(dāng) 下標(biāo)i 與 下標(biāo) j 相差為 1，例如 aa，也是回文串
• 當(dāng) 下標(biāo)i 與 下標(biāo) j 相差大于 1 時(shí)，例如 abcba，這時(shí)候就看bcb 是否是回文串，bcb 的區(qū)間是 [i + 1, j - 1]
• 如果 dp[i][j] 是回文串，并且長(zhǎng)度大于結(jié)果長(zhǎng)度：我們就更新結(jié)果
2. 確定遞推公式：

const?longestPalindrome?=?function?(s)?{
??let?result?=?s[0];
??const?dp?=?[];
??for?(let?i?=?0;?i?????dp[i]?=?[];
????for?(let?j?=?0;?j?<=?i;?j++)?{
??????if?(i?-?j?===?0)?{
????????dp[i][j]?=?true;
??????}?else?if?(i?-?j?===?1?&&?s[i]?===?s[j])?{
????????dp[i][j]?=?true;
??????}?else?if?(s[i]?===?s[j]?&&?dp[i?-?1][j?+?1])?dp[i][j]?=?true;
??????if?(dp[i][j]?&&?i?-?j?+?1?>?result.length)?{
????????result?=?s.slice(j,?i?+?1);
??????}
????}
??}
??return?result;
};
復(fù)制代碼

盛最多水的容器

給你 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)?(i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個(gè)端點(diǎn)分別為?(i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

說明：你不能傾斜容器。

示例 1：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49?
解釋：圖中垂直線代表輸入數(shù)組?[1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為?49。
復(fù)制代碼

示例 2：

輸入：height =?[1,1]
輸出：1
復(fù)制代碼

示例 3：

輸入：height =?[4,3,2,1,4]
輸出：16
復(fù)制代碼

思路：

• 根據(jù)面積計(jì)算規(guī)則，面積是由兩個(gè)柱子的距離和柱子最低高度決定的。

• 一開始前后指針指向第一根柱子和最后一根柱子，計(jì)算這兩根柱子的面積，此時(shí)他們距離是最大的。

• 后面的柱子水平距離肯定小于第一根柱子和最后一根柱子的距離，所以只有在高度上，兩根柱子更高才有機(jī)會(huì)比之前的大），再重新計(jì)算面積，并和前面的比較，取最大值

var?maxArea?=?function(height)?{
????let?left?=?0;
????let?right?=?height.length?-?1;
????let?result?=?0;
????while(left?????????if(height[left]?<=?height[right]){
????????????result?=?Math.max(height[left]?*?(right?-?left),?result);
????????????left++
????????}?else?{
????????????result?=?Math.max(height[right]?*?(right?-?left),?result);
????????????right--
????????}
????}
????return?result;
};
復(fù)制代碼

三數(shù)之和

給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有和為 0 且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例 1：

輸入：nums =?[-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
復(fù)制代碼

示例 2：

輸入：nums =?[]
輸出：[]
復(fù)制代碼

示例 3：

輸入：nums =?[0]
輸出：[]
復(fù)制代碼

思路：排序 + 雙指針

1. 排序

為什么要排序呢？我想是不是這樣：

• 排序后相同的數(shù)會(huì)挨在一起，對(duì)于去除重復(fù)的數(shù)字有幫助，比如說[-1,-1,0,2]其中兩個(gè)-1和0，2都能3數(shù)字之和為0，我們排序之后左邊相同的就直接忽略掉了。

2. 遍歷

• 使用三個(gè)指針 i、j 和 k 分別代表要找的三個(gè)數(shù)。

• 通過枚舉 i 確定第一個(gè)數(shù)，另外兩個(gè)指針 j，k 分別從左邊 i + 1 和右邊 n - 1 往中間移動(dòng)，找到滿足 nums[i] + nums[j] + nums[k] == 0 的所有組合。

• j 和 k 指針的移動(dòng)邏輯，分情況討論 sum = nums[i] + nums[j] + nums[k] ：

• sum > 0：k 左移，使 sum 變小

• sum < 0：j 右移，使 sum 變大

• sum = 0：找到符合要求的答案，存起來

const?threeSum?=?(nums)?=>?{
????nums.sort((a,?b)?=>?a-b);
????const?res?=?[];
????????if(nums?==?null?||?nums.length3){
????????return?[];
????}
????for(let?i?=?0;?i?2;?i++){
????????const?curr?=?nums[i];
????????if(curr?>?0)?break;
????????if(i?-?1?>=?0?&&?curr?===?nums[i-1])?continue;
????????let?left?=?i+1;
????????let?right?=?nums.length?-1;
????????while(left?????????????let?l?=?nums[left];let?r?=?nums[right];
????????????if(curr?+?nums[left]?+?nums[right]?===?0){
????????????????res.push([curr,?nums[left],?nums[right]]);
????????????????while(left?????????????????while(left?????????????}?else?if?(curr?+?nums[left]?+?nums[right]?>?0){
????????????????right--;
????????????}?else?{
????????????????left++;
????????????}
????????}
????}
????return?res;
};
復(fù)制代碼

17 電話號(hào)碼的字母組合

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

示例 1：

輸入：digits =?"23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
復(fù)制代碼

示例 2：

輸入：digits =?""
輸出：[]
復(fù)制代碼

示例 3：

輸入：digits =?"2"
輸出：["a","b","c"]
復(fù)制代碼

思路：這是一類叫全排列的算法類型，試著去理解解題的過程，比如

• 當(dāng)給定了輸入字符串，比如："23"，那么整棵樹就構(gòu)建完成了，如下：

var?letterCombinations?=?function(digits)?{
??if?(digits.length?==?0)?return?[];
???const?res?=?[];
???const?map?=?{?'2':?'abc',?'3':?'def',?'4':?'ghi',?'5':?'jkl',?'6':?'mno',?'7':?'pqrs',?'8':?'tuv',?'9':?'wxyz'?};
?????function?dfs(str,?deep){
???????if(str.length?===?digits.length){
????????res.push(str);
????????return;
?????}
?????let?curr=?map[digits[deep]];
?????for(let?i?=0;?i???????dfs(str?+?curr[i],?deep?+?1)
???}
??}
???dfs('',0)
???return?res
?};
復(fù)制代碼

22. 括號(hào)生成

數(shù)字?n?代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且?有效的 括號(hào)組合。

示例 1：

輸入：n =?3
輸出：?["((()))","(()())","(())()","()(())","()()()"]
復(fù)制代碼

示例 2：

輸入：n =?1
輸出：?["()"]
復(fù)制代碼

var?generateParenthesis?=?function?(n)?{
??const?res?=?[];

??const?dfs?=?(lRemain,?rRemain,?str)?=>?{?//?左右括號(hào)所剩的數(shù)量，str是當(dāng)前構(gòu)建的字符串
????if?(str.length?==?2?*?n)?{?//?字符串構(gòu)建完成
??????res.push(str);???????????//?加入解集
??????return;??????????????????//?結(jié)束當(dāng)前遞歸分支
????}
????if?(lRemain?>?0)?{?????????//?只要左括號(hào)有剩，就可以選它，然后繼續(xù)做選擇（遞歸）
??????dfs(lRemain?-?1,?rRemain,?str?+?"(");
????}
????if?(lRemain?//?右括號(hào)比左括號(hào)剩的多，才能選右括號(hào)
??????dfs(lRemain,?rRemain?-?1,?str?+?")");?//?然后繼續(xù)做選擇（遞歸）
????}
??};

??dfs(n,?n,?"");?//?遞歸的入口，剩余數(shù)量都是n，初始字符串是空串
??return?res;
};
復(fù)制代碼

29. 兩數(shù)相除

這道題，說實(shí)話，可以列為比較難的題，主要是邊界處理有個(gè)天坑(1073741824 << 1) 返回 -2147483648返回負(fù)數(shù)了，加倍不能使用 << 1來乘以2。也就是位移操作符乘法運(yùn)算會(huì)有問題。（比如2進(jìn)制00001111 左移4位，就是11110000，第一位表示符號(hào)位，正數(shù)是0，負(fù)數(shù)是1，所以正數(shù)就變?yōu)樨?fù)數(shù)了）

給定兩個(gè)整數(shù)，被除數(shù)?dividend?和除數(shù)?divisor。將兩數(shù)相除，要求不使用乘法、除法和 mod 運(yùn)算符。

返回被除數(shù)?dividend?除以除數(shù)?divisor?得到的商。

整數(shù)除法的結(jié)果應(yīng)當(dāng)截去（truncate）其小數(shù)部分，例如：truncate(8.345) = 8?以及?truncate(-2.7335) = -2

示例?1:

輸入:?dividend?=?10,?divisor?=?3
輸出:?3
解釋:?10/3?=?truncate(3.33333..)?=?truncate(3)?=?3
復(fù)制代碼

示例?2:

輸入:?dividend?=?7,?divisor?=?-3
輸出:?-2
解釋:?7/-3?=?truncate(-2.33333..)?=?-2
復(fù)制代碼

思路:

• 每次以除數(shù)作為基數(shù)，不斷自加，當(dāng) sum 逼近到遞歸的被除數(shù)時(shí)，記錄當(dāng)前的 count 和剩余的值 (dividend-sum),繼續(xù)遞歸

• 如 divide(10,3) = recur(10,3) = 2 + recur(10-6,3) = 2 + 1 + recur(10-6-3, 3) = 3

• 注意，遞歸函數(shù)中都是以雙整數(shù)位基礎(chǔ)的，所以最外層調(diào)用的時(shí)候，要根據(jù)入?yún)⒅颠M(jìn)行一定的調(diào)整

最后值不能超出 [-2^31,2^31-1]

var?divide?=?function(dividend,?divisor)?{
????let?flag?=?dividend?>?0?&&?divisor?0?||?dividend?0?&&?divisor?>?0?;
????dividend?=?Math.abs(dividend);
????divisor?=?Math.abs(divisor);
????function?recur(dividend,?divisor)?{
????????let?count?=?1;
????????let?nextDivisor?=?divisor;
????????if(dividend?return?0;
????????while((nextDivisor?+?nextDivisor)?????????????count?+=?count;
????????????nextDivisor?=?nextDivisor?+?nextDivisor;
????????}
????????return?count?+?recur(dividend?-?nextDivisor,?divisor);
????}
????const?result?=??flag???-recur(dividend,?divisor)?:?recur(dividend,?divisor);
????const?max?=?Math.pow(2,?31)?-?1,?min?=?-Math.pow(2,?31);
????if?(result?>?max)?return?max
????if?(result?return?min
????return?result;
};
復(fù)制代碼

字符串轉(zhuǎn)換整數(shù) (atoi)

示例 1：

輸入：s =?"42"
輸出：42
解釋：加粗的字符串為已經(jīng)讀入的字符，插入符號(hào)是當(dāng)前讀取的字符。
第?1?步："42"（當(dāng)前沒有讀入字符，因?yàn)闆]有前導(dǎo)空格）
?????????^
第?2?步："42"（當(dāng)前沒有讀入字符，因?yàn)檫@里不存在?'-'?或者?'+'）
?????????^
第?3?步："42"（讀入?"42"）
???????????^
解析得到整數(shù)?42?。
由于?"42"?在范圍?[-231,?231?-?1]?內(nèi)，最終結(jié)果為?42?。
復(fù)制代碼

示例 2：

輸入：s =?"???-42"
輸出：-42
解釋：
第?1?步："???-42"（讀入前導(dǎo)空格，但忽視掉）
????????????^
第?2?步："???-42"（讀入?'-'?字符，所以結(jié)果應(yīng)該是負(fù)數(shù)）
?????????????^
第?3?步："???-42"（讀入?"42"）
???????????????^
解析得到整數(shù)?-42?。
由于?"-42"?在范圍?[-231,?231?-?1]?內(nèi)，最終結(jié)果為?-42?。
復(fù)制代碼

示例 3：

輸入：s =?"4193?with?words"
輸出：4193
解釋：
第?1?步："4193?with?words"（當(dāng)前沒有讀入字符，因?yàn)闆]有前導(dǎo)空格）
?????????^
第?2?步："4193?with?words"（當(dāng)前沒有讀入字符，因?yàn)檫@里不存在?'-'?或者?'+'）
?????????^
第?3?步："4193?with?words"（讀入?"4193"；由于下一個(gè)字符不是一個(gè)數(shù)字，所以讀入停止）
?????????????^
解析得到整數(shù)?4193?。
由于?"4193"?在范圍?[-231,?231?-?1]?內(nèi)，最終結(jié)果為?4193?。
復(fù)制代碼

示例 4：

輸入：s =?"words?and?987"
輸出：0
解釋：
第?1?步："words?and?987"（當(dāng)前沒有讀入字符，因?yàn)闆]有前導(dǎo)空格）
?????????^
第?2?步："words?and?987"（當(dāng)前沒有讀入字符，因?yàn)檫@里不存在?'-'?或者?'+'）
?????????^
第?3?步："words?and?987"（由于當(dāng)前字符?'w'?不是一個(gè)數(shù)字，所以讀入停止）
?????????^
解析得到整數(shù)?0?，因?yàn)闆]有讀入任何數(shù)字。
由于?0?在范圍?[-231,?231?-?1]?內(nèi)，最終結(jié)果為?0?。
復(fù)制代碼

這道題我用正則很快就解決了，不需要啥思路了。。。

var?myAtoi?=?function(s)?{
??let?result?=?s.trim().match(/^(\-|\+)?\d+/g);
??let?res?=?s.trim().match(/^(\-|\+)?\d+/g);
??return?res???Math.max(Math.min(Number(res[0]),?2**31-1),?-(2**31))?:?0;
};
復(fù)制代碼

395. 至少有 K 個(gè)重復(fù)字符的最長(zhǎng)子串

給你一個(gè)字符串?s?和一個(gè)整數(shù)?k?，請(qǐng)你找出?s?中的最長(zhǎng)子串，?要求該子串中的每一字符出現(xiàn)次數(shù)都不少于?k?。返回這一子串的長(zhǎng)度。

示例 1：

輸入：s =?"aaabb",?k?=?3
輸出：?3
解釋：?最長(zhǎng)子串為?"aaa"?，其中?'a'?重復(fù)了?3?次。
復(fù)制代碼

示例 2：

輸入：s =?"ababbc",?k?=?2
輸出：?5
解釋：?最長(zhǎng)子串為?"ababb"?，其中?'a'?重復(fù)了?2?次，?'b'?重復(fù)了?3?次。
復(fù)制代碼