当前位置:   article > 正文

力扣每日一题(一)_力扣的每日一题

力扣的每日一题

突发奇想,想要在博客上记录一下做的会的力扣每一日一题,原因是,虽然每天会在小本本上记录一下,但是记得乱没有章法,回头不一定回仔细看,所以还是每周再汇总回顾一下,或许效果会更好。但是其中肯定也有很多我理解不是很透彻的地方,还有一些可能也只是记住了,不知道原因~但是,就学嘛

目录

一、4.29建立四叉树

二、4.30最小差值Ⅰ

三、5.1两颗二叉搜索树中的所有元素

四、5.2检验验证器


一、4.29建立四叉树

题目大意:给定一个n*n矩阵grid,矩阵由若干0和1组成。要求用四叉树表示该矩阵。

说明:四叉树中的每个父节点有四个字节点,每个节点中有两个属性:val->表示该结点的值;isLeaf->判断是否为叶子节点(即没有子节点),若是则为True,否则为False。

构建四叉树步骤:

1、如果当前网格值相同(全为0或1),将isLeaf设为True,将val设为网格相同的值,并将四个子节点都设为Null然后停止。

2、如果当前网格值不同,将isLeaf设为False,将val设为任意值,然后将网格划分为四个子网格(topLeft,topRight,bottomLeft,bottomRight),然后递归每个子网格。

  1. """
  2. # Definition for a QuadTree node.
  3. class Node:
  4. def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
  5. self.val = val
  6. self.isLeaf = isLeaf
  7. self.topLeft = topLeft
  8. self.topRight = topRight
  9. self.bottomLeft = bottomLeft
  10. self.bottomRight = bottomRight
  11. """
  12. class Solution:
  13. def construct(self, grid: List[List[int]]) -> 'Node':
  14. # 定义递归函数,遍历当前网格是否全部相等
  15. def dfs(r0: int, c0: int, r1:int, c1: int)->'Node':
  16. for i in range(r0, r1):
  17. for j in range(c0,c1):
  18. # 若不相等则继续进行遍历,遍历四个网格部分
  19. if grid[i][j] != grid[r0][c0]:
  20. return Node(
  21. True,
  22. False,
  23. dfs(r0, c0, (r0+r1)//2, (c0+c1)//2),
  24. dfs(r0, (c0+c1)//2, (r0+r1)//2, c1),
  25. dfs((r0+r1)//2, c0, r1, (c0+c1)//2),
  26. dfs((r0+r1)//2, (c0+c1)//2, r1, c1),
  27. )
  28. # 所有都相等则返回节点
  29. return Node(grid[r0][c0]==1, True)
  30. return dfs(0, 0, len(grid), len(grid))

二、4.30最小差值Ⅰ

题目大意:给定一个整数数组nums,和一个整数k。可以将nums[i[改为nums[i]+x,x范围为[-k, k]。每个数只能修改一次,求修改后数组nums中最大值和最小值的最小差值。

解析:每个数都能修改,故只需要考虑最大值和最小值的修改即可(因为修改范围是确定的,最其他数修改之后不可能比最大/小值修改后的值更大/小,而且最大/小值变小/大之后,其它的数也可以在最大最小值修改,不会出现说最大值修改后不是这组数据的最大值了;另外,每个数的变化是我们不需要考虑的,我们只是要知道最后的差值,而不需要知道过程,这是我之前所多想的)。那么我们只需要考虑两种情况:①max - min > 2 * k的,这样我们就只需要将最大值-k,最小值+k,就是最后最小的差值结果,即max-min-2*k;②max - min ≤ 2 * k的。那么这个时候,他们的最小差值就为0了!

  1. class Solution:
  2. def smallestRangeI(self, nums: List[int], k: int) -> int:
  3. maxn = max(nums)
  4. minn = min(nums)
  5. if maxn - minn > 2 * k:
  6. return maxn - minn - 2 * k
  7. else:
  8. return 0

三、5.1两颗二叉搜索树中的所有元素

题目大意:给定root1,root2两颗二叉搜索树,返回列表,包含两个树的所有整数并按升序排序。

解析:二叉搜索树的中序遍历是有序的!!!那么直接中序遍历两棵树,得到两个有序数组,再合并两个有序数组就可以了(糟糕的感觉,思想有了,但是,不会写代码。。。)

中序遍历:采用递归进行遍历。

合并两个有序数组-->归并排序:需要一个额外的数组和两个指针,然后对指针遍历两个数组比较大小就可以了。

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. # def __init__(self, val=0, left=None, right=None):
  4. # self.val = val
  5. # self.left = left
  6. # self.right = right
  7. class Solution:
  8. def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
  9. nums1 = []
  10. nums2 = []
  11. self.inOrder(root1, nums1)
  12. self.inOrder(root2, nums2)
  13. return self.merge(nums1, nums2)
  14. def inOrder(self, root, nums):
  15. if not root:
  16. return
  17. # 遍历节点,将节点值放入nums中
  18. self.inOrder(root.left, nums)
  19. nums.append(root.val)
  20. self.inOrder(root.right, nums)
  21. # 归并排序,增加了一个新的数组,两个指针相比较
  22. def merge(self, nums1, nums2):
  23. res = []
  24. p1 = 0
  25. p2 = 0
  26. while p1<len(nums1) and p2<len(nums2):
  27. if nums1[p1] < nums2[p2]:
  28. res.append(nums1[p1])
  29. p1 += 1
  30. else:
  31. res.append(nums2[p2])
  32. p2 += 1
  33. if p1<len(nums1):
  34. res.extend(nums1[p1:])
  35. if p2<len(nums2):
  36. res.extend(nums2[p2:])
  37. return res

四、5.2检验验证器

这个题目太长要求太多了,就不叙述了,就只记录一下正则匹配的一点点相关知识。

. 表示任何字符

* 表示0次或多次

.* 表示任何字符出现0次或多次

.*? 表示非贪婪模式,例如 a.*?b 表示匹配满足a开头b结尾最短的字符串

<[A-Z]{1,9}> 表示大写字母和1-9

</\1>  表示与第一个内容完全匹配

[^<]*  除了<以外的任何字符

果然,一下子写完不是我的风格,坚持不下去,从4月29号到现在5月22号确实不少,虽然中间也有很多是简单的,困难的,但是,写完是我所坚持不下去的,若非要写完,只能是敷衍了事,所以,换个任务,下次继续写,现在就干其他事吧。

最后,既然开始了,就不要停下你的脚步了吧!

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号