10.21

题目

925. 长按键入

难度简单

你的朋友正在使用键盘输入他的名字 name。偶尔,在键入字符 c 时,按键可能会被长按,而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字(其中一些字符可能被长按),那么就返回 True

示例 1:

1
2
3
输入:name = "alex", typed = "aaleex"
输出:true
解释:'alex' 中的 'a' 和 'e' 被长按。

示例 2:

1
2
3
输入:name = "saeed", typed = "ssaaedd"
输出:false
解释:'e' 一定需要被键入两次,但在 typed 的输出中不是这样。

示例 3:

1
2
输入:name = "leelee", typed = "lleeelee"
输出:true

示例 4:

1
2
3
输入:name = "laiden", typed = "laiden"
输出:true
解释:长按名字中的字符并不是必要的。

提示:

  1. name.length <= 1000
  2. typed.length <= 1000
  3. nametyped 的字符都是小写字母。

思路

还是比较简单的,是两年前就通过的一道老题

然而今天却调试了好久,刷题这么久总有种越刷越菜的感觉

  • 双指针i = 0 , j = 0遍历两个字符串,i遍历namej遍历typed
    • 如果碰到两个字母相等,两个指针都往后移一格
      • i+=1
      • j+=1
    • 字母不相等,检查一下是不是typed[j]是不是被长按出来的
      • 发现是被长按的,就让j指针后移一格,继续循环
    • 如果不是被长按出来的,且字母不相等,说明无法对应,直接返回False
  • 循环到最后,如果i把name字符串遍历完了,说明是对应的,返回True
    • 如果没遍历完,返回False

代码

1
2
3
4
5
6
7
8
9
10
11
12
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. 重排链表

难度中等

给定一个单链表 LL0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→LnL1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

1
给定链表 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
  • 返回头节点

具体的快慢指针找中点法和翻转链表方法就不再提了,之前已经刷过了

直接上代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 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. 比较含退格的字符串

难度简单

给定 ST 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

**注意:**如果对空文本输入退格字符,文本继续为空。

示例 1:

1
2
3
输入:S = "ab#c", T = "ad#c"
输出:true
解释:S 和 T 都会变成 “ac”。

示例 2:

1
2
3
输入:S = "ab##", T = "c#d#"
输出:true
解释:S 和 T 都会变成 “”。

示例 3:

1
2
3
输入:S = "a##c", T = "#a#c"
输出:true
解释:S 和 T 都会变成 “c”。

示例 4:

1
2
3
输入:S = "a#c", T = "b"
输出:false
解释:S 会变成 “c”,但 T 仍然是 “b”。

提示:

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. ST 只含有小写字母以及字符 '#'

进阶:

  • 你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?

思路

  • 为了实现进阶要求,很明显是用双指针
    • 从字符串尾,同时遍历两个字符串
    • 遇到退格
      • 记录退格数+1
    • 遇到字母
      • 有退格数就继续往前遍历
      • 无退格数就结束循环,比较两个字符串当前字符是否相等
    • 一直遍历到字符串头
  • 结果我自己调试了半天还是WA
image-20201019145219480
  • 最后还是看了下题解,调整了一下代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

题解

正好一个月前刷过,那就直接提交了呗

  • 快慢指针法

  • 详情图解

    leet1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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 的棋盘上,并且使皇后彼此之间不能相互攻击。

img

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回 n 皇后不同的解决方案的数量。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

