力扣 | Richard's Blob

# 62. 不同路径

题目描述

# 解法1：组合数

走到终点，需要向右走m-1步，向下走n-1步，根据高中黑板上排列组合，你还不舍得解开吗？问题就演变成从m-1 + n - 1 = m + n - 2的总步数中，挑出n-1步向下走，有多少种组合？

$\mathbf\color{red}{C_{m-1+n-1}^{n-1}}$

或者

$\mathbf\color{red}{C_{m-1+n-1}^{m-1}}$

组合数公式：

$\mathbf\color{green}{C_n^m = {P_n^m \over P_m} = {n! \over m!(n-m)!}, C_n^0=1}$

var uniquePaths = function(m, n) {
  function cal(n) {
    let sum = 1;
    for(let i = 1; i <= n; i++) {
      sum *= i
    }
    return sum;
  }
  let max = Math.max(m, n);
  let min = Math.min(m, n);
  return cal(max - 1 + min - 1) / cal(min - 1) / cal(max - 1)
};

1
2
3
4
5
6
7
8
9
10
11
12

# 解法2：动态规划

想象一下如果只差一步就可以能走到终点 $d[i][j]$ , 则当前位置可能是在终点上一格 $d[i-1][j]$ ，或者终点的前一格 $d[i][j-1]$ , 那到终点的走法数就是

$\mathbf\color{red}{d[i][j] = d[i-1][j] + d[i][j-1]}$

以上就是动态方程

再考虑边界情况

$\mathbf\color{red}{d[i][j] = 1, i=0 || j=0}$

var uniquePaths = function(m, n) {
  let result = Array.from({length: m}).map(() => [])
  for(let i = 0; i < n; i++) {
      result[0][i] = 1;
  } 
  for(let i = 0; i < m; i++) {
      result[i][0] = 1;
  }
  for(let i = 1; i < m; i++) {
      for(let j = 1; j < n; j++) {
          result[i][j] = result[i-1][j] + result[i][j-1];
      }
  }
  return result[m-1][n-1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 300. 最长上升子序列

题目描述

动态规划思想，当数组长度是1的时候，结果是1；当数组长度是2，看当前数是否大于前面的数，是的话答案就是1+1，否则答案还是1；当数组长度是3，得看前面所有的数，从而得出动态方程：

$\mathbf\color{red} {dp[i] = Max(dp[j]) + 1}$

其中，

0 <= j < i && nums[i] > nums[j]
dp[0] = 1
时间复杂度 $O(n^2)$
空间复杂度： $O(n)$

var lengthOfLIS = function(arr) {
  if(arr.length <= 1) {
    return arr.length;
  }
  let maxArr = [1];
  let max = 1;
  for(let i = 1; i < arr.length; i++) {
    let num = arr[i];
    maxArr[i] = 1;
    for(let j = 0; j < i; j++) {
      if(num > arr[j]) {
        maxArr[i] = Math.max(maxArr[j] + 1, maxArr[i]); // 取最大
      }
    }
    if(maxArr[i] > max) {
      max = maxArr[i];
    }
  }
  return max;
}

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

# 70. 爬楼梯

题目描述

就是一个求斐波那契额数列问题。假设剩下最后一步就能走完了，那此时此刻，你有可能在倒数第n-1步楼梯，或者n-2步楼梯。所以去到第n步楼梯的方法数，就是 $f(n-1) + f(n-2)$

$f(n) = f(n-1) + f(n-2)$

var climbStairs = function(n) {
  if(n <= 2) return n;
  let a = 1;
  let b = 2;
  for(let i = 3; i <= n; i++) {
    [a, b] = [b, a + b]
  }
  return b;
};

1
2
3
4
5
6
7
8
9

时间复杂度： $O(n)$ ，单循环到n，需要计算第n个斐波那契数。
空间复杂度： $O(1)$ ，使用常量级空间。

# 3. 无重复字符的最长子串

题目描述

选定一个初始位置，往前查找字符，若无重复字符（维护一个Set辅助判断），计算字串长度和max比较。若存在相同字符，从开始位置查找到该相同的字符（若不是该字符，则从Set中移除），将开始位置置为该相同字符的下一个字符。

var lengthOfLongestSubstring = function(s) {
  let res = 0;
  let set = new Set()
  let start = 0;
  for(let i = 0; i < s.length; i++) {
    let char = s[i]
    if (!set.has(char)) {
      set.add(char)
      res = Math.max(res, i - start + 1)
    } else {
      for(let j = start; j < i; j++) {
        if (s[j] === char) {
          start = j + 1
          break
        } else {
          set.delete(s[j])
        }
      }
    }
  }
  return res
};

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

← Welcome 某厂前端面试算法题目 →