本文題目選自 LeetCode 精選 TOP 面試題^[1]，這些題在自己和同事親身經歷中，確實遇到的幾率在百分之80%以上（成都和北京的前端崗位）。

本篇是簡單題（下）20題左右，上半部分詳見leetcode 最常見的 150 道前端面試題（簡單題上）

二叉樹（DFS）

二叉樹前中后遍歷套路詳解

前序遍歷題目如下：

root節(jié)點是A節(jié)點（下圖的A節(jié)點），然后讓你按照下圖數(shù)字的順序依次打印出節(jié)點。

我們可以看到這其中的規(guī)律，就是深度優(yōu)先遍歷，先遍歷左子樹，再遍歷右子樹，這里我們不用遞歸，因為一些大廠嚴格要求二叉樹遍歷不用遞歸，遞歸太簡單了。

重點思路就是：深度優(yōu)先遍歷，先遍歷左子樹，再遍歷右子樹，

所以，我們需要一套如何遍歷一顆二叉樹，并且是先左子樹，再右子樹的通用模板，如下

var?Traversal?=?function(root)?{
????const?stack?=?[];
????while?(root?||?stack.length){
??????while(root){
????????stack.push(root);
????????root?=?root.left;
??????}
??????root?=?stack.pop();
??????root?=?root.right;
????}
????return?res;
};
復制代碼

我們結合圖片發(fā)現(xiàn)這個遍歷產生的整體壓棧的順序是

• A、B、D入棧，
• D出棧
• B出棧
• E入棧
• E出棧
• A出棧
• C入棧
• C出棧
• F入棧
• F出棧

我們把上面入棧的元素按順序排列一下就是，A、B、D、E、C、F，而這就是前序遍歷的順序！解答完畢！

是不是很有意思，下面的中序遍歷，我們看看出棧順序是不是中序遍歷的要求：D、B、E、A、C、F（這就是中序遍歷的要求，好了，兩個題解決）

放具體前序遍歷代碼：

var?preorderTraversal?=?function(root)?{
????//?初始化數(shù)據
????const?res?=[];
????const?stack?=?[];
????while?(root?||?stack.length){
??????while(root){
????????res.push(root.val);
????????stack.push(root);
????????root?=?root.left;
??????}
??????root?=?stack.pop();
??????root?=?root.right;
????}
????return?res;
};
復制代碼

中序遍歷是一個意思，在前序遍歷的基礎上改造一下

var?preorderTraversal?=?function(root)?{
????//?初始化數(shù)據
????const?res?=[];
????const?stack?=?[];
????while?(root?||?stack.length){
??????while(root){
????????stack.push(root);
????????root?=?root.left;
??????}
??????root?=?stack.pop();
??????res.push(root.val);
??????root?=?root.right;
????}
????return?res;
};
復制代碼

后序遍歷有點不太一樣，但是套路是一樣的，我們需要先遍歷右子樹，再遍歷左子樹，反著來，就可以了，代碼如下：

var?postorderTraversal?=?function(root)?{
??//?初始化數(shù)據
????const?res?=[];
????const?stack?=?[];
????while?(root?||?stack.length){
??????while(root){
????????stack.push(root);
????????res.unshift(root.val);
????????root?=?root.right;
??????}
??????root?=?stack.pop();
??????root?=?root.left;
????}
????return?res;
};
復制代碼

對稱二叉樹

這個題簡而言之就是判斷一個二叉樹是對稱的，比如說：

二叉樹 [1,2,2,3,4,4,3] 是對稱的。

????1
???/?\
??2???2
?/?\?/?\
3??4?4??3
復制代碼

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

????1
???/?\
??2???2
???\???\
???3????3

復制代碼

思路：

遞歸解決：

• 判斷兩個指針當前節(jié)點值是否相等
• 判斷 A 的右子樹與 B 的左子樹是否對稱
• 判斷 A 的左子樹與 B 的右子樹是否對稱