提示:

  • 皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一或 N-1 步,可进可退。(引用自 百度百科 - 皇后

思路

经典的回溯法例题,和之前做的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来定位皇后的右对角线

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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:

1
2
输入:[-4,-1,0,3,10]
输出:[0,1,9,16,100]

示例 2:

1
2
输入:[-7,-3,2,3,11]
输出:[4,9,9,49,121]

提示:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A 已按非递减顺序排序。

思路

去年提交过的一道题,当时还是偷懒的LYC

python一行用库排序返回新数组,时间复杂度是O(NlogN)

今天用个稍微朴素一点的双指针吧,时间复杂度是O(N)(不过提交之后发现甚至还没排序快)

  • 先遍历一遍数组,找到绝对值最小的数
  • 先把这个数的平方放到ans数组
  • 然后从这个数字开始往两边找
    • 一个left指针,初始值为最小数的索引值-1
    • 一个right指针,初始值为最小数的索引值+1
  • 先往左找,直到找到的数比右边大
    • 边向左找,边把已经找到的数的平方放到ans数组中
  • 再往右找,直到找到的数比左边大
    • 同理,边遍历边存答案
  • 直到两边都走到底
  • 这里要注意,如果左边走到底了,右边直接遍历完就行,左右同理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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. 填充每个节点的下一个右侧节点指针

难度中等

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL

初始状态下,所有 next 指针都被设置为 NULL

示例:

img

1
2
3
4
5
输入:{"$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,继续处理一下层

代码

1
2
3
4
5
6
7
8
9
10
11
12
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:

1
2
输入:["bella","label","roller"]
输出:["e","l","l"]

示例 2:

1
2
输入:["cool","lock","cook"]
输出:["c","o"]

提示:

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100
  3. A[i][j] 是小写字母

思路

今天第一遍写的代码竟然还没有我2年前写的效率高

🙃怎么大三比大一还菜了呢

  • 主要思想
    • 遍历第一个字符串中的不同字母
    • 针对每个字母,找出该字母在所有字符串中出现的最小次数(可能为0)
    • 在答案数组中置入最小次数个该字母
  • 技巧
    • 利用set()去重
    • 利用count()计算出现次数

代码

1
2
3
4
5
6
7
8
9
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
给定 1->2->3->4, 你应该返回 2->1->4->3.

思路

这不是巧了吗,今天的每日一题是国庆刚自己刷过的一道题

image-20201013124401755

发现自己的方法把迭代和递归混在一起写了,今天就优化一下

  • 设置一个dummy哑结点,放在一开始的头节点前面
    • 方便之后返回答案链表的头节点
  • 之后从dummy开始遍历
    • 当前遍历的结点假设是0结点
    • 把0->1->2换成0->2->1
    • 把1作为下一个0,重复上述操作
    • 当0结点之后没有结点,说明交换完毕

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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
2
3
4
5
6
7
8
9
10
11
12
13
输入:

1
\
3
/
2

输出:
1

解释:
最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。

提示:

思路

可恶,我竟然简单题都不会做了

对二叉树的中序遍历还是不太熟悉

因为是二叉搜索树,所以可以看作是有序数组

就是在一个有序数组上求两个数的最小插值

  • 把二叉树转换成数组,然后对排序好的数组求两个数值最小值
  • 直接对二叉树进行递归和迭代求解
    • 用一个pre结点记录当前结点的前一个结点
    • 因为是中序遍历,所以pre结点必定是在当前结点的左边,也就是说root.val>pre.val
    • 所以遍历所有结点,同时更新最小差值即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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. 分割等和子集

难度中等

给定一个只包含正整数非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

1
2
3
4
5
输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

1
2
3
4
5
输入: [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]
    • 这里要保证是从后到前循环的,即jsum/2循环到0
    • 原因是保证判断的时候,用的都是“上一行”的数据,而不是这一行新产生的数据

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:

1
2
3
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

img

示例 2:

1
2
3
输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

img

示例 3:

1
2
3
输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

img

进阶:
你是否可以不用额外空间解决此题?

思路

一开始以为和昨天的一摸一样,后来发现还没那么简单

昨天的题目只要判断是否存在环形链表,今天的要返回环的头节点

最终还是看了大佬的题解,发现原来是数学解法

还是老样子,为了实现常数空间用快慢指针

  • 一开始快慢指针都从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圈
    • 此时两者的位置也正好是入环的头节点

这个方法太妙了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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:

img

1
2
3
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

img

1
2
3
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

img

1
2
3
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos-1 或者链表中的一个 有效索引

思路

  1. 用一个哈希表存储已经访问过的结点
    • 每遍历一个结点,就存入哈希表中
    • 存的时候如果发现哈希表中存在该结点,说明遍历过,返回True
    • 存到最后空指针时没有重复遍历的结点,说明没有环,返回False
  2. 快慢指针遍历链表
    • 慢指针起点为head,快指针起点为head.next
    • 慢指针一次一步,快指针一次两步,相当于追及问题
    • 如果快指针追上了慢指针,说明有环
    • 如果快指针先走到了空指针,说明没有环

代码

就放一个快慢指针的方法吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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:

1
2
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

1
2
输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

思路

  • 设置双指针前后同时开始遍历字符串
  • 边遍历边交换值

代码

1
2
3
4
5
6
7
8
9
10
11
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 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

1
2
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

思路

  • 利用双指针,把0移到前面,把1移到0的后面

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 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

代码

参考的别人的题解,我就不写解题思路丢人了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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,cd ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例:

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

代码

参考了官方题解,前两个数,后两个数用双指针的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 开头。

示例:

1
2
3
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

思路

对整个过程进行模拟

其实这道只考数据结构和代码的细节,其他没啥

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

好家伙,原来我2年前就满足于O(N²)

1年前用JAVA刷了一遍估计是为了当时的期末考试吧

image-20201003090402562

那么这道题到底该怎么做呢?

  • 用哈希表以键值对的形式,存储 值->下标
  • 遍历nums
  • 更新哈希表前,先看看哈希表中有没有满足的值和当前遍历的数加起来为target
    • 如果有就直接返回两个的下标
    • 如果没有就更新哈希表

代码

1
2
3
4
5
6
7
8
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

image-20201002193815926

又经历了一次高考查分

虽然不一定出国了,但是本来是想考满105的

虽然本来是想考满105,但是考试的时候阅读和听力出分26和28,我其实不报啥希望了,甚至还想着能考到100+就不错了

所以104对于我来说已经算比较满意了

好了,来刷题吧

题目

771. 宝石与石头

难度简单

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,JS中的所有字符都是字母。字母区分大小写,因此"a""A"是不同类型的石头。

示例 1:

1
2
输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

1
2
输入: J = "z", S = "ZZ"
输出: 0

注意:

  • SJ 最多含有50个字母。
  • J 中的字符不重复。

思路

image-20201002194244919

一晃已经过了两年了

一开始看见题目限制了S和J最多50个字母,便直接用暴力法,循环两遍,发现速度好慢哦

于是用了哈希表(我用的是字典,不过跟用集合是一个道理)

代码

1
2
3
4
5
6
7
8
9
10
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 仅包含小写字符 ry, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。
出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

示例 1:

输入:leaves = "rrryyyrryyyrr"

输出:2

解释:调整两次,将中间的两片红叶替换成黄叶,得到 “rrryyyyyyyyrr”

示例 2:

输入:leaves = "ryr"

输出:0

解释:已符合要求,不需要额外操作

提示:

  • 3 <= leaves.length <= 10^5
  • leaves 中只包含字符 '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]是不存在这种可能性的,因为第二片叶子最多只能是中段黄色,而不能是后段红色。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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]

9.29

遍历二叉树我还是太菜,今儿个只是非递归的后序遍历我看题解都看了半天

题目

145. 二叉树的后序遍历

难度中等

给定一个二叉树,返回它的 后序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
1
\
2
/
3

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路

老样子,两种解法,一种python写,另一种java写

  • 普通递归

  • 思想就是写一个递归函数,先遍历左子树,再遍历后子树,最后再把结点值放到答案里。

  • 不用理解后序遍历的本质就能写出来的方法

  • 非递归解法

  • 利用栈去存储需要遍历的结点

  • 基本思想就是,先一直向左下遍历,当遍历不下去的时候,再看看右下还有没有

  • 每次记录结点值得时候保证遍历的这个结点右下角没了,或者右下角全部被记录过了

  • 讲不太清。。。直接看代码吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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 postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def postOrder(root):
if not root:
return
postOrder(root.left)
postOrder(root.right)
res.append(root.val)
return
postOrder(root)
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.LinkedList;

class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// stk用来暂存遍历的结点
Deque<TreeNode> stk= new LinkedList<>();
// ans用来存放后序遍历的结果
List<Integer> ans = new ArrayList<>();
stk.push(root);
// prev用来记录上一个遍历完成的结点
TreeNode prev = null;
while(!stk.isEmpty()||root!=null){
// 先把左子树遍历完
while(root!=null){
stk.push(root);
root = root.left;
}
root = stk.pop();
if(root.right == null || root.right == prev){
// 当右子树为空或者右子树已经记录时 记录当前结点的值
ans.add(root.val);
prev = root;
root = null;
}else{
// 右子树非空且没被记录过,就继续遍历右子树
stk.push(root);
root = root.right;
}
}
return ans;
}
}

