前言

本文題目選自 LeetCode 精選 TOP 面試題^[1]，而這些題在自己和同事親身經(jīng)歷中，確實(shí)遇到的幾率在百分之80%以上（成都和北京的前端崗位）。本文挑選其中所有簡單題做歸類和解法分析。后續(xù)更新所有中等題分析。

為了幫助大家快速刷題，通過將數(shù)據(jù)結(jié)構(gòu) + 題型的方式總結(jié)出來，比如說哈希表擁有記數(shù)的功能，如果題目中包含字眼至多xx次， 至少xx次,唯一等等字眼，可以聯(lián)想到用哈希表來解決。刷個(gè)3-4道類似的題，就會(huì)養(yǎng)成一種條件反射。

舉例：存在重復(fù)元素（類似題還有3道，后面一起說，解法一樣）

題目描述如下：

給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素。

如果存在一值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true 。如果數(shù)組中每個(gè)元素都不相同，則返回 false 。

示例 1:

輸入: [1,2,3,1]
輸出: true

示例 2:

輸入: [1,2,3,4]
輸出: false
復(fù)制代碼

這題一看就是 計(jì)數(shù)問題，題目中如果存在一值在數(shù)組中出現(xiàn)至少兩次，這句話就告訴我們記錄每一個(gè)數(shù)字出現(xiàn)的次數(shù)就能解決問題了。

解決思路：

我們遍歷數(shù)組時(shí)，經(jīng)過數(shù)組中的每一項(xiàng)就往map中添加，比如[1,2,3,1]

• 第一項(xiàng)：遍歷到第一個(gè)1時(shí)，對(duì)象返回{ 1: 1 },代表1出現(xiàn)1次
• 第二項(xiàng)：遍歷到2時(shí)，返回 { 1: 1, 2: 1 }
• 第三項(xiàng)：遍歷到3時(shí)，返回 { 1: 1, 2: 1， 3: 1 }
• 第四項(xiàng)：遍歷到第二個(gè)1時(shí)，發(fā)現(xiàn)原來的對(duì)象里已經(jīng)有1了，返回false

所以，代碼自然也就出來了，如下：

const containsDuplicate = function(nums) {
    let map = new Map();
    for(let i of nums){
        if(map.has(i)){
            return true;
        }else{
            map.set(i, 1);
        }
    }
    return false;
};
復(fù)制代碼

哈希表 + 計(jì)數(shù)類型

除了上面的那道題，在最熱門的簡單題型中還有一些記數(shù)類型的題，我們一一解答，這是一類題型

387. 字符串中的第一個(gè)唯一字符

一看題目，唯一，條件反射，記數(shù)題啊，map走起！我們先看一下題目：

給定一個(gè)字符串，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引。如果不存在，則返回 -1。

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2
 
// 提示：你可以假定該字符串只包含小寫字母
復(fù)制代碼

思路：

• 遍歷字符串
• 用一個(gè)對(duì)象{}來記數(shù)，出現(xiàn)過一次就+1，
• 
  
• 遍歷完畢，再次遍歷字符串，看它們?cè)谥坝涗浀膶?duì)象里的值，是否是1，是就返回下標(biāo)，不是返回-1。

參考答案：

var firstUniqChar = function(s) {
  const map = {};
  for(let v of s) map[v] = (map[v] || 0) + 1;
  for(let i = 0; i < s.length; i++) if(map[s[i]] === 1) return i;
  return -1;
};
復(fù)制代碼

242. 有效的字母異位詞

我們先看一下題目：

給定兩個(gè)字符串 s 和 t ，編寫一個(gè)函數(shù)來判斷 t 是否是 s 的字母異位詞。

注意：若 s 和 t 中每個(gè)字符出現(xiàn)的次數(shù)都相同，則稱 s 和 t 互為字母異位詞。

示例 1:

輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:

輸入: s = "rat", t = "car"
輸出: false
復(fù)制代碼

思路：這個(gè)題一看字眼，出現(xiàn)次數(shù)相同，次數(shù)不就是記數(shù)嗎，記數(shù)題型，map走起！

