2596. 检查骑士巡视方案(medium)

2023/9/13

00 : 20 : 58

---

题目描述

骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

示例 1：

输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出：true
解释：grid 如上图所示，可以证明这是一个有效的巡视方案。

示例 2：

输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
输出：false
解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 7
• 0 <= grid[row][col] < n * n
• grid 中的所有整数 互不相同

---

我的答案

class Solution {
public:
    bool check(vector<vector<int>>& grid, int& posX, int& posY, int& x)
    {
        int n = grid.size();
        // 1
        if (posX > 1 && posY > 0 && grid[posX-2][posY-1] == x+1)
        {
            x++;
            posX -= 2;
            posY -= 1;
            return true;
        }
        // 2
        if (posX > 0 && posY > 1 && grid[posX-1][posY-2] == x+1)
        {
            x++;
            posX -= 1;
            posY -= 2;
            return true;
        }
        // 3
        if (posX < n-1 && posY > 1 && grid[posX+1][posY-2] == x+1)
        {
            x++;
            posX += 1;
            posY -= 2;
            return true;
        }
        // 4
        if (posX < n-2 && posY > 0 && grid[posX+2][posY-1] == x+1)
        {
            x++;
            posX += 2;
            posY -= 1;
            return true;
        }
        // 5
        if (posX > 1 && posY < n-1 && grid[posX-2][posY+1] == x+1)
        {
            x++;
            posX -= 2;
            posY += 1;
            return true;
        }
        // 6
        if (posX > 0 && posY < n-2 && grid[posX-1][posY+2] == x+1)
        {
            x++;
            posX -= 1;
            posY += 2;
            return true;
        }
        // 7
        if (posX < n-1 && posY < n-2 && grid[posX+1][posY+2] == x+1)
        {
            x++;
            posX += 1;
            posY += 2;
            return true;
        }
        // 8
        if (posX < n-2 && posY < n-1 && grid[posX+2][posY+1] == x+1)
        {
            x++;
            posX += 2;
            posY += 1;
            return true;
        }
        return false;

    }
    bool checkValidGrid(vector<vector<int>>& grid) {
        int x = 0;
        int n = grid.size();
        int posX = 0, posY = 0;
        if (grid[0][0] != 0)
        {
            return false;
        }
        while (x < n*n - 1)
        {
            if (!check(grid, posX, posY, x))
            {
                return false;
            }
        }
        return true;
    }
};

---

参考答案

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.size();
        vector<array<int, 2>> indices(n * n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                indices[grid[i][j]] = {i, j};
            }
        }
        for (int i = 1; i < indices.size(); i++) {
            int dx = abs(indices[i][0] - indices[i - 1][0]);
            int dy = abs(indices[i][1] - indices[i - 1][1]);
            if (dx * dy != 2) {
                return false;
            }
        }
        return true;
    }
};

---

感想

可以预先存放indices数组为骑士依次走过的位置, 再进行一个绝对值的乘积的判断即可

1222. 可以攻击国王的皇后(medium)

2023/9/14

00 : 16 : 58

---

题目描述

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释： 
[0,1] 的皇后可以攻击到国王，因为他们在同一行上。 
[1,0] 的皇后可以攻击到国王，因为他们在同一列上。 
[3,3] 的皇后可以攻击到国王，因为他们在同一条对角线上。 
[0,4] 的皇后无法攻击到国王，因为她被位于 [0,1] 的皇后挡住了。 
[4,0] 的皇后无法攻击到国王，因为她被位于 [1,0] 的皇后挡住了。 
[2,4] 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。

示例 2：

输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
输出：[[2,2],[3,4],[4,4]]

示例 3：

输入：queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
输出：[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

提示：

• 1 <= queens.length <= 63
• queens[i].length == 2
• 0 <= queens[i][j] < 8
• king.length == 2
• 0 <= king[0], king[1] < 8
• 一个棋盘格上最多只能放置一枚棋子。

---

我的答案

class Solution {
public:
    int distance(vector<int> queen, vector<int> king)
    {
        int differX = queen[0] - king[0];
        int differY = queen[1] - king[1];
        return differX * differX + differY * differY;
    }
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<int>> res;
        // 0 1 2
        // 3   4
        // 5 6 7
        unordered_map<int, vector<int>> canAtt;
        for (auto & queen : queens)
        {
            int differX = queen[0] - king[0];
            int differY = queen[1] - king[1];
            int flag;
            if (differX == 0)
            {
                flag = differY > 0 ? 4 : 3;
            }
            else if (differY == 0)
            {
                flag = differX > 0 ? 6 : 1;
            }
            else if (differX == differY)
            {
                flag = differX > 0 ? 7 : 0;
            }
            else if (differX == -differY)
            {
                flag = differX > 0 ? 5 : 2;
            }
            else
            {
                continue;
            }
            if (canAtt.find(flag) == canAtt.end())
            {
                canAtt[flag] = queen;
            }
            else if (distance(queen, king) < distance(canAtt[flag], king))
            {
                canAtt[flag] = queen;
            }
        }
        for (auto & it : canAtt)
        {
            res.push_back(it.second);
        }
        return res;
    }
};