9.28

题目

117. 填充每个节点的下一个右侧节点指针 II

难度中等

给定一个二叉树

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL

初始状态下,所有 next 指针都被设置为 NULL

进阶:

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例:

image-20201016192008791

1
2
3
输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

提示:

  • 树中的节点数小于 6000
  • -100 <= node.val <= 100

思路

这次的二叉树要用bfs来解

I am so 菜 that I 看题解

老样子,有两种思路,一种用python实现,一种用java实现

空间复杂度O(N)

  • 利用队列进行层序遍历
  • 每次在遍历某一层的时候,设计pre结点来存储上一个遍历的结点(也就是左边最近的结点)
  • 将pre.next设置为当前结点
  • 将pre设置为当前结点
  • 继续向右遍历
  • 向右遍历的同时要把自己的左右子节点放到队列里

空间复杂度O(1)

  • 假设我们已经遍历完第二层,那么此时计算第三层结点的右侧指针时我们可以借助第二层

  • 我们从第二层的最左边结点向右遍历

  • 假设第二层最左边的结点为cur

  • 去判断cur.left和cur.right

  • 用上面的思路,利用pre结点来设置cur.left.next和cur.right.next

  • 然后遍历cur.next,直到遍历完该层

  • 再把cur设置为第三层最左边的结点继续

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from queue import Queue
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""

class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return
# 利用队列实现二叉树的层序遍历
queue = Queue()
queue.put(root)
while not queue.empty():
# level表示这一层的总结点数
level = queue.qsize()
pre = Node()
for i in range(level):
node = queue.get()
# pre为空表示这个结点是这层第一个结点
if pre:
pre.next = node
# 此时的这个节点为下一个结点的pre
pre = node
if node.left:
queue.put(node.left)
if node.right:
queue.put(node.right)
return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/

class Solution {
public Node connect(Node root) {
if(root == null){
return null;
}
Node cur = root;
// cur来记录每层的最左边的结点
while(cur!=null){
// dummy结点方便我们遍历下一层
Node dummy = new Node();
Node pre = dummy;
while(cur!=null){
// 去判断cur的左右子结点
if(cur.left != null){
// 当子节点存在时,就更新pre.next结点和pre结点
pre.next = cur.left;
pre = cur.left;
}
if(cur.right != null){
pre.next = cur.right;
pre = cur.right;
}
cur = cur.next;
}
cur = dummy.next;
}
return root;
}
}

9.27

题目

235. 二叉搜索树的最近公共祖先

难度简单

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

img

示例 1:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

通过次数89,309

提交次数136,007

思路

参考了官方题解知道了两种解法

解法1

  • 分别找到根节点到达p的路径path_q和根节点到达q的路径path_q
  • 从头开始遍历两个路径,当path_q[i] != path_p[i]时,遍历的上一个结点就是分叉点

解法2

  • 从root开始遍历整棵树
  • 如果root.val<p.val且root.val<q.val,就往root的右边去找分叉点
  • 如果root.val>p.val且root.val>q.val,就往root的左边去找分叉点
  • 如果都不满足,说明此时p在root的左子树,q在root的右子树,root就是分叉点

代码

  • java写的解法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pathToP = getPath(root, p);
List<TreeNode> pathToQ = getPath(root, q);
TreeNode ans = new TreeNode();
for(int i = 0;i<pathToP.size() && i<pathToQ.size();i++){
if (pathToP.get(i)==pathToQ.get(i)){
ans = pathToP.get(i);
}else{
break;
}
}
return ans;
}
private List<TreeNode> getPath(TreeNode root, TreeNode target){
List<TreeNode> path = new ArrayList<>();
while(root!=target){
path.add(root);
if(root.val>target.val){
root = root.left;
}else{
root = root.right;
}
}
path.add(root);
return path;
}
}
  • python用的是解法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
cur = root.val
if cur<p.val and cur<q.val:
root = root.right
elif cur>p.val and cur>q.val:
root = root.left
else:
return root

9.26

托福考完了,总分估计不太行,不过估计也不准备考第二次了吧

考试真的紧张死,然后还是碰到了听力加试,结果没想到听力比阅读高

来刷题放松一下吧