function?isSame(leftNode,?rightNode){
????if(leftNode?===?null?&&?rightNode?===?null)?return?true;
????if(leftNode?===?null?||?rightNode?===?null)?return?false;
????return?leftNode.val?===?rightNode.val?&&?isSame(leftNode.left,?rightNode.right)?&&?isSame(leftNode.right,?rightNode.left)
}
var?isSymmetric?=?function(root)?{
????if(!root)?return?root;
????return?isSame(root.left,?root.right);
};
復制代碼

二叉樹的最大深度

這個題在面試滴滴的時候遇到過，主要是掌握二叉樹遍歷的套路

• 只要遍歷到這個節(jié)點既沒有左子樹，又沒有右子樹的時候
• 說明就到底部了，這個時候如果之前記錄了深度，就可以比較是否比之前記錄的深度大，大就更新深度
• 然后以此類推，一直比較到深度最大的

var?maxDepth?=?function(root)?{
????if(!root)?return?root;
????let?ret?=?1;
????function?dfs(root,?depth){
????????if(!root.left?&&?!root.right)?ret?=?Math.max(ret,?depth);
????????if(root.left)?dfs(root.left,?depth+1);
????????if(root.right)?dfs(root.right,?depth+1);
????}
????dfs(root,?ret);
????return?ret
};
復制代碼

將有序數(shù)組轉化為二叉搜索樹

我們先看題：

給你一個整數(shù)數(shù)組 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵 高度平衡 二叉搜索樹。

高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

示例 1：

輸入：nums =?[-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9]?也將被視為正確答案：
復制代碼

示例 2：

輸入：nums =?[1,3]
輸出：[3,1]
解釋：[1,3]?和?[3,1]?都是高度平衡二叉搜索樹。
?

提示：

1?<=?nums.length?<=?104
-104?<=?nums[i]?<=?104
nums?按?嚴格遞增?順序排列
復制代碼

思路：

• 構建一顆樹包括：構建root、構建 root.left 和 root.right
• 題目要求"高度平衡" — 構建 root 時候，選擇數(shù)組的中間元素作為 root 節(jié)點值，即可保持平衡。
• 遞歸函數(shù)可以傳遞數(shù)組，也可以傳遞指針，選擇傳遞指針的時候：l r 分別代表參與構建BST的數(shù)組的首尾索引。

var?sortedArrayToBST?=?function(nums)?{
????return?toBST(nums,?0,?nums.length?-?1)
};
const?toBST?=?function(nums,?l,?r){
????if(?l?>?r){
????????return?null;
????}
????const?mid?=?l?+?r?>>?1;
????const?root?=?new?TreeNode(nums[mid]);
????root.left?=?toBST(nums,?l,?mid?-?1);
????root.right?=?toBST(nums,?mid?+?1,?r);

????return?root;
}
復制代碼

棧

棧是一種先進先出的數(shù)據結構，所以涉及到你需要先進先出這個想法后，就可以使用棧。

其次我覺得棧跟遞歸很相似，遞歸是不是先壓棧，然后先進來的先出去，就跟函數(shù)調用棧一樣。

20. 有效的括號

這是一道很典型的用棧解決的問題， 給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。左括號必須以正確的順序閉合。

示例?1：

輸入：s =?"()"
輸出：true
示例?2：

輸入：s =?"()[]{}"
輸出：true
示例?3：

輸入：s =?"(]"
輸出：false
示例?4：

輸入：s =?"([)]"
輸出：false
復制代碼

思路：這道題有一規(guī)律：

1. 右括號前面，必須是相對應的左括號，才能抵消！
2. 右括號前面，不是對應的左括號，那么該字符串，一定不是有效的括號！

也就是說左括號我們直接放入棧中即可，發(fā)現(xiàn)是右括號就要對比是否跟棧頂元素相匹配，不匹配就返回false

var?isValid?=?function(s)?{
????const?map?=?{?'{':?'}',?'(':?')',?'[':?']'?};
????const?stack?=?[];
????for(let?i?of?s){
????????if(map[i]){
????????????stack.push(i);
????????}?else?{
????????????if(map[stack[stack.length?-?1]]?===?i){
????????????????stack.pop()
????????????}else{
????????????????return?false;
????????????}
????????}
????}
????return?stack.length?===?0;
};
復制代碼

