MiKin Blog

松岛川树

0%

发表于 分类于 ， ，

056. Merge Intervals

难度: Medium

刷题内容

原题连接

内容描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

 输入: [[1,3],[2,6],[8,10],[15,18]]
 输出: [[1,6],[8,10],[15,18]]
 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

 输入: [[1,4],[4,5]]
 输出: [[1,5]]
 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题方案

思路 1
**- 时间复杂度: 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
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

var merge = function(intervals) {
    if (!intervals || !intervals.length) {
        return intervals;
    }
    intervals.sort((a, b) => (a[0] - b[0]))
    return intervals.reduce((acc, [ currentLeft, currentRight ]) => {
        if (currentLeft > acc[acc.length - 1][1]) {
            acc.push([ currentLeft, currentRight ]);
        } else if (currentRight > acc[acc.length - 1][1]){
            acc[acc.length - 1][1] = currentRight;
        }
        return acc;

    }, [intervals[0]]);
};

发表于 分类于 ， ，

58. Length of Last Word

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Input: "Hello World"

Output: 5

解题方案

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

  • 将数组以空格分割，找到最后一个字符串输出长度
  • 注意以空格结尾以及输入空字符串

代码：

1
2
3
4
5
6
7
8
9
10
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    var temp = s.split(' ').filter(function (value) {
        return value!='';
    });
    return temp.length>0?temp.pop().length:0;
};

发表于 分类于 ， ，

061. Rotate List

难度: Medium

刷题内容

原题连接

内容描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

 输入: 1->2->3->4->5->NULL, k = 2
 输出: 4->5->1->2->3->NULL
 解释:
 向右旋转 1 步: 5->1->2->3->4->NULL
 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

 输入: 0->1->2->NULL, k = 4
 输出: 2->0->1->NULL
 解释:
 向右旋转 1 步: 2->0->1->NULL
 向右旋转 2 步: 1->2->0->NULL
 向右旋转 3 步: 0->1->2->NULL
 向右旋转 4 步: 2->0->1->NULL

解题方案

思路 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
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) {
        return head;
    }
    const list = [];
    let cur = head;

    while (cur) {
        list.push(cur)
        cur = cur.next;
    }

    const index = k%list.length;
    list.unshift(...list.splice(list.length - index, list.length))
    list.forEach((node, index) => {
        if (index < list.length) {
            node.next = list[index+1]
        } else {
            node.next = null;
        }
    })
    return list[0]
};

发表于 分类于 ， ，

62. Unique Paths 不同路径

难度: Medium

刷题内容

原题连接

内容描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？
img

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
3
4
5
6
7
8
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

解题方案

思路 1 排列组合方式

例子中，m=7、n=3，也就是说，可以向右走6步（m-1）和向下走2步（n-2）；
如果用符号→表示向右走，符号↓表示向下走，那么这道题就变成了，(m-1)个→和(n-1)个↓有多少种排列组合方式，也就是最终

1
2
计算公式：(m-1 + n-1)! ÷ （(m-1)! × （n-1）!）

自行实现阶乘计算函数——factorial即可

代码：

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
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
// 为了提高算法效率，利用cache缓存计算结果
let cache = {
  1: 1
}
var uniquePaths = function(m, n) {
  return factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1)
};

function factorial(num){
  if(num <= 1) {
    return 1;
  } else if (cache[num]) {
    return cache[num]
  }else{
    let value = num * factorial(num-1);
    cache[num] = value;
    return value
  }
}

思路 2 模拟矩阵
- 时间复杂度: O(N)

- 空间复杂度: O(N)

如果用每个格子上的值表示，当前格子到左上角格子的走法数量的话，那么右下角格子的值就是最终结果，样子如下
| | | |
| - | - | - |
| 1 | 1 | 1 |
| 1 | 2 | 3 |
| 1 | 3 | 6 |
| 1 | 4 | 10 |
| 1 | 5 | 15 |
| 1 | 6 | 21 |
| 1 | 7 | 28 |

发现规律，每个格子的值等于左侧格子值 + 上方格子值，所以用双层循环绘制表格，再去最后的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  let metrics = [];
  for (let x = 0; x < m; x++) {
    for (let y = 0; y < n; y++) {
      if (!metrics[x]) {
        metrics[x] = []
      }
      if (y === 0 || x === 0) {
        metrics[x][y] = 1
      } else {
        metrics[x][y] = metrics[x][y - 1] + metrics[x - 1][y]
      }
    }
  }
  return metrics[m-1][n-1];
};

发表于 分类于 ， ，

62. Unique Paths 不同路径

难度: Medium

刷题内容

原题连接

内容描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

 输入:
 [
   [1,3,1],
   [1,5,1],
   [4,2,1]
 ]
 输出: 7
 解释: 因为路径 1→3→1→1→1 的总和最小。

解题方案

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

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

这样一次循环即可。