• 聲明計(jì)數(shù)器，一個(gè)對(duì)象 const obj = {}
• 遍歷s字符串，如果遍歷到字符串的'a'字母，去看obj[a]是否存在
• 不存在說明第一次遍歷到'a'字母，那么初始化obj[a] = 1
• 如果存在則obj[a] += 1
• t字符串同理，它每次減1
• 遍歷完s字符串后，遍歷obj對(duì)象，看它的每一對(duì)key：value，是否value都是0

var isAnagram = function(s, t) {

  const sLen = s.length;
  const tLen = t.length;
  if(sLen !== tLen ) {
      return false;
  }
  const obj = {};
  for(let i = 0 ; i < sLen ; i++){
      const currentS = s[i];
      const currentT = t[i];
      obj[currentS] ? obj[currentS]++ : obj[currentS] = 1;
      obj[currentT] ? obj[currentT]-- : obj[currentT] = -1;
  }
  return Object.values(obj).every(v=>v===0);
};
復(fù)制代碼

169. 多數(shù)元素

我們先看題目（題目里有次數(shù)兩個(gè)字，又是記數(shù)題型，map繼續(xù)走起）：

給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例 1：

輸入：[3,2,3]
輸出：3
示例 2：

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

思路：

• 聲明一個(gè)計(jì)數(shù)器,也就是一個(gè)對(duì)象const map = {}
• 遍歷字符串，開始記數(shù)，如果字符串的字母第一次碰見，map[第一次碰見的字母] = 1
• 如果map已經(jīng)記錄過這個(gè)字母，則map[記錄過的的字母] += 1
• 在遍歷的過程中，看map[記錄過的的字母] 是否大于 數(shù)組總長度/2

解答：

var majorityElement = function(nums) {
  const map = {}
  const n = nums.length >> 1 // >>是右移運(yùn)算符，意思是除以2
  for(let i = 0; i < nums.length; i++){
      map[nums[i]] = map[nums[i]] !== undefined ? map[nums[i]] + 1 : 1
      if(map[nums[i]] > n) return nums[i]
  }
}
復(fù)制代碼

只出現(xiàn)一次的數(shù)字

這個(gè)題一看，出現(xiàn)一次，map走起，但是呢，這個(gè)題比較巧的是，因?yàn)轭}目的一些限制條件，可以有更好的解法，我們先看題：

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,1]
輸出: 1
示例 2:

輸入: [4,1,2,1,2]
輸出: 4
復(fù)制代碼

這里我們用map記錄一遍，類似這樣的代碼，

const countMap = {};
數(shù)組.forEach((item)=> { countMap[item] ? countMap[item] += 1 : countMap[item] = 1 } )
最后再遍歷一次countMap，然后看誰的次數(shù)是`1`，就解決了
復(fù)制代碼

但是這套題有另一個(gè)解法，用異或運(yùn)算符，首先我們看看異或運(yùn)算符有啥用：

異或運(yùn)算符(^)，我們了解下，這個(gè)運(yùn)算符的功能

• 任何數(shù)和自己做異或運(yùn)算，結(jié)果為 0，即 a⊕a=0。
• 任何數(shù)和 0 做異或運(yùn)算，結(jié)果還是自己，即 a⊕0=a。
• 異或運(yùn)算中，滿足交換律和結(jié)合律，也就是a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

所以出現(xiàn)兩次的字母異或運(yùn)算得0，跟出現(xiàn)一次的字母異或運(yùn)算得到自己

解答：

var singleNumber = function(nums) {
  let init = nums[0];
  for(let i = 1; i < nums.length; i++){
      init ^=  nums[i];
  }
  return init;
};
復(fù)制代碼

位1的個(gè)數(shù)

編寫一個(gè)函數(shù)，輸入是一個(gè)無符號(hào)整數(shù)（以二進(jìn)制串的形式），返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 '1' 的個(gè)數(shù)（也被稱為漢明重量）。

示例 1：

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進(jìn)制串 00000000000000000000000000001011 中，共有三位為 '1'。
示例 2：

輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進(jìn)制串 00000000000000000000000010000000 中，共有一位為 '1'。
復(fù)制代碼

思路：

