菜鸡勇闯第136场双周赛

菜鸡鼓足了勇气报名了力扣双周赛（后来复盘才知道双周赛更难一点，我真是头铁。。）
没想到还拿了个竞赛名次哈哈哈哈哈还在前50%，小力它真的，我哭死
为什么我本科被高数老师忽悠，去打了两年数模o(≧口≦)o
每一天都在想，我要是也接触acm，现在一定不会因为算法头大了吧(▼へ▼メ)

3238. 求出胜利玩家的数目

class Solution {public int winningPlayerCount(int n, int[][] pick) {int count = 0;HashMap<Integer, List<Integer>> map = new HashMap<>();for(int i = 0; i < pick.length; i++) {int player = pick[i][0];int ball = pick[i][1];if(map.containsKey(player)) {map.get(player).add(ball);}else {List<Integer> tmp = new ArrayList<>();tmp.add(ball);map.put(player, tmp);}}for(int key: map.keySet()) {List<Integer> tmplist = map.get(key);HashMap<Integer, Integer> tmpmap = new HashMap<>();for(int i = 0; i < tmplist.size(); i++) {int num = tmplist.get(i);tmpmap.put(num, tmpmap.getOrDefault(num, 0) + 1);}for(int key1: tmpmap.keySet()) {if(tmpmap.get(key1) > key) {count++;break;}}}return count;}
}

3239.最少翻转次数使二进制矩阵回文I

class Solution {public int minFlips(int[][] grid) {int row = grid.length;int col = grid[0].length;int[][] tmp1 = new int[row][col];int[][] tmp2 = new int[row][col];for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {tmp1[i][j] = grid[i][j];tmp2[i][j] = grid[i][j];}}for(int i = 0; i < row; i++) {int left = 0;int right = col - 1;while(left < right) {int tmp = tmp1[i][left];tmp1[i][left] = tmp1[i][right];tmp1[i][right] = tmp;left++;right--;}}for(int j = 0; j < col; j++) {int upper = 0;int lower = row - 1;while(upper < lower) {int tmp = tmp2[upper][j];tmp2[upper][j] = tmp2[lower][j];tmp2[lower][j] = tmp;upper++;lower--;}}int res1 = 0;int res2 = 0;for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if(grid[i][j] != tmp1[i][j]) {res1++;}}}for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if(grid[i][j] != tmp2[i][j]) {res2++;}}}return (res1 >= res2) ? res2/2 : res1/2;}
}

3240.最少翻转次数使二进制矩阵回文II

public int minFlips(int[][] grid) {
// 记录一个dp的题解int m = grid.length, n = grid[0].length;int flips = 0;// 遍历左上角的四分之一矩阵，并与右上角、左下角、右下角的相应位置元素配对，计算每组需要的最小翻转次数for (int i = 0; i < m / 2; i++) {for (int j = 0; j < n / 2; j++) {// sum 代表当前 4 个对称元素的和int sum = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];// 增加使这 4 个元素一致所需的最小flipflips += Math.min(sum, 4 - sum);}}boolean changed = false;  // 用于标记是否已经在处理奇数行或列时进行了1/0 changeint countOne = 0;  // 用于记录当奇数行或列时 1 的数量// 处理矩阵列数为奇数的情况，单独处理中间一列if (n % 2 == 1) {int colIndex = n / 2;for (int i = 0; i < m / 2; i++) {// 如果对称位置的元素不同，flip++, change = trueif (grid[i][colIndex] != grid[m - 1 - i][colIndex]) {flips++;changed = true;} else if (grid[i][colIndex] == 1) {// 如果两个位置的元素相同且为 1，countOne + 2countOne += 2;}}}// 处理矩阵行数为奇数的情况，单独处理中间一行if (m % 2 == 1) {int[] row = grid[m / 2];for (int j = 0; j < n / 2; j++) {// 如果对称位置的元素不同，flip++, change = trueif (row[j] != row[n - 1 - j]) {flips++;changed = true;} else if (row[j] == 1) {// 如果两个位置的元素相同且为 1，countcountOne += 2;}}}// 如果没有进行任何翻转且 countOne % 4 == 2，需要额外的翻转if (!changed && countOne % 4 == 2) {flips += 2;}// 如果矩阵行列都为奇数，需要检查中心元素if (m % 2 == 1 && n % 2 == 1 && grid[m / 2][n / 2] == 1) {flips++;}return flips;
}

3241.标记所有节点需要的时间

class Solution {// 记录一个换根DP的解法int[] head, nxt, to;// first 当前节点最长耗时// firstNo 最长耗时子节点编号// second 当前节点第二大耗时int[] first, firstNo, second;int[] ans;public int[] timeTaken(int[][] edges) {int n = edges.length + 1;head = new int[n];Arrays.fill(head, -1);nxt = new int[n << 1];to = new int[n << 1];for (int i = 0, j = 2; i < n - 1; i++) {int u = edges[i][0], v = edges[i][1];nxt[j] = head[u]; head[u] = j; to[j++] = v;nxt[j] = head[v]; head[v] = j; to[j++] = u;}first = new int[n];firstNo = new int[n];second = new int[n];ans = new int[n];dfs(-1, 0);dp(-1, 0, 0);return ans;}// 换根 DP：维护之前节点到 u 的最长耗时 —— preFirstpublic void dp(int f, int u, int preFirst) {for (int e = head[u], v; e != -1; e = nxt[e]) {v = to[e];if (f != v) {// 如果 v 为 firstNo[u]，表示 v 为最长耗时子节点，取 second[u] 进行比较// 否则，取 first[u] 进行比较// 同时，在得到 v 的所有之前节点到 u 的最长耗时后，该耗时还需要加上 u → v 的耗时// 从而得到 v 之前的所有节点到 v 的最长耗时int pf = Math.max(preFirst, v == firstNo[u] ? second[u] : first[u]) + ((u & 1) == 0 ? 2 : 1);ans[v] = Math.max(ans[v], pf);dp(u, v, pf);}}}public void dfs(int f, int u) {for (int e = head[u], v; e != -1; e = nxt[e]) {v = to[e];if (f != v) {dfs(u, v);// t 表示 u → v 和 v 的所有后继节点的最长耗时int t = first[v] + ((v & 1) == 0 ? 2 : 1);if (first[u] < t) {second[u] = first[u];first[u] = t;firstNo[u] = v;} else if (second[u] < t) {second[u] = t;}}}// 将每个结点答案初始化为当前节点最长耗时ans[u] = first[u];}
}