赞
踩
突发奇想,想要在博客上记录一下做的会的力扣每一日一题,原因是,虽然每天会在小本本上记录一下,但是记得乱没有章法,回头不一定回仔细看,所以还是每周再汇总回顾一下,或许效果会更好。但是其中肯定也有很多我理解不是很透彻的地方,还有一些可能也只是记住了,不知道原因~但是,就学嘛
目录
题目大意:给定一个n*n矩阵grid,矩阵由若干0和1组成。要求用四叉树表示该矩阵。
说明:四叉树中的每个父节点有四个字节点,每个节点中有两个属性:val->表示该结点的值;isLeaf->判断是否为叶子节点(即没有子节点),若是则为True,否则为False。
构建四叉树步骤:
1、如果当前网格值相同(全为0或1),将isLeaf设为True,将val设为网格相同的值,并将四个子节点都设为Null然后停止。
2、如果当前网格值不同,将isLeaf设为False,将val设为任意值,然后将网格划分为四个子网格(topLeft,topRight,bottomLeft,bottomRight),然后递归每个子网格。
- """
- # Definition for a QuadTree node.
- class Node:
- def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
- self.val = val
- self.isLeaf = isLeaf
- self.topLeft = topLeft
- self.topRight = topRight
- self.bottomLeft = bottomLeft
- self.bottomRight = bottomRight
- """
-
- class Solution:
- def construct(self, grid: List[List[int]]) -> 'Node':
- # 定义递归函数,遍历当前网格是否全部相等
- def dfs(r0: int, c0: int, r1:int, c1: int)->'Node':
- for i in range(r0, r1):
- for j in range(c0,c1):
- # 若不相等则继续进行遍历,遍历四个网格部分
- if grid[i][j] != grid[r0][c0]:
- return Node(
- True,
- False,
- dfs(r0, c0, (r0+r1)//2, (c0+c1)//2),
- dfs(r0, (c0+c1)//2, (r0+r1)//2, c1),
- dfs((r0+r1)//2, c0, r1, (c0+c1)//2),
- dfs((r0+r1)//2, (c0+c1)//2, r1, c1),
- )
- # 所有都相等则返回节点
- return Node(grid[r0][c0]==1, True)
-
- return dfs(0, 0, len(grid), len(grid))

题目大意:给定一个整数数组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了!
- class Solution:
- def smallestRangeI(self, nums: List[int], k: int) -> int:
- maxn = max(nums)
- minn = min(nums)
- if maxn - minn > 2 * k:
- return maxn - minn - 2 * k
- else:
- return 0
题目大意:给定root1,root2两颗二叉搜索树,返回列表,包含两个树的所有整数并按升序排序。
解析:二叉搜索树的中序遍历是有序的!!!那么直接中序遍历两棵树,得到两个有序数组,再合并两个有序数组就可以了(糟糕的感觉,思想有了,但是,不会写代码。。。)
中序遍历:采用递归进行遍历。
合并两个有序数组-->归并排序:需要一个额外的数组和两个指针,然后对指针遍历两个数组比较大小就可以了。
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution:
- def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
- nums1 = []
- nums2 = []
- self.inOrder(root1, nums1)
- self.inOrder(root2, nums2)
- return self.merge(nums1, nums2)
-
- def inOrder(self, root, nums):
- if not root:
- return
- # 遍历节点,将节点值放入nums中
- self.inOrder(root.left, nums)
- nums.append(root.val)
- self.inOrder(root.right, nums)
-
- # 归并排序,增加了一个新的数组,两个指针相比较
- def merge(self, nums1, nums2):
- res = []
- p1 = 0
- p2 = 0
- while p1<len(nums1) and p2<len(nums2):
- if nums1[p1] < nums2[p2]:
- res.append(nums1[p1])
- p1 += 1
- else:
- res.append(nums2[p2])
- p2 += 1
- if p1<len(nums1):
- res.extend(nums1[p1:])
- if p2<len(nums2):
- res.extend(nums2[p2:])
- return res

这个题目太长要求太多了,就不叙述了,就只记录一下正则匹配的一点点相关知识。
. 表示任何字符
* 表示0次或多次
.* 表示任何字符出现0次或多次
.*? 表示非贪婪模式,例如 a.*?b 表示匹配满足a开头b结尾最短的字符串
<[A-Z]{1,9}> 表示大写字母和1-9
</\1> 表示与第一个内容完全匹配
[^<]* 除了<以外的任何字符
果然,一下子写完不是我的风格,坚持不下去,从4月29号到现在5月22号确实不少,虽然中间也有很多是简单的,困难的,但是,写完是我所坚持不下去的,若非要写完,只能是敷衍了事,所以,换个任务,下次继续写,现在就干其他事吧。
最后,既然开始了,就不要停下你的脚步了吧!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。