LeetCode 熱題 HOT 100題解 (easy級別)

1.兩數(shù)之和

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
  }
}

14.最長公共前綴

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

思路：

1. 先遍歷數(shù)組
2. 再遍歷數(shù)組的第一個字符串，用字符串中的每一個字符和數(shù)組中的每一項的對應(yīng)的該字符串下標相比，不同則跳出循環(huán)，兩兩找出公共前綴，最終結(jié)果即為最長公共前綴的長度 j。
3. 截取字符串長度 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)

18.刪除鏈表的節(jié)點

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
}

20.有效的括號

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

方法分析：

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

解題思路：

1. 有效括號字符串的長度，一定是偶數(shù)！
2. 右括號前面，必須是相對應(yīng)的左括號，才能抵消！
3. 右括號前面，不是對應(yīng)的左括號，那么該字符串，一定不是有效的括號！

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
}

21.合并兩個有序鏈表

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
  }
}

53.最大子序和

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
}

70.爬樓梯

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]
}

101.對稱二叉樹

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)
}

112.路徑總和

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

var hasPathSum = function (root, targetSum) {
  // 深度優(yōu)先遍歷
  if (root === null) {
    //1.剛開始遍歷時
    //2.遞歸中間 說明該節(jié)點不是葉子節(jié)點
    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)
  )
}

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

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
}

155.最小棧

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]
}

160.相交鏈表

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

方法 1：暴力法

思路

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

復(fù)雜度

時間復(fù)雜度：O(M * N)O(M?N), M, N 分別為兩個鏈表的長度?？臻g復(fù)雜度：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，用哈希表把每個節(jié)點都記錄下來(注意要存節(jié)點引用而不是節(jié)點值)。再去遍歷鏈表 B，找到在哈希表中出現(xiàn)過的節(jié)點即為兩個鏈表的交點。

復(fù)雜度

時間復(fù)雜度：O(M + N), M, N 分別為兩個鏈表的長度?？臻g復(fù)雜度：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：雙指針

如果鏈表沒有交點

兩個鏈表長度一樣，第一次遍歷結(jié)束后 pA 和 pB 都是 null，結(jié)束遍歷 兩個鏈表長度不一樣，兩次遍歷結(jié)束后 pA 和 pB 都是 null，結(jié)束遍歷

復(fù)雜度

時間復(fù)雜度：O(M + N) , M, N 分別為兩個鏈表的長度?？臻g復(fù)雜度：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
}

206.反轉(zhuǎn)鏈表

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
}

234.回文鏈表

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

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

543.二叉樹的直徑

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

方法 1

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

617.合并二叉樹

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
    //遞歸合并每一個節(jié)點
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
  }
  return root1
}

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