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

本篇是簡(jiǎn)單題（下）20題左右，上半部分詳見\# 簡(jiǎn)單題上（22題左右）^[2]

二叉樹（DFS）

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

前序遍歷題目如下：

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

我們可以看到這其中的規(guī)律，就是深度優(yōu)先遍歷，先遍歷左子樹，再遍歷右子樹，這里我們不用遞歸，因?yàn)橐恍┐髲S嚴(yán)格要求二叉樹遍歷不用遞歸，遞歸太簡(jiǎn)單了。

重點(diǎn)思路就是：深度優(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ù)制代碼

我們結(jié)合圖片發(fā)現(xiàn)這個(gè)遍歷產(chǎ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（這就是中序遍歷的要求，好了，兩個(gè)題解決）

放具體前序遍歷代碼：

var preorderTraversal = function(root) {
    // 初始化數(shù)據(jù)
    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;
};
復(fù)制代碼

中序遍歷是一個(gè)意思，在前序遍歷的基礎(chǔ)上改造一下

var preorderTraversal = function(root) {
    // 初始化數(shù)據(jù)
    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;
};
復(fù)制代碼

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

var postorderTraversal = function(root) {
  // 初始化數(shù)據(jù)
    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;
};
復(fù)制代碼

對(duì)稱二叉樹

這個(gè)題簡(jiǎn)而言之就是判斷一個(gè)二叉樹是對(duì)稱的，比如說：

二叉樹 [1,2,2,3,4,4,3] 是對(duì)稱的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
復(fù)制代碼

但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱的:

    1
   / \
  2   2
   \   \
   3    3

復(fù)制代碼

思路：

遞歸解決：

• 判斷兩個(gè)指針當(dāng)前節(jié)點(diǎn)值是否相等
• 判斷 A 的右子樹與 B 的左子樹是否對(duì)稱
• 判斷 A 的左子樹與 B 的右子樹是否對(duì)稱

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);
};
復(fù)制代碼

二叉樹的最大深度

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

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

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
};
復(fù)制代碼

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

我們先看題：

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 嚴(yán)格遞增 順序排列
復(fù)制代碼

思路：

• 構(gòu)建一顆樹包括：構(gòu)建root、構(gòu)建 root.left 和 root.right
• 題目要求"高度平衡" — 構(gòu)建 root 時(shí)候，選擇數(shù)組的中間元素作為 root 節(jié)點(diǎn)值，即可保持平衡。
• 遞歸函數(shù)可以傳遞數(shù)組，也可以傳遞指針，選擇傳遞指針的時(shí)候：l r 分別代表參與構(gòu)建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;
}
復(fù)制代碼

棧

棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，所以涉及到你需要先進(jìn)先出這個(gè)想法后，就可以使用棧。

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

20. 有效的括號(hào)

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

有效字符串需滿足：

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

示例 1：

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

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

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

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

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

1. 右括號(hào)前面，必須是相對(duì)應(yīng)的左括號(hào)，才能抵消！
2. 右括號(hào)前面，不是對(duì)應(yīng)的左括號(hào)，那么該字符串，一定不是有效的括號(hào)！

也就是說左括號(hào)我們直接放入棧中即可，發(fā)現(xiàn)是右括號(hào)就要對(duì)比是否跟棧頂元素相匹配，不匹配就返回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;
};
復(fù)制代碼

155、 最小棧

先看題目：

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

• 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 操作總是在 非空棧 上調(diào)用。
復(fù)制代碼

我們先不寫getMin方法，滿足其他方法實(shí)現(xiàn)就非常簡(jiǎ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];
};
復(fù)制代碼

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

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

• 開始我們向stack push -2
• 此時(shí)輔助棧minStack，因?yàn)榇藭r(shí)stack最小的是-2，也push -2
• stack push 0
• 此時(shí)輔助站minStack 會(huì)用 0 跟 -2對(duì)比，-2更小，minstack會(huì)push -2
• stack push -3
• 此時(shí)輔助站minStack 會(huì)用 -3 跟 -2對(duì)比，-3更小，minstack會(huì)push -3

所以我們?nèi)∽钚〉臅r(shí)候，總能在minStack中取到最小值，所以解法就出來了：

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

MinStack.prototype.push = function(x) {
    this.stack.push(x);
    // 如果是第一次或者當(dāng)前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];
};
復(fù)制代碼

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃，一定要知道動(dòng)態(tài)轉(zhuǎn)移方程，有了這個(gè)，就相當(dāng)于解題的鑰匙，我們從題目中體會(huì)一下

53. 最大子序和

題目如下：

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

示例 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
復(fù)制代碼

思路：

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

確定轉(zhuǎn)義方程的公示：

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

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

這樣代碼就出來了，其實(shí)更多的就是求dp，遍歷nums每一個(gè)下標(biāo)都會(huì)產(chǎn)生最大子序和，我們記錄下來即可

var maxSubArray = function(nums) {
  let res = nums[0];
  const dp = [nums[0]];
  for(let i=1;i < nums.length;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
};
復(fù)制代碼

70. 爬樓梯

先看題目：

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

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

示例 1：

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

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

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

這道題我們假設(shè)dp[10]表示爬到是你爬到10階就到達(dá)樓頂?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]
};
復(fù)制代碼

數(shù)學(xué)問題