题目

113. 路径总和 II

难度中等

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22

1
2
3
4
5
6
7
      5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

返回:

1
2
3
4
[
[5,4,11,2],
[5,8,4,5]
]

思路

老回溯法了

还是比较轻松的,虽然提交的时候WA了四次

或者说叫dfs?

  • 向下遍历
  • 如果是空结点,直接return
  • 如果不是叶节点,自动继续向下遍历,同时在已遍历的路径中加入该结点的值,目标值减去该结点的值
  • 如果是叶节点,同时节点值就等于当前需要的target,就把这条路径放到答案里

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
ans = []
if not root:
return ans
def isLeave(root):
if root and not root.left and not root.right:
return True
else:
return False
def findPath(path, target, root):
if not root:
return
if not isLeave(root):
findPath(path+[root.val], target-root.val, root.left)
findPath(path+[root.val], target-root.val, root.right)
elif root.val == target:
ans.append(path+[root.val])
findPath([], sum,root)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
cur = root.val
if cur<p.val and cur<q.val:
root = root.right
elif cur>p.val and cur>q.val:
root = root.left
else:
return root

9.24

大概是放弃出国了,但是周六托福还得好好考啊,毕竟是2k块钱呢呜呜呜

今天不知道是睡多了还是什么,头很痛

题目

501. 二叉搜索树中的众数

难度简单197

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

例如:
给定 BST [1,null,2,2],

1
2
3
4
5
1
\
2
/
2

返回[2].

提示:如果众数超过1个,不需考虑输出顺序

**进阶:**你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

代码

没能实现常数空间,只是用了中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def findMode(self, root: TreeNode) -> List[int]:
answer = []
last = 0
cnt = 0
maxCount = 0
def inorder(root):
nonlocal last, cnt, maxCount, answer
if not root:
return 0
if root.left:
inorder(root.left)
if root.val == last:
cnt += 1
else:
cnt = 1
if cnt == maxCount:
answer.append(root.val)
elif cnt>maxCount:
maxCount = cnt
answer=[root.val]
last = root.val
if root.right:
inorder(root.right)
inorder(root)
return answer

9.23

好累,痒痒鼠好非

题目

617. 合并二叉树

难度简单497

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7

注意: 合并必须从两个树的根节点开始。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1:
return t2
if not t2:
return t1
cur = TreeNode(t1.val + t2.val)
left = self.mergeTrees(t1.left,t2.left)
right = self.mergeTrees(t1.right, t2.right)
cur.left, cur.right = left, right
return cur

9.21

周六考托福啦,这周就不写题解了,直接上代码吧

题目

538. 把二叉搜索树转换为累加树

难度简单

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

1
2
3
4
5
6
7
8
9
输入: 原始二叉搜索树:
5
/ \
2 13

输出: 转换为累加树:
18
/ \
20 13

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
def addKids(root):
nonlocal total
if root:
addKids(root.right)
total += root.val
root.val = total
addKids(root.left)
total = 0
addKids(root)
return root

9.20

又是美好的周日,双休日就多刷点题吧(不过题解我就懒得多写了)

题目

78. 子集

难度中等759

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

**说明:**解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

题解

经典老番

  • 数组
  • 所有可能的子集

dfs嘛,这道题甚至还不用剪枝

看到不重复就知道dfs函数里面肯定有一个参数去决定循环开始的位置

直接上代码

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(nums, path, begin):
res.append(path)
if len(path) == len(nums):
return
for i in range(begin, len(nums)):
dfs(nums, path + [nums[i]], i+1)
dfs(nums, [], 0)
return res

改成java改的我头大,果然还是太菜了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
dfs(nums, res, 0, path);
return res;
}
private void dfs(int[] nums, List<List<Integer>> res, int begin, ArrayList<Integer> path){
res.add(new ArrayList<>(path));
if(nums.length == path.size()){
return;
}
for(int i = begin;i<nums.length;i++){
path.add(nums[i]);
dfs(nums, res, i+1, path);
path.remove(path.size()-1);
}

}
}

9.19

leetcode的周六,i了i了

题目

404. 左叶子之和

难度简单

计算给定二叉树的所有左叶子之和。

示例:

1
2
3
4
5
6
7
3
/ \
9 20
/ \
15 7

在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

题解

  1. 遍历所有节点
  2. 把所有自己本身是左子节点且自己没有子节点的节点加起来

总结:万能的dfs

这边用了一个flag位去判断该节点是不是左子节点,这么写的话递归过程比较好理解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
def findAndAdd(root, flag):
if not root:
return 0
if flag and root and not root.left and not root.right:
return root.val
return findAndAdd(root.left, True) + findAndAdd(root.right, False)
return findAndAdd(root, False)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// java就是单纯的翻译一遍上面的代码
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return add(root, false);
}

private int add(TreeNode root, boolean flag){
if(root == null){
return 0;
}
if(flag && root.left == null && root.right == null){
return root.val;
}
return add(root.left, true)+add(root.right, false);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
dfs(nums, res, 0, path);
return res;
}
private void dfs(int[] nums, List<List<Integer>> res, int begin, ArrayList<Integer> path){
res.add(new ArrayList<>(path));
if(nums.length == path.size()){
return;
}
for(int i = begin;i<nums.length;i++){
path.add(nums[i]);
dfs(nums, res, i+1, path);
path.remove(path.size()-1);
}

}
}

9.18

人在图书馆 很困 想睡 晚安

题目

47. 全排列 II

难度中等

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

题解

跟组合一样,这道题还是老方法,回溯法

不断地递归去求排列的可能性

区别在于剪枝的方法