155、 最小棧

先看題目：

設計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內檢索到最小元素的棧。

• push(x) —— 將元素 x 推入棧中。
• pop() —— 刪除棧頂?shù)脑亍?/section>
• top() —— 獲取棧頂元素。
• getMin() —— 檢索棧中的最小元素。

示例:

MinStack?minStack?=?new?MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();???-->?返回?-3.
minStack.pop();
minStack.top();??????-->?返回?0.
minStack.getMin();???-->?返回?-2.

提示：

pop、top 和 getMin 操作總是在?非空棧?上調用。
復制代碼

我們先不寫getMin方法，滿足其他方法實現(xiàn)就非常簡單，我們來看一下：

var?MinStack?=?function()?{
????this.stack?=?[];
};

MinStack.prototype.push?=?function(x)?{
????this.stack.push(x);
};

MinStack.prototype.pop?=?function()?{
????this.stack.pop();
};

MinStack.prototype.top?=?function()?{
????return?this.stack[this.stack.length?-?1];
};
復制代碼

如何保證每次取最小呢，我們舉一個例子：

如上圖，我們需要一個輔助棧來記錄最小值，

• 開始我們向stack push -2
• 此時輔助棧minStack，因為此時stack最小的是-2，也push -2
• stack push 0
• 此時輔助站minStack 會用 0 跟 -2對比，-2更小，minstack會push -2
• stack push -3
• 此時輔助站minStack 會用 -3 跟 -2對比，-3更小，minstack會push -3

所以我們取最小的時候，總能在minStack中取到最小值，所以解法就出來了：

var?MinStack?=?function()?{
????this.stack?=?[];
????//?輔助棧
????this.minStack?=?[];
};

MinStack.prototype.push?=?function(x)?{
????this.stack.push(x);
????//?如果是第一次或者當前x比最小棧里的最小值還小才push?x
????if(this.minStack.length?===?0?||?x?this.minStack[this.minStack.length?-?1]){
????????this.minStack.push(x)
????}?else?{
?????????this.minStack.push(?this.minStack[this.minStack.length?-?1])
????}
};

MinStack.prototype.pop?=?function()?{
????this.stack.pop();
????this.minStack.pop();
};

MinStack.prototype.top?=?function()?{
????return?this.stack[this.stack.length?-?1];
};

MinStack.prototype.getMin?=?function()?{
????return?this.minStack[this.stack.length?-?1];
};
復制代碼

動態(tài)規(guī)劃

動態(tài)規(guī)劃，一定要知道動態(tài)轉移方程，有了這個，就相當于解題的鑰匙，我們從題目中體會一下

53. 最大子序和

題目如下：

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例?1：

輸入：nums =?[-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組?[4,-1,2,1]?的和最大，為?6?。
示例?2：

輸入：nums =?[1]
輸出：1
示例?3：

輸入：nums =?[0]
輸出：0
復制代碼

思路：

• 這道題可以用動態(tài)規(guī)劃來解決，關鍵是找動態(tài)轉移方程
• 我們動態(tài)轉移方程中，dp表示每一個nums下標的最大自序和，所以dp[i]的意思為：包括下標i之前的最大連續(xù)子序列和為dp[i]。

確定轉義方程的公示：

dp[i]只有兩個方向可以推出來：

• 1、如果dp[i - 1] < 0，也就是當前遍歷到nums的i，之前的最大子序和是負數(shù)，那么我們就沒必要繼續(xù)加它了，因為dp[i] = dp[i - 1] + nums[i] 會比nums[i]更小，所以此時還不如dp[i] = nums[i]，就是目前遍歷到i的最大子序和呢
• 2、同理dp[i - 1] > 0，說明nums[i]值得去加dp[i - 1]，此時回避nums[i]更大

這樣代碼就出來了，其實更多的就是求dp，遍歷nums每一個下標都會產生最大子序和，我們記錄下來即可

var?maxSubArray?=?function(nums)?{
??let?res?=?nums[0];
??const?dp?=?[nums[0]];
??for(let?i=1;i???????if(dp[i-1]>0){
????????dp[i]=nums[i]+dp[i-1]
??????}else{
???????dp[i]=nums[i]
??????}
??????
????res=Math.max(dp[i],res)
??}
????return?res
};
復制代碼

70. 爬樓梯

先看題目：

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

示例?1：

輸入：?2
輸出：?2
解釋：?有兩種方法可以爬到樓頂。
1.??1?階?+?1?階
2.??2?階
示例?2：

輸入：?3
輸出：?3
解釋：?有三種方法可以爬到樓頂。
1.??1?階?+?1?階?+?1?階
2.??1?階?+?2?階
3.??2?階?+?1?階
復制代碼

涉及到動態(tài)規(guī)劃，一定要知道動態(tài)轉移方程，有了這個，就相當于解題的鑰匙，

這道題我們假設dp[10]表示爬到是你爬到10階就到達樓頂?shù)姆椒〝?shù)，

