周赛复盘300-done

不积跬步，无以至千里；不积小流，无以成江海

📅：2020-7-3 🔗：https://leetcode.cn/contest/weekly-contest-300

A: 解密消息

思路：
关键点：

/**
 * @param {string} key
 * @param {string} message
 * @return {string}
 */
var decodeMessage = function(key, message) {
    let decodeMap = new Map();
    const m = key.length, n = 26;
    for (let i = 0, j = 0; i < m; i++) {
        let char = key.charAt(i);
        if (char != ' ' && !decodeMap.has(char)) {
            decodeMap.set(char, String.fromCharCode(j + 97));
            j++;
        }
    }
    let ans = [];
    for (let char of message) {
        ans.push(char == ' ' ? ' ' : decodeMap.get(char));
    }
    return ans.join('');
};

总结：

B: 螺旋矩阵 IV

思路：螺旋矩阵
关键点：边界

/**
 * @param {number} m
 * @param {number} n
 * @param {ListNode} head
 * @return {number[][]}
 */
var spiralMatrix = function(m, n, head) {
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let ans = Array.from({ length: m }, v => new Array(n).fill(-1));
    let i = 0, j = 0, k = 0;
    while (head) {
        ans[i][j] = head.val;
        head = head.next;
        let x = i + dirs[k][0];
        let y = j + dirs[k][1];
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || ans[x][y] != -1) {
            k = (k + 1) % 4;
        }
        i = i + dirs[k][0];
        j = j + dirs[k][1];
    }
    return ans;
};

总结：
雷同59. 螺旋矩阵 II

C: 知道秘密的人数

思路：动态规划
关键点：

/**
 * @param {number} n
 * @param {number} delay
 * @param {number} forget
 * @return {number}
 */
var peopleAwareOfSecret = function(n, delay, forget) {
    let dp = new Array(n + 1).fill(0n);
    dp[1] = 1n;
    for (let i = 2; i <= n; i++) {
        let pre = 0n;
        for (let j = i - forget + 1; j <= i - delay; j++) {
            if (j > 0) {
                pre += dp[j];
            }
        }
        dp[i] = pre;
    }
    let pre = 0n;
    let i = n + 1;
    for (let j = i - forget; j < i; j++) {
        if (j > 0) {
            pre += dp[j];
        }
    }
    return Number(pre % BigInt(10 ** 9 + 7));
};

总结：

D: 网格图中递增路径的数目

思路：dp + dfs-最大岛屿问题
关键点：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countPaths = function(grid) {
    const mod = BigInt(10 ** 9 + 7);
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const m = grid.length, n = grid[0].length;
    const dp = Array.from({ length: m }, v => new Array(n).fill(-1n));
    function dfs (x, y) {
        if (dp[x][y] != -1) return dp[x][y];
        let count = 1n;
        for (let [dx, dy] of dirs) {
            let i = x + dx, j = y + dy;
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= grid[x][y]) continue;
            count = (count + dfs(i, j)) % mod;
        }
        dp[x][y] = count;
        return count;
    }
    let sum = 0n;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            sum = (sum + dfs(i, j)) % mod;
        }
    }
    return Number(sum);
};

总结：

🛵复盘

🚀收获： 最高一次排名 推测原因：

1. 充足的休息
2. 心态平静
3. 面对问题耐心分析原因