2020年10月刷题日志
10.31
python选手的福音来了
题目
381. O(1) 时间插入、删除和获取随机元素 - 允许重复
难度困难
设计一个支持在平均 时间复杂度 O(1) 下**，** 执行以下操作的数据结构。
注意: 允许出现重复元素。
insert(val)：向集合中插入元素 val。remove(val)：当 val 存在时，从集合中移除一个 val。getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。示例:
// 初始化一个空的集合。 RandomizedCollection collection = new RandomizedCollection(); // 向集合中插入 1 。返回 true 表示集合不包含 1 。 collection.insert(1); // 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。 collection.insert(1); // 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。 collection.insert(2); // getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。 collection.getRandom(); // 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。 collection.remove(1); // getRandom 应有相同概率返回 1 和 2 。 collection.getRandom();
思路
对于python来说这也就是一道表面困难题
一开始我只用了一个哈希表来解，结果发现单纯用字典在返回随机值的时候时间复杂度是O(N)
于是乎又用数组+哈希表来优化解法，接下来针对每种操作讲解一下
-
初始化
- 新建一个空数组
nums - 新建一个空字典
dic
- 新建一个空数组
-
插入元素
- 直接在
nums数组中append要插入的值 - 令
dic[插入的值]+=1- 如果要插入的值不在字典的
key中，就令dic[插入的值]=1
- 如果要插入的值不在字典的
- 直接在
-
删除元素
- 首先使用字典来判断这个删除的数是否在数组中
- 如果这个数在字典的key中，且对应的
dic[要删除的数]>=1，说明是可以成功删除的- 于是就使用
nums.remove(要删除的数)和dic[要删除的数]-=1，来实现删去这个数
- 于是就使用
-
获取随机值
-
直接使用
random.randint(0, len(nums)-1)来随机取一个index，返回nums[index] -
可以看到这样的实现是真的O(1)
10.30
昨天晚上九点多买完kfc发现自行车钥匙丢了
结果就推到了修车摊，人走回的学校
今天刚走去修车摊把我的车锁换了
累死了
不过leetcode这道题确实简单
题目
463. 岛屿的周长
难度简单300
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 :
输入: [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]] 输出: 16 解释: 它的周长是下面图片中的 16 个黄色的边：
思路
- 先算出所有陆地方格的边总数
- 陆地方格数*4
- 然后遍历每个陆地方格的四周，去掉重复计算的边
代码
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ans = 0
for i in grid:
ans += sum(i)*4
if not grid:
return 0
judges = [[0,1],[1,0],[0,-1],[-1,0]]
rows = len(grid)
cols = len(grid[0])
for i in range(rows):
for j in range(cols):
if grid[i][j]==0:
continue
for x,y in judges:
row = x+i
col = y+j
if row<0 or row>=rows or col<0 or col>=cols:
continue
if grid[row][col]==1:
ans-=1
return ans
10.29
今天又放假？
题目
129. 求根到叶子节点数字之和
难度中等
给定一个二叉树，它的每个结点都存放一个
0-9的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径
1->2->3代表数字123。计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25.示例 2:
输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.
思路
也没啥好讲的，就递归深搜求解呗
搜到底的时候就记录一下值
代码
- 我的丑陋代码
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root:
return 0
res = []
def add_ans(cur_num, root):
if not root.left and not root.right:
res.append(cur_num*10+root.val)
if root.left:
add_ans(cur_num*10+root.val, root.left)
if root.right:
add_ans(cur_num*10+root.val, root.right)
add_ans(0, root)
return sum(res)
- 大佬的优美递归
class Solution:
def dfs(self, cur_num, root):
if not root:
return 0
if not root.left and not root.right:
return cur_num*10+root.val
return self.dfs(cur_num*10+root.val, root.left) + self.dfs(cur_num*10+root.val, root.right)
def sumNumbers(self, root: TreeNode) -> int:
return self.dfs(0, root)
10.28
今天又是简单题
题目
1207. 独一无二的出现次数
难度简单
给你一个整数数组
arr，请你帮忙统计数组中每个数的出现次数。如果每个数的出现次数都是独一无二的，就返回
true；否则返回false。示例 1：
输入：arr = [1,2,2,1,1,3] 输出：true 解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。示例 2：
输入：arr = [1,2] 输出：false示例 3：
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0] 输出：true提示：
1 <= arr.length <= 1000-1000 <= arr[i] <= 1000
思路
-
常规思路
- 用字典计数
- 用集合判重
-
不常规思路
-
利用python的collections库中的Counter计数类，来统计数组中的数出现次数
-
利用
Counter(arr)来让[1,2,3,4,1,1,1]来生成计数用的字典{1：4，2：1，3：1，4：1} -
然后判重
其实就是一个道理
-
代码
from collections import Counter
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
cs = Counter(arr)
for num in cs:
if list(cs.values()).count(cs[num]) != 1:
return False
return True
10.27
剪刀石头布的通信实验终于让我做完了！！！
快乐刷题
题目
144. 二叉树的前序遍历
难度中等
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路
就不用递归写了，没啥技术含量
练习一下迭代吧
常规解法
-
利用栈的后进先出的特性，来实现先左后右
-
初始化栈，将根节点存入栈
-
从栈中pop出一个结点
- 然后把这个结点的值存储ans数组中
- 把该节点的右子结点push到栈中
- 把该节点的左子节点push到栈中
- 直到栈为空
模板解法
- 初始化栈
- 令cur结点为根节点
- 当栈非空或cur结点非空时继续循环
- 将cur结点的值存入ans数组
- 把cur和它所有的左子结点都push到栈里
- 然后从栈顶取出一个结点
- 这个结点我们知道一定是最左下角的一个
- 将cur设为该节点的右子结点
代码
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
node = root
ans = []
if not root:
return []
while stack or node:
while node:
ans.append(node.val)
stack.append(node)
node = node.left
node = stack.pop()
node = node.right
return ans
10.26
美好的自习周末就这么过去了，我却还卡在操作系统的剪刀石头布实验
题目
1365. 有多少小于当前数字的数字
难度简单
给你一个数组
nums，对于其中每个元素nums[i]，请你统计数组中比它小的所有数字的数目。换而言之，对于每个
nums[i]你必须计算出有效的j的数量，其中j满足j != i且nums[j] < nums[i]。以数组形式返回答案。
示例 1：
输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。示例 2：
输入：nums = [6,5,4,8] 输出：[2,1,0,3]示例 3：
输入：nums = [7,7,7,7] 输出：[0,0,0,0]提示：
2 <= nums.length <= 5000 <= nums[i] <= 100
思路
-
一道五个月前提交过的老题
-
当时用的是排序，排完序之后找index函数确定每个数字的位置
-
其实挺无脑的，就贴个代码看一下吧
-
class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: tmp_lst = sorted(nums) ans = [0]*len(nums) for i in range(len(nums)): ans[i] = tmp_lst.index(nums[i]) return ans
-
-
上一种思路的时间复杂度是
O(NlogN)，空间复杂度是O(N) -
看了官方题解的计数法重新写了一下（虽然也用了python的特性）
- 数字出现的值域是固定的
[1,100] - 建立一个长度为101的
cnt数组去记录每个数字出现的次数 - 遍历数组
nums，cnt[num]+=1 - 然后因为要计算的是比某个数字小的数出现的次数
- 所以要对cnt数组做一次前缀和
- 每个数加上所有在它左边的数
- 最后
cnt[i]就是比i这个数小的数字出现次数 - 遍历
nums，找到答案
- 数字出现的值域是固定的
代码
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
# 由于数字的值域是[0, 100]
# 所以直接开辟一个数组来记录数字的出现次数
cnt = [0 for i in range(101)]
for num in nums:
cnt[num] += 1
# 根据出现次数我们可以计算出比x小的数有多少个
tmp = 0
for i in range(len(cnt)):
# 这里直接用python的特性来少设一个变量
tmp, cnt[i] = tmp+cnt[i], tmp
ans = []
for i in nums:
ans.append(cnt[i])
return ans
还是比原来方法快很多的
10.25
今日重阳节，云登山。
题目
845. 数组中的最长山脉
难度中等
我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
B.length >= 3- 存在
0 < i < B.length - 1使得B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]（注意：B 可以是 A 的任意子数组，包括整个数组 A。）
给出一个整数数组
A，返回最长 “山脉” 的长度。如果不含有 “山脉” 则返回
0。示例 1：
输入：[2,1,4,7,3,2,5] 输出：5 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。示例 2：
输入：[2,2,2] 输出：0 解释：不含 “山脉”。提示：
0 <= A.length <= 100000 <= A[i] <= 10000
思路
- 用
diffs数组去记录A[i]-A[i-1]的值 - 找到最长的山脉也就是找到最长的
[+,+,+,....,-,-,-,]的数组长度+1 - 这个数组满足数组的前半部分都是正数，后半部分都是负数
- 要保证前半部分和后半部分的个数都大于0
代码
今天代码写的很烂，建议直接忽略
一道中等题WA了将近10次才Pass我也太菜了吧
class Solution:
def longestMountain(self, A: List[int]) -> int:
diffs = []
for i in range(1,len(A)):
diffs.append(A[i]-A[i-1])
ans = 0
flag = 0 # 用来标记是否已经经过山峰
cur = 0
# 找到diffs数组中最长的 ++++ ----- 数组
# 1, -1, 1, -1, -1
for i in diffs:
if i>0 and flag==0:
if not cur:
cur = 2
else:
cur += 1
elif i>0 and flag==1:
ans = max(cur, ans)
cur = 2
flag = 0
elif i<0 and flag==0:
if cur==1 or not cur:
continue
cur += 1
flag = 1
elif i<0 and flag==1:
cur += 1
elif i==0:
if flag==1:
ans = max(ans, cur)
cur = 1
flag = 0
if flag:
ans = max(ans, cur)
return 0 if ans<3 else ans
10.24
程序员节快乐！
小D同学为啥每天都要生我的气呢…
题目
1024. 视频拼接
难度中等
你将会获得一系列视频片段，这些片段来自于一项持续时长为
T秒的体育赛事。这些片段可能有所重叠，也可能长度不一。视频片段
clips[i]都用区间进行表示：开始于clips[i][0]并于clips[i][1]结束。我们甚至可以对这些片段自由地再剪辑，例如片段[0, 7]可以剪切成[0, 1] + [1, 3] + [3, 7]三部分。我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（
[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回-1。示例 1：
输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 输出：3 解释： 我们选中 [0,2], [8,10], [1,9] 这三个片段。 然后，按下面的方案重制比赛片段： 将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。 现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。示例 2：
输入：clips = [[0,1],[1,2]], T = 5 输出：-1 解释： 我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。示例 3：
输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9 输出：3 解释： 我们选取片段 [0,4], [4,7] 和 [6,9] 。示例 4：
输入：clips = [[0,4],[2,8]], T = 5 输出：2 解释： 注意，你可能录制超过比赛结束时间的视频。提示：
1 <= clips.length <= 1000 <= clips[i][0] <= clips[i][1] <= 1000 <= T <= 100
思路
题目序号是1024呢，标了中等但其实很简单，没啥算法和数据结构
- 一开始设定
start, end = -1, 0用来记录上一次的剪辑片段 - 就是很纯粹的贪心法，不断地找最长的片段拼到一起
- 每次找的片段的开始时间必须早于上一个片段的结束时间，同时还必须晚于上一个片段的开始时间
- 同时结束时间要比上一个片段的结束时间晚
- 然后保证每次找到的片段的结束时间是合法片段中能最晚结束的
代码
class Solution:
def videoStitching(self, clips: List[List[int]], T: int) -> int:
start, end = -1, 0
ans = 0
while end<T:
tmp = []
for i in clips:
if i[0]<= end and i[1]>end and i[0]>=start:
if not tmp:
tmp = i
elif i[1]>=tmp[1]:
tmp = i
if not tmp:
return -1
start = tmp[0]
end = tmp[1]
ans += 1
return -1 if not ans else ans
10.23
太好了，今天可以自习一天了
题目
234. 回文链表
难度简单
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false示例 2:
输入: 1->2->2->1 输出: true进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路
- O(n) 空间复杂度
- 用数组nums存下每个结点值，利用切片操作直接返回nums == nums[::-1]
- O(1)空间复杂度
- 首先用快慢指针找到中间结点
- 翻转后半部分的链表
- 逐个对比前半部分链表结点和后半部分链表的值
- 这几个算法写过了就不展开了，直接上进阶要求的代码
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 先找到中间节点
if not head or not head.next:
return True
fast,slow=head,head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
# 找到后半链表的头节点mid
mid = slow.next
# 反转后半部分的列表
node1, node2 = head, self.reverse(mid)
# 逐个对比前后链表中结点的值
while node1 and node2:
if node1.val != node2.val:
return False
node1 = node1.next
node2 = node2.next
return True
def reverse(self, head):
# 从head开始反转列表
prev = None
cur = head
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
10.22
明天是运动会，所以今天就是这周上课的最后一天啦，坚持一哈
最近有一大堆实验报告要写，再过一个星期又是期中考试，实验室还有项目要做
不说了，我冲了！
题目
763. 划分字母区间
难度中等
字符串
S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。示例 1：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。提示：
S的长度在[1, 500]之间。S只包含小写字母'a'到'z'。
思路
可恶，我以为是用动态规划啥的，结果最后发现是贪心法
本题的贪心思想
-
从字符串头部开始，以
start = end = 0开始尝试划分区间[start, end]- 题目要求是划分的尽可能多
- 所以我们就把每个区间划分的尽量的小
- 当这个区间合法的时候就划分
- 然后令
start = end + 1, end = end + 1 - 直到把这个字符串全部划分完
-
怎么判断区间是否合理呢？
-
首先需要使用哈希表或数组去记录每个字母出现的最后的位置
-
针对
S[start, end]- 我们知道当这个区间里的每个字母
i的最右位置right_i <= end的时候 - 这个区间就是合理的
- 又因为是采取了贪心策略，要保证这个区间最小
- 所以这个
end必定是对应了这个区间中某个字母k的最右位置right_k - 且这个
right_k一定是这个区间里的所有字母的最右位置right_i的最大值
- 我们知道当这个区间里的每个字母
-
当
end == right_k，就进行划分，并继续划分下一个区间 -
如果
end != right_k，就令right_k = max(right_k, right_S[end])
-
-
大概理解思路就行，看代码就懂了
代码
class Solution:
def partitionLabels(self, S: str) -> List[int]:
# 找到每个字母出现的最后一个位置
dic = dict()
for i in range(len(S)):
dic[S[i]] = i
start, end = 0, 0
ans = []
while end<len(S):
max_end = dic[S[end]] # 用来记录当前这个区间里的字母需要扩的最右边界
while end<len(S) and end!=max_end:
# 贪心法：这个区间正好合法的时候就进行划分
end += 1
max_end = max(max_end, dic[S[end]])
ans.append(end-start+1)
start, end = end+1, end+1
return ans
10.21
题目
925. 长按键入
难度简单
你的朋友正在使用键盘输入他的名字
name。偶尔，在键入字符c时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符
typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回True。示例 1：
输入：name = "alex", typed = "aaleex" 输出：true 解释：'alex' 中的 'a' 和 'e' 被长按。示例 2：
输入：name = "saeed", typed = "ssaaedd" 输出：false 解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。示例 3：
输入：name = "leelee", typed = "lleeelee" 输出：true示例 4：
输入：name = "laiden", typed = "laiden" 输出：true 解释：长按名字中的字符并不是必要的。提示：
name.length <= 1000typed.length <= 1000name和typed的字符都是小写字母。
思路
还是比较简单的，是两年前就通过的一道老题
然而今天却调试了好久，刷题这么久总有种越刷越菜的感觉
- 双指针
i = 0 , j = 0遍历两个字符串，i遍历name，j遍历typed- 如果碰到两个字母相等，两个指针都往后移一格
i+=1j+=1
- 字母不相等，检查一下是不是
typed[j]是不是被长按出来的- 发现是被长按的，就让
j指针后移一格，继续循环
- 发现是被长按的，就让
- 如果不是被长按出来的，且字母不相等，说明无法对应，直接返回False
- 如果碰到两个字母相等，两个指针都往后移一格
- 循环到最后，如果
i把name字符串遍历完了，说明是对应的，返回True- 如果没遍历完，返回False
代码
class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
i, j = 0, 0
while j<len(typed):
if i<len(name) and name[i]==typed[j]:
i += 1
j += 1
elif j>0 and typed[j]==typed[j-1]:
j += 1
else:
return False
return i == len(name)
10.20
麻烦快进到周末
题目
143. 重排链表
难度中等
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→*Ln-1→L2→*Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
思路
因为要求是结点交换而不能是改变内部的值，所以用线性表的都是耍流氓
比较规范的解法是这样的
- 首先用快慢指针找到中间结点
- 例如
1->2->3->4的中间结点就是3
- 例如
- 把从中间结点开始的后半段链表进行翻转
- 翻转完之后就形成了
1->2->4->3
- 翻转完之后就形成了
- 把后半部分的结点逐个插入前半部分的结点后
- 4插到1后面
1->4->2->3 - 3插到2后面
1->4->2->3
- 4插到1后面
- 返回头节点
具体的快慢指针找中点法和翻转链表方法就不再提了，之前已经刷过了
直接上代码
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
slow, fast = head, head
if not head or not head.next:
return
# 找到链表的中结点
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
mid = slow.next
slow.next= None
# 把链表后半部分反转
def reverse(node):
prev = None
cur = node
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
mid = reverse(mid)
# 将后半部分的结点逐个插入前半部分结点后
node1 = head
node2 = mid
while node2:
tmp1 = node1.next
tmp2 = node2.next
node1.next = node2
node2.next = tmp1
node1 = tmp1
node2 = tmp2
10.19
又到周一了😭
题目
844. 比较含退格的字符串
难度简单
给定
S和T两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。#代表退格字符。**注意：**如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：S = "ab#c", T = "ad#c" 输出：true 解释：S 和 T 都会变成 “ac”。示例 2：
输入：S = "ab##", T = "c#d#" 输出：true 解释：S 和 T 都会变成 “”。示例 3：
输入：S = "a##c", T = "#a#c" 输出：true 解释：S 和 T 都会变成 “c”。示例 4：
输入：S = "a#c", T = "b" 输出：false 解释：S 会变成 “c”，但 T 仍然是 “b”。提示：
1 <= S.length <= 200
1 <= T.length <= 200
S和T只含有小写字母以及字符'#'。进阶：
- 你可以用
O(N)的时间复杂度和O(1)的空间复杂度解决该问题吗？
思路
- 为了实现进阶要求，很明显是用双指针
- 从字符串尾，同时遍历两个字符串
- 遇到退格
- 记录退格数+1
- 遇到字母
- 有退格数就继续往前遍历
- 无退格数就结束循环，比较两个字符串当前字符是否相等
- 一直遍历到字符串头
- 结果我自己调试了半天还是WA
- 最后还是看了下题解，调整了一下代码
代码
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
index_S, index_T = len(S)-1, len(T)-1
cnt_S, cnt_T = 0, 0
while index_T>=0 or index_S>=0:
while index_S >= 0:
if S[index_S] == "#":
cnt_S += 1
index_S -= 1
elif cnt_S>0:
cnt_S -= 1
index_S -= 1
else:
break
while index_T >= 0:
if T[index_T] == "#":
cnt_T += 1
index_T -= 1
elif cnt_T>0:
cnt_T -= 1
index_T -= 1
else:
break
if index_S>=0 and index_T>=0:
if S[index_S] != T[index_T]:
return False
elif index_S>=0 or index_T>=0:
return False
index_S -= 1
index_T -= 1
if index_T<=0 and index_S<=0:
return True
else:
return False
10.18
今天是学校校庆，虽然是志愿者但是负责接待的嘉宾跟我说我可以自己忙自己的
那就学习呗
题目
19. 删除链表的倒数第N个节点
难度中等1039
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
题解
正好一个月前刷过，那就直接提交了呗
-
快慢指针法
-
详情图解
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
front = ListNode(0)
front.next = head
pre, back = front, front
for i in range(n+1):
pre = pre.next
while pre:
pre = pre.next
back = back.next
back.next = back.next.next
return front.next
10.17
今天又是复习N皇后
题目
52. N皇后 II
难度困难
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]提示：
思路
经典的回溯法例题，和之前做的N皇后区别在于这道题求的是N皇后的解法数量
某种方面感觉甚至比上次还要简单，因为不用存储棋盘了
- 整体思想递归求解
- 每次往合法的位置放一个皇后
- 成功放完N个皇后说明有一种解法
- 回溯法核心思想
- 考虑完该种放置皇后的可能性之后
- 调用自身的函数直接考虑下一个
- 递归到底之后（无论是能放完还是放不完N个皇后）会退出递归
- 退出递归后要把该种方法放置的皇后位置清空
- 其中要考虑的核心点，如何判断位置是否合法？
- 如果每次都存储棋盘，看一遍每行每列每个对角线，会浪费很多时间和空间
- 因此用3个集合来保证放置皇后的合理性
- 保证每行只有一个
- 用cnt作为参数，来确保我们放皇后是按照从第0行放到第N-1行
- 保证每列只有一个
- 建cols集合，存储放过的皇后的列
- 每次放到col列之前，判断col是否为1
- 如果是1就说明不能放，如果是0说明该列可以放
- 保证每根左对角线只有一个
- 建立left集合
- 用
row+col来定位皇后的左对角线- 例如第1行第2列的皇后合第2行第1列的皇后是在同一条左对角线上的
- 1+2 == 2+1
- 保证每根左对角线只有一个
- 建立right集合
- 用
row-col来定位皇后的右对角线
- 保证每行只有一个
代码
class Solution:
def totalNQueens(self, n: int) -> int:
ans = 0
def dfs(cols, left, right, cnt):
if cnt == n:
return 1
row = cnt
ans = 0
for i in range(n):
if i in cols:
continue
r = row-i
if r in right:
continue
l = row+i
if l in left:
continue
cols.add(i)
left.add(l)
right.add(r)
ans += dfs(cols, left, right, cnt+1)
cols.remove(i)
left.remove(l)
right.remove(r)
return ans
cols = set()
left = set()
right = set()
ans = dfs(cols, left, right, 0)
return ans
10.16
好困
题目
977. 有序数组的平方
难度简单
给定一个按非递减顺序排序的整数数组
A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例 1：
输入：[-4,-1,0,3,10] 输出：[0,1,9,16,100]示例 2：
输入：[-7,-3,2,3,11] 输出：[4,9,9,49,121]提示：
1 <= A.length <= 10000-10000 <= A[i] <= 10000A已按非递减顺序排序。
思路
去年提交过的一道题，当时还是偷懒的LYC
python一行用库排序返回新数组，时间复杂度是O(NlogN)
今天用个稍微朴素一点的双指针吧，时间复杂度是O(N)（不过提交之后发现甚至还没排序快）
- 先遍历一遍数组，找到绝对值最小的数
- 先把这个数的平方放到ans数组
- 然后从这个数字开始往两边找
- 一个left指针，初始值为最小数的索引值-1
- 一个right指针，初始值为最小数的索引值+1
- 先往左找，直到找到的数比右边大
- 边向左找，边把已经找到的数的平方放到ans数组中
- 再往右找，直到找到的数比左边大
- 同理，边遍历边存答案
- 直到两边都走到底
- 这里要注意，如果左边走到底了，右边直接遍历完就行，左右同理
代码
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
min_index = 0
min_abs = abs(A[0])
for i in range(len(A)):
if abs(A[i])<min_abs:
min_abs = abs(A[i])
min_index = i
left = min_index - 1
right = min_index + 1
ans = [min_abs**2]
while left>=0 or right<len(A):
while left>=0 and (right>=len(A) or -A[left]<=A[right]):
ans.append(A[left]**2)
left -= 1
while right<len(A) and (left<0 or A[right]<=-A[left]):
ans.append(A[right]**2)
right += 1
return ans
10.15
今天又是一道老题，刷完睡午觉咯
题目
116. 填充每个节点的下一个右侧节点指针
难度中等
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。示例：
输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1} 输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1} 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
思路
- 题目甚至给了条件是完美二叉树，直接利用自顶向下，自左向右逐层遍历的思想
- 定义一个
begin结点，记录每层的最左侧的结点，就是我们每层开始遍历的结点node = begin- 因为是完美二叉树，所以左右子节点必定成对出现，所以直接给左子节点加上next指针
node.left.next = node.left.right- 因为是自顶向下的，所以我们这边是知道是否有
node.next的 - 如果有，那么
node.right.next = node.next.left - 继续遍历该层剩下的结点，即
node = node.next
- 遍历完该层之后，令
begin=begin.left，继续处理一下层
- 定义一个
代码
class Solution:
def connect(self, root: 'Node') -> 'Node':
begin = root
while begin and begin.left:
node = begin
while node:
node.left.next = node.right
if node.next:
node.right.next = node.next.left
node = node.next
begin = begin.left
return root
10.14
题目
1002. 查找常用字符
难度简单141
给定仅有小写字母组成的字符串数组
A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。你可以按任意顺序返回答案。
示例 1：
输入：["bella","label","roller"] 输出：["e","l","l"]示例 2：
输入：["cool","lock","cook"] 输出：["c","o"]提示：
1 <= A.length <= 1001 <= A[i].length <= 100A[i][j]是小写字母
思路
今天第一遍写的代码竟然还没有我2年前写的效率高
🙃怎么大三比大一还菜了呢
- 主要思想
- 遍历第一个字符串中的不同字母
- 针对每个字母，找出该字母在所有字符串中出现的最小次数（可能为0）
- 在答案数组中置入最小次数个该字母
- 技巧
- 利用set()去重
- 利用count()计算出现次数
代码
class Solution:
def commonChars(self, A: List[str]) -> List[str]:
ans = []
for i in set(A[0]):
cnts = A[0].count(i)
for j in range(1,len(A)):
cnts = min(A[j].count(i), cnts)
ans+=[i]*cnts
return ans
10.13
题目
24. 两两交换链表中的节点
难度中等
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
思路
这不是巧了吗，今天的每日一题是国庆刚自己刷过的一道题
发现自己的方法把迭代和递归混在一起写了，今天就优化一下
- 设置一个
dummy哑结点，放在一开始的头节点前面- 方便之后返回答案链表的头节点
- 之后从
dummy开始遍历- 当前遍历的结点假设是0结点
- 把0->1->2换成0->2->1
- 把1作为下一个0，重复上述操作
- 当0结点之后没有结点，说明交换完毕
代码
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
node = dummy
while node.next and node.next.next:
first = node.next
second = node.next.next
node.next = second
first.next = second.next
second.next = first
node = first
return dummy.next
10.12
今天周一啦
题目
530. 二叉搜索树的最小绝对差
难度简单
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入： 1 \ 3 / 2 输出： 1 解释： 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。提示：
- 树中至少有 2 个节点。
- 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
思路
可恶，我竟然简单题都不会做了
对二叉树的中序遍历还是不太熟悉
因为是二叉搜索树，所以可以看作是有序数组
就是在一个有序数组上求两个数的最小插值
- 把二叉树转换成数组，然后对排序好的数组求两个数值最小值
- 直接对二叉树进行递归和迭代求解
- 用一个pre结点记录当前结点的前一个结点
- 因为是中序遍历，所以pre结点必定是在当前结点的左边，也就是说
root.val>pre.val - 所以遍历所有结点，同时更新最小差值即可
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getMinimumDifference(self, root: TreeNode) -> int:
ans = float("inf")
pre = -1
def dfs(root):
nonlocal ans,pre
if not root:
return
dfs(root.left)
if pre!=-1:
ans = min(ans, root.val-pre)
pre = root.val
else:
pre = root.val
dfs(root.right)
dfs(root)
return ans
10.11
今天又是周日呀
上午实验室招新，去面试了半天，现在的学弟都这么强的吗
题目
416. 分割等和子集
难度中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
思路
- 动态规划呗，我不会呗，看题解呗
- 一开始先判断和是否为偶数
- 是奇数直接返回False
- 是偶数就继续检查
- 定义动态规划的dp数组
dp[i][j]说明nums[0:i]中的数字中取一些加起来能否是j- 这里的
i最大为nums的元素数 - 这里的
j最大为nums的和的一半 - 最后判断
dp数组的最后一行最后一格是否为Ture - 注意一开始要初始化
dp[0][nums[0]]和dp[0][0]为True
- 时间优化
- 当判断到某一行的最后
- 若
dp[i][j]==True and j==sum/2，可以直接返回True，因为此时已经能做到和为一半了
- 空间优化
- 因为每一行的数据只和上一行数据有关，所以可以优化为一行
- 把
dp[i][j]优化为dp[j] - 这里要保证是从后到前循环的，即
j从sum/2循环到0 - 原因是保证判断的时候，用的都是“上一行”的数据，而不是这一行新产生的数据
代码
class Solution:
def canPartition(self, nums: List[int]) -> bool:
rows = len(nums)
cols = sum(nums)/2
if not cols == int(cols):
# sum为奇数说明不可能分割两个等和子集
return False
else:
cols = int(cols)+1
dp = [False for i in range(cols)]
dp[0] = True
if nums[0]<=cols:
dp[nums[0]] = True
for i in range(1,rows):
for j in range(cols-1,-1,-1):
if nums[i] == j:
dp[j] = True
elif nums[i]<j:
dp[j] = dp[j] or dp[j-nums[i]]
if j==cols-1 and dp[j]:
return True
return dp[-1]
10.10
题目
142. 环形链表 II
难度中等
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回
null。为了表示给定链表中的环，我们使用整数
pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。**说明：**不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。
进阶： 你是否可以不用额外空间解决此题？
思路
一开始以为和昨天的一摸一样，后来发现还没那么简单
昨天的题目只要判断是否存在环形链表，今天的要返回环的头节点
最终还是看了大佬的题解，发现原来是数学解法
还是老样子，为了实现常数空间用快慢指针
- 一开始快慢指针都从head出发
- 快指针一次走两步，慢指针一次走一步
- 这里定义
- a=从头节点到入环第一个节点前的所有结点数
- b=环中的结点数
- 当快慢节点第一次相遇的时候
- fast = 2*slow
- slow = a+nb
- fast = 2nb, slow = nb
- 这时令fast回到head结点，slow不动（即slow领先fast了nb步）
- 两个指针都是一次走一步
- 当fast走了a步，slow就一共走了a+nb步
- 这时两者相遇因为slow正好比fast快了n圈
- 此时两者的位置也正好是入环的头节点
这个方法太妙了
代码
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast = head
slow = head
while True:
if not fast or not fast.next:
return
slow = slow.next
fast = fast.next.next
if slow == fast:break
# 第一次相遇的时候 fast比slow多走了n圈环形链表 slow在nb的位置
fast = head
while slow!=fast:
slow = slow.next
fast = fast.next
# 第二次fast走到a时，slow走到了a+nb的位置，此时两者重合
return slow
10.9
突然开学了，上课睡到流口水
不过今天又是简单题🤭
题目
141. 环形链表
难度简单
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回
true。 否则，返回false。进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。提示：
- 链表中节点的数目范围是
[0, 104]-105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
思路
- 用一个哈希表存储已经访问过的结点
- 每遍历一个结点，就存入哈希表中
- 存的时候如果发现哈希表中存在该结点，说明遍历过，返回True
- 存到最后空指针时没有重复遍历的结点，说明没有环，返回False
- 快慢指针遍历链表
- 慢指针起点为head，快指针起点为head.next
- 慢指针一次一步，快指针一次两步，相当于追及问题
- 如果快指针追上了慢指针，说明有环
- 如果快指针先走到了空指针，说明没有环
代码
就放一个快慢指针的方法吧
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
slow, fast = head, head.next
while slow!=fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
10.8
舒服了呀，今天是简单题
题目
344. 反转字符串
难度简单
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
char[]的形式给出。不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]示例 2：
输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
思路
- 设置双指针前后同时开始遍历字符串
- 边遍历边交换值
代码
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
p0,p1=0,len(s)-1
while p0<p1:
s[p0],s[p1]=s[p1],s[p0]
p0+=1
p1-=1
10.7
题目
75. 颜色分类
难度中等
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
思路
- 利用双指针，把0移到前面，把1移到0的后面
代码
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# p0为存储0的指针，p1是存储1的指针
p0, p1 = 0, 0
for i in range(len(nums)):
if nums[i]==1:
# 碰到1就存放到p1指针处
nums[p1],nums[i]=nums[i],nums[p1]
# 同时p1指针后移一格
p1+=1
elif nums[i]==0:
# 碰到0的话有可能会把前面的1移到后面去
nums[p0],nums[i]=nums[i],nums[p0]
if p0<p1:
# p0<p1说明把一个刚刚移到前面的1移到了i处
nums[i],nums[p1]=nums[p1],nums[i]
p1+=1
p0+=1
10.6
今天放假在家，没刷题
其实是我10.7回学校补的
题目
834. 树中距离之和
难度困难
给定一个无向、连通的树。树中有
N个标记为0...N-1的节点以及N-1条边 。第
i条边连接节点edges[i][0]和edges[i][1]。返回一个表示节点
i与其他所有节点距离之和的列表ans。示例 1:
输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 输出: [8,12,6,10,10,10] 解释: 如下为给定的树的示意图： 0 / \ 1 2 /|\ 3 4 5 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。说明:
1 <= N <= 10000
代码
参考的别人的题解，我就不写解题思路丢人了
class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
# 先构建邻接表
distance_graph = [[] for i in range(N)]
for edge in edges:
distance_graph[edge[0]].append(edge[1])
distance_graph[edge[1]].append(edge[0])
node_sum = [1 for i in range(N)]
distance_sum = [0 for i in range(N)]
def post_order(root, parent):
# 先用后序遍历从下至上，确定每个结点的子树的结点数
# 以及结点到子树所有结点的距离和
neighbours = distance_graph[root]
for neighbour in neighbours:
if neighbour==parent:
continue
post_order(neighbour, root)
node_sum[root] += node_sum[neighbour]
distance_sum[root] += node_sum[neighbour]+distance_sum[neighbour]
# 此时求出了所有结点的子树距离和以及子树结点数
# 根据图可以找出规律 某一个结点到所有结点的距离和 = 根结点到所有结点距离和-该结点子树的结点数+（树的结点总数-该结点子树的结点数）
def pre_order(node, parent):
# 从上至下，确定结点到所有其余结点的距离和
for n in distance_graph[node]:
if n == parent:
continue
distance_sum[n] = distance_sum[node]-node_sum[n]+N-node_sum[n]
pre_order(n, node)
post_order(0, -1)
pre_order(0, -1)
return distance_sum
10.5
我可没有偷懒噢 我只是不想写题解了
21岁了 😭
题目
18. 四数之和
难度中等
给定一个包含 n 个整数的数组
nums和一个目标值target，判断nums中是否存在四个元素 *a，*b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组。注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
代码
参考了官方题解，前两个数，后两个数用双指针的解法
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
ans = []
nums.sort()
for i in range(0,len(nums)-3):
if i>0 and nums[i]==nums[i-1]:continue
for j in range(i+1,len(nums)-2):
if j>i+1 and nums[j]==nums[j-1]:continue
cur_target = target - (nums[i]+nums[j])
start = j+1
end = len(nums)-1
while start<end:
if nums[start]+nums[end] == cur_target:
ans.append([nums[i],nums[j],nums[start],nums[end]])
while start < end and nums[start]==nums[start+1]:
start+=1
while start<end and nums[end]==nums[end-1]:
end-=1
start+=1
end-=1
elif nums[start]+nums[end] < cur_target:
start += 1
else:
end -=1
return ans
10.4
好家伙，今天又是经典老题
题目
2. 两数相加
难度中等
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
思路
对整个过程进行模拟
其实这道只考数据结构和代码的细节，其他没啥
代码
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
node = head # 实际结果从head.next开始存储
flag = 0 # 进位标记
while l1 or l2:
if l1 and l2:
# 当l1和l2列表都没走完的时候 就正常进行加法
cur_sum = l1.val+l2.val+flag
# 注意用完进位标记之后要重新判断是否需要进位
flag = 1 if cur_sum>=10 else 0
cur_sum %= 10
node.next = ListNode(cur_sum)
node = node.next
l1 = l1.next
l2 = l2.next
continue
if not l1:
# 如果l1走完了，就让l1代替l2走接下来的路
l1, l2 = l2, l1
while l1:
# 此时l2已经走完了，所以只需要对于l1剩下结点进行加法
cur_sum = l1.val+flag
flag = 1 if cur_sum>=10 else 0
cur_sum %= 10
node.next = ListNode(cur_sum)
node = node.next
l1 = l1.next
if flag:
# 最后判断一下最高位是否有进位1
node.next = ListNode(1)
return head.next
10.3
一到国庆甚至leetcode都怠惰了，全是多年前刷过的简单题
直接看题把
题目
1. 两数之和
难度简单9268
给定一个整数数组
nums和一个目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
思路
好家伙，原来我2年前就满足于O(N²)
1年前用JAVA刷了一遍估计是为了当时的期末考试吧
那么这道题到底该怎么做呢？
- 用哈希表以键值对的形式，存储 值->下标
- 遍历nums
- 更新哈希表前，先看看哈希表中有没有满足的值和当前遍历的数加起来为target
- 如果有就直接返回两个的下标
- 如果没有就更新哈希表
代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = dict()
for i in range(len(nums)):
diff = target - nums[i]
if diff in dic:
return [dic[diff], i]
dic[nums[i]] = i
10.2
又经历了一次高考查分
虽然不一定出国了，但是本来是想考满105的
虽然本来是想考满105，但是考试的时候阅读和听力出分26和28，我其实不报啥希望了，甚至还想着能考到100+就不错了
所以104对于我来说已经算比较满意了
好了，来刷题吧
题目
771. 宝石与石头
难度简单
给定字符串
J代表石头中宝石的类型，和字符串S代表你拥有的石头。S中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J中的字母不重复，J和S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。示例 1:
输入: J = "aA", S = "aAAbbbb" 输出: 3示例 2:
输入: J = "z", S = "ZZ" 输出: 0注意:
S和J最多含有50个字母。J中的字符不重复。
思路
一晃已经过了两年了
一开始看见题目限制了S和J最多50个字母，便直接用暴力法，循环两遍，发现速度好慢哦
于是用了哈希表（我用的是字典，不过跟用集合是一个道理）
代码
class Solution:
def numJewelsInStones(self, J: str, S: str) -> int:
ans = 0
dic = dict()
for i in J:
dic[i]=1
for i in S:
if i in dic:
ans+=1
return ans
10.1
中秋国庆快乐兄弟萌
leetcode的每日一题终于来到了动态规划（俺最不会的）
题目
LCP 19. 秋叶收藏集
难度中等
小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集
leaves， 字符串leaves仅包含小写字符r和y， 其中字符r表示一片红叶，字符y表示一片黄叶。 出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。示例 1：
输入：
leaves = "rrryyyrryyyrr"输出：
2解释：调整两次，将中间的两片红叶替换成黄叶，得到 “rrryyyyyyyyrr”
示例 2：
输入：
leaves = "ryr"输出：
0解释：已符合要求，不需要额外操作
提示：
3 <= leaves.length <= 10^5leaves中只包含字符'r'和字符'y'通过次数3,414
提交次数11,095
思路
orz，我看了一分钟题目就去看了题解
简单总结题目
- 调换叶子，把叶子的序列换成 红黄红
动态规划
-
将叶子分成三段，前段红，中段黄，后段红
-
建立数组存放叶子的状态和操作次数
dp[i][0]表示替换完所有leaves[0…i]中叶子后，第i片叶子为前段红色的操作次数dp[i][1]表示替换完所有leaves[0…i]中叶子后，第i片叶子为黄色的操作次数dp[i][2]表示替换完所有leaves[0…i]中叶子后，第i片叶子为后段红色的操作次数
-
再来看状态转移方程
- 我们定义status表示叶子的颜色，status=1表示黄色，status=0表示红色
dp[i][0]，说明第i片叶子属于前段红色，那么它前面也肯定全是红色dp[i][0] = dp[i][0]+status
dp[i][1]，此时这片叶子属于中段黄色，那么它前面可能是中段黄色也可能是前段红色，但是我们要考虑的只有总操作次数的最小值。dp[i][1] = min(dp[i-1][0], dp[i-1][1])+(1-status)
dp[i][2]，这片叶子属于后段黄色，那么它前面只可能是中段黄色或者后段红色。不可能是前段红色的原因是题目强调了每段的叶子必须至少有一片。dp[i][2] = min(dp[i-1][1], dp[i-1][2])+status
-
最后的答案就是最后一片叶子属于后段红色的操作次数，即
dp[len(leaves)-1][2] -
要注意的是一开始要单独更新第一片叶子状态
-
以及对于所有
j>i的dp[i][j]而言，意味着叶子的颜色状态数大于该叶子前面的叶子数，所以要排除这种可能性，全部置为正无穷。- 例如
dp[1][2]是不存在这种可能性的，因为第二片叶子最多只能是中段黄色，而不能是后段红色。
- 例如
代码
class Solution:
def minimumOperations(self, leaves: str) -> int:
length = len(leaves)
dp = [[0,0,0] for i in range(length)]
# 其中dp[i][0]表示替换完所有leaves[0...i]中叶子后，第i片叶子为前段红色的操作次数
# 其中dp[i][1]表示替换完所有leaves[0...i]中叶子后，第i片叶子为黄色的操作次数
# 其中dp[i][2]表示替换完所有leaves[0...i]中叶子后，第i片叶子为后段红色的操作次数
dp[0][1] = dp[0][2] = dp[1][2] = float('inf')
dp[0][0] = int(leaves[0] == 'y')
for i in range(1, length):
if leaves[i] == 'r':
status = 0
else:
status = 1
# 状态更新
dp[i][0] = dp[i-1][0]+status
dp[i][1] = min(dp[i-1][0], dp[i-1][1])+(1-status)
dp[i][2] = min(dp[i-1][1], dp[i-1][2])+status
return dp[length-1][2]