力扣 || 第 254 场周赛题解 || LeetCode

本文主要是介绍力扣 || 第 254 场周赛题解 || LeetCode，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作为子字符串出现在单词中的字符串数目

题意：

就是找一个字符串是不是在另外一个字符串中出现过。

思路：

由于数据规模很小， 所以直接暴力就可以了。有函数可以用函数。

暴力匹配：

bool check(string s, string t) {for (int i = 0; i < t.length(); ++i){bool vis = 0;for (int j = 0; j < s.length(); ++j)if (i+j >= t.length() || s[j] != t[i+j]) vis = 1;if (vis == 0) return true;}return false;
}class Solution {
public:int numOfStrings(vector<string>& patterns, string word) {int ans = 0;for (auto it : patterns) {if (check(it, word)) ans ++;}return ans;}
};

调C++的 函数，String 有一个find()函数，找到返回下标，否则返回 string::npos，
返回值可以强转int类型。

class Solution {
public:int numOfStrings(vector<string>& patterns, string word) {int ans = 0;for (auto it : patterns){if (word.find(it) < word.size()) ans++;}return ans;}
};

构造元素不等于两相邻元素平均值的数组

题意：

给定一个数组，重新排列，使得数组中的每个元素都 不等于 其两侧相邻元素的 平均值 。
保证数组中的所有数都不一样。

思路：

如果满足题目要求，必然连续的三个数是递增的，或者递减的。
所以我们只需要打破三个连续的数字就可以了。
首先对数组进行排序， 然后构造一个新数组，
新数组的值为：最小值、最大值、次小值、次大值、第三小值、第三大值、以此类推。。。

class Solution {
public:vector<int> rearrangeArray(vector<int>& nums) {sort(nums.begin(), nums.end());vector<int>ans;int len = nums.size();for (int i = 0; i < nums.size(); ++i){ans.push_back(nums[i]);if (ans.size() == len) break;ans.push_back(nums[len-i-1]);if (ans.size() == len) break;}return ans;}
};

数组元素的最小非零乘积

题意：

数组包含范围 [1, $2^p$ - 1] 内所有整数的二进制形式,可以选择两个数，然后对调这两个数二进制形式某一数位上的数，对调的必须是同一个数位。
所以要怎么调整，才能使得数组内所有数的乘积最小。（结果不能为0）

思路：

PS：不会证明，只是把我的想法写了出来。

$2^p-1$ 这个数的二进制形式全是1， 把这个数去掉，剩下的所有数二进制形式中，0 和1的个数一样多，所以可以组成一半 $2^p-1$ 和一半 $0$. 由于不能有0，所以把0变成1，
也就变成了一半的 $2^p-2$ 和一半 $1$
最终分别有 $(2^p-1)/2$ 个 $2^p-2$ 和 0. 还有一个 $2^p-1$
过程中需要用到快速幂，还有取模。

long long mod = 1000000007;long long pow(long long a, long long p) {long long c = 1;a %= mod;while(p) {if (p & 1) c = (c * a) % mod;a = (a * a) % mod;p >>= 1;}return c;
}
class Solution {
public:int minNonZeroProduct(int p) {long long mx = (1ll << p) - 1;long long ans = 1;ans =  pow(mx - 1, mx / 2);mx %= mod;return (ans * mx) % mod;}
};

你能穿过矩阵的最后一天

题意：

有一个 n * m 的格子，每天都有一个格子变成水坑，变成水坑就不能走了，
想知道最晚到多少天，还可以从第一行走到最后一行，只能走不是水坑的格子。

思路：

要想走不到最后一行，那一定是水坑横着连起来了，把地图一分为二。所以我们就判断什么时候水坑可以横着连起来。
使用并查集：
把每个格子看成一个点，另外建一个源点，一个汇点。源点为最左面的点，如果一个格子在第一列，就和源点连起来。汇点为最右面的点，如果一个格子在最后一列，就和汇点连起来。
处理每一个格子的时候，判断周围八个格子是不是有水坑，如果有要连起来。
如果源点和汇点在同一个并查集里面的，那必然是走不到最后一行了，就可以数出答案了。

const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int f[90000];
int find(int k) {if (f[k] == k) return k;return f[k] = find(f[k]);
}
void uni(int x, int y) {int fx,fy;fx = find(x); fy = find(y);if (fx != fy) f[fx] = fy;
}class Solution {
public:int latestDayToCross(int row, int col, vector<vector<int>>& cells) {int tot = row * col + 100,begin = col*row+2, end = begin + 1;bool mp[row+10][col+10];memset(mp, 0, sizeof mp);for (int i = 0; i < tot; ++i) f[i] = i;int ans = 0;for (auto it : cells) {int X,Y,pos,x,y;X = it[0]; Y = it[1];mp[X][Y] = 1;pos = (X-1)*col + Y;if (Y == 1) uni(begin, pos);if (Y == col) uni(end, pos);for (int i = 0; i < 8; ++i) {x = X + dx[i]; y = Y + dy[i];if (x < 1 || x > row || y < 1 || y > col) continue;if (mp[x][y]) {uni(pos, (x-1)*col + y);}}if (find(begin) == find(end)) return ans;ans++;}return 0;}
};

这篇关于力扣 || 第 254 场周赛题解 || LeetCode的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---