MiKin Blog

松岛川树

0%

发表于 分类于 ， ，

020. Valid Parentheses

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

解题方案

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

代码：

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
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
        if(!s){
            return true;
        }
        let array = [];
        for(let i = 0,len = s.length; i<len; i++){
            let cur = s.charAt(i);
            if(cur === '(' || cur === '{' || cur === '['){
                array.push(cur);
            }else if(!array.length){
                return false;
            }else{
                let pre = array.pop();
                if(pre === '(' && cur !== ')'){
                    return false;
                }
                if(pre === '{' && cur !== '}'){
                    return false;
                }
                if(pre === '[' && cur !== ']'){
                    return false;
                }
            }
        }
        return !array.length
    };

发表于 分类于 ， ，

021. Merge Two Sorted Lists

难度: Easy

原题连接

内容描述

1
2
3
4
5
6
7
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解题方案

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

代码：

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 singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if(l2 == null) return l1;
    if(l1 == null) return l2;
    if(l1.val<l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l2.next,l1);
        return l2;
    }
};

思路 2: 暴力解法
**- 时间复杂度: O(2N)**- 空间复杂度: O(2N)**

由于是有序的链表，所以可以用数组中转的方式。把两个数组全部转成数组，再将两个数组合并再排序，最后再将两个数组转化为链表。

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if (!l1 && !l2) {
    return null
  }
  let array1 = listNodeToArray(l1)
  let array2 = listNodeToArray(l2)
  let array = array1.concat(array2)
  array.sort((a, b) => (a - b))
  
  return arrayToListNode(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
  
  for(let i = 1; i < array.length; i++) {
    node = new ListNode(array[i])
    pnode.next = node
    pnode = node
  }
  
  return head
}

思路 3: 单次循环遍历
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
let mergeTwoLists = function(l1, l2) {
    if(!l1 || !l2){
        return (l1 || l2)
    }
    let result = new ListNode;
    let preNode = result;
    while (l1 || l2){
        let currentNode = new ListNode;
        if(!l2){
            currentNode.val = l1.val;
            l1 = l1.next;
        }else if(!l1){
            currentNode.val = l2.val;
            l2 = l2.next;
        }else{
            if(l1.val < l2.val){
                currentNode.val = l1.val;
                l1 = l1.next;
            }else{
                currentNode.val = l2.val;
                l2 = l2.next;
            }
        }
        preNode.next = currentNode;
        preNode = currentNode;
    }
    return result.next;
};

发表于 分类于 ， ，

022. generate-parentheses

难度: Medium

刷题内容

原题连接

内容描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
8

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题方案

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

代码：

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
/**
 * 递归函数
 * @param left  剩余的左括号
 * @param right 剩余的又括号
 * @param str  当前已拼装括号的字符串
 * @param list  最终结果集
 */
let helper = function (left,right,str,list) {
    //当前右括号大于左括号
    if (left > right){
        return ;
    }
    //左括号，右括号均无剩余，作为终值填充
    if(left === 0 && right === 0){
        list.push(str);
        return ;
    }
    //左括号有剩余
    if(left > 0){
        helper(left - 1,right,str + '(',list);
    }
    //右括号有剩余
    if(right > 0){
        helper(left,right - 1,str + ')',list);
    }
};
/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function(n) {
    let list = [];
    helper(n,n,'',list);
    return list;
};

发表于 分类于 ， ，

0024. Swap Nodes In Pairs

难度: Medium

刷题内容

原题连接

内容描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 
示例:

 给定 1->2->3->4, 你应该返回 2->1->4->3.

解题方案

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

递归方式：思路主要是每次swapPairs返回的都是替换后的头指针，所以每次只替换两个，然后当前head.next指向的是移动两次指针后的swapParis返回结果

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs = function(head) {
  if (!head || !head.next) {
    return head;
  }
  
  let root = head.next;
  head.next = swapPairs(head.next.next);
  root.next = head;
  return root;
};

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

这里借鉴了Python的解题思路

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
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs = function(head) {
  if (!head || !head.next) {
    return head;
  }
  
  let tmp = new ListNode();
  tmp.next = head;
  
  let current = tmp;
  while (current.next && current.next.next) {
    let next1 = current.next;
    let next2 = current.next.next;
    let next3 = current.next.next.next;
    current.next = next2;
    next2.next = next1;
    next1.next = next3;
    current = next1;
  }
  
  return tmp.next;
};

发表于 分类于 ， ，

027. Remove Element

难度: Easy

刷题内容

原题连接

内容描述

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

 Given nums = [3,2,2,3], val = 3,

 Your function should return length = 2, with the first two elements of nums being 2.

 It doesn't matter what you leave beyond the returned length.

Example 2:

 Given nums = [0,1,2,2,3,0,4,2], val = 2,

 Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

 Note that the order of those five elements can be arbitrary.

 It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

 // nums is passed in by reference. (i.e., without making a copy)
 int len = removeElement(nums, val);

 // any modification to nums in your function would be known by the caller.
 // using the length returned by your function, it prints the first len elements.
 for (int i = 0; i < len; i++) {
     print(nums[i]);
 }

解题方案

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

