讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

有多少小于当前数字的数字

思路

  1. 统计个数
  2. 用小于当前数字的个数替换统计个数
  3. 转成答案格式

答题

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    map<int, int> count;
    for (auto& n : nums)
    {
        count[n]++;
    }
    int t = 0;
    for (auto& p : count)
    {
        swap(t, p.second);
        t += p.second;
    }
    for (auto& n : nums)
    {
        n = count[n];
    }
    return nums;
}

通过投票对团队排名

思路

  1. 阅读理解错误,通过 WA WA 用例审题,耗时 75 分
  2. 此处跳过

二叉树中的列表

思路

  1. 使用 bfs 找到起点
  2. 使用 dfs 匹配

答题

bool dfs(ListNode* head, TreeNode* root)
{
    if (head == nullptr) return true;
    if (root == nullptr) return false;
    if (root->val != head->val) return false;
    return dfs(head->next, root->left) || dfs(head->next, root->right);
}

bool isSubPath(ListNode* head, TreeNode* root) 
{
    queue<TreeNode*> que;
    que.push(root);

    while (!que.empty())
    {
        auto q = que.front();
        que.pop();
        if (q == nullptr) continue;

        if (q->val == head->val)
        {
            if (dfs(head, q)) return true;
        }
        que.push(q->left);
        que.push(q->right);
    }
    return false;
}

使网格图至少有一条有效路径的最小代价

思路

  1. 使用 bfs ,找到最短路径
  2. 有箭头的方向相当于步数 +0
  3. 其他方向相当于步数 +1
  4. 将 +0 的格子加入到本次队列
  5. 将 +1 的格子加入到下次队列

答题

int minCost(vector<vector<int>>& grid)
{
    vector<vector<int>> dd = { {}, {0, 1}, {0, -1}, {1, 0}, {-1, 0} };  // 方向数组
    vector<vector<int>> vi(grid.size(), vector<int>(grid[0].size(), INT_MAX));  // 使用步数作为 visited 标准
    queue<vector<int>> cq;  // 本次队列 curr queue
    queue<vector<int>> nq;  // 下次队列 next queue
    int ans = 0;
    cq.push({ 0, 0 });
    vi[0][0] = 0;

    while (!cq.empty() || !nq.empty())
    {
        while (!cq.empty())
        {
            auto q = cq.front();
            cq.pop();
            int x = q[0];
            int y = q[1];
            if (vi[x][y] < ans) continue;
            if (x == grid.size() - 1 && y == grid[0].size() - 1) return ans;

            for (int i = 1; i < dd.size(); i++)
            {
                int dx = x + dd[i][0];
                int dy = y + dd[i][1];
                if ((dx < 0 || dx >= grid.size()) || (dy < 0 || dy >= grid[0].size())) continue;
                if (vi[dx][dy] <= ans) continue;

                // 将箭头所指格子加入当前队列,其他加入下次队列
                auto& sq = (i == grid[x][y]) ? cq : nq;
                sq.push({ dx, dy });
                vi[dx][dy] = (i == grid[x][y]) ? ans : ans + 1;
            }
        }
        swap(cq, nq);
        ans++;
    }
    return ans;
}

致谢

上周卡 T1 ,这周卡 T2 ,求进步!

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

2
展开全部 21 讨论