那么，dp[10] 是不是就是你爬到8階，然后再走2步就到了，還有你走到9階，再走1步就到了，

所以 dp[10] 是不是等于 dp[9]+dp[8]

延伸一下 dp[n] 是不是等于 dp[n \- 1] + dp[n \- 2]

代碼如下：

var?climbStairs?=?function(n)?{
????const?dp?=?{};
????dp[1]?=?1;
????dp[2]?=?2;
????for(let?i?=?3;?i?<=?n;?i++){
????????dp[i]?=?dp[i-1]?+?dp[i-2]
????}
????return?dp[n]
};
復制代碼

數(shù)學問題

以下更多的是涉及數(shù)學問題，這些解法非常重要，因為在中級題里面會經常用到，比如我們馬上講到的加一這個題， 中級的兩數(shù)相加都是一個模板。

66. 加一

題目如下：

給定一個由 整數(shù) 組成的 非空 數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎上加一。

最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲單個數(shù)字。

你可以假設除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。

示例?1：

輸入：digits =?[1,2,3]
輸出：[1,2,4]
解釋：輸入數(shù)組表示數(shù)字?123。
示例?2：

輸入：digits =?[4,3,2,1]
輸出：[4,3,2,2]
解釋：輸入數(shù)組表示數(shù)字?4321。
示例?3：

輸入：digits =?[0]
輸出：[1]
復制代碼

這個題的關鍵有兩點：

• 需要有一個進位的變量carry記錄到底進位是幾
• 還需要一個每次迭代都重置和的變量sum來幫我們算是否進位，以及進位后的數(shù)字

記住這個題，這是兩數(shù)字相加的套路，這次是+1，其實就是兩數(shù)相加的題（騰訊面試遇到過兩數(shù)相加）

var?plusOne?=?function(digits)?{
??let?carry?=?1;?//?進位（因為我們確定+1，初始化進位就是1）
??for(let?i?=?digits.length?-?1;?i?>=?0;?i--){
??????let?sum?=?0;?//?這個變量是用來每次循環(huán)計算進位和digits[i]的值的
??????sum?=?digits[i]?+?carry;?
??????digits[i]?=?sum?%?10;?//?模運算取個位數(shù)
??????carry?=?(sum?/?10)?|?0;?//??除以10是取百位數(shù)，并且｜0表示舍棄小數(shù)位
??}
??if(digits[0]?===?0)?digits.unshift(carry);
??return?digits
};
復制代碼

69 x的平方根

題目如下：實現(xiàn) int sqrt(int x) 函數(shù)。

計算并返回 x 的平方根，其中 x 是非負整數(shù)。

由于返回類型是整數(shù)，結果只保留整數(shù)的部分，小數(shù)部分將被舍去。

示例 1:

輸入:?4
輸出:?2
復制代碼

示例 2:

輸入:?8
輸出:?2
說明:?8?的平方根是?2.82842...,?
?????由于返回類型是整數(shù)，小數(shù)部分將被舍去。
復制代碼

這道題是典型的二分法解題，所以我們需要熟悉二分法的通用模板，我們出一個題：

