lc-day21

发表于

114. 二叉树展开为链表

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var flatten = function(root) {
    const list = [];
    dfs(root, list);
    const size = list.length;
    for(let i = 1; i < size; i++){
        const pre = list[i - 1], cur = list[i];
        pre.left = null;
        pre.right = cur;
    }
};

const dfs = (root, list) => {
    if(root == null) return;
    list.push(root);
    dfs(root.left, list);
    dfs(root.right, list);
}

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

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    
    const p = new Array(128).fill(0);
    const a = 0;
    let res = 0;
    for(let i = 0, j = 0; i < s.length; i++){
        p[s.charCodeAt(i)]++;
        while(p[s.charCodeAt(i)] > 1){
            p[s.charCodeAt(j)]--;
            j++;
        }
        res = Math.max(i - j + 1, res);
        
    }
    return res;
};

使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    if(cost.length == 2) return Math.min(cost[0], cost[1]);
    
    for(let i = 2; i < cost.length; i++){
        cost[i] += Math.min(cost[i - 1], cost[i - 2]);
    }
    return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
};

一个简单题还做了半天, 没脸了

62. 不同路径

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
// 二维数组版本
var uniquePaths = function(m, n) {
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i = 0; i < m; i++) f[i][0] = 1;
    for(let i = 0; i < n; i++) f[0][i] = 1;

    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            f[i][j] += f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
};

我们发现数组每一次循环都可以重复利用上一次的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const f = new Array(n).fill(0);
    //定义一个n列的数列
    
    for(let i = 0; i < n; i++) f[i] = 1;
    //初始时所有的格子路径数为1
    
    for(let i = 1; i < m; i++){
        //m次循环
        for(let j = 1; j < n; j++){
            //更新n列,  每次都是在上次的基础上相加
            f[j] += f[j - 1];
        }
    }
    return f[n - 1];
};

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, -1));
        return dfs(0, 0, m, n, dp);
    }
    int dfs(int i, int j, int m, int n, vector<vector<int>>& dp){
        if(i >= m || j >= n) return 0;
        if(i == m - 1 && j == n - 1) return 1;
        if(dp[i][j] != -1) return dp[i][j];
        
        int sum = 0;
        sum += dfs(i + 1, j, m, n, dp);
        sum += dfs(i, j + 1, m, n, dp);
        dp[i][j] = sum;
        return sum;
    }
};