計(jì)算個(gè)數(shù)，按照我們之前的思路，把整個(gè)數(shù)字轉(zhuǎn)為字符串，類似這樣：

數(shù)字 0001 => String(0001) => '0001' => 遍歷看1的個(gè)數(shù)
復(fù)制代碼

然后直接遍歷計(jì)算就可以了，這是我為什么把它歸為記數(shù)類別的原因，當(dāng)然也可以把它歸為數(shù)學(xué)類，我們用數(shù)學(xué)的算法來解，先看答案，我們?cè)俳馕觥?/p>

var hammingWeight = function(n) {
    let ret = 0;
    while(n){
        n &= (n - 1);
        ret++;
    }
    return ret;
};
復(fù)制代碼

原理：

每執(zhí)行一次x = x & (x-1)，會(huì)將x用二進(jìn)制表示時(shí)最右邊的一個(gè)1變?yōu)?code style="font-size: 14px;border-radius: 4px;font-family: 'Operator Mono', Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(155, 110, 35);background-color: rgb(255, 245, 227);padding: 3px;margin: 3px;">0，因?yàn)?code style="font-size: 14px;border-radius: 4px;font-family: 'Operator Mono', Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(155, 110, 35);background-color: rgb(255, 245, 227);padding: 3px;margin: 3px;">x-1將會(huì)將該位(x用二進(jìn)制表示時(shí)最右邊的一個(gè)1)變?yōu)?code style="font-size: 14px;border-radius: 4px;font-family: 'Operator Mono', Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(155, 110, 35);background-color: rgb(255, 245, 227);padding: 3px;margin: 3px;">0。因此，對(duì) x 重復(fù)該操作，直到 x 變成 0，則操作次數(shù)即為 x 的二進(jìn)制數(shù)中的 1 的數(shù)目。

接下來，我們把其他類型的哈希表題也介紹了（相同的題型沒那么多）

哈希表 + 映射功能

哈希表有一個(gè)非常常見的功能就是建立映射關(guān)系，比如說設(shè)計(jì)模式里的策略模式，思路是一樣的，映射表常常見于后端的枚舉類型，typescript也是一樣，我們舉一個(gè)js的例子

// 后端只會(huì)返回0，1，2
const TYPE = {
    2: 'orange',
    1: 'red',
    0: 'blue'
}

// 然后前端會(huì)這樣用
TYPE[后端返回的數(shù)字0或1或2]
復(fù)制代碼

對(duì)應(yīng)的題有：

• 1.兩數(shù)之和
• 349.兩個(gè)數(shù)組的交集

兩數(shù)之和

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個(gè) 整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：

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

用 hashMap 存儲(chǔ)遍歷過的元素和對(duì)應(yīng)的索引。每遍歷一個(gè)元素，看看 hashMap 中是否存在滿足要求的目標(biāo)數(shù)字。所有事情在一次遍歷中完成（用了空間換取時(shí)間）

var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0, len = nums.length; i < len; i++){
        if(map.get(nums[i]) !== undefined){
            return [map.get(nums[i]), i];
        } else {
            map.set(target - nums[i], i);
        }
    }
    return [];
};
復(fù)制代碼

兩數(shù)組交集

題目如下：給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]
示例 2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
 

說明：

輸出結(jié)果中的每個(gè)元素一定是唯一的。
我們可以不考慮輸出結(jié)果的順序。
復(fù)制代碼

這道題可以用set，很簡單,但是空間復(fù)雜度和時(shí)間復(fù)雜度都太高，不太優(yōu)雅

var intersection = function (nums1, nums2) {
    return result =[...new Set(nums1)].filter(item=>new Set(nums2).has(item))
};
復(fù)制代碼

我們可以用map來做，時(shí)間和空間復(fù)雜度都低很多 思路：

• 用一個(gè)map去存nums1數(shù)組里的每一項(xiàng)，類似map[nums1[i]] = true
• 然后去遍歷nums2，如果在map中已經(jīng)有的值，類似map[nums2[i]], 就把它push到一個(gè)數(shù)組里
• 并且將map[nums2[i]]設(shè)為false，后面有相同的值就不push到數(shù)組了