保留两个指针 i 和 j，其中 i 是慢指针，j 是快指针。当 nums[j] 与给定的值相等时，递增 j 以跳过该元素。只要 nums[j] !== val,我们就复制 nums[j] 到 nums[i] 并同时递增两个索引。重复这一过程，直到 j 到达数组的末尾，该数组的新长度为 i。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums,val) {
    let j = 0;
    for(let i = 0,len = nums.length; i<len; i++){
        if(nums[i] !== val){
            nums[j] = nums[i];
            j++
        }
    }
    return j;
};

发表于 分类于 ， ，

031. Next Permutation

难度: Medium

刷题内容

原题连接

内容描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题方案

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

下一个排序与当前排序的关系是尽可能多的共用前面的位数

以[1,2,4,6,5,3]为例：

分为三个步骤

  1. 从后向前查找，找到第一个升序排列的组合，即[4,6]，保存这个位置2（即4所在的位置）
  2. 在这个位置上后面找到一个比他的数字进行调换——5，数组变为[1,2,5,6,4,3]，如果没有找到，则说明数组已经为最大的排列方式，直接翻转即可
  3. 对于这个位置后面的数组([6,4,2])进行升序排列，数组变为[1,2,5,3,4,6]

代码：

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
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  if (!nums || !nums.length || nums.length <= 1) {
    return nums
  }
  
  let index = -1;
  
  // step 1: 找到最大共有位置
  for (let i = nums.length - 1; i > 0; i--) {
    if (nums[i-1] < nums[i]) {
      index = i - 1;
      break;
    }
  }
  
  // 未找到的情况，翻转即可
  if (index === -1) {
    return nums.reverse();
  }
  
  // step 2: 替换最大共有位置上的值
  for (let i = nums.length - 1; i > index; i--) {
    if (nums[i] > nums[index]) {
      [nums[i], nums[index]] = [nums[index], nums[i]]
      break;
    }
  }
  
  // step 3: 最大共有位置之后的数据进行升序排列
  const afterList = nums.slice(index + 1)
  afterList.reverse()
  for (let i = index + 1; i < nums.length; i ++) {
    nums[i] = afterList[i - index - 1]
  }
};

发表于 分类于 ， ，

035. Search Insert Position

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

解题方案

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let searchInsert = function(nums, target) {
    let lo = 0,high = nums.length-1;
    while(lo<=high){
         let mid = Math.floor((high-lo)/2)+lo;
         if(nums[mid]===target)
             return mid;
         if(nums[mid]>target)
             high = mid-1;
         else lo = mid+1;
    }
    return lo;
};

发表于 分类于 ， ，

053. Maximum Subarray

难度: Medium

刷题内容

原题连接

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

内容描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

 输入: [-2,1,-3,4,-1,2,1,-5,4],
 输出: 6
 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题方案

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

解法DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  if(nums.length === 1) {
    return nums[0]
  }
  let sum = nums[0]
  let dp = nums[0]
  for (let i = 1; i < nums.length; i++) {
    dp = Math.max(dp + nums[i], nums[i])
    sum = Math.max(sum, dp)
  }
  return sum;
};

发表于 分类于 ， ，

054.Spiral Matrix

难度: Easy

刷题内容

原题连接

内容描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1：

1
2
3
4
5
6
7
输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2：

1
2
3
4
5
6
7
输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题方案

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

代码：
递归思路：

  1. 取矩阵的第一行

  2. 将矩阵逆时针反转90°

  3. 递归

    终止条件：
    矩阵为空 => 返回空矩阵
    矩阵只剩下一行 => 返回这一行

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
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  if (!matrix || !matrix.length) {
    return matrix
  } else if (matrix.length === 1 && Array.isArray(matrix[0])) {
    return matrix[0]
  } else {
    return matrix.shift().concat(spiralOrder(rotate(matrix)))
  }
};


var rotate = function(matrix) {
  if (!matrix || !matrix.length) {
    return null
  }
  let newMatrix = []
  let m = matrix[0].length
  let n = matrix.length
  for (let y = m - 1; y >= 0; y--) {
    let newLine = []
    for (let x = n - 1; x >= 0; x--) {
      newLine.unshift(matrix[x][y])
    }
    newMatrix.push(newLine);
  }
  return newMatrix;
}

发表于 分类于 ， ，

0055. Jump Game

难度: Medium

刷题内容

原题连接

内容描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1:

 输入: [2,3,1,1,4]
 输出: true
 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2：

 输入: [3,2,1,0,4]
 输出: false
 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

解题方案

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

  1. 如果数组中没有0，那么结果一定为true
  2. reach代表目前能跳到的最远位置（数组下标）
  3. 每轮循环，数组下标固定向有移动一位
  4. start代表本轮循环的位置
  5. 每轮循环更新一次最远可达的位置——reach，reach的值为当前循环的值+当前的数组下标与之前reach值的最大值
  6. 循环终止条件：
  • 当前下标值大于可达最远位置时，代表当前下标永远达到不了
  • 可达最远位置已经大于数组长度，代表已经能跳到最后位置了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  let start = 0;
  let reach = 0;
  if (nums.every(i => i)) {
    return true
  }
  while (start <= reach && reach < nums.length - 1) {
    reach = Math.max(reach, nums[start] + start);
    start++;
  }
  return reach >= nums.length-1;
};