以下更多的是涉及數(shù)學(xué)問題，這些解法非常重要，因?yàn)樵谥屑?jí)題里面會(huì)經(jīng)常用到，比如我們馬上講到的加一這個(gè)題， 中級(jí)的兩數(shù)相加都是一個(gè)模板。

66. 加一

題目如下：

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

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

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

示例 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]
復(fù)制代碼

這個(gè)題的關(guān)鍵有兩點(diǎn)：

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

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

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

69 x的平方根

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

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

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

示例 1:

輸入: 4
輸出: 2
復(fù)制代碼

示例 2:

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

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

在 [1, 2, 3, 4, 5, 6] 中找到 4，若存在則返回下標(biāo)，不存在返回-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
復(fù)制代碼

所以這道題的意思就是，我們找一個(gè)數(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 < x){
            ans = mid; // 防止越界
            l = mid + 1;
        } else {
            ans = mid;
            return ans;
        }
    }
    return ans;
};
};
復(fù)制代碼

171. Excel表序列號(hào)

這個(gè)題比較重要，也比較基礎(chǔ)，簡(jiǎn)而言之就是進(jìn)制轉(zhuǎn)換，必須牢牢掌握

題目如下：

給你一個(gè)整數(shù) columnNumber ，返回它在 Excel 表中相對(duì)應(yīng)的列名稱。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...
復(fù)制代碼

示例 1：

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

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

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

輸入：columnNumber = 2147483647
輸出："FXSHRXW"
復(fù)制代碼

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

思路：

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

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

172. 階乘中的零

題目：

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

示例 1:

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

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

這道題很簡(jiǎn)單，有多少個(gè)5就有多少個(gè)0，為什么這么說呢，我們分析一下題目

比如說 5!，

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

• 再看看10!

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 其中，除了10 = 2 * 5和本身有一對(duì)2 * 5，所以有兩個(gè)0，這樣這道題的規(guī)律就出來了，我們?cè)倬M(jìn)一步

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

我們?cè)龠M(jìn)一步，按照上面的說法，我們需要計(jì)算比如10的階乘有多少個(gè)0，要把10的階乘算出來，其實(shí)我們只需要算10有幾個(gè)5就好了，為什么呢

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

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

190.顛倒二進(jìn)制位

題目如下：

顛倒給定的 32 位無符號(hào)整數(shù)的二進(jìn)制位。

示例 1：

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

示例 2：

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

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

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

1. 與預(yù)算 `&`
   

1 & 1 // 1的2進(jìn)制最后一位是1，得到1
2 & 0 // 2的2進(jìn)制最后一位是0，得到0
3 & 1 // 3的2進(jìn)制最后一位是1，得到1
4 & 0 // 4的2進(jìn)制最后一位是0，得到0
復(fù)制代碼

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

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

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

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

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

3. '<< 1' 運(yùn)算

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

• 2的2進(jìn)制是 10，2 << 1 得到4， 4的2進(jìn)制是100，所以比10多了個(gè)0
• 3的2進(jìn)制是 11，3 << 1 得到6。6的2進(jìn)制是110，所以比11多了個(gè)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沒有無符號(hào)整數(shù)，全是有符號(hào)的
  // 不>>>0的話，得出來的值是負(fù)數(shù)，但是無符號(hào)整數(shù)是沒有符號(hào)的
  // javascript 有符號(hào)轉(zhuǎn)化為無符號(hào)的方法就是>>>0
  return result >>> 0
}
復(fù)制代碼

268. 丟失的數(shù)字

題目如下：

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

進(jìn)階：

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

示例 1：

輸入：nums = [3,0,1]
輸出：2
解釋：n = 3，因?yàn)橛?nbsp;3 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,3] 內(nèi)。2 是丟失的數(shù)字，因?yàn)樗鼪]有出現(xiàn)在 nums 中。
示例 2：

輸入：nums = [0,1]
輸出：2
解釋：n = 2，因?yàn)橛?nbsp;2 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,2] 內(nèi)。2 是丟失的數(shù)字，因?yàn)樗鼪]有出現(xiàn)在 nums 中。
復(fù)制代碼

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

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

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

3的冪

題目如下：

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

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

示例 1：

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

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

輸入：n = 9
輸出：true
復(fù)制代碼

思路

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

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

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

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

412. Fizz Buzz

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

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

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

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

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

示例：

n = 15,

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

  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;
  };
復(fù)制代碼

• 
  
7. 整數(shù)反轉(zhuǎn)

這個(gè)題跟之前的excel序號(hào)題差不多，我們先看題目：

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

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

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
};
復(fù)制代碼

環(huán)問題

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

141. 環(huán)形鏈表

題目如下：

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

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

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

示例 1：

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

示例 2：

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

我們采用標(biāo)記法：

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

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

160. 相交鏈表

題目如下：

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

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

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

示例 1：

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

示例 2：

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

稍后更新本文章

202. 快樂數(shù)

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

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

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

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

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

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

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

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

• 可以看到如果你是13位，你的下一次快樂數(shù)算法會(huì)變?yōu)?位1053，
• 如果你是9999, 4位，下一個(gè)快樂數(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
};
復(fù)制代碼

后面會(huì)寫中級(jí)算法的題，請(qǐng)大家務(wù)必把這些基礎(chǔ)算法題掌握好，基礎(chǔ)不牢地動(dòng)山搖，后面中級(jí)題很多都是在這些基礎(chǔ)題的基礎(chǔ)上的。