var intersection = function(nums1, nums2) {
    const map = {};
    const ret = [];
    for(let i = 0; i < nums1.length; i++){
        map[nums1[i]] = true;
    }
    for(let i = 0; i < nums2.length; i++){
        if(map[nums2[i]]){
            ret.push(nums2[i])
            map[nums2[i]] = false
        }
    }
    return ret;
};
復(fù)制代碼

找規(guī)律題

這類題一般畫個(gè)圖或者稍微分析一下就能得出答案

13. 羅馬數(shù)字轉(zhuǎn)整數(shù)

這個(gè)題，我來簡單描述一下，羅馬數(shù)字對(duì)應(yīng)我們阿拉伯?dāng)?shù)字的map如下：

        I: 1,
        V: 5,
        IV: 4,
        IX: 9,
        X: 10,
        XL: 40,
        XC: 90,
        L: 50,
        C: 100,
        CD: 400,
        CM: 900,
        D: 500,
        M: 1000,
復(fù)制代碼

題目是給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。輸入確保在 1 到 3999 的范圍內(nèi)。

示例 1:

輸入: "III"
輸出: 3
示例 2:

輸入: "IV"
輸出: 4
示例 3:

輸入: "IX"
輸出: 9
示例 4:

輸入: "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.
復(fù)制代碼

解題思路就是我們發(fā)現(xiàn)這些案例的規(guī)律，就是把map表里面對(duì)應(yīng)數(shù)字加起來就行了，比如說

"LVIII" = 'L'（對(duì)應(yīng)map表50）+ 'V'（對(duì)應(yīng)map表5）+ 'I'（對(duì)應(yīng)map表1） + 'I'對(duì)應(yīng)map表1） + 'I'（對(duì)應(yīng)map表1）

所以解答就很簡單了，就是遍歷數(shù)字把對(duì)應(yīng)的值加起來，如下：

var romanToInt = function(s) {
    const map = {
        I: 1,
        V: 5,
        IV: 4,
        IX: 9,
        X: 10,
        XL: 40,
        XC: 90,
        L: 50,
        C: 100,
        CD: 400,
        CM: 900,
        D: 500,
        M: 1000,
    }
    let res = 0;
    let index = 0;
    let len = s.length;
    while(index < len){
        if(index + 1 < len && map[s.slice(index, index+2)]){
            res += map[s.slice(index, index+2)];
            index += 2;
        }else{
            res += map[s.slice(index, index+1)];
            index += 1;
        }
    }
    return res;
};
復(fù)制代碼

14. 最長公共前綴

題目如下：

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。
 

提示：

0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 僅由小寫英文字母組成
復(fù)制代碼

思路：這個(gè)題的思路就是，假如你求數(shù)組里3個(gè)元素的最長公共前綴

• 你先拿前兩個(gè)比較，求出他們兩個(gè)的最長公共前綴
• 然后上面求出的結(jié)果去跟第三個(gè)元素求最長公共前綴
• n個(gè)元素就一直這么reduce下去

// 這個(gè)是求出兩個(gè)元素最長公共前綴的方法
var longestCommonPrefix = function (strs) {
  if (strs.length === 0) return ''
  if (strs.length === 1) return strs[0];
  return strs.reduce(getSameStr, strs[0]);
};

function getSameStr(a, b) {
  let res = ''
  for (let j = 0; j < a.length; j++) {
    if (a[j] === b[j]) {
      res += a[j];
    } else {
      return res;
    }
  }
  return res
}
復(fù)制代碼

21. 合并兩個(gè)有序鏈表

這個(gè)題簡而言之就是看圖找規(guī)律，就是合并為升序鏈表，具體題目如下：

我們先看一下題目：

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例 1：


輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：

輸入：l1 = [], l2 = []
輸出：[]
示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]
 

提示：

兩個(gè)鏈表的節(jié)點(diǎn)數(shù)目范圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列
復(fù)制代碼

思路:

那就挨個(gè)遍歷，按順序誰小拼接誰，接著進(jìn)入下一輪循環(huán)，看代碼更清晰一些：

