- A+
所属分类：.NET技术
哈哈，今天整活上瘾了. 复习了一下最近两场周赛感觉能做出来但是实际没有做出来的题目 感觉有几点不足，希望以后可以逐渐改过来： 1. 基础知识不扎实，有时候会在细节上栽跟头 2. 有时候容易脑子一热，想到一部分就开始写，简单题还能处理，中等或困难就有点难搞了，太局部，不全面 3. 心态还是需要调整一下，不能提交没过就心里有点紧张~~ 希望今年内可以AK一次吧，哈哈，加油，废话不多，上题目。
199期 第三题 给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二狗把做题的一些感想和思路也写在注释里了，所以就直接上代码吧： ` using CSharpLeetCode.Common;
namespace CSharpLeetCode.Core { /* 这道题是199次周赛的第三题,笔者当时没有做出来 记录一下 当时印象深刻的错误是如何去重。 考虑到需要递归的计算左右子树的好节点对，但当时禁锢于细节，陷入了去重影响当前逻辑，不去重结果必然错误的窘境.
官方题解在这方面处理的方法值得思考。每次计算到可以作为子数根的结点P时，判断结点对是否满足条件的时候，人为增加了一个条件： 两个结点必须分别在P的左右子数中，这样其实就会避免我上面遇到的问题. 并且在这种情况下,好节点对之间的举例就等于A到Left的距离 + B到Right的距离 + 2. */ public class CountPairs_1530 { public int CountPairs(TreeNode root, int distance) { var pair = DFS(root, distance); return pair.count; } private Pair DFS(TreeNode root, int distance) { int[] depth = new int[distance + 1]; bool isLeaf = root.left == null && root.right == null; //这个结点是叶子结点，因此depth[0] = 1, 且它没有子树，因此count = 0 if (isLeaf) { depth[0] = 1; return new Pair(depth, 0); } int[] leftDepth = new int[distance + 1]; int[] rightDepth = new int[distance + 1]; int leftCount = 0; int rightCount = 0; //分别计算左右子树 if (root.left != null) { var pair = DFS(root.left, distance); leftDepth = pair.depth; leftCount = pair.count; } if (root.right != null) { var pair = DFS(root.right, distance); rightDepth = pair.depth; rightCount = pair.count; } //注意这里结合depth的定义，这里计算的时当前结点为根的子树的 到当前结点长度为n的 叶子结点的个数 //如果这个结点有子树，它一定不是叶子结点，也就没有必要计算 i = 0的情况，此外，还要额外加上1 为P的子树到p的距离. for (int i = 0; i < distance; i++) { depth[i + 1] += leftDepth[i]; depth[i + 1] += rightDepth[i]; } int count = 0; //排列组合，注意这里计算的都是当前结点为根的子树中的好结点对数，且一定是一个是在左子树，一个在右子树. for (int i = 0; i <= distance; i++) { for (int j = 0; j + i + 2 <= distance; j++) { count += leftDepth[i] * rightDepth[j]; } } //注意这里的count + leftCount + rightCount //其中count是P的好结点对个数，leftCount是P的左子树的对个数，rightCount类似. return new Pair(depth, count + leftCount + rightCount); } #region 没完成的Code //下面注释掉的是参赛时的代码： /* Dictionary<List<TreeNode>, int> dic = new Dictionary<List<TreeNode>, int>(); public int CountPairs(TreeNode root, int distance) { if (distance <= 1) return 0; return GetResult(root, distance); } public int GetResult(TreeNode root, int height) { if (root == null) return 0; int result = 0; var left = new List<TreeNode>(); var right = new List<TreeNode>(); for (int i = 1; i <= height - 1; i++) { var tempLeft = GetLeaf(root.left, i).Except(left).ToList(); var tempRight = GetLeaf(root.right, height - i).Except(right).ToList(); if (tempLeft.Count != 0 && tempRight.Count != 0) { left.AddRange(tempLeft); right.AddRange(tempRight); result += tempLeft.Count * tempRight.Count; } } if (root.left != null) result += GetResult(root.left, height); if (root.right != null) result += GetResult(root.right, height); return result; } public List<TreeNode> GetLeaf(TreeNode root, int height) { if (height == 0 || root == null) return new List<TreeNode>(); var result = new List<TreeNode>(); if (root.left == null && root.right == null) { result.Add(root); return result; } if (root.left != null) { result.AddRange(GetLeaf(root.left, height - 1)); } if (root.right != null) { result.AddRange(GetLeaf(root.right, height - 1)); } return result; } */ #endregion } /// <summary> /// 注意这个类 用于描述某个子数的根结点的相关信息 /// depth[i] 代表叶子结点到当前子树结点P的距离为i的叶子节点个数。例如 depth[2] = 1 代表到P的距离为2的叶子结点的个数为1 /// count 代表以当前结点P为根的树中，好结点的对数 /// </summary> public class Pair { public int[] depth; public int count; public Pair(int[] depth, int count) { this.depth = depth; this.count = count; } } } `
200期 第三题 5477. 排布二进制网格的最少交换次数 给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。
请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。
主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。
提示：
n == grid.length n == grid[i].length 1 ⇐ n ⇐ 200 grid[i][j] 要么是 0 要么是 1 。
链接： https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid/
一样，上代码： ` namespace CSharpLeetCode.Core { /* 这是第200次周赛的第三题 */ public class MinSwaps_5477 { public int MinSwaps(int[][] grid) { // 规模 int n = grid.Length; var array = new int[n]; //记录每行 从后向前连续的0的个数
for (int i = 0; i < n; i++) { int count = 0; for (int j = n - 1; j >= 0; j--) { if (grid[i][j] == 0) { count++; } else { break; } } array[i] = count; } //记录一下交换顺序 int result = 0; for (int i = 0; i < n - 1; i++) { //不需要交换的情况,这里很容易发现，每行需要的从后向前连续的0的个数是依次递减的.所以即使超过了 n - i - 1 也没关系的 if (array[i] >= n - i - 1) { continue; } else //需要交换的情况 { int j = i; for (j = i; j < n; j++) { //找到了！ if (array[j] >= n - i - 1) break; } //找不到满足条件的结果了，直接判断不能完成，返回-1 if (j == n) return -1; for (; j > i; j--) { //经典冒泡向上浮动，哈哈 var temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; //别忘了计算操作的次数 result++; } } } return result; } } #region 比赛版本 /* 先贴一个没有完成的版本吧。感觉还是没有适应比赛的状态，和某位大佬的思路开头几乎一毛一样。 可惜后来为啥想不开要去套个冒泡排序，哈哈哈 public class Solution { public int MinSwaps(int[][] grid) { int n = grid.Length; var dict = new Dictionary<int, List<List<int>>>(); var dict2 = new int[n]; for (int i = 0; i < n; i++) { int count = 0; for (int j = n - 1; j >= 0; j--) { if (grid[i][j] == 0) { count++; } else { dict2[i] = count; if (dict.ContainsKey(count)) { dict[count].Add(grid[i].ToList()); } else { var temp = new List<List<int>>(); temp.Add(grid[i].ToList()); dict.Add(count, temp); } } } } int remind = 0; for (int i = n - 1; i >= 1; i--) { if (!dict.ContainsKey(i) && remind <= 0) { return -1; } else if (dict.ContainsKey(i)) { remind += dict[i].Count() - 1; } else if (!dict.ContainsKey(i) && remind > 0) { remind--; } } int result = 0; for (int i = 0; i < n - 1; i ++) { for (int j = i + 1; j < n; j++) { if (dict2[i] < dict2[j]) { var zzz = dict2[i]; dict2[i] = dict2[j]; dict2[j] = zzz; result++; } } } return result; } } */ #endregion } `