在 [1, 2, 3, 4, 5, 6] 中找到 4，若存在則返回下標，不存在返回-1

const?arr?=?[1,?2,?3,?4,?5,?6];
function?getIndex1(arr,?key)?{
??let?low?=?0;
??const?high?=?arr.length?-?1;
??while?(low?<=?high)?{
????const?mid?=?Math.floor((low?+?high)?/?2);
????if?(key?===?arr[mid])?{
??????return?mid;
????}
????if?(key?>?arr[mid])?{
??????low?=?mid?+?1;
????}?else?{
??????height?=?mid?-?1;
????}
??}
??return?-1;
}
console.log(getIndex1(arr,?5));?//?4
復制代碼

所以這道題的意思就是，我們找一個數(shù)平方跟x最相近的數(shù)，二分法的用法中也有找相近數(shù)的功能

所以代碼如下：

var?mySqrt?=?function(x)?{
????let?[l?,?r]?=?[0,?x];
????let?ans?=?-1;
????while(l?<=?r)?{
????????const?mid?=?(l?+?r)?>>?1;
????????if(mid?*?mid?>?x){
????????????r?=?mid?-?1
????????}?else?if(mid?*?mid?????????????ans?=?mid;?//?防止越界
????????????l?=?mid?+?1;
????????}?else?{
????????????ans?=?mid;
????????????return?ans;
????????}
????}
????return?ans;
};
};
復制代碼

171. Excel表序列號

這個題比較重要，也比較基礎，簡而言之就是進制轉換，必須牢牢掌握

題目如下：

給你一個整數(shù) columnNumber ，返回它在 Excel 表中相對應的列名稱。

例如：

A?->?1
B?->?2
C?->?3
...
Z?->?26
AA?->?27
AB?->?28?
...
復制代碼

示例?1：

輸入：columnNumber =?1
輸出："A"
示例?2：

輸入：columnNumber =?28
輸出："AB"
示例?3：

輸入：columnNumber =?701
輸出："ZY"
示例?4：

輸入：columnNumber =?2147483647
輸出："FXSHRXW"
復制代碼

說白了，這就是一道26進制的問題，以前我們知道10進制轉2進制就是不停的除2，把余數(shù)加起來，26進制也是一樣，不停的除26

思路：

• 初始化結果 ans = 0，遍歷時將每個字母與 A 做減法，因為 A 表示 1，所以減法后需要每個數(shù)加 1，計算其代表的數(shù)值 num = 字母 - ‘A’ + 1
• 因為有 26 個字母，所以相當于 26 進制，每 26 個數(shù)則向前進一位
• 所以每遍歷一位則ans = ans * 26 + num
• 以 ZY 為例，Z 的值為 26，Y 的值為 25，則結果為 26 * 26 + 25=701

var?titleToNumber?=?function(columnTitle)?{
????let?ans?=?0;
????for(let?i?=?0;?i?????????ans?=?ans?*?26?+?(columnTitle[i].charCodeAt()?-?'A'.charCodeAt()?+?1)
????}
????return?ans;
};
復制代碼

172. 階乘中的零

題目：

給定一個整數(shù) n，返回 n! 結果尾數(shù)中零的數(shù)量。

示例?1:

輸入:?3
輸出:?0
解釋:?3!?=?6, 尾數(shù)中沒有零。
示例?2:

輸入:?5
輸出:?1
解釋:?5!?=?120,?尾數(shù)中有?1?個零.
復制代碼

這道題很簡單，有多少個5就有多少個0，為什么這么說呢，我們分析一下題目

比如說 5!，

• 也就是 5 * 4 * 3 * 2 * 1 = 120，我們發(fā)現(xiàn)只有1個0，怎么產生的呢，主要造成者就是 2 * 5 構造了一個0

• 再看看10!

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 其中，除了10 = 2 * 5和本身有一對2 * 5，所以有兩個0，這樣這道題的規(guī)律就出來了，我們再精進一步

如上圖，每四個數(shù)字都會出現(xiàn)一個或者多個2的因子，但是只有每 5 個數(shù)字才能找到一個或多個5的因子。所以總體上看來，2的因子是遠遠多于5的因子的，所以我們只需要找5的倍數(shù)就可以了。