---

参考答案

class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        unordered_set<int> queen_pos;
        for (const auto& queen: queens) {
            int x = queen[0], y = queen[1];
            queen_pos.insert(x * 8 + y);
        }

        vector<vector<int>> ans;
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                int kx = king[0] + dx, ky = king[1] + dy;
                while (kx >= 0 && kx < 8 && ky >= 0 && ky < 8) {
                    int pos = kx * 8 + ky;
                    if (queen_pos.count(pos)) {
                        ans.push_back({kx, ky});
                        break;
                    }
                    kx += dx;
                    ky += dy;
                }
            }
        }
        return ans;
    }
};

---

感想

从国王出发, 可以维护一个哈希表

LCP 50. 宝石补给(easy)

2023/9/15

00 : 02 : 31

---

题目描述

欢迎各位勇者来到力扣新手村，在开始试炼之前，请各位勇者先进行「宝石补给」。

每位勇者初始都拥有一些能量宝石， gem[i] 表示第 i 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送，operations[j] = [x, y] 表示在第 j 次的赠送中 第 x 位勇者将自己一半的宝石（需向下取整）赠送给第 y 位勇者。

在完成所有的赠送后，请找到拥有最多宝石的勇者和拥有最少宝石的勇者，并返回他们二者的宝石数量之差。

注意：

• 赠送将按顺序逐步进行。

示例 1：

输入：gem = [3,1,2], operations = [[0,2],[2,1],[2,0]]

输出：2

解释： 第 1 次操作，勇者 0 将一半的宝石赠送给勇者 2， gem = [2,1,3] 第 2 次操作，勇者 2 将一半的宝石赠送给勇者 1， gem = [2,2,2] 第 3 次操作，勇者 2 将一半的宝石赠送给勇者 0， gem = [3,2,1] 返回 3 - 1 = 2

示例 2：

输入：gem = [100,0,50,100], operations = [[0,2],[0,1],[3,0],[3,0]]

输出：75

解释： 第 1 次操作，勇者 0 将一半的宝石赠送给勇者 2， gem = [50,0,100,100] 第 2 次操作，勇者 0 将一半的宝石赠送给勇者 1， gem = [25,25,100,100] 第 3 次操作，勇者 3 将一半的宝石赠送给勇者 0， gem = [75,25,100,50] 第 4 次操作，勇者 3 将一半的宝石赠送给勇者 0， gem = [100,25,100,25] 返回 100 - 25 = 75

示例 3：

输入：gem = [0,0,0,0], operations = [[1,2],[3,1],[1,2]]

输出：0

提示：

• 2 <= gem.length <= 10^3
• 0 <= gem[i] <= 10^3
• 0 <= operations.length <= 10^4
• operations[i].length == 2
• 0 <= operations[i][0], operations[i][1] < gem.length

---

我的答案

class Solution {
public:
    int giveGem(vector<int>& gem, vector<vector<int>>& operations) {
        for (auto & op : operations)
        {
            int tmp = gem[op[0]] / 2;
            gem[op[0]] -= tmp;
            gem[op[1]] += tmp;
        }
        int max = 0, min = 1000;
        for (auto & it : gem)
        {
            max = it > max ? it : max;
            min = it < min ? it : min;
        }
        return max - min;
    }
};

---

参考答案

class Solution {
public:
    int giveGem(vector<int>& gem, vector<vector<int>>& operations) {
        for (auto &operation : operations) {
            int x = operation[0], y = operation[1];
            int number = gem[x] / 2;
            gem[x] -= number;
            gem[y] += number;
        }
        int mn = *min_element(gem.begin(), gem.end());
        int mx = *max_element(gem.begin(), gem.end());
        return mx - mn;
    }
};

---

感想

自然且简单

213. 打家劫舍 II(medium)

2023/9/17

00 : 25 : 01

---

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

---

我的答案

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n < 4)
        {
            return *max_element(nums.begin(), nums.end());
        }
        vector<int> Inc(n, 0); // include 1
        vector<int> nInc(n, 0); // not include 1
        Inc[0] = nums[0]; nInc[0] = 0;
        Inc[1] = 0; nInc[1] = nums[1];
        Inc[2] = nums[0] + nums[2]; nInc[2] = nums[2];
        int res = Inc[2];
        for (int i = 3; i < n-1; ++i)
        {
            Inc[i] = max(Inc[i-2], Inc[i-3]) + nums[i];
            nInc[i] = max(nInc[i-2], nInc[i-3]) + nums[i];
            res = max(res, max(Inc[i], nInc[i]));
        }
        nInc[n-1] = max(nInc[n-3], nInc[n-4]) + nums[n-1];
        res = max(res, nInc[n-1]);
        return res;
    }
};

---

参考答案

