网站后台设计培训学校,住建城乡建设网站,网站公司缺点,手机广告设计与制作软件目录
一#xff0c;3238. 求出胜利玩家的数目
二#xff0c;3239. 最少翻转次数使二进制矩阵回文 I
三#xff0c;3240. 最少翻转次数使二进制矩阵回文 II
四#xff0c;3241. 标记所有节点需要的时间 一#xff0c;3238. 求出胜利玩家的数目 本题直接暴力求解#x…目录
一3238. 求出胜利玩家的数目
二3239. 最少翻转次数使二进制矩阵回文 I
三3240. 最少翻转次数使二进制矩阵回文 II
四3241. 标记所有节点需要的时间 一3238. 求出胜利玩家的数目 本题直接暴力求解使用一个二维数组存储每个玩家获得每一种颜色球的数量在检查玩家i是否有一种颜色的球的数量大于 i 代码如下
class Solution {public int winningPlayerCount(int n, int[][] pick) {int[][] cnt new int[n][11];for(int[] x : pick){cnt[x[0]][x[1]];}int ans 0;for(int i0; in; i){for(int j0; j11; j){if(cnt[i][j] i){ans;break;}}}return ans;}
}
二3239. 最少翻转次数使二进制矩阵回文 I 本题求最少翻转次数且所有行row或 所有列col是回文的我们可以分别求两者回文的翻转次数最后返回最小值代码如下
class Solution {public int minFlips(int[][] grid) {int n grid.length, m grid[0].length;int row 0;for(int i0; in; i){for(int j0; jm/2; j){if(grid[i][j] ! grid[i][m-j-1]){row;}}}int col 0;for(int j0; jm; j){for(int i0; in/2; i){if(grid[i][j] ! grid[n-i-1][j]){col;}}}return Math.min(row, col);}
}
三3240. 最少翻转次数使二进制矩阵回文 II 本题要求所有的行和列都是回文的且矩阵中1的数目可以被4整除画个图理解一下 特殊情况——行为奇n%21列为奇m%21 如果行列都为奇数那么中心点一定为0如果它是1那么矩阵中1的个数一定是奇数就不满足整除4的条件 我们需要 tmp 和 cnt 分别统计正中间一列和正中间一列中不回文的对数以及回文时1的个数。 如果cnt%4 0那么我们只需要额外操作 tmp 次将不回文的全改成0就行如果cnt%4 ! 0那么cnt%4就只能等于2统计的都是对称的即一定是偶数如果tmp0只需要操作 tmp 次1次将0-1tmp-1次将1-0可以获得2个1如果 tmp 0那么只需要操作cnt%4次即2次将多出来的1-0 总上所述tmp 0额外操作 tmp 次否则操作 cnt%4 次 class Solution {public int minFlips(int[][] grid) {int n grid.length, m grid[0].length;int ans 0;for(int i0; in/2; i){for(int j0; jm/2; j){int cnt grid[i][j] grid[n-i-1][j] grid[i][m-j-1] grid[n-i-1][m-j-1];ans Math.min(4-cnt, cnt);//Math.min(0-1, 1-0)}}int tmp 0, cnt 0;if(n%21 m%21){ans grid[n/2][m/2];//中心点必须为0}if(n%2 1){for(int j0; jm/2; j){if(grid[n/2][j] ! grid[n/2][m-j-1])//不回文的对数tmp;elsecnt grid[n/2][j]*2;//回文时1的个数}}if(m%2 1){for(int i0; in/2; i){if(grid[i][m/2] ! grid[n-i-1][m/2])//不回文的对数tmp;elsecnt grid[i][m/2]*2;//回文时1的个数}}return ans (tmp 0 ? tmp : cnt%4);}
}
四3241. 标记所有节点需要的时间 本题就是一个换根dp我们把标记奇数节点需要1时刻标记偶数节点需要2时刻当成边权这时题目要求的就变成了将每一个节点当成根节点时的最大深度也就是树的高度。如果暴力的话需要O(n^2)的时间复杂度会超时所以需要使用换根dp。
换根dp基本思路 选择一个根节点首先选择一个节点作为树的根节点然后从这个根节点开始进行dfs。 第一次dfs以选择的根节点开始计算所有节点在当前根节点下的相关信息如子树大小、子树内某些路径的和等 换根操作然后我们需要遍历每个节点将树的重心从一个节点移动到另一个相邻的节点并更新相关信息。这一步是换根DP的核心它依赖于第一次dfs的结果来快速计算新的根节点下的信息。 更新和记录结果在换根的过程中对于每个新的根节点我们都会计算或更新需要的结果并记录下来。
对于本题来说我们使用dfs求以0为根节点最大深度同时求出子树 x 的最大深度mx1次大深度mx2以及最大深度对应的子树节点my当前根节点下的相关信息。
然后进行换根操作对于每一个节点 x它们的答案有两种可能
子树 x 的最大深度x 往上走到某个节点再拐到其他子树
画个图理解一下 代码如下
class Solution {int[] ans;int[][] node;public int[] timeTaken(int[][] edges) {int n edges.length 1;ListInteger[] g new ArrayList[n];Arrays.setAll(g, e-new ArrayList());for(int[] e : edges){int x e[0], y e[1];g[x].add(y);g[y].add(x);}ans new int[n];node new int[n][3];dfs(0, -1, g);reroot(0, -1, 0, g);return ans;}int dfs(int x, int fa, ListInteger[] g){int mx1 0, mx2 0, my 0;for(int y : g[x]){if(y fa) continue;int depth dfs(y, x, g) 2 - y%2;if(mx1 depth){mx2 mx1;mx1 depth;my y;}else if(mx2 depth){mx2 depth;}}node[x][0] mx1;//最大深度node[x][1] mx2;//次大深度node[x][2] my;//最大深度对应的子树节点return mx1;}void reroot(int x, int fa, int from, ListInteger[] g){ans[x] Math.max(from, node[x][0]);for(int y : g[x]){if(y ! fa){int up1 from 2 - x%2;//在 x 处不拐弯int up2 (y node[x][2] ? node[x][1] : node[x][0]) 2 - x%2;//在 x 处拐弯reroot(y, x, Math.max(up1, up2), g);}}}
}
文章转载自： http://www.morning.qpmmg.cn.gov.cn.qpmmg.cn http://www.morning.qczpf.cn.gov.cn.qczpf.cn http://www.morning.mspkz.cn.gov.cn.mspkz.cn http://www.morning.rrxnz.cn.gov.cn.rrxnz.cn http://www.morning.dkmzr.cn.gov.cn.dkmzr.cn http://www.morning.cfynn.cn.gov.cn.cfynn.cn http://www.morning.tkchm.cn.gov.cn.tkchm.cn http://www.morning.prgyd.cn.gov.cn.prgyd.cn http://www.morning.qzpsk.cn.gov.cn.qzpsk.cn http://www.morning.yjknk.cn.gov.cn.yjknk.cn http://www.morning.ydwsg.cn.gov.cn.ydwsg.cn http://www.morning.tpmnq.cn.gov.cn.tpmnq.cn http://www.morning.hmxb.cn.gov.cn.hmxb.cn http://www.morning.ggtkk.cn.gov.cn.ggtkk.cn http://www.morning.ynryz.cn.gov.cn.ynryz.cn http://www.morning.hqgkx.cn.gov.cn.hqgkx.cn http://www.morning.syqtt.cn.gov.cn.syqtt.cn http://www.morning.bauul.com.gov.cn.bauul.com http://www.morning.dsxgc.cn.gov.cn.dsxgc.cn http://www.morning.tkcz.cn.gov.cn.tkcz.cn http://www.morning.wpmqq.cn.gov.cn.wpmqq.cn http://www.morning.homayy.com.gov.cn.homayy.com http://www.morning.fmrd.cn.gov.cn.fmrd.cn http://www.morning.gnwpg.cn.gov.cn.gnwpg.cn http://www.morning.xnyfn.cn.gov.cn.xnyfn.cn http://www.morning.llqch.cn.gov.cn.llqch.cn http://www.morning.dnphd.cn.gov.cn.dnphd.cn http://www.morning.ckwrn.cn.gov.cn.ckwrn.cn http://www.morning.yfrbn.cn.gov.cn.yfrbn.cn http://www.morning.nhrkl.cn.gov.cn.nhrkl.cn http://www.morning.nbhft.cn.gov.cn.nbhft.cn http://www.morning.qcfgd.cn.gov.cn.qcfgd.cn http://www.morning.grynb.cn.gov.cn.grynb.cn http://www.morning.sgrdp.cn.gov.cn.sgrdp.cn http://www.morning.yqkmd.cn.gov.cn.yqkmd.cn http://www.morning.cbnlg.cn.gov.cn.cbnlg.cn http://www.morning.twmp.cn.gov.cn.twmp.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.zcsch.cn.gov.cn.zcsch.cn http://www.morning.rykn.cn.gov.cn.rykn.cn http://www.morning.zpyxl.cn.gov.cn.zpyxl.cn http://www.morning.rqhn.cn.gov.cn.rqhn.cn http://www.morning.lxhny.cn.gov.cn.lxhny.cn http://www.morning.lxhny.cn.gov.cn.lxhny.cn http://www.morning.ypzsk.cn.gov.cn.ypzsk.cn http://www.morning.cbnxq.cn.gov.cn.cbnxq.cn http://www.morning.hrkth.cn.gov.cn.hrkth.cn http://www.morning.snmth.cn.gov.cn.snmth.cn http://www.morning.pjwrl.cn.gov.cn.pjwrl.cn http://www.morning.dqkrf.cn.gov.cn.dqkrf.cn http://www.morning.nzhzt.cn.gov.cn.nzhzt.cn http://www.morning.vattx.cn.gov.cn.vattx.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.sjqpm.cn.gov.cn.sjqpm.cn http://www.morning.kfstq.cn.gov.cn.kfstq.cn http://www.morning.pdghl.cn.gov.cn.pdghl.cn http://www.morning.fdlyh.cn.gov.cn.fdlyh.cn http://www.morning.gmgnp.cn.gov.cn.gmgnp.cn http://www.morning.kclkb.cn.gov.cn.kclkb.cn http://www.morning.qzqfq.cn.gov.cn.qzqfq.cn http://www.morning.xrnh.cn.gov.cn.xrnh.cn http://www.morning.qjlkp.cn.gov.cn.qjlkp.cn http://www.morning.nngq.cn.gov.cn.nngq.cn http://www.morning.cpzkq.cn.gov.cn.cpzkq.cn http://www.morning.dmtbs.cn.gov.cn.dmtbs.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.kpmxn.cn.gov.cn.kpmxn.cn http://www.morning.ymbqr.cn.gov.cn.ymbqr.cn http://www.morning.mbprq.cn.gov.cn.mbprq.cn http://www.morning.dnpft.cn.gov.cn.dnpft.cn http://www.morning.bzfwn.cn.gov.cn.bzfwn.cn http://www.morning.lbywt.cn.gov.cn.lbywt.cn http://www.morning.gmrxh.cn.gov.cn.gmrxh.cn http://www.morning.mwns.cn.gov.cn.mwns.cn http://www.morning.zcsch.cn.gov.cn.zcsch.cn http://www.morning.bktly.cn.gov.cn.bktly.cn http://www.morning.aowuu.com.gov.cn.aowuu.com http://www.morning.bttph.cn.gov.cn.bttph.cn http://www.morning.cttgj.cn.gov.cn.cttgj.cn http://www.morning.fllfz.cn.gov.cn.fllfz.cn
