MiKin Blog

松岛川树

0%

发表于 分类于 ， ，

083. Remove Duplicates From Sorted List

难度: Easy

刷题内容

原题连接

内容描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

1
2
输入: 1->1->2
输出: 1->2

示例 2:

1
2
输入: 1->1->2->3->3
输出: 1->2->3

解题方案

思路 1
- 时间复杂度: O(N)

- 空间复杂度: O(2N)

暴力解法：将链表转化为数组，对数组去重，然后数组转换为链表

执行用时 :100 ms, 在所有 JavaScript 提交中击败了**75.87%**的用户

内存消耗 :36.7 MB, 在所有 JavaScript 提交中击败了**7.05%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  if (!head) {
    return null
  }
  let array = listNodeToArray(head)
  return arrayToListNode([...new Set(array)])
};


function listNodeToArray (head) {
  let array = []
  while (head) {
    array.push(head.val)
    head = head.next
  }
  return array
}

function  arrayToListNode(array) {
  if(!array || !array.length) {
    return null
  }
  
  let node
  let head = new ListNode(array[0])
  let pnode = head  //pnode变量用来保存前一个节点
  
  for(let i = 1; i < array.length; i++) {
    node = new ListNode(array[i])
    pnode.next = node   //将前一个节点的next指向当前节点
    pnode = node   //将node赋值给pnode
  }
  
  return head
}

思路 2
- 时间复杂度: O(N)

- 空间复杂度: O(1)

快慢指针：每次循环，判断当前的值与下一个是否相等，如果相等，快指针(head)向前移动，慢指针（slow）原地不动；如果不等则把下一个节点连接到慢指针后，再将快慢指针都向前移动。

执行用时 :92 ms, 在所有 JavaScript 提交中击败了**91.01%**的用户

内存消耗 :35.7 MB, 在所有 JavaScript 提交中击败了**69.46%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  if (!head) {
    return null
  }
  let slow = head
  let result = slow
  while (head) {
    if (head.next && (head.val === head.next.val)) {
      head = head.next
    } else {
      slow.next = head.next
      slow = slow.next
      head = head.next
    }
  }
  return result
};

发表于 分类于 ， ，

094. Binary Tree Inorder Traversal

难度: Medium

刷题内容

原题连接

内容描述

给定一个二叉树，返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

解题方案

思路 1 迭代
- 时间复杂度: O(3N)

- 空间复杂度: O(N)

执行用时 :64 ms, 在所有 JavaScript 提交中击败了**97.85%**的用户

内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了**34.70%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = node => {
  const valueList = []
  forEachTree(node)
  return valueList
  function forEachTree (node) {
    if (!node) {
      return
    }
    forEachTree(node.left)
    valueList.push(node.val)
    forEachTree(node.right)
  }
}

思路 2 迭代

  • 时间复杂度: O(N²)
  • 空间复杂度: O(N²)

执行用时 :76 ms, 在所有 JavaScript 提交中击败了**69.05%**的用户

内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了**36.57%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = (node) => {
  const valList = []
  const stack = []
  while (node || stack.length) {
    if (node) {
      stack.push(node)
      node = node.left
    } else {
      node = stack.pop()
      valList.push(node.val)
      node = node.right
    }
  }
  return valList
};

发表于 分类于 ， ，

098. Validate Binary Search Tree

难度: Medium

刷题内容

原题连接

内容描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
         5
        / \
       1   4
          / \
         3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解题方案

思路 1
**- 时间复杂度: O(2N)**- 空间复杂度: O(2N)**

一个思路简单的算法，二叉搜索树的中序遍历结果是个有序数组。

  1. 获取当前二叉树的中序遍历结果数组
  2. 判断上步的数组是否是一个有序数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  var list = inorderTraversal(root)
  var base = list.join(',')
  return base === [...new Set(list)].sort((a, b) => (a - b)).join(',')
};

// 获取中序遍历
var inorderTraversal = function (root) {
  if (root === null) return []
  return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
};

发表于 分类于 ， ，

100. Same Tree

难度: Easy

刷题内容

原题连接

内容描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

递归解法

  1. 获取当前二叉树的中序遍历结果数组
  2. 判断上步的数组是否是一个有序数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
  if (p) {
    return p && !!q && (p.val === q.val) && isSameTree(p.left, q.left) && isSameTree(p.right,q.right)
  } else {
    return !q
  }
};

发表于 分类于 ， ，

101. Symmetric Tree

难度: Easy

刷题内容

原题连接

内容描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

