LeetCode 熱題 HOT 100 題解 -easy 級別-

精選 100 道力扣（LeetCode）上最熱門的題目，本篇文章只有 easy 級別的，適合初識算法與數據結構的新手和想要在短時間內高效提升的人。

兩數之和

https://leetcode-cn.com/problems/two-sum

方法一

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    let diff = target - nums[i]
    for (let j = i + 1; j < nums.length; j++) {
      if (diff == nums[j]) {
        return [i, j]
      }
    }
  }
}

方法二

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  var temp = []
  for (var i = 0; i < nums.length; i++) {
    var dif = target - nums[i]
    if (temp[dif] != undefined) {
      return [temp[dif], i]
    }
    temp[nums[i]] = i
  }
}

最長公共前綴

https://leetcode-cn.com/problems/longest-common-prefix

思路：

先遍歷數組
再遍歷數組的第一個字符串，用字符串中的每一個字符和數組中的每一項的對應的該字符串下標相比，不同則跳出循環，兩兩找出公共前綴，最終結果即爲最長公共前綴的長度 j。
截取字符串長度 j 的字符即爲最長公共前綴

const strs = ['flower', 'flow', 'flight']
const longestCommonPrefix = function (strs) {
  if (strs === null || strs.length === 0) return ''
  let commonString = ''

  for (let i = 1; i < strs.length; i++) {
    let j = 0
    for (; j < strs[0].length && j < strs[i].length; j++) {
      if (strs[0][j] !== strs[i][j]) break
    }
    commonString = strs[0].substring(0, j)
  }
  return commonString
}
longestCommonPrefix(strs)

刪除鏈表的節點

https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof

var deleteNode = function (head, val) {
  if (head.val === val) return head.next
  let prev = head,
    node = prev.next
  while (node) {
    if (node.val === val) {
      prev.next = node.next
    }
    prev = node
    node = node.next
  }
  return head
}

有效的括號

https://leetcode-cn.com/problems/valid-parentheses

方法分析：

該題使用的堆棧（stack）的知識。棧具有先進後出（FILO）的特點。堆棧具有棧頂和棧底之分。所謂入棧，就是將元素壓入（push）堆棧；所謂出棧，就是將棧頂元素彈出（pop）堆棧。先入棧的一定後出棧，所以可以利用堆棧來檢測符號是否正確配對。

解題思路：

有效括號字符串的長度，一定是偶數！
右括號前面，必須是相對應的左括號，才能抵消！
右括號前面，不是對應的左括號，那麼該字符串，一定不是有效的括號！

var isValid = function (s) {
  let stack = []
  if (!s || s.length % 2) return false
  for (let item of s) {
    switch (item) {
      case '{':
      case '[':
      case '(':
        stack.push(item)
        break
      case '}':
        if (stack.pop() !== '{') return false
        break
      case '[':
        if (stack.pop() !== ']') return false
        break
      case '(':
        if (stack.pop() !== ')') return false
        break
    }
  }
  return !stack.length
}

合併兩個有序鏈表

https://leetcode-cn.com/problems/merge-two-sorted-lists

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2
  } else if (l2 === null) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
}

最大子序和

https://leetcode-cn.com/problems/maximum-subarray

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let ans = nums[0]
  let sum = 0
  for (const num of nums) {
    if (sum > 0) {
      sum += num
    } else {
      sum = num
    }
    ans = Math.max(ans, sum)
  }
  return ans
}

爬樓梯

https://leetcode-cn.com/problems/climbing-stairs