代码：

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 {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  const height = grid.length
  const width = grid[0].length
  if (width === 1) {
    return grid.reduce((cur, pre) => (cur + pre[0]), 0)
  }
  if (height === 1) {
    return grid[0].reduce((cur, pre) => (cur + pre), 0)
  }
  let min = 0
  for (let i = 0; i < width; i++) {
    for (let j = 0; j < height; j++) {
      if (j === 0 && i === 0) {
        grid[j][i] = grid[j][i]
      } else if (j === 0) {
        grid[j][i] = grid[j][i] + grid[j][i - 1]
      } else if (i === 0) {
        grid[j][i] = grid[j][i] + grid[j - 1][i]
      } else {
        grid[j][i] = grid[j][i] + Math.min(grid[j][i - 1], grid[j - 1][i])
      }
      min = grid[j][i]
    }
  }
  return min
};

发表于 分类于 ， ，

66. Plus One

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

解题方案

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

  • 如果数字小于9则不会发生进位，仅当前位置++即可
  • 因进位和plus one 都是数字加一
  • 数字大于9则进位与初始加一的处理方式一样

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(var i=digits.length-1;i>=0;i--){
        if(digits[i]<9){
            digits[i]++;
            return digits;
        }
        digits[i]=0;
    }
    digits.unshift(1);
    return digits;
};

发表于 分类于 ， ，

67. Add Binary

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"
Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

解题方案

思路 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
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    var tempA = a.split('');
    var tempB = b.split('');
    var result =[];
    var aLen=tempA.length,bLen=tempB.length;
    var carry = 0;
    while(aLen>0||bLen>0){
        var charA=0,charB=0;
        if(aLen>0)
            charA = tempA[--aLen]-0;
        if(bLen>0)
            charB = tempB[--bLen]-0;
        var temp = charA + charB + carry;
        carry = temp>1?1:0;
        result.unshift(temp%2);
    }
    if(carry===1)
        result.unshift(1);
    return result.toString().replace(/,/g,'');
};

发表于 分类于 ， ，

074. Search a 2D Matrix

难度: Medium

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true
Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

解题方案

思路 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
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    if(matrix.length===0)
        return false;
    var row=0,col=matrix[0].length-1;
    while(row<matrix.length&&col>=0){
        if(matrix[row][col]===target)
            return true;
        else if(matrix[row][col]>target)
            col--;
        else
            row++;
    }
    return false;
};

发表于 分类于 ， ，

077. Combinations

难度: Medium

刷题内容

原题连接

https://leetcode-cn.com/problems/combinations/

内容描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

 输入: n = 4, k = 2
 输出:
 [
   [2,4],
   [3,4],
   [2,3],
   [1,2],
   [1,3],
   [1,4],
 ]

进阶:

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

解题方案

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

回溯算法，算法参考：leetCode回溯算法+剪枝

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
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */

var combine = function(n, k) {
  const result = []
  if (n <= 0 || k <= 0 || n < k) {
    return result;
  }
  findCombinations(n, k, 1, [])
  function findCombinations(n, k, index, list) {
    list = [...list]
    if (list.length === k) {
      result.push(list);
      return;
    }
    for (let i = index; i <= n - (k - list.length) + 1; i++) {
      list.push(i);
      findCombinations(n, k, i + 1, list);
      list.pop();
    }
  }
  
  return result
};

发表于 分类于 ， ，

0079. Word Seach

难度: Medium

刷题内容

原题连接

内容描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

 board =
 [
   ['A','B','C','E'],
   ['S','F','C','S'],
   ['A','D','E','E']
 ]

 给定 word = "ABCCED", 返回 true.
 给定 word = "SEE", 返回 true.
 给定 word = "ABCB", 返回 false.

解题方案

思路
**- 时间复杂度: O(?)**- 空间复杂度: 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
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
58
59
60
61
62
63
64
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    let height = board.length;
    let width = board[0].length;
    let result = false;
    for(let x = 0; x < height; x++) {
        for(let y = 0; y < width; y++) {
            if (board[x][y] === word[0]) {
                result = result || searchDFS(board, [ x, y ], shiftWord(word), [[x,y]])
            }
        }
    }
    return result;
};

var searchDFS = function (board, [x,y], word, useList = []) {
    const list = [...useList];
    let result = false;
    if(!word || !word.length) {
        return true;
    }

    // 上
    if(x > 0 && board[x-1][y] === word[0] && !positionInList([x-1,y], list)) {
        const l = [...list]
        l.push([x-1, y]);
        result = result || searchDFS(board, [x-1,y], shiftWord(word), l);
    }

    // 下
    if (x < board.length-1 && board[x+1][y] === word[0] && !positionInList([x+1,y], list)) {
        const l  = [...list]
        l.push([x+1, y]);
        result = result || searchDFS(board, [x+1,y], shiftWord(word), l);
    }

    // 左
    if (y > 0 && board[x][y-1] === word[0] && !positionInList([x,y-1], list)) {
        const l = [...list]
        l.push([x, y-1]);
        result = result || searchDFS(board, [x,y-1], shiftWord(word), l);
    }

    // 右
    if (y < board[0].length-1 && board[x][y+1] === word[0] && !positionInList([x,y+1], list)) {
        const l = [...list]
        l.push([x, y+1]);
        result = result || searchDFS(board, [x,y+1], shiftWord(word), l);
    }

    return result;
}

var positionInList = function ([x, y], list = []) {
    return list.some(([oX, oY]) => (oX === x && oY === y))
}

var shiftWord = function (word) {
    return Array.prototype.slice.call(word, 1).join('')
}