// 鏈表定義函數(shù)
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var mergeTwoLists = function(l1, l2) {
  const dummpy = node = new ListNode();
  while(l1 && l2){
      if(l1.val >= l2.val){
          node.next = l2;
          node = node.next;
          l2 = l2.next;
      } else {
          node.next = l1;
          node = node.next;
          l1 = l1.next;
      }
  }
  node.next = l1 || l2;
  return dummpy.next;
};
復(fù)制代碼

28. 實(shí)現(xiàn)str（）

題目如下：

實(shí)現(xiàn) strStr() 函數(shù)。

給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。如果不存在，則返回 -1 。

示例 1：

輸入：haystack = "hello", needle = "ll"
輸出：2
示例 2：

輸入：haystack = "aaaaa", needle = "bba"
輸出：-1
示例 3：

輸入：haystack = "", needle = ""
輸出：0
 

提示：

0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 僅由小寫英文字符組成
復(fù)制代碼

思路：

本來這道題最佳算法是KMP，這個(gè)算法理解起來對(duì)我來說有難度，所以自己換了另一種思路

• 遍歷字符串看是否有和需要找的字符串第一個(gè)字母相同
• 如果相同，就截取字符串跟需要找的字符串相同長度的字符串對(duì)比
• 相同就返回下標(biāo)，不同就繼續(xù)遍歷原字符串

var strStr = function (haystack, needle) {
  if (needle === "") return 0
  for (var i = 0; i < haystack.length; i++) {
      if (haystack[i] === needle[0]) {
          if (haystack.substring(i, i + needle.length) === needle) return i;
      }
  }
  return -1
};
復(fù)制代碼

118. 楊輝三角

這個(gè)可是找規(guī)律的代表題，并且這道題可以訓(xùn)練一下你對(duì)二維數(shù)組 轉(zhuǎn)化為 代碼的能力：

給定一個(gè)非負(fù)整數(shù) numRows， 生成楊輝三角的前 numRows 行。

在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。

示例:

輸入: 5
輸出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
復(fù)制代碼

思路：

• 看到上圖可以發(fā)現(xiàn)，生成楊輝三角numRows行，數(shù)組就有numRows行
• 每一行，它的數(shù)組第一個(gè)位置和最后一個(gè)位置都是1
• 每一行，除了第一個(gè)和最后一個(gè)位置，其它位置的值等于上一行的兩個(gè)值相加

把思路翻譯成代碼即可：

var generate = function(numRows) {
  if(numRows === 0){ return [] }
  const result = Array.from(new Array(numRows), ()=>[])
  for(let i = 0; i < numRows; i++){
    result[i][0] = 1; result[i][i] = 1;
      for(let j = 1; j < i; j++){
      result[i][j] = result[i-1][j-1] + result[i-1][j] 
    }
  }
return result
};
復(fù)制代碼

121. 買賣股票的最佳時(shí)機(jī)

接下來這道題，你簡單看下題目就行，解答原理超級(jí)簡單，看圖說話，找規(guī)律！

我們先看題：

給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

示例 1：

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。
示例 2：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。
 

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104
復(fù)制代碼

解題思路：我們先看一張圖，假設(shè)給定的數(shù)組為：[7, 1, 5, 3, 6, 4]

• 第一天是7，我們記錄一下，因?yàn)檫€沒到第二天不知道這個(gè)價(jià)格是高是低，標(biāo)記最小值是7
• 第二天是1，比7小，那么只要當(dāng)前天數(shù)的值比前面小，就說明不賣，因?yàn)樗亲钚≈担?code style="font-size: 14px;border-radius: 4px;font-family: 'Operator Mono', Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(155, 110, 35);background-color: rgb(255, 245, 227);padding: 3px;margin: 3px;">標(biāo)記最小值是7
• 第三天是5，5比前一天大，說明比最小值要大，那么可以賣，利潤就是5-1=4
• 第四天發(fā)現(xiàn)是3，比5小，還是一樣的道理，比之前小，最小值就要變?yōu)楫?dāng)前值，啥也不干，標(biāo)記最小值是3
• 第五天發(fā)現(xiàn)是6...，第六天發(fā)現(xiàn)是4，規(guī)律是一樣的

