10.31

python选手的福音来了

题目

381. O(1) 时间插入、删除和获取随机元素 - 允许重复

难度困难

设计一个支持在平均 时间复杂度 O(1) 下**,** 执行以下操作的数据结构。

注意: 允许出现重复元素。

  1. insert(val):向集合中插入元素 val。
  2. remove(val):当 val 存在时,从集合中移除一个 val。
  3. getRandom:从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 初始化一个空的集合。
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)

image-20201031101705654

于是乎又用数组+哈希表来优化解法,接下来针对每种操作讲解一下

  • 初始化

    • 新建一个空数组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)

    image-20201031102903759

10.30

昨天晚上九点多买完kfc发现自行车钥匙丢了

结果就推到了修车摊,人走回的学校

今天刚走去修车摊把我的车锁换了

累死了

不过leetcode这道题确实简单

题目

463. 岛屿的周长

难度简单300

给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。

网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 :

1
2
3
4
5
6
7
8
9
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

输出: 16

解释: 它的周长是下面图片中的 16 个黄色的边:

img

思路

  • 先算出所有陆地方格的边总数
    • 陆地方格数*4
  • 然后遍历每个陆地方格的四周,去掉重复计算的边

代码

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 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
4
5
6
7
8
9
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此,数字总和 = 12 + 13 = 25.

示例 2:

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

思路

也没啥好讲的,就递归深搜求解呗

搜到底的时候就记录一下值

代码

  • 我的丑陋代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)
  • 大佬的优美递归
1
2
3
4
5
6
7
8
9
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:

1
2
3
输入:arr = [1,2,2,1,1,3]
输出:true
解释:在该数组中,1 出现了 3 次,2 出现了 2 次,3 只出现了 1 次。没有两个数的出现次数相同。

示例 2:

1
2
输入:arr = [1,2]
输出:false

示例 3:

1
2
输入: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}
    • 然后判重

    其实就是一个道理

代码

1
2
3
4
5
6
7
8
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
2
3
4
5
6
7
8
输入: [1,null,2,3]  
1
\
2
/
3

输出: [1,2,3]

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

思路

就不用递归写了,没啥技术含量

练习一下迭代吧

常规解法

  • 利用栈的后进先出的特性,来实现先左后右

  • 初始化栈,将根节点存入栈

  • 从栈中pop出一个结点

    • 然后把这个结点的值存储ans数组中
    • 把该节点的右子结点push到栈中
    • 把该节点的左子节点push到栈中
    • 直到栈为空

模板解法

  • 初始化栈
  • 令cur结点为根节点
  • 当栈非空或cur结点非空时继续循环
    • 将cur结点的值存入ans数组
    • 把cur和它所有的左子结点都push到栈里
    • 然后从栈顶取出一个结点
      • 这个结点我们知道一定是最左下角的一个
    • 将cur设为该节点的右子结点

代码

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

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

1
2
输入:nums = [6,5,4,8]
输出:[2,1,0,3]

示例 3:

1
2
输入:nums = [7,7,7,7]
输出:[0,0,0,0]

提示:

  • 2 <= nums.length <= 500
  • 0 <= 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
      
      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

      - 上一种思路的时间复杂度是`O(NlogN)`,空间复杂度是`O(N)`

      - 看了官方题解的计数法重新写了一下(虽然也用了python的特性)

      - 数字出现的值域是固定的`[1,100]`
      - 建立一个长度为101的`cnt`数组去记录每个数字出现的次数
      - 遍历数组`nums`,`cnt[num]+=1`
      - 然后因为要计算的是比某个数字小的数出现的次数
      - 所以要对cnt数组做一次前缀和
      - 每个数加上所有在它左边的数
      - 最后`cnt[i]`就是比`i`这个数小的数字出现次数
      - 遍历`nums`,找到答案

      **代码**

      ```python
      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

还是比原来方法快很多的

image-20201026092115525

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:

1
2
3
输入:[2,1,4,7,3,2,5]
输出:5
解释:最长的 “山脉” 是 [1,4,7,3,2],长度为 5。

示例 2:

1
2
3
输入:[2,2,2]
输出:0
解释:不含 “山脉”。

提示:

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

思路

  • diffs数组去记录A[i]-A[i-1]的值
  • 找到最长的山脉也就是找到最长的[+,+,+,....,-,-,-,]的数组长度+1
  • 这个数组满足数组的前半部分都是正数,后半部分都是负数
  • 要保证前半部分和后半部分的个数都大于0

代码

今天代码写的很烂,建议直接忽略

一道中等题WA了将近10次才Pass我也太菜了吧

image-20201025132211962
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
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:

1
2
3
4
5
6
7
输入: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:

1
2
3
4
输入:clips = [[0,1],[1,2]], T = 5
输出:-1
解释:
我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 3:

1
2
3
4
输入: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:

1
2
3
4
输入:clips = [[0,4],[2,8]], T = 5
输出:2
解释:
注意,你可能录制超过比赛结束时间的视频。

提示:

  • 1 <= clips.length <= 100
  • 0 <= clips[i][0] <= clips[i][1] <= 100
  • 0 <= T <= 100

思路

题目序号是1024呢,标了中等但其实很简单,没啥算法和数据结构

  • 一开始设定start, end = -1, 0用来记录上一次的剪辑片段
  • 就是很纯粹的贪心法,不断地找最长的片段拼到一起
    • 每次找的片段的开始时间必须早于上一个片段的结束时间,同时还必须晚于上一个片段的开始时间
    • 同时结束时间要比上一个片段的结束时间晚
    • 然后保证每次找到的片段的结束时间是合法片段中能最晚结束的

代码

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

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

思路

  • O(n) 空间复杂度
    • 用数组nums存下每个结点值,利用切片操作直接返回nums == nums[::-1]
  • O(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 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:

1
2
3
4
5
6
输入: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
    • 直到把这个字符串全部划分完
  • 怎么判断区间是否合理呢?

    1. 首先需要使用哈希表或数组去记录每个字母出现的最后的位置

    2. 针对S[start, end]

      • 我们知道当这个区间里的每个字母i的最右位置right_i <= end的时候
      • 这个区间就是合理的
      • 又因为是采取了贪心策略,要保证这个区间最小
      • 所以这个end必定是对应了这个区间中某个字母k的最右位置right_k
      • 且这个right_k一定是这个区间里的所有字母的最右位置right_i的最大值
    3. end == right_k,就进行划分,并继续划分下一个区间

    4. 如果end != right_k,就令right_k = max(right_k, right_S[end])

  • 大概理解思路就行,看代码就懂了

代码

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

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]