欢迎光临
我的个人博客网站

LeetCode刷题 — 部分周赛题

  哈哈,今天整活上瘾了.   复习了一下最近两场周赛感觉能做出来但是实际没有做出来的题目   感觉有几点不足,希望以后可以逐渐改过来:   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 

} `

赞(0) 打赏
未经允许不得转载:张拓的天空 » LeetCode刷题 — 部分周赛题
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