我們再進一步，按照上面的說法，我們需要計算比如10的階乘有多少個0，要把10的階乘算出來，其實我們只需要算10有幾個5就好了，為什么呢

我們發(fā)現(xiàn)只有5的倍數(shù)的階乘，才會產生5, 所以我們需要看看階層數(shù)有多少個5，代碼如下：

var?trailingZeroes?=?function?(n)?{
??let?r?=?0;
??while?(n?>?1)?{
????n?=?Math.floor(n?/?5);
????r?+=?n;
??}
??return?r;
};
復制代碼

190.顛倒二進制位

題目如下：

顛倒給定的 32 位無符號整數(shù)的二進制位。

示例 1：

輸入:?00000010100101000001111010011100
輸出:?00111001011110000010100101000000
解釋:?輸入的二進制串?00000010100101000001111010011100?表示無符號整數(shù)?43261596，
?????因此返回?964176192，其二進制表示形式為?00111001011110000010100101000000。
復制代碼

示例 2：

輸入：11111111111111111111111111111101
輸出：10111111111111111111111111111111
解釋：輸入的二進制串?11111111111111111111111111111101?表示無符號整數(shù)?4294967293，
?????因此返回?3221225471?其二進制表示形式為?10111111111111111111111111111111?。
復制代碼

這類題，就是翻轉字符串，我們可以把其轉為字符串，再轉成數(shù)組，再reverse一下，這里我們選用數(shù)學的方式去解答，不用這種轉字符串的方式。

解答這道題之前，我們需要了解的前置知識：

1. 與預算 `&`
   

1?&?1?//?1的2進制最后一位是1，得到1
2?&?0?//?2的2進制最后一位是0，得到0
3?&?1?//?3的2進制最后一位是1，得到1
4?&?0?//?4的2進制最后一位是0，得到0
復制代碼

所以我們知道了怎么取10進制最后1位的2進制是幾。

2. JavaScript 使用 32 位按位運算數(shù)(意思是我們的按位運算都會轉成32位，你的數(shù)字不能超過32位，會出問題)

• JavaScript 將數(shù)字存儲為 64 位浮點數(shù)，但所有按位運算都以 32 位二進制數(shù)執(zhí)行。

• 在執(zhí)行位運算之前，JavaScript 將數(shù)字轉換為 32 位有符號整數(shù)。

• 執(zhí)行按位操作后，結果將轉換回 64 位 JavaScript 數(shù)。

3. '<< 1' 運算

這個運算實際上就是把10進制乘以2，這個乘2在2進制上表現(xiàn)出右邊填了一個0，我們距舉例來說，

• 2的2進制是 10，2 << 1 得到4， 4的2進制是100，所以比10多了個0
• 3的2進制是 11，3 << 1 得到6。6的2進制是110，所以比11多了個0

以上就是規(guī)律

思路：循環(huán)取最后一位拼接起來即可

var?reverseBits?=?function?(n)?{
??let?result?=?0
??for?(let?i?=?0;?i?32;?i++)?{
????result?=?(result?<1)?+?(n?&?1)
????n?=?n?>>?1
??}
??//?為什么要?>>>?0?呢，一位javascript沒有無符號整數(shù)，全是有符號的
??//?不>>>0的話，得出來的值是負數(shù)，但是無符號整數(shù)是沒有符號的
??//?javascript?有符號轉化為無符號的方法就是>>>0
??return?result?>>>?0
}
復制代碼

268. 丟失的數(shù)字

題目如下：

給定一個包含 [0, n] 中 n 個數(shù)的數(shù)組 nums ，找出 [0, n] 這個范圍內沒有出現(xiàn)在數(shù)組中的那個數(shù)。

進階：

你能否實現(xiàn)線性時間復雜度、僅使用額外常數(shù)空間的算法解決此問題?

示例?1：

輸入：nums =?[3,0,1]
輸出：2
解釋：n =?3，因為有?3?個數(shù)字，所以所有的數(shù)字都在范圍?[0,3]?內。2?是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。
示例?2：

