【LeetCode第 300 场周赛】

简介: 笔记

解密消息


题目

30.png


思路

  • 模拟,打标记即可。

代码

class Solution {
public:
    string decodeMessage(string key, string message) {
        string res = "";
        int n = key.size();
        bool st[26] = {0};
        map<char, int> mp;
        int now = 0;
        for (int i = 0; i < n; i++) {
            if(key[i] == ' ') continue;
            if(!st[key[i] - 'a']) {
                st[key[i] - 'a'] = true;
                mp[key[i]] = now;
                now ++;
            }
        }
        for (int i = 0; i < message.size(); i++) {
            if(message[i] == ' ') res += ' ';
            else {
                res += mp[message[i]] + 'a';
            }
        }
        return res;
    }
};

螺旋矩阵 IV


题目


31.png


思路


设定当前方向 n o w ,(0、1、2、3)对应方向数组 w a l k 。

设定上下左右(lx、rx、ly、ry)四个边界,在转向方向的时候进行调整。


代码

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> res(m, vector<int>(n, -1));
        ListNode *p = head;
        if(p == nullptr) return res;
        vector<int> v;
        while(p) { v.push_back(p->val); p = p->next; }
        int x = 0, y = -1;
        int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
        int now = 0;
        int lx = 0, rx = m - 1, ly = 0, ry = n - 1;
        for (int i = 0; i < v.size(); i++) {
            int dx = x + walk[now][0], dy = y + walk[now][1];
            if(dx > rx || dx < lx || dy > ry || dy < ly) {
                if(now == 0) lx += 1;
                if(now == 1) ry -= 1;
                if(now == 2) rx -= 1;
                if(now == 3) ly += 1;
                now = (now + 1) % 4;
                dx = x + walk[now][0], dy = y + walk[now][1];
            }
            res[dx][dy] = v[i];
            x = dx, y = dy;
        }
        return res;
    }
};

知道秘密的人数


题目

32.png


思路


33.png

代码

class Solution {
public:
    constexpr static int mod = 1e9 + 7;
    int peopleAwareOfSecret(int n, int delay, int forget) {
        map<int, int> mp;
        int res = 0;
        mp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int cnt = 0;
            for (auto &x: mp) {
                int a = x.first, b = x.second;
                if(i >= a + forget) { mp.erase(a); continue; }
                if (i >= a + delay) cnt = (cnt + b) % mod;
            }
            mp.insert({i, cnt});
        }
        for (auto &x: mp) res = (res + x.second) % mod;
        return res % mod;
    }
};

网格图中递增路径的数目


题目

34.png

思路

35.png



记忆化搜素


考虑样例图解

3->4:1

1->3、1->3->4: 2


相邻能抵达,状态转移 dp[i][j]=dp[x][y]+1。


代码

class Solution {
public:
    constexpr static int mod = 1e9 + 7;
    int n, m;
    int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
    int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& dp) {
        int s = 0;
        for (int i = 0; i < 4; i++) {
            int dx = x + walk[i][0];
            int dy = y + walk[i][1];
            if(dx >= n || dx < 0 || dy >= m || dy < 0) continue;
            if(grid[x][y] >= grid[dx][dy]) continue;
            if(dp[dx][dy]) { s += dp[dx][dy] + 1; continue; }
            s += dfs(dx, dy, grid, dp) + 1;
            s %= mod;
        }
        dp[x][y] = (s + dp[x][y]) % mod;
        return dp[x][y];
    }
    int countPaths(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(!dp[i][j]) {
                    dfs(i, j, grid, dp);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res = (res + dp[i][j] + 1) % mod;
        return res;
    }
};


相关文章
|
6月前
|
Go
golang力扣leetcode 第 291 场周赛
golang力扣leetcode 第 291 场周赛
61 0
|
6月前
|
Go vr&ar
golang力扣leetcode 第 288 场周赛
golang力扣leetcode 第 288 场周赛
52 0
|
6月前
|
Go
golang力扣leetcode 第 286 场周赛
golang力扣leetcode 第 286 场周赛
57 0
|
算法 Android开发
LeetCode 周赛上分之旅 #48 一道简单的树上动态规划问题
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
64 1
|
6月前
|
Go
golang力扣leetcode第 294 场周赛
golang力扣leetcode第 294 场周赛
53 0
|
6月前
|
算法 Java Go
golang力扣leetcode 第 293 场周赛
golang力扣leetcode 第 293 场周赛
82 0
|
6月前
|
Go
golang力扣leetcode 第 290 场周赛
golang力扣leetcode 第 290 场周赛
52 0
|
6月前
|
Go C++
golang力扣leetcode 第 284 场周赛
golang力扣leetcode 第 284 场周赛
58 0
|
6月前
|
Go
golang力扣leetcode 第 292 场周赛
golang力扣leetcode 第 292 场周赛
66 0
|
6月前
|
存储
Leetcode第383场周赛
在LeetCode第383场周赛中,选手完成了3道题目。第一题是关于边界上的蚂蚁,蚂蚁根据非零整数数组nums的值移动,返回蚂蚁返回边界上的次数。解题方法是计算数组累加和为0的次数。第二题涉及计算网格的区域平均强度,给定一个灰度图像和阈值,返回每个像素所属区域的平均强度。解题关键在于理解相邻像素和区域定义,并计算平均强度。第三题是恢复单词初始状态的最短时间问题,通过移除前k个字符并添加k个字符,求恢复原词所需的最短时间。解题策略是检查去除前k个字符后的子串是否能作为原词的前缀。
33 1
Leetcode第383场周赛