var climbStairs = function (n) {
  let dp = []
  dp[0] = 1
  dp[1] = 1
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

對稱二叉樹

https://leetcode-cn.com/problems/symmetric-tree

/**遞歸 代碼
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  const check = (left, right) => {
    if (left == null && right == null) {
      return true
    }
    if (left && right) {
      return (
        left.val === right.val &&
        check(left.left, right.right) &&
        check(left.right, right.left)
      )
    }
    return false // 一個子樹存在一個不存在，肯定不對稱
  }
  if (root == null) {
    // 如果傳入的root就是null，對稱
    return true
  }
  return check(root.left, root.right)
}

路徑總和

https://leetcode-cn.com/problems/path-sum

var hasPathSum = function (root, targetSum) {
  // 深度優先遍歷
  if (root === null) {
    //1.剛開始遍歷時
    //2.遞歸中間 說明該節點不是葉子節點
    return false
  }
  if (root.left === null && root.right === null) {
    return root.val - targetSum === 0
  }
  // 拆分成兩個子樹
  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  )
}

只出現一次的數字

https://leetcode-cn.com/problems/single-number

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ans = ''
  for (const num of nums) {
    ans ^= num
    console.log(ans)
  }
  return ans
}

最小棧

https://leetcode-cn.com/problems/min-stack

var MinStack = function () {
  this.x_stack = []
  this.min_stack = [Infinity]
}

MinStack.prototype.push = function () {
  this.x_stack.push(x)
  this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x))
}
MinStack.prototype.pop = function () {
  this.x_stack.pop()
  this.min_stack.pop()
}
MinStack.prototype.top = function () {
  return this.x_stack[this.x_stack.length - 1]
}
MinStack.prototype.getMin = function () {
  return this.min_stack[this.min_stack.length - 1]
}

相交鏈表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists

方法 1：暴力法

思路

對於鏈表 A 的每個節點，都去鏈表 B 中遍歷一遍找看看有沒有相同的節點。

複雜度

時間複雜度：O(M * N)O(M∗N), M, N 分別爲兩個鏈表的長度。空間複雜度：O(1)O(1)。

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null
  let pA = headA
  while (pA) {
    let pB = headB
    while (pB) {
      if (pA === pB) return pA
      pB = pB.next
    }
    pA = pA.next
  }
}

方法 2：哈希表

思路

先遍歷一遍鏈表 A，用哈希表把每個節點都記錄下來 (注意要存節點引用而不是節點值)。再去遍歷鏈表 B，找到在哈希表中出現過的節點即爲兩個鏈表的交點。

複雜度

時間複雜度：O(M + N), M, N 分別爲兩個鏈表的長度。空間複雜度：O(N)，N 爲鏈表 A 的長度。

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null
  const hashmap = new Map()
  let pA = headA
  while (pA) {
    hashmap.set(pA, 1)
    pA = pA.next
  }
  let pB = headB
  while (pB) {
    if (hashmap.has(pB)) return pB
    pB = pB.next
  }
}

方法 3：雙指針

如果鏈表沒有交點

兩個鏈表長度一樣，第一次遍歷結束後 pA 和 pB 都是 null，結束遍歷兩個鏈表長度不一樣，兩次遍歷結束後 pA 和 pB 都是 null，結束遍歷

複雜度

時間複雜度：O(M + N) , M, N 分別爲兩個鏈表的長度。空間複雜度：O(1)。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null

  let pA = headA,
    pB = headB
  while (pA !== pB) {
    pA = pA === null ? headB : pA.next
    pB = pB === null ? headA : pB.next
  }
  return pA
}

反轉鏈表

var reverseList = function (head) {
  let prev = null
  cur = head
  while (cur) {
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
}

方案 2

var reverseList = function (head) {
  let prev = null
  cur = head
  while (cur) {
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
}

迴文鏈表

https://leetcode-cn.com/problems/palindrome-linked-list

const isPalindrome = (head) => {
  const vals = []
  while (head) {
    // 丟進數組裏
    vals.push(head.val)
    head = head.next
  }
  let start = 0,
    end = vals.length - 1 // 雙指針
  while (start < end) {
    if (vals[start] != vals[end]) {
      // 理應相同，如果不同，不是迴文
      return false
    }
    start++
    end-- // 雙指針移動
  }
  return true // 循環結束也沒有返回false，說明是迴文
}

二叉樹的直徑

https://leetcode-cn.com/problems/diameter-of-binary-tree

方法 1

var diameterOfBinaryTree = function (root) {
  // 默認爲1是因爲默認了根節點自身的路徑長度
  let ans = 1
  function depth(rootNode) {
    if (!rootNode) {
      // 如果不存在根節點，則深度爲0
      return 0
    }
    // 遞歸，獲取左子樹的深度
    let left = depth(rootNode.left)
    // 遞歸，獲取右子樹的深度
    let right = depth(rootNode.right)
    /* 關鍵點1
        L+R+1的公式是如何而來？
        等同於：左子樹深度(節點個數) + 右子樹深度（節點個數） + 1個根節點
        便是這株二叉樹從最左側葉子節點到最右側葉子節點的最長路徑
        類似於平衡二叉樹的最小值節點到最大值節點的最長路徑
        之所以+1是因爲需要經過根節點
         */
    // 獲取該樹的最長路徑和現有最長路徑中最大的那個
    ans = Math.max(ans, left + right + 1)
    /* 關鍵點2
        已知根節點的左右子樹的深度，
        則，左右子樹深度的最大值 + 1，
        便是以根節點爲數的最大深度*/
    return Math.max(left, right) + 1
  }
  depth(root)
  // 由於depth函數中已經默認加上數節點的自身根節點路徑了，故此處需減1
  return ans - 1
}

方法 2

function height(node) {
  //求樹高
  if (!node) return 0
  return 1 + Math.max(height(node.left), height(node.right))
}

var diameterOfBinaryTree = function (root) {
  if (!root) return 0
  let tempH = height(root.left) + height(root.right)
  return Math.max(
    tempH,
    diameterOfBinaryTree(root.left),
    diameterOfBinaryTree(root.right)
  )
}

合併二叉樹

https://leetcode-cn.com/problems/merge-two-binary-trees/

var mergeTrees = function (root1, root2) {
  if (root1 == null && root2) {
    return root2
  } else if (root2 == null && root1) {
    return root1
  } else if (root1 && root2) {
    root1.val = root1.val + root2.val
    //遞歸合併每一個節點
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
  }
  return root1
}

注：部分題解參考 LeetCode 最佳題解，有需要的同學可以自行去 LeetCode 官網查看。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/_s5ML3gkKUoSMdpyB9I7qg