輸入：nums =?[0,1]
輸出：2
解釋：n =?2，因為有?2?個數(shù)字，所以所有的數(shù)字都在范圍?[0,2]?內。2?是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。
復制代碼

這題很簡單，就是用0-n的總和減去數(shù)組總和

• 0 - n 的總和用等差數(shù)列:（首數(shù)+尾數(shù)）* 項數(shù) / 2 來求

?var?missingNumber?=?function(nums)?{
????const?len?=?nums.length
?
???let?sum?=?((1?+?len)?*?len)?/?2
?
???for?(let?i?=?0;?i??????sum?-=?nums[i]
???}
?
???return?sum
?}
復制代碼

3的冪

題目如下：

給定一個整數(shù)，寫一個函數(shù)來判斷它是否是 3 的冪次方。如果是，返回 true ；否則，返回 false 。

整數(shù) n 是 3 的冪次方需滿足：存在整數(shù) x 使得 n == 3的x次方

示例?1：

輸入：n =?27
輸出：true
示例?2：

輸入：n =?0
輸出：false
示例?3：

輸入：n =?9
輸出：true
復制代碼

思路

• 我們拿27來說：27 = 3 * 3 * 3，所以27是3的冪次方
• 我們拿29來說：29 = 3 * 3 * 3點幾

也就是說，如果是3的冪次方，一直除以3，除到最后就等于1比如27/3/3/3等于1 如果不是3的冪次方，除到最后就是3點幾/3 等于1點幾

代碼就出來了判斷是不是等于1即可

var?isPowerOfThree?=?function(n)?{
????while(n?>=?3){
????????n?/=?3;
????}
????return?n?===?1;
};
復制代碼

412. Fizz Buzz

這個題沒啥好說的，就按照題目說的寫代碼就行，先看題目：

寫一個程序，輸出從 1 到 n 數(shù)字的字符串表示。

1. 如果 n 是3的倍數(shù)，輸出“Fizz”；

2. 如果 n 是5的倍數(shù)，輸出“Buzz”；

3. 如果 n 同時是3和5的倍數(shù)，輸出 “FizzBuzz”。

示例：

n?=?15,

返回:
[
????"1",
????"2",
????"Fizz",
????"4",
????"Buzz",
????"Fizz",
????"7",
????"8",
????"Fizz",
????"Buzz",
????"11",
????"Fizz",
????"13",
????"14",
????"FizzBuzz"
]
復制代碼

??var?fizzBuzz?=?function?(n)?{
????const?list?=?[];
????for?(let?i?=?1;?i?<=?n;?i++)?{
??????const?is3Times?=?i?%?3?===?0;?//?是否是3的倍數(shù)
??????const?is5Times?=?i?%?5?===?0;?//?是否是5的倍數(shù)
??????const?is15Times?=?is3Times?&&?is5Times;?//?是否是15的倍數(shù)
??????if?(is15Times)?{
????????list.push('FizzBuzz');
????????continue;
??????}
??????if?(is3Times)?{
????????list.push('Fizz');
????????continue;
??????}
??????if?(is5Times)?{
????????list.push('Buzz');
????????continue;
??????}
??????list.push(`${i}`);
????}
????return?list;
??};
復制代碼

• 
  
7. 整數(shù)反轉

這個題跟之前的excel序號題差不多，我們先看題目：

思路如下：這道題可以將數(shù)字轉字符串然后翻轉，我們不用這種方法，用更純正的數(shù)學方法，速度和效率更好。

假設我們有一個數(shù)字12345，下圖展示了翻轉的過程

var?reverse?=?function(x)?{
????let?ret?=?0;
????while(x){
????????ret?=?ret?*?10?+?x?%?10;
????????if(ret?>?Math.pow(2,?31)?-?1?||?ret?Math.pow(-2,?31))?return?0;
????????x?=?(x?/?10)?|?0
????}
????return?ret
};
復制代碼

環(huán)問題

這類問題的特點就是，你要循環(huán)尋找，到底怎么循環(huán)尋找，看題便知。