意思是只要今天比昨天低，就可以用今天的減去最小值，就是利潤，然后每次都比較這個(gè)利潤是不是最大就行了

結(jié)合一下代碼，就會(huì)清楚

var maxProfit = function(prices) {
  let res = 0;
  let min = prices[0];
  for(let i = 1; i < prices.length; i++){
      if(prices[i] < min){
          min = prices[i]
      } else {
          res = Math.max(res, prices[i] - min)
      }   
  }
  return res;
};
復(fù)制代碼

122. 買賣股票的最佳時(shí)機(jī)2

又來一道看圖說話題目，簡單！走起！

先看題目：

給定一個(gè)數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:

輸入: prices = [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:

輸入: prices = [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
復(fù)制代碼

思路，看圖馬上思路就出來了：

我們的利潤就跟上圖綠色部分顯示的一樣，也就是說只要今天減去昨天，是正數(shù)就是利潤，簡單吧，哈哈！

var maxProfit = function(prices) {
  let result = 0
  for(let i = 1; i < prices.length; i++){
      if(prices[i] > prices[i-1]){
          result += prices[i] - prices[i - 1]
      }
  }
  return result
};
復(fù)制代碼

206. 反轉(zhuǎn)鏈表

這個(gè)題必須掌握牢實(shí)，是解很多鏈接表題的基礎(chǔ)的基礎(chǔ)。先看題目：

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

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

示例 2：

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

解題思路依然是看圖找規(guī)律，下圖就是，我們把鏈表前面加一個(gè)null，這樣翻轉(zhuǎn)前和翻轉(zhuǎn)后就一致了。 解答：

var reverseList = function(head) {
  let [pre, node] = [null, head];
  while(node){
      const temp = node.next;
      node.next = pre;
      pre = node;
      node = temp;
  }
  return pre;
};
復(fù)制代碼

雙指針

雙指針是解數(shù)組類型題最常見解法

• 比如有頭尾分別有指針，然后依次向中間靠攏的雙指針，
• 還有一種是快慢是指針，兩個(gè)指針都是從左邊開始，一個(gè)走的快，一個(gè)走得慢

具體的細(xì)節(jié)還是需要從題里體會(huì)，我們現(xiàn)在就開始！

26. 刪除數(shù)組中的重復(fù)項(xiàng)

先看一下題目：

給你一個(gè)有序數(shù)組 nums ，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。

示例 1：

輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函數(shù)應(yīng)該返回新的長度 2 ，并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長度后面的元素。
示例 2：

輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數(shù)應(yīng)該返回新的長度 5 ， 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4 。不需要考慮數(shù)組中超出新長度后面的元素。
 

提示：

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
復(fù)制代碼

初始狀態(tài)是：

• 慢指針是i，快指針是j
• 如果nums[i] 等于 nums[j] 說明是相同的元素，j繼續(xù)走，i還在原位
• 如果nums[i] 不等于 nums[j] 說明是不相同的元素，那么nums[i++] = nums[j]，j繼續(xù)向前走

依次類推，就相當(dāng)于i指針保證它和它前面的數(shù)字都是不重復(fù)的，j就是一個(gè)遍歷器

var removeDuplicates = function(nums) {
  let i = 0;
  for(let j = 1; j < nums.length; j++){
      if(nums[j] !== nums[i]){
          nums[i+1] = nums[j];
          i++
      }
  }
  return i + 1
};
復(fù)制代碼

88. 合并兩個(gè)有序數(shù)組

我們先看題目：

給你兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，請(qǐng)你將 nums2 合并到 nums1 中，使 nums1 成為一個(gè)有序數(shù)組。

初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 。你可以假設(shè) nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來自 nums2 的元素。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
示例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
 

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109
復(fù)制代碼

這道題大家很容易想到，新創(chuàng)建一個(gè)數(shù)組，然后分別比較這兩個(gè)數(shù)組里的每一項(xiàng)，push進(jìn)去就行了

然而因?yàn)槭怯行驍?shù)組，第一個(gè)數(shù)組還有正好滿足假如第二數(shù)組的空間，所以這里可以采取雙指針來解答，從后往前遍歷

