leetcode解题思路分析（一百四十五）1254 - 1266 题

1254. 统计封闭岛屿的数目
      二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。请返回 封闭岛屿 的数目。

BFS或者DFS解题均可。

class Solution {
public:static constexpr int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int closedIsland(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int ans = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {queue<pair<int,int>> qu;grid[i][j] = 1;bool closed = true;qu.push(make_pair(i, j));while (!qu.empty()) {auto [cx, cy] = qu.front();qu.pop();if (cx == 0 || cy == 0 || cx == m - 1 || cy == n - 1) {closed = false;}for (int i = 0; i < 4; i++) {int nx = cx + dir[i][0];int ny = cy + dir[i][1];if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {grid[nx][ny] = 1;qu.emplace(nx, ny);}}}if (closed) {ans++;}}}}return ans;}
};

1255. 得分最高的单词集合
      你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

状态压缩枚举单词，然后取计数最大的。

class Solution {
public:int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {int n = words.size(), res = 0;vector<int> count(26);for (auto c : letters) {count[c - 'a']++;}for (int s = 1; s < (1 << n); s++) {vector<int> wordCount(26); // 统计子集 s 所有单词的字母数目for (int k = 0; k < n; k++) {if ((s & (1 << k)) == 0) { // words[k] 不在子集 s 中continue;}for (auto c : words[k]) {wordCount[c - 'a']++;}}bool ok = true; // 判断子集 s 是否合法int sum = 0; // 保存子集 s 的得分for (int i = 0; i < 26; i++) {sum += score[i] * wordCount[i];ok = ok && (wordCount[i] <= count[i]);}if (ok) {res = max(res, sum);}}return res;}
};

1260. 二维网格迁移
      给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。请你返回 k 次迁移操作后最终得到的 二维网格。

展开为一维然后再重新排列即可。

class Solution {
public:vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {int m = grid.size(), n = grid[0].size();vector<vector<int>> ret(m, vector<int>(n));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int index1 = (i * n + j + k) % (m * n);ret[index1 / n][index1 % n] = grid[i][j];}}return ret;}
};

1261. 在受污染的二叉树中查找元素
      给出一个满足下述规则的二叉树.现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
      请你先还原二叉树，然后实现 FindElements 类

很简单的题，DFS即可。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class FindElements {
private:unordered_set<int> s;void dfs(TreeNode* curr, int val){if (curr != nullptr){curr->val = val;s.insert(val);dfs(curr->left, 2*val + 1);dfs(curr->right, 2*val + 2);}}
public:FindElements(TreeNode* root) {dfs(root, 0);}bool find(int target) {return s.find(target) != s.end();}
};/*** Your FindElements object will be instantiated and called as such:* FindElements* obj = new FindElements(root);* bool param_1 = obj->find(target);*/

1262. 可被三整除的最大和
      给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

可以用贪心算法解题：将数组分为Mod为0、1、2的三类，然后0的全取，1和2尽量取最多丢最少最小。也可以用动态规划解题，本题因为涉及到mod，所以动态规划中除了和前一个数i相关，还要和三种状态0/1/2相关。

class Solution {
public:int maxSumDivThree(vector<int>& nums) {vector<int> f = {0, INT_MIN, INT_MIN};for (int num: nums) {vector<int> g = f;for (int i = 0; i < 3; ++i) {g[(i + num % 3) % 3] = max(g[(i + num % 3) % 3], f[i] + num);}f = move(g);}return f[0];}
};

1263. 推箱子
      「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

BFS解题。

class Solution {
public:int minPushBox(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int sx, sy, bx, by; // 玩家、箱子的初始位置for (int x = 0; x < m; x++) {for (int y = 0; y < n; y++) {if (grid[x][y] == 'S') {sx = x;sy = y;} else if (grid[x][y] == 'B') {bx = x;by = y;}}}auto ok = [&](int x, int y) -> bool { // 不越界且不在墙上return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';};vector<int> d = {0, -1, 0, 1, 0};vector<vector<int>> dp(m * n, vector<int>(m * n, INT_MAX));queue<pair<int, int>> q;dp[sx * n + sy][bx * n + by] = 0; // 初始状态的推动次数为 0q.push({sx * n + sy, bx * n + by});while (!q.empty()) {queue<pair<int, int>> q1;while (!q.empty()) {auto [s1, b1] = q.front();q.pop();int sx1 = s1 / n, sy1 = s1 % n, bx1 = b1 / n, by1 = b1 % n;if (grid[bx1][by1] == 'T') { // 箱子已被推到目标处return dp[s1][b1];}for (int i = 0; i < 4; i++) { // 玩家向四个方向移动到另一个状态int sx2 = sx1 + d[i], sy2 = sy1 + d[i + 1], s2 = sx2*n+sy2;if (!ok(sx2, sy2)) { // 玩家位置不合法continue;}if (bx1 == sx2 && by1 == sy2) { // 推动箱子int bx2 = bx1 + d[i], by2 = by1 + d[i + 1], b2 = bx2*n+by2;if (!ok(bx2, by2) || dp[s2][b2] <= dp[s1][b1] + 1) { // 箱子位置不合法 或 状态已访问continue;}dp[s2][b2] = dp[s1][b1] + 1;q1.push({s2, b2});} else {if (dp[s2][b1] <= dp[s1][b1]) { // 状态已访问continue;}dp[s2][b1] = dp[s1][b1];q.push({s2, b1});}}}q.swap(q1);}return -1;}
};

1266. 访问所有点的最小时间
      平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。

对于任意一种情况，从 x 移动到 y 的最少次数为 dx 和 dy 中的较大值 max(dx, dy)，这也被称作 x 和 y 之间的 切比雪夫距离。

class Solution {
public:int minTimeToVisitAllPoints(vector<vector<int>>& points) {int x0 = points[0][0], x1 = points[0][1];int ans = 0;for (int i = 1; i < points.size(); ++i) {int y0 = points[i][0], y1 = points[i][1];ans += max(abs(x0 - y0), abs(x1 - y1));x0 = y0;x1 = y1;}return ans;}
};