141. 環(huán)形鏈表

題目如下：

給定一個鏈表，判斷鏈表中是否有環(huán)。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進行傳遞，僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環(huán)，則返回 true 。否則，返回 false 。

示例 1：

輸入：head =?[3,2,0,-4], pos = 1
輸出：?true
解釋：?鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。
復制代碼

示例 2：

輸入：head =?[1,2], pos =?0
輸出：?true
解釋：?鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。
復制代碼

我們采用標記法：

給遍歷過的節(jié)點打記號，如果遍歷過程中遇到有記號的說明已環(huán)

var?hasCycle?=?function(head)?{
????let?traversingNode?=?head;
????while(traversingNode){
????????if(traversingNode.isVistitd)?return?true
????????traversingNode.isVistitd?=?true
????????traversingNode?=?traversingNode.next
????}
????return?false;
};
復制代碼

160. 相交鏈表

題目如下：

給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點，返回 null 。

圖示兩個鏈表在節(jié)點 c1 開始相交：

題目數(shù)據 保證 整個鏈式結構中不存在環(huán)。

注意，函數(shù)返回結果后，鏈表必須 保持其原始結構 。

示例 1：

輸入：intersectVal =?8,?listA?=?[4,1,8,4,5],?listB?=?[5,0,1,8,4,5],?skipA?=?2,?skipB?=?3
輸出：Intersected at '8'
解釋：相交節(jié)點的值為?8?（注意，如果兩個鏈表相交則不能為?0）。
從各自的表頭開始算起，鏈表?A?為?[4,1,8,4,5]，鏈表?B?為?[5,0,1,8,4,5]。
在?A?中，相交節(jié)點前有?2?個節(jié)點；在 B 中，相交節(jié)點前有?3?個節(jié)點。
復制代碼

示例 2：

輸入：intersectVal =?2,?listA?=?[0,9,1,2,4],?listB?=?[3,2,4],?skipA?=?3,?skipB?=?1
輸出：Intersected at '2'
解釋：相交節(jié)點的值為?2?（注意，如果兩個鏈表相交則不能為?0）。
從各自的表頭開始算起，鏈表?A?為?[0,9,1,2,4]，鏈表?B?為?[3,2,4]。
在?A?中，相交節(jié)點前有?3?個節(jié)點；在 B 中，相交節(jié)點前有?1?個節(jié)點。
復制代碼

稍后更新本文章

202. 快樂數(shù)

題目如下：編寫一個算法來判斷一個數(shù) n 是不是快樂數(shù)。

「快樂數(shù)」定義為：

• 對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
• 然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。
• 如果 可以變?yōu)?1，那么這個數(shù)就是快樂數(shù)。
• 如果 n 是快樂數(shù)就返回 true ；不是，則返回 false 。

快樂數(shù)怎么分析呢？

我們來看一個表，就會得出結論，一個數(shù)按照快樂數(shù)定義的方式分別每個數(shù)字平方，會有兩種情況

• 
  
1. 得到1
• 
  
2. 無限循環(huán)

無限循環(huán)參照下圖

有人會說會不會一直變大，答案是不會：我們看下面列表，

• 可以看到如果你是13位，你的下一次快樂數(shù)算法會變?yōu)?位1053，
• 如果你是9999, 4位，下一個快樂數(shù)是324

所以代碼只要判斷這兩種就行了，代碼如下：

//?封裝獲取快樂數(shù)的方法
function?getNext(n){
????n?=?String(n);
????let?sum?=?0;
????for(let?num?of?n){
????????sum?=?sum?+?Math.pow(+num,?2);
????}
????return?sum;
}
var?isHappy?=?function(n)?{
????//?哈希表來看是否循環(huán)
????const?map?=?{};
????while(?n?!==?1?){
????????map[n]?=?true;
????????n?=?getNext(n)
????????if(map[n])?return?false
????}
????return?true
};
復制代碼

后面會寫中級算法的題，請大家務必把這些基礎算法題掌握好，基礎不牢地動山搖，后面中級題很多都是在這些基礎題的基礎上的。