參考如下：

var merge = function (nums1, m, nums2, n) {
  let len = m + n - 1;
  m--, n--;
  while (m >= 0 && n >= 0) {
    if (nums1[m] > nums2[n]) {
      nums1[len] = nums1[m--]
    } else {
      nums1[len] = nums2[n--]
    }
    len--;
  }
  if(m === -1){
    return nums1.splice(0, len+1, ...nums2.slice(0, n + 1));
  }
  if(n === -1){
    return nums1;
  }
};
復(fù)制代碼

125. 驗(yàn)證回文串

請(qǐng)看題目：

給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。

說明：本題中，我們將空字符串定義為有效的回文串。

示例 1:

輸入: "A man, a plan, a canal: Panama"
輸出: true
解釋："amanaplanacanalpanama" 是回文串
示例 2:

輸入: "race a car"
輸出: false
解釋："raceacar" 不是回文串
復(fù)制代碼

這個(gè)題太簡單了，以至于不用寫思路了，看代碼就知道，就是用用雙指針頭尾向中間靠攏的解法，

var isPalindrome = function(s) {
  s = s.replace(/[^\w]/g, '').toLowerCase();
  let leftPointer = 0;
  let rightPointer = s.length - 1;
  while(rightPointer > leftPointer){
      if(s[leftPointer++] === s[rightPointer--]){
          continue;
      }else{
          return false;
      }
  }
  return true;
};
復(fù)制代碼

234. 回文鏈表

這個(gè)題思路跟上面是一樣的，都是雙指針對(duì)比，但是主要這個(gè)題寫起來很麻煩，要用到我們之前說的翻轉(zhuǎn)鏈表，

解題思路：

• 先用快慢指針的手法，讓我們知道這個(gè)鏈表的中點(diǎn)是哪，然后從中點(diǎn)截?cái)?/section>
• 然后截?cái)喑蔀閮蓚€(gè)鏈表，把后面的鏈表翻轉(zhuǎn)
• 最后依次去判斷這兩個(gè)鏈表每一項(xiàng)是否相同

關(guān)鍵點(diǎn)：如何從中點(diǎn)截?cái)噙@個(gè)鏈表,方法如下，讓一個(gè)指針每次走一步，另一個(gè)指針每次走兩步，這樣他們每次走的倍數(shù)就相差2倍。代碼如下：

  let fast = head;
  let slow = head;
  let prev;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
prev.next = null;  // 斷成兩個(gè)鏈表
復(fù)制代碼

• 接著我們需要翻轉(zhuǎn)鏈表

 // 翻轉(zhuǎn)后半段
  let head2 = null;
  while (slow) {
    const tmp = slow.next;
    slow.next = head2;
    head2 = slow;
    slow = tmp;
  }
復(fù)制代碼

• 最后對(duì)比就看下面具體代碼了

const isPalindrome = (head) => {
  if (head == null || head.next == null) {
    return true;
  }
  let fast = head;
  let slow = head;
  let prev;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null;  // 斷成兩個(gè)鏈表
  // 翻轉(zhuǎn)后半段
  let head2 = null;
  while (slow) {
    const tmp = slow.next;
    slow.next = head2;
    head2 = slow;
    slow = tmp;
  }
  // 比對(duì)
  while (head && head2) {
    if (head.val != head2.val) {
      return false;
    }
    head = head.next;
    head2 = head2.next;
  }
  return true;
};
復(fù)制代碼

237. 刪除鏈表中的節(jié)點(diǎn)

題目如下：

請(qǐng)編寫一個(gè)函數(shù)，使其可以刪除某個(gè)鏈表中給定的（非末尾）節(jié)點(diǎn)。傳入函數(shù)的唯一參數(shù)為 要被刪除的節(jié)點(diǎn) 。

現(xiàn)有一個(gè)鏈表 -- head = [4,5,1,9]，它可以表示為:

示例 1：

輸入：head = [4,5,1,9], node = 5
輸出：[4,1,9]
解釋：給定你鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?nbsp;4 -> 1 -> 9.
示例 2：

