教育云平台网站建设,网站建设有哪些方面,安卓上架app要多少钱,抖音服务商文章目录 1、找出转圈游戏输家1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、相邻值的按位异或2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、 矩阵中移动的最大次数3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 4、 统计完全连通分量的数量4.1 题目链接… 文章目录 1、找出转圈游戏输家1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、相邻值的按位异或2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、 矩阵中移动的最大次数3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 4、 统计完全连通分量的数量4.1 题目链接4.2 题目描述4.3 解题代码4.4 解题思路 打鸡血 1、找出转圈游戏输家
1.1 题目链接
点击跳转到题目位置
1.2 题目描述
n 个朋友在玩游戏。这些朋友坐成一个圈按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i 1) 个朋友的位置1 i n而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。
游戏规则如下
第 1 个朋友接球。
接着第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。 然后接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。 接着接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友以此类推。 换句话说在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。
当某个朋友第 2 次接到球时游戏结束。
在整场游戏中没有接到过球的朋友是 输家 。
给你参与游戏的朋友数量 n 和一个整数 k 请按升序排列返回包含所有输家编号的数组 answer 作为答案。
1.3 解题代码
class Solution {unordered_mapint, int hash;
public:vectorint circularGameLosers(int n, int k) {int i 0;int m 1;while(hash[i] 0){hash[i] 1;i (i m * k) % n; m;}vectorint res;for(int i 0; i n; i){if(hash[i] 0){res.push_back(i1);}}return res;}
};1.4 解题思路
(1) 模拟题首先我们要弄懂模拟规则用一个参数m来表示传到第几次了。然后下标i从0开始不是题目中从1开始其目的就是为了方便进行模运算。
(2) 每次下标变换到的位置是i m * k % n。
(3) 然后用哈希表来记录谁被传到球了如果传了两次则跳出传球过程模拟。
(4) 最后遍历如果哈希表中记录没有传到球则压入结果数组当中。
2、相邻值的按位异或
2.1 题目链接
点击跳转到题目位置
2.2 题目描述
下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或⊕派生而来。
特别地对于范围 [0, n - 1] 内的每个下标 i
如果 i n - 1 那么 derived[i] original[i] ⊕ original[0] 否则 derived[i] original[i] ⊕ original[i 1] 给你一个数组 derived 请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。
如果存在满足要求的原始二进制数组返回 true 否则返回 false 。
二进制数组是仅由 0 和 1 组成的数组。
2.3 解题代码
class Solution {
public:bool doesValidArrayExist(vectorint derived) {int n derived.size();vectorint copy1(n);vectorint copy2(n);copy1[0] 1;for(int i 1; i n; i){copy1[i] (copy1[i-1]^derived[i-1]);}if(derived[n-1] (copy1[n-1] ^ copy1[0])){return true;}copy2[0] 0;for(int i 1; i n; i){copy2[i] (copy2[i-1]^derived[i-1]);}if(derived[n-1] (copy2[n-1] ^ copy2[0])){return true;}return false;}
};2.4 解题思路
(1) 这道题目的核心就在于倒推给结果能否知晓是由什么数组生成而来的。
(2) 根据规则我们假设生成数组第一个元素分别为0和1可以倒推生成数组判断生成得到的数组能否满足题目要求这里用derived[n-1]来判断因为这个数字与生成数组的第一个元素也有关系。
(3) 如果无论生成数组第一个元素是0还是1都不能得到最终的数组那么就可以下判断不可能派生得到derived数组。
3、 矩阵中移动的最大次数
3.1 题目链接
点击跳转到题目位置
3.2 题目描述
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid 矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一 单元格出发按以下方式遍历 grid
从单元格 (row, col) 可以移动到 (row - 1, col 1)、(row, col 1) 和 (row 1, col 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。 返回你在矩阵中能够 移动 的 最大 次数。
3.3 解题代码
class Solution {
public:int maxMoves(vectorvectorint grid) {int m grid.size();int n grid[0].size();int dp[m][n];memset(dp, 0, sizeof(dp));for(int j n-2; j 0; --j){for(int i 0; i m; i){int row i;if(row - 1 0){if(grid[row - 1][j 1] grid[i][j]){dp[i][j] max(dp[i][j], dp[row - 1][j 1] 1);}}if(grid[i][j1] grid[i][j]){dp[i][j] max(dp[i][j], dp[i][j1] 1);}if(row 1 m){if(grid[row 1][j 1] grid[i][j]){dp[i][j] max(dp[i][j], dp[row 1][j 1] 1);}}}}int max0 0;for(int i 0; i m; i){max0 max(max0, dp[i][0]);}return max0;}
};3.4 解题思路
(1) 根据题目所描述的这道题目的关键在于最终要求的是第一列元素所能移动的最大值。
(2) 我们又可以得出移动的方向永远是向着下一列这代表着我们同一列的每一个元素的所在的位置的最大值只与后面一列的元素有关即考虑使用动态规划来解决问题。
(3) 最终找出第一列的最大值即可。
4、 统计完全连通分量的数量
4.1 题目链接
点击跳转到题目位置
4.2 题目描述
给你一个整数 n 。现有一个包含 n 个顶点的 无向 图顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。
返回图中 完全连通分量 的数量。
如果在子图中任意两个顶点之间都存在路径并且子图中没有任何一个顶点与子图外部的顶点共享边则称其为 连通分量 。
如果连通分量中每对节点之间都存在一条边则称其为 完全连通分量 。
4.3 解题代码
class Solution {int Find(vectorint pre, int index){while(pre[index] ! index){index pre[index];}return index;}void Join(vectorint pre, int index1, int index2){index1 Find(pre, index1);index2 Find(pre, index2);if(index1 ! index2){pre[index1] index2;}}unordered_mapint, int hash;unordered_mapint, int point;
public:int countCompleteComponents(int n, vectorvectorint edges) {int m edges.size();vectorint pre(100);for(int i 0; i n; i){pre[i] i;}for(int i 0; i m; i){int x edges[i][0]; int y edges[i][1];Join(pre, x, y);}for(int i 0; i m; i){int x edges[i][0];hash[Find(pre, x)];}for(int i 0; i n; i){point[Find(pre, i)];}int res 0;for(int i 0; i n; i){if(i pre[i]){if(hash[i] (point[i] * (point[i] - 1)) / 2){res;}}}return res;}
};4.4 解题思路
(1) 这道题目是问有多少个完全通量那么我们首先要知道有多少个子图。那么我们可以用并查集来统计有多少个子图。
(2) 我们将并查集中统领子图中的所有节点的节点所连接的边和所拥有的点的数量统计出来。
(3) 遍历所有子图已知点的数量n已知边的数量m如果m 等于(n * n-1) / 2那么完全通量1即可。
打鸡血
心若在梦就在只不过是从头再来。哪怕每次周赛一题都做不出来都得努力去研究因为未来的某一天一定能够进步的。
