LeetCode HOT 100 Solution (Easy level)

Selected from 100 LeetCode topics, this article is easy level only, suitable for beginners of algorithms and data structures and those who want to improve quickly and efficiently.

1. Sum of two numbers

Leetcode-cn.com/problems/tw…

Methods a

/ * * *@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]
      }
    }
  }
}
Copy the code

Method 2

/ * * *@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
  }
}
Copy the code

14. Longest public prefix

Leetcode-cn.com/problems/lo…

Ideas:

Let’s go through the set
Iterate over the first string of the array again and compare each character in the string with the corresponding subscript of each item in the array. If the difference is different, the loop breaks out and the common prefix is found in pairs. The final result is the length j of the longest common prefix.
A character that intercepts the string length j is the longest public prefix

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)
Copy the code

18. Delete nodes in the linked list

Leetcode-cn.com/problems/sh…

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
}
Copy the code

20. Valid brackets

Leetcode-cn.com/problems/va…

Method analysis:

A stack is a stack. The stack has a first in, last out (FILO) feature. A stack can be top or bottom of a stack. Pushing is pushing elements onto the stack; To unstack is to pop the top element off the stack. So you can use the stack to check if symbols are paired correctly.

Answer:

Length of valid parenthesis string, must be even!
The close parenthesis must be preceded by the corresponding open parenthesis to cancel!
If the opening parenthesis is not preceded by the corresponding opening parenthesis, then the string must not be a valid parenthesis!

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 }Copy the code

21. Merge two ordered lists

Leetcode-cn.com/problems/me…

/** * 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
  }
}
Copy the code

53. Maximum suborder sum

Leetcode-cn.com/problems/ma…

/ * * *@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
}
Copy the code

70. Climb the stairs

Leetcode-cn.com/problems/cl…

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]
}
Copy the code

101. Symmetric binary trees

Leetcode-cn.com/problems/sy…

/** recursive code *@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 // A subtree exists and a subtree does not exist
  }
  if (root == null) {
    // If the root passed in is null, symmetric
    return true
  }
  return check(root.left, root.right)
}
Copy the code

112. Sum of paths

Leetcode-cn.com/problems/pa…

var hasPathSum = function (root, targetSum) {
  Depth-first traversal
  if (root === null) {
    //1
    //2. The middle of recursion indicates that the node is not a leaf node
    return false
  }
  if (root.left === null && root.right === null) {
    return root.val - targetSum === 0
  }
  // Split into two subtrees
  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  )
}
Copy the code

136. A number that appears only once

Leetcode-cn.com/problems/si…

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

155. The minimum stack

Leetcode-cn.com/problems/mi…

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]}Copy the code

160. Intersecting linked lists

Leetcode-cn.com/problems/in…

Method 1: Violence

Train of thought

For each node in linked list A, I’m going to go through linked list B and see if there are any identical nodes.

The complexity of the

Time complexity: O(M * N)O(M∗N), where M and N are the lengths of two linked lists respectively. Space complexity: 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
  }
}
Copy the code

Method 2: Hash table

Train of thought

Walk through linked list A, using the hash table to record each node (remember to store node references, not node values). Then I iterate through list B and find the nodes that appear in the hash table as the intersection of the two lists.

The complexity of the

Time complexity: O(M + N), M, N are the lengths of two linked lists respectively. Space complexity: O(N), where N is the length of linked list A.

var getIntersectionNode = function (headA, headB) {
  if(! headA || ! headB)return null
  const hashmap = new Map(a)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
  }
}
Copy the code

Method 3: Double Pointers

If there are no intersections in the list

The two linked lists have the same length. PA and pB are null after the first traversal. The two linked lists have different lengths

The complexity of the

Time complexity: O(M + N), M, N are the lengths of two linked lists respectively. Space complexity: 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
}
Copy the code

206. Reverse linked lists

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

Scheme 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
}
Copy the code

234. Palindrome linked list

Leetcode-cn.com/problems/pa…

const isPalindrome = (head) = > {
  const vals = []
  while (head) {
    // Drop it into the array
    vals.push(head.val)
    head = head.next
  }
  let start = 0,
    end = vals.length - 1 / / double pointer
  while (start < end) {
    if(vals[start] ! = vals[end]) {// Should be the same, if different, not palindrome
      return false
    }
    start++
    end-- // Double pointer move
  }
  return true // No return false at the end of the loop, indicating palindrome
}
Copy the code

543. Diameter of binary tree

Leetcode-cn.com/problems/di…

Method 1

var diameterOfBinaryTree = function (root) {
  // Defaults to 1 because the root node's own path length is default
  let ans = 1
  function depth(rootNode) {
    if(! rootNode) {// If there is no root node, the depth is 0
      return 0
    }
    // Get the depth of the left subtree recursively
    let left = depth(rootNode.left)
    // Get the depth of right subtree recursively
    let right = depth(rootNode.right)
    /* Key point 1: where does L+R+1 come from? Equivalent: left subtree depth (nodes) + right subtree depth (nodes) + 1 a root node Is this binary tree from the plant on the left side of the leaf node to the longest path on the right side of the leaf node Similar to the balanced binary tree of the minimum maximum node to node longest path + 1 because takes root node * /
    // Get the longest path of the tree and the largest of the existing longest paths
    ans = Math.max(ans, left + right + 1)
    /* Key point 2 is given the depth of the left and right subtrees of the root node. Then, the maximum depth of the left and right subtrees + 1 is the maximum depth of the number of root nodes */
    return Math.max(left, right) + 1
  }
  depth(root)
  // The depth function already adds the root node path of several nodes by default, so we need to subtract 1
  return ans - 1
}
Copy the code

Method 2

function height(node) {
  / / tree height
  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)
  )
}
Copy the code

617. Merge binary trees

Leetcode-cn.com/problems/me…

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
    // Merge each node recursively
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
  }
  return root1
}
Copy the code

Note: Some of the solutions refer to the best solutions of LeetCode. If you need them, you can go to the official website of LeetCode.

LeetCode HOT 100 Solution (Easy level)

1. Sum of two numbers

Methods a

Method 2

14. Longest public prefix

Ideas:

18. Delete nodes in the linked list

20. Valid brackets

Method analysis:

Answer:

21. Merge two ordered lists

53. Maximum suborder sum

70. Climb the stairs

101. Symmetric binary trees

112. Sum of paths

136. A number that appears only once

155. The minimum stack

160. Intersecting linked lists

Method 1: Violence

Train of thought

The complexity of the

Method 2: Hash table

Train of thought

The complexity of the

Method 3: Double Pointers

If there are no intersections in the list

The complexity of the

206. Reverse linked lists

Scheme 2

234. Palindrome linked list

543. Diameter of binary tree

Method 1

Method 2

617. Merge binary trees

Related Posts

Page click heat map

React + TS uses Tencent Map GL

JavaScript data structure Object