輸入：head = [4,5,1,9], node = 1
輸出：[4,5,9]
解釋：給定你鏈表中值為 1 的第三個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?nbsp;4 -> 5 -> 9.
 

提示：

鏈表至少包含兩個(gè)節(jié)點(diǎn)。
鏈表中所有節(jié)點(diǎn)的值都是唯一的。
給定的節(jié)點(diǎn)為非末尾節(jié)點(diǎn)并且一定是鏈表中的一個(gè)有效節(jié)點(diǎn)。
不要從你的函數(shù)中返回任何結(jié)果。
復(fù)制代碼

這個(gè)題很簡單，其實(shí)這個(gè)node是個(gè)引用類型，你只需要把node的val變?yōu)閚ode.next的val，然后node的next指向node.next.next，就移花接木，完成任務(wù)了！自己可以試著在草稿上畫一下，結(jié)合代碼很快就會(huì)明白！

var deleteNode = function(node) {
  node.val = node.next.val
  node.next = node.next.next
};
復(fù)制代碼

283. 移動(dòng)零

題目如下：給定一個(gè)數(shù)組 nums，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序。

示例:

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:

必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)。
復(fù)制代碼

如動(dòng)畫所示，我們可以用快慢指針來解答，具體不好用語言敘述，看動(dòng)圖

var moveZeroes = function(nums) {
  let i = j = 0;
  while(i < nums.length) {
      if(nums[i] !== 0){
          [nums[i], nums[j]] = [nums[j], nums[i]]
          j++
      }
      i++
  }

  return nums
};
復(fù)制代碼

344. 反轉(zhuǎn)字符串

題目如下：

編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 char[] 的形式給出。

不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。

你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。

示例 1：

輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
示例 2：

輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
復(fù)制代碼

這個(gè)題目實(shí)在太簡單了，知道用首位雙指針即可，看參考：

var reverseString = function(s) {
  let l = 0 ;
  let r = s.length - 1;
  while(l < r){
    [s[l], s[r]] = [s[r], s[l]];
    l++; r--;
  }
  return s;
};
復(fù)制代碼

350. 兩個(gè)數(shù)組的交集II

題目如下：給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2,2]
示例 2:

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[4,9]

說明：

輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)次數(shù)的最小值一致。
我們可以不考慮輸出結(jié)果的順序。

復(fù)制代碼

這個(gè)取交集需要保留重復(fù)元素，可以是用雙指針來解答，具體思路和代碼如下

• 如果兩個(gè)數(shù)組是有序的，則可以使用雙指針的方法得到兩個(gè)數(shù)組的交集。

• 首先對(duì)兩個(gè)數(shù)組進(jìn)行排序，然后使用兩個(gè)指針遍歷兩個(gè)數(shù)組。

• 初始時(shí)，兩個(gè)指針分別指向兩個(gè)數(shù)組的頭部。每次比較兩個(gè)指針指向的兩個(gè)數(shù)組中的數(shù)字，如果兩個(gè)數(shù)字不相等，則將指向較小數(shù)字的指針右移一位，如果兩個(gè)數(shù)字相等，將該數(shù)字添加到答案，并將兩個(gè)指針都右移一位。當(dāng)至少有一個(gè)指針超出數(shù)組范圍時(shí)，遍歷結(jié)束

var intersect = function(nums1, nums2) {
  nums1 = nums1.sort((a, b) => a - b);
  nums2 = nums2.sort((a, b) => a - b);
  let l1 = 0;
  let l2 = 0;
  const nums1Len = nums1.length;
  const nums2Len = nums2.length;
  const ret = [];
  while(l1 < nums1Len && l2 < nums2Len){
    if(nums1[l1] === nums2[l2]){
      ret.push(nums1[l1]);
      l1++;
      l2++;
    }
    if(nums1[l1] > nums2[l2]) l2++;
    if(nums1[l1] < nums2[l2]) l1++;
  }
  return ret;
};
復(fù)制代碼

剩下20道題的分類和解答應(yīng)該明后天寫完，后續(xù)包括

• 棧
• 動(dòng)態(tài)規(guī)劃
• 數(shù)學(xué)問題
• 環(huán)問題