1
2
3
if not used[i]:
if i>0 and nums[i] == nums[i-1] and not used[i-1]:
continue

就拿题目里的[1, 1, 2]来举例说明吧

  1. 一开始我选第一个1
    • 接下来我选1
      • 由于只剩下一个2,所以构成[1,1,2]
    • 接下来我选2
      • 由于只剩下一个1,所以构成[1,2,1]
  2. 一开始我选第二个1
    • 这时我们知道其实这种条件下是跟上面一摸一样的,因为两个数字相同嘛
    • 那么这种就没有必要继续递归求解
    • 这种条件具体就是指
      • 我现在选的这个数字已经在上一个分支里出现过
      • 也就是nums[i] == nums[i-1]
      • 同时我还要保证这个分支里,没有继续选上一个数 not used[i-1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
if len(nums) == 0:
return []
def dfs(nums, depth, used, path,res):
if depth == len(nums):
res.append(path.copy())
return
for i in range(len(nums)):
if not used[i]:
if i>0 and nums[i] == nums[i-1] and not used[i-1]:
continue
path.append(nums[i])
used[i] = 1
dfs(nums, depth+1, used, path, res)
used[i] = 0
path.pop()


res = []
used = [0 for i in range(len(nums))]
dfs(nums, 0, used, [], res)
return res

9.17

人傻了,到图书馆一看,发现是困难题

看完题目,发现是图论,得,咱直接看题解好了

685. 冗余连接 II

难度困难

在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。

输入一个有向图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

结果图是一个以组成的二维数组。 每一个 的元素是一对 [u, v],用以表示有向图中连接顶点 u 和顶点 v 的边,其中 uv 的一个父节点。

返回一条能删除的边,使得剩下的图是有N个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

示例 1:

1
2
3
4
5
6
7
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
1
/ \
v v
2-->3

示例 2:

1
2
3
4
5
6
7
输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
^ |
| v
4 <- 3

注意:

  • 二维数组大小的在3到1000范围内。
  • 二维数组中的每个整数在1到N之间,其中 N 是二维数组的大小。

题解

看完weiwei大佬的题解,发现自己好菜

题目的意思就是说现在给了你很多根边,要求是删除一根边,让剩下边拼到一块儿就是一个有根树

那怎么需要删除的边呢?

说到底无非就是

  • 删一条边
  • 看剩下的边能不能成树

那大佬总结出来怎么删的边的可能性有

  • 删掉一条入度为2的边,看还会不会构成回路
  • 删掉一条入度为1的边,看还会不会构成回路

那么具体要做的看上去有两件事

  • 统计每条边的入度
  • 判断删掉某条边后,是否会构成回路

那么判断回路还需要用到一种算法,叫做并查集。

可以参考这篇文章,特别好懂

https://blog.csdn.net/qq_41593380/article/details/81146850

简单来说并查集就是用来快速查找某个点的根节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int len = edges.length;
// 先记录所有点的入度
int[] inDegree = new int[len+1];
for(int[] edge:edges){
inDegree[edge[1]]++;
}
for(int i = len-1;i >= 0;i--){
if(inDegree[edges[i][1]] == 2){
// 尝试删除入度为2的边
if(!judgeCircle(edges,len,i)){
// 删除该边后如果不形成环,说明就是要删除的那条变
return edges[i];
}
}
}
for(int i = len-1;i>=0;i--){
if(inDegree[edges[i][1]] == 1){
// 尝试删除入度为1的边
if(!judgeCircle(edges,len,i)){
// 同理,删除后不成环就返回边
return edges[i];
}
}
}
return new int[0];
}

private boolean judgeCircle(int[][] edges, int len, int remove){
UnionFind unionFind = new UnionFind(len+1);
// 尝试删除某条边之后 判断是否成环
for(int i = 0;i<len;i++){
if (i == remove){
continue;
}
if(!unionFind.union(edges[i][0], edges[i][1])){
// 如果合并失败,说明edges[i][0]和edges[i][1]在一个联通分量离
return true;
}
}
return false;
}

private class UnionFind{
private int[] parent;

public UnionFind(int n){
parent = new int[n];
for(int i = 0;i<n;i++){
parent[i] = i;
}
}

public int find(int x){
while(x!=parent[x]){
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

public boolean union(int x, int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY){
return false;
}
parent[rootX] = rootY;
return true;
}
}
}

9.16

ohhhhh,又是简单题,赶快刷完去刷托福了

题目

226. 翻转二叉树

难度简单

翻转一棵二叉树。

示例:

输入:

1
2
3
4
5
4
/ \
2 7
/ \ / \
1 3 6 9

输出:

1
2
3
4
5
4
/ \
7 2
/ \ / \
9 6 3 1

题解

思路很简单,用一个递归函数去把每个节点的左子树和右子树交换一下就完事儿了

唯一需要提的就是python的代码会跟java的有点不一样

python属于自顶向下的,java属于自底向上的。

因为python可以直接root.left, root.right = root.right, root.left

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return root;
}else{
TreeNode left = invertTree(root.right);
TreeNode right = invertTree(root.left);
root.left = left;
root.right = right;
}
return root;
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
def reverse(root):
if not root:
return
root.left, root.right = root.right, root.left
reverse(root.left)
reverse(root.right)
reverse(root)
return root

9.15

今天是困难题,有点懵

不过幸好今天没课

题目

37. 解数独

难度困难

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

img

一个数独。

img

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.'
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

题解

首先确定我们的方法,回溯法

基本思路就是

  • 根据当前的棋盘,在一个空格内填入可能的数字
  • 在填入一个可能的解后,继续在下一个空格内填入可能的数字
  • 若填入当前数字后发现没有下一个能填入的数字,就退回上一步,在该空格内填另一个可能的数字(回溯法的关键思想)
  • 直到将所有空格填满