递归解法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (!root) {
        return true
    }
    return isMirror(root, root)
};

function isMirror(t1, t2) {
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  return (t1.val == t2.val)
    && isMirror(t1.right, t2.left)
    && isMirror(t1.left, t2.right);
}

发表于 分类于 ， ，

104. Maximum Depth of Binary Tree

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

解题方案

思路 1
**- 时间复杂度: O(log2 N)**- 空间复杂度: O(N)**

  • 这道题使用递归进行解决，因为对于树的每一个儿子的处理方法是一致的。
  • 将左儿子和右儿子中最大的数进行返回再加上当前的深度1即可解决。

代码：

1
2
3
4
5
var maxDepth = function(root) {
    if(root===null||root === undefined)
        return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
};

发表于 分类于 ， ，

106. Construct Binary Tree From Inorder And Postorder Traversal

难度: Medium

刷题内容

原题连接

内容描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

  • 代码：

1
2
3
4
5
6
7
8
9
10
11
12
var buildTree = function(inorder, postorder) {
  if (!inorder.length || !postorder.length) {
    return null
  }
  let rootVal = postorder[postorder.length - 1]
  let root = new TreeNode(rootVal)
  let k = inorder.indexOf(rootVal)
  root.left = buildTree(inorder.slice(0, k), postorder.slice(0, k))
  root.right = buildTree(inorder.slice(k+1), postorder.slice(k, postorder.length - 1))
  return root
};

发表于 分类于 ， ，

62. Triangle

难度: Medium

刷题内容

原题连接

内容描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

 [
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
 ]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

解题方案

**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

每个坐标的最小期望 = Min(左上的最小期望， 右上的最小期望) + 当前坐标值。

这样一次循环即可。

Tips：

特殊情况：

  • 顶点的最小期望是自己
  • 最左侧的点的期望 = 当前坐标值 + 上方的值
  • 最右侧的点的期望 = 当前坐标值 + 上方的值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  if (triangle[triangle.length - 1].length === 1) {
    return triangle[0][0]
  }
  triangle.forEach((list, height) => {
    list.forEach((n, i) => {
      if (height === 0) {
        triangle[height][i] = triangle[height][i]
      } else if (i === 0) {
        triangle[height][i] = triangle[height][i] + triangle[height - 1][0]
      } else if (i === list.length - 1) {
        triangle[height][i] = triangle[height][i] + triangle[height - 1][i - 1]
      } else {
        triangle[height][i] = triangle[height][i] + Math.min(triangle[height - 1][i], triangle[height - 1][i - 1])
      }
    })
  })
  return Math.min(...triangle[triangle.length - 1])
};

发表于 分类于 ， ，

0121. Best Time To Buy And Sell Stock

难度: Easy

刷题内容

原题连接

内容描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例1

 输入: [7,1,5,3,6,4]
 输出: 5
 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例2

 输入: [7,6,4,3,1]
 输出: 0
 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题方案

思路1：DP
**- 时间复杂度: O(N)**- 空间复杂度: O(2N)**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  var lowestPrice = prices.shift()
  var maxProfitCount = 0
  while (prices.length) {
    var current = prices.shift()
    lowestPrice = Math.min(lowestPrice, current)
    maxProfitCount = Math.max(current - lowestPrice, maxProfitCount)
  }
  return maxProfitCount
};

思路 2： 暴力穷举法
**- 时间复杂度: O(N²)**- 空间复杂度: O(2N)**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  var profitList = []
  while (prices.length) {
    var cur = prices.shift()
    profitList.push(Math.max(...prices) - cur)
  }
  var maxProfit = Math.max(...profitList)
  return maxProfit > 0 ? maxProfit : 0
};

发表于 分类于 ， ，

0141. Linked List Cycle

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

img

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

使用快慢指针的思路进行解题。就像两个运动员在同一个环形赛道上赛跑，如果一个运动员跑的快，一个跑得慢，最后两个运动员一定会相遇。

下面代码中的fast每次会走两步，而slow每次会走一步，如果fast没有next节点，自然没有环；如果fast等于slow说明二者相遇，最终为表明存在环。

执行结果

执行用时 :92 ms, 在所有 JavaScript 提交中击败了94.16%的用户

内存消耗 :36.6 MB, 在所有 JavaScript 提交中击败了51.93%

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  if (head === null || head.next === null) {
    return false
  }
  
  let slow = head
  let fast = head.next
  
  while (slow !== fast) {
    if (fast === null || fast.next === null) {
      return false
    }
    slow = slow.next
    fast = fast.next.next
  }
  return true
};