class Solution {
    // 198. 打家劫舍
    int rob1(vector<int> &nums, int start, int end) { // [start,end) 左闭右开
        int f0 = 0, f1 = 0;
        for (int i = start; i < end; ++i) {
            int new_f = max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }

public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        return max(nums[0] + rob1(nums, 2, n - 1), rob1(nums, 1, n));
    }
};

---

感想

分成两段来执行打家劫舍1的操作很好

2560. 打家劫舍 IV(medium)

2023/9/19

---

题目描述

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

示例 1：

输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。

示例 2：

输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= (nums.length + 1)/2

---

我的答案

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int lower = *min_element(nums.begin(), nums.end());
        int upper = *max_element(nums.begin(), nums.end());
        while (lower <= upper)
        {
            int mid = (lower + upper) / 2;
            int cnt = 0;
            bool passed = false;
            for (auto & num : nums)
            {
                if (passed)
                {
                    passed = false;
                    continue;
                }
                if (num <= mid)
                {
                    cnt++;
                    passed = true;
                }
            }
            if (cnt < k)
                lower = mid + 1;
            else
                upper = mid - 1;
        }
        return lower;
    }
};

---

参考答案

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int lower = *min_element(nums.begin(), nums.end());
        int upper = *max_element(nums.begin(), nums.end());
        while (lower <= upper) {
            int middle = (lower + upper) / 2;
            int count = 0;
            bool visited = false;
            for (int x : nums) {
                if (x <= middle && !visited) {
                    count++;
                    visited = true;
                } else {
                    visited = false;
                }
            }
            if (count >= k) {
                upper = middle - 1;
            } else {
                lower = middle + 1;
            }
        }
        return lower;
    }
};

---

感想

不是dp了, 是二分查找

LCP 06. 拿硬币(easy)

2023/9/20

00 : 01 : 21

---

题目描述

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

输入：[2,3,10]

输出：8

限制：

• 1 <= n <= 4
• 1 <= coins[i] <= 10

---

我的答案

class Solution {
public:
    int minCount(vector<int>& coins) {
        int res = 0;
        for (auto & coin : coins)
        {
            res += (coin + 1) / 2;
        }
        return res;
    }
};

---

参考答案

---

感想

最简单的一题, 小学生都会做

2603. 收集树中金币(hard)

2023/9/21

00 : 29 : 47

---

题目描述

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

• 收集距离当前节点距离为 2 以内的所有金币，或者
• 移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

提示：

• n == coins.length
• 1 <= n <= 3 * 104
• 0 <= coins[i] <= 1
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges 表示一棵合法的树。

---

我的答案

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        int remain = n;
        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);
        for (auto & edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        queue<int> q;
        for (int i = 0; i < n; ++i)
        {
            if (degree[i] == 1 && !coins[i])
            {
                q.push(i);
            }
        }
        while (!q.empty())
        {
            int toDel = q.front();
            degree[toDel]--;
            remain--;
            q.pop();
            for (auto & it : graph[toDel])
            {
                degree[it]--;
                if (degree[it] == 1 && !coins[it])
                {
                    q.push(it);
                }
            }
        }

        for (int _ = 0; _ < 2; ++_)
        {
            for (int i = 0; i < n; ++i)
            {
                if (degree[i] == 1)
                {
                    q.push(i);
                }
            }
            while (!q.empty())
            {
                int toDel = q.front();
                degree[toDel]--;
                remain--;
                q.pop();
                for (auto & it : graph[toDel])
                {
                    degree[it]--;
                }
            }
        }
        return remain <= 1 ? 0 : (remain - 1) * 2;
    }
};

---

参考答案

---

感想

完全没有思路, 三分钟就看答案去了, 感觉确实想不到, 下次再不会继续看题解()

2591. 将钱分给最多的儿童(easy)

2023/9/22

00 : 13 : 31

---

题目描述

给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。

你需要按照如下规则分配：

• 所有的钱都必须被分配。
• 每个儿童至少获得 1 美元。
• 没有人获得 4 美元。

请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美元。如果没有任何分配方案，返回 -1 。

示例 1：

输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。

示例 2：

输入：money = 16, children = 2
输出：2
解释：每个儿童都可以获得 8 美元。

提示：

• 1 <= money <= 200
• 2 <= children <= 30

---

我的答案

class Solution {
public:
    int distMoney(int money, int children) {
        money -= children;
        if (money < 0)  return -1;
        int ans = money / 7;
        if (ans > children)
        {
            return children - 1;
        }
        else if (ans == children  && money % 7 > 0)
        {
            ans--;
        }
        else if (ans == children - 1 && money % 7 == 3)
        {
            ans--;
        }
        return ans;

    }
};

---

参考答案

class Solution {
public:
    int distMoney(int money, int children) {
        if (money < children) {
            return -1;
        }
        money -= children;
        int cnt = min(money / 7, children);
        money -= cnt * 7;
        children -= cnt;
        if ((children == 0 && money > 0) || (children == 1 && money == 3)) {
            cnt--;
        }
        return cnt;
    }
};

---

感想

贪心, 但是感觉更像是