我们根据数独的三个规则找到填入数字的可能性

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

如何快速判断某一个格子能填几呢?针对三个规则,定义三个数组

  1. row数组,用来检查每行的数字的出现情况
    • row[i][j]=1代表了第i+1行出现过j+1这个数字
  2. col数组,用来检查每列的数字的出现情况
    • col[i][j]=1代表了第i+1列出现过j+1这个数字
  3. block数组,用来检查九个九宫格内数字的出现情况
    • block[i/3][j/3][k]=1代表了第i/3行,第j/3的九宫格内出现过k+1这个数字

如何知道哪些空格需要填呢?

  • 建立一个动态数组spaces,一开始遍历棋盘找到所有空格,以[i,j]的格式放入spaces中

解数独具体的流程

  1. 遍历一遍当前棋盘,初始化row,col,block,spaces数组
  2. 对整个棋盘进行递归求解
    1. 如果此时已经没有空格可以填入,则退出循环,找到解
    2. 否则就找到需要填的空格,尝试将1-9其中满足规则的填入空格并更新三个数组
    3. 在调用递归函数之后,要把当前填入的整个数字给去掉,并还原三个数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
// row[i][j] 用来记录第i+1行有没有出现过j+1这个数字
private int[][] row = new int[9][9];
// col[i][j] 用来记录第i+1列有没有出现过j+1这个数字
private int[][] col = new int[9][9];
// block[i][j][k] 用来记录第i+1行第j+1列的这个九宫格内是否出现过k+1这个数字
private int[][][] block = new int[3][3][9];
// spaces中的第i个数组[i,j]用来存储的是第i+1行,j+1列这个方格是否为空
private List<int[]> spaces = new ArrayList<>();
// valid用来判断数独是否已经完成
private boolean valid = false;
public void solveSudoku(char[][] board) {
for(int i = 0;i<9;i++){
for(int j = 0;j<9;j++){
if(board[i][j] == '.'){
spaces.add(new int[]{i,j});
}else{
int num = board[i][j] - '1';
row[i][num] = col[j][num] = block[i/3][j/3][num] = 1;
}
}
}
dfs(board,0);
}

private void dfs(char[][] board, int index){
if(index == spaces.size()){
valid = true;
return;
}else{
int cur_i = spaces.get(index)[0];
int cur_j = spaces.get(index)[1];
for(int num = 1; num <= 9 && !valid;num++){
if(row[cur_i][num-1]==0 && col[cur_j][num-1]==0 && block[cur_i/3][cur_j/3][num-1]==0){
row[cur_i][num-1] = col[cur_j][num-1] = block[cur_i/3][cur_j/3][num-1] = 1;
board[cur_i][cur_j] = (char)(num+ '0');
dfs(board, index+1);
row[cur_i][num-1] = col[cur_j][num-1] = block[cur_i/3][cur_j/3][num-1] = 0;
}
}
}
}
}

9.14

三天的数模竞赛终于结束了,头发掉光,疯狂爆痘,人快猝死了

算是见到了凌晨三点的苏大,24小时内只吃了一顿饭,已经没空去饿了

努力了 尝试了 尽力了 也可以说这次就算理想不结果也是问心无愧了

image-20200914130951082

终于又回到了leetcode的怀抱

在研究了三天热学,整数规划,机理模型,从数学建模到语文建模后

今天的ta用美好的二叉树来欢迎我,我简直感动到热泪盈眶

题目

94. 二叉树的中序遍历

难度中等

给定一个二叉树,返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题解1

首先用递归来解,很简单

中序遍历就是写一个递归,然后在递归函数内对结点的处理顺序就是先左结点,再父节点,最后右结点

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return ans

题解2

然后用java写一个非递归的

参考了官方题解,简单来说就是用stack来模拟递归

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 * Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new LinkedList<>();
while(!stk.isEmpty() || root!=null){
while(root != null){
stk.push(root);
root = root.left;
}
root = stk.pop();
ans.add(root.val);
root = root.right;
}
return ans;
}
}

9.10

题目

40. 组合总和 II

难度中等

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

  • 所有数字(包括目标数)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

题解

总体上跟昨天的每日一题差不多

思路都是利用dfs或者说回溯法,逐个可能性递归求解

唯一的区别就是,昨天是可以重复的,今天是不能重复的

  • java我使用的依然是昨天的方法,只是更改了一下每次递归时begin的位置,昨天是从原数字开始,今天从原数字后面一个开始递归(因为每个数字只能用一次)
  • python的话我尝试了使用哈希表(字典)来记录数字出现的次数,然后在遍历时候先把数组去重。最后在回溯的时候去增删这个数字出现的次数,来保证每个数字不会被重复使用

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.nio.file.Path;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;

class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, target, 0, ans, path);
return ans;
}

public void dfs(int[] candidates, int target, int begin, List<List<Integer>> ans, Deque<Integer> path){
if(target == 0){
ans.add(new ArrayList<>(path));
}else{
for(int i = begin;i<candidates.length;i++){
if(candidates[i] > target){
break;
}else if(i > begin && candidates[i] == candidates[i-1]){
continue;
}else{
path.addLast(candidates[i]);
dfs(candidates, target-candidates[i], i+1, ans, path);
path.removeLast();
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates_set = list(set(candidates))
dic = dict()
for i in candidates_set:
dic[i] = candidates.count(i)
def dfs(nums, target, begin):
if target == 0:
ans.append(nums)
else:
for i in range(begin,len(candidates_set)):
num = candidates_set[i]
if not dic[num]:
continue
elif num>target:
return
else:
dic[num] -= 1
dfs(nums+[num],target-num,i)
dic[num] += 1
dfs([], target,0)
return ans

9.9

题目

39. 组合总和

难度中等884

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入:candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

提示:

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

题解

一看题目就知道,深搜肯定好用

那么首先要考虑的是递归函数的参数也就是,dfs(?)

  • 首先肯定得有一个列表去存放目前为止已经被加起来的数,那就先设定为nums吧

  • 同时为了避免每次递归时都要求一次数组nums的和,还得有一个变量存储当前nums的和,就叫它cur_sum吧

  • 假设我们就用这两个显然的参数来写递归

    • 考虑出递归的条件,很简单,有两种
      1. cur_sum > target
      2. cur_sum == target
    • 其中第一种情况因为此时不管再怎么往nums里加数字都不可能成立,所以直接return
    • 第二种情况,nums数组属于题目要求的组合,就把nums数组放到ans数组中,然后return
  • 除此之外,就是cur_sum < target了

    • 这个时候很容易想到,去遍历一遍candidates数组中所有的数字,添加到nums数组里试一下就好了

      • 此时可以有一个剪枝的小办法,先判断cur_sum加上这个数字是不是小于等于target

      • 如果小于等于,就继续搜

      • 反之,就不用dfs了

    • 但是这样操作下来有一个问题

      • 例如candidates = [2, 3], target = 8
      • 那么最后答案中会出现[2,2,3], [2,3,2], [3,2,2]
      • 为什么呢?因为我们每次深搜的时候都是把整个nums数组遍历一遍,自然会出现不同顺序同样数字的组合
      • 怎么解决呢?
    • 增加一个变量begin,用来存储每次遍历开始的位置

      • 用这个变量来保证每次我遍历数组,去尝试各个可能性的时候都是从至少当前数字开始往后
      • 由于题目给的candidates是从小到大排序的,所以就绝对不会出现[2,3,2]这种组合了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
# 存放答案
def dfs(nums,cur_sum, begin):
# 递归深搜
if cur_sum > target:
return
elif cur_sum == target:
ans.append(nums)
else:
for i in range(begin,len(candidates)):
cur_num = candidates[i]
if cur_sum+cur_num <= target:
dfs(nums+[cur_num], cur_sum+cur_num, i)
return
dfs([],0,0)
return ans

9.8

又到了愉快(并不)的刷题时间啦

77. 组合

难度中等

给定两个整数 nk,返回 1 … n 中所有可能的 k 个数的组合。

示例:

1
2
3
4
5
6
7
8
9
10
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

题解1

一种解法是比较巧妙的结合了数学归纳法,评论里的大佬是真滴强

  • 利用C(m,n) = C(m-1,n) + C(m-1,n-1),使用递归的方式

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if k>n or k == 0:
return []
if k == 1:
return [[i] for i in range(1,n+1)]
if k == n:
return [i for i in range(1,n+1)]

answer = self.combine(n-1,k)
for i in self.combine(n-1,k-1):
i.append(n)
answer.append(i)

return answer

题解2

这种解法就非常朴实无华,总结就是dfs加剪枝

  • 举个例子,例如n=5,k=3

  • 现在我的path中存放了1,2,那么我要怎么找到第三个数呢?

  • 通过循环,begin值设为3,然后递增1,每次循环的时候把对应的值加到path中,最后在回溯的时候要把这个加进去的值remove掉

  • 会有一个什么样的过程呢?

    • i = begin = 3
    • path.add(3)
    • 此时执行dfs
    • 发现path的长度等于3,所以res.add(path)
    • 然后这个时候又回到path.add(3)之后
    • 因为3已经被用过了,就把3remove掉,继续循环
    • 这一次 i = 4,重复以上步骤
  • 可能有点难理解,直接看代码好了

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
public List<List<Integer>> combine(int n, int k) {
// res存放结果,path存放在递归过程中的临时数组
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
if(k<=0 || k>n){
return res;
}
dfs(n, k, 1, path, res);
return res;
}

private void dfs(int n, int k,int begin, Deque<Integer> path, List<List<Integer>> res){
if(path.size() == k){
// 当path中有k个元素时就把path加入到结果中
res.add(new ArrayList<>(path));
}else{
// 这里处理剪枝时可以注意到i<=n其实是一个过于宽泛的条件
// 例如n=15,k=4,path里已经有了两个数,接下来还要选择两个数
// 搜索的起点begin值最大就是14,最后一个被选的是[14,15]
// 也就是说i<=15条件过大,应该是i<=14,这里的14 = n-(k-path里已经有的元素数) + 1
for(int i = begin;i<=n-(k-path.size())+1;i++){
path.addLast(i);
dfs(n, k, i+1, path, res);
// 每次回溯都需要把那个加进去的值删掉再继续循环
path.removeLast();
}
}
}
}

9.7

开学第一天哦,题目不算难噢(好尬)

题目

347. 前 K 个高频元素

难度中等

给定一个非空的整数数组,返回其中出现频率前 *k* 高的元素。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

提示:

  • 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
  • 你可以按任意顺序返回答案。

题解

首先题目要求返回的是出现频率的前k个元素,那这个出现频率首先肯定得求出来对不对。

那么题目还要求时间复杂度要由于N log N,那么直接用两层循环去求每个元素的次数(python里的count方法)肯定是不满足的。(是N²了)

那就用字典嘛,或者说哈希表。

dic[i]=x,这里的i是nums数组中的数字,x是i在数组nums中出现的总次数。

循环一遍nums,遇到一个i就把dic[i]+1。

求出了出现次数之后怎么办呢,要找到前k个。

这里就有两种方法了

  • 一种是死办法,把所有的数字根据出现次数,直接排序,虽然是 N log N不过也能通过呢。(代码见下python)

  • 一种是稍微巧妙一点的办法,建小顶堆,也就是说堆顶的那个元素的值一定是堆中最小的。

    • 把哈希表中所有的键值对一个一个丢到堆里。
    • 如果堆里面装的个数小于k(题目中要求返回出现次数排序前k个的元素),就直接丢到堆里
    • 如果堆的个数等于k了,就检查这个键对应value是否比堆顶的value大,如果更大,就把堆顶的丢掉,把新的一个键值对塞进堆里
    • 要注意,塞进去的同时要能够保证堆顶的值一直是最小的

代码

python是纯自己写,但是java的由于学术不精,只会语法,库和包都不会用,就剽的大佬的。

大佬的题解

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dic = dict()
for i in nums:
if not dic.get(i):
dic[i] = 1
else:
dic[i] += 1
nums = list(set(nums))
nums.sort()
cnts = []
for i in nums:
if dic[i]:
cnts.append([i,dic[i]])
cnts.sort(key = lambda d:d[1], reverse = True)
ans = [(cnts[i][0]) for i in range(k)]

return ans

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)){
map.put(num, map.get(num)+1);
}else{
map.put(num,1);
}
}
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return map.get(a)-map.get(b);
}
});
for(Integer key : map.keySet()){
if (pq.size() < k){
pq.add(key);
} else if (map.get(key) > map.get(pq.peek())){
pq.remove();
pq.add(key);
}
}
int[] res = new int[k];
int i = 0;
while(!pq.isEmpty()){
res[i++] = pq.remove();
}
return res;
}
}

9.6

题目

107. 二叉树的层次遍历 II

难度简单

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
3
/ \
9 20
/ \
15 7

返回其自底向上的层次遍历为:

1
2
3
4
5
[
[15,7],
[9,20],
[3]
]

题解

看到难度是简单就松了一口气

果不其然, 今天的题目也算是对一年前的数据结构的复习吧,还记得当时老师只要求画图,不要求具体的代码

这次就来试试看吧

一看到二叉树就想到了递归

由于个人对于dfs比较熟悉,就直接写了一个dfs递归解法

  • 用res来存储最终结果
  • 当遍历到新的一层的时候(也就是depth>=res数组的长度的时候),就往res里append一个空列表用于存储新的一层的结点值
  • 同时往该结点对应那一层的列表里(res[depth])append结点的值
  • 对该结点的左子节点和右子节点重复以上工作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
res = []
def dfs(root, depth):
if not root:
return
if len(res)<depth+1:
res.append([])
res[depth].append(root.val)
dfs(root.left, depth+1)
dfs(root.right, depth+1)
dfs(root,0)
return res[::-1]

9.5

又到新学期啦(上学期啥都没学就过去了,暑假也跟飞一样地过去了)

事不宜迟开始刷题吧,毕竟不管是为了实习,还是为了读研,还是为了申请出国的项目,刷题都是血赚。

题目

60. 第k个排列

难度中等

给出集合 [1,2,3,…,*n*],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

给定 nk,返回第 k 个排列。

说明:

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1, n!]。

示例 1:

1
2
输入: n = 3, k = 3
输出: "213"

示例 2:

1
2
输入: n = 4, k = 9
输出: "2314"

题解

给定两个数字,一个n是数字的位数,一个k意思是返回所有排序中第k大的那个排序。

思路也不难理解,位数从大到小开始考虑。

举个例子就能明白,就拿示例二来讲。

1
2
输入: n = 4, k = 9
输出: "2314"
  • n=4,k=9,我们第一个要考虑的是千位数;

  • 由于是从小到大的全排列,而且我们有1 2 3 4,这四个数字;

  • 那么很显然全排列中一开始一定是一些1XXX,然后是2XXX,然后是3XXX,最后是4XXX,其中每个数字开头的排列数肯定是相同的;

  • 每个数字开头有多少种排列呢?

    • 1XXX有 $3!=3\times2\times1=6$种
    • 同样2XXX,3XXX,4XXX也都是每个6种
  • 有了这个,加上k=9,我们就知道,我们要找的排列肯定是2开头的,因为(9/6)向上取整=2

  • 当我们找到这个千位数字之后,我们就要继续找百位数了,方法跟千位数一样。循环n次即获得最终答案。

  • 有一个点需要注意的就是,我们用一个数组nums去存储我们排列中可能的数字,当取用其中一个数字之后,要把它在数组中删掉

代码

部分命名习惯及语法可能有所欠缺,望指出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def getPermutation(self, n: int, k: int) -> str:
def fac(n):
res = 1
for i in range(1,n+1):
res *= i
return res

nums = [i for i in range(1,n+1)]
res = ""
for i in range(n-1,-1,-1):
# 1.找出对应位数-1的阶乘
# 2.比如找n = 3, k = 3时,一开始就是 (3-1)! = 2
# 说明有2个百位为1的,2个百位为2的,2个百位为3的数字
# 3.因为我们要找的是第3个,按小到大排就是百位为2的
# 4.然后我们就把第2个数字就nums数组中删掉
# 5.后面的数字从第一步开始重复,直到nums数组为空
cur_fac = fac(i)
ind = math.ceil(k/cur_fac)
if k>cur_fac:
k %= cur_fac
cur_num = nums[ind-1]
res += str(cur_num)
nums.remove(cur_num)
return res

执行结果:

执行用时:32 ms, 在所有 Python3 提交中击败了98.22%的用户

内存消耗:13.7 MB, 在所有 Python3 提交中击败了46.33%的用户