2021年2月刷题日志
2.28
题目
896. 单调数列
难度简单89
如果数组是单调递增或单调递减的,那么它是单调的。
如果对于所有
i <= j
,A[i] <= A[j]
,那么数组A
是单调递增的。 如果对于所有i <= j
,A[i]> = A[j]
,那么数组A
是单调递减的。当给定的数组
A
是单调数组时返回true
,否则返回false
。示例 1:
1
2 输入:[1,2,2,3]
输出:true示例 2:
1
2 输入:[6,5,4,4]
输出:true示例 3:
1
2 输入:[1,3,2]
输出:false示例 4:
1
2 输入:[1,2,4,5]
输出:true示例 5:
1
2 输入:[1,1,1]
输出:true提示:
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
思路
遍历数组,利用flag
记录下当前的趋势(递增 1,递减 -1,或者全都一样 0)
若当前的趋势和flag
的趋势相反,即之前为递增现在递减,或者之前递减现在递增,就说明不单调。
反之,到最后没有出现不同趋势,则说明单调。
代码
1 | /** |
2.26
题目
395. 至少有K个重复字符的最长子串
难度中等
找到给定字符串(由小写字符组成)中的最长子串 *T* , 要求 *T* 中的每一字符出现次数都不少于 k 。输出 *T* 的长度。
示例 1:
1
2
3
4
5
6
7 输入:
s = "aaabb", k = 3
输出:
3
最长子串为 "aaa" ,其中 'a' 重复了 3 次。示例 2:
1
2
3
4
5
6
7 输入:
s = "ababbc", k = 2
输出:
5
最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。
思路
分治法,根据字母的出现次数,找到出现次数小于k的字母,将字符串进行分割。
例如s = 'aaabbbbccbaaaadbbb', k = 3
,第一次会把s
分割成三段'aaabbbb','baaaa'(事实上),'bbb'
。
然后需要对子串也进行同样地切割,保证子串中所有字母的出现次数大于等于k
,例如上面的baaaa
就会被分割成aaaa
。
最后就能知道最大字串长度为7
,即aaabbbb
子串的长度。
代码
参考的一个大佬的分治法代码
1 | class Solution: |
2.25
题目
867. 转置矩阵
难度简单163
给你一个二维整数数组
matrix
, 返回matrix
的 转置矩阵 。矩阵的 转置 是指将矩阵的主对角线翻转,交换矩阵的行索引与列索引。
示例 1:
1
2 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[[1,4,7],[2,5,8],[3,6,9]]示例 2:
1
2 输入:matrix = [[1,2,3],[4,5,6]]
输出:[[1,4],[2,5],[3,6]]提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
-109 <= matrix[i][j] <= 109
代码
1 | class Solution: |
1 | /** |
2.24
拿到驾照啦,嘿嘿👶
题目
832. 翻转图像
难度简单
给定一个二进制矩阵
A
,我们想先水平翻转图像,然后反转图像并返回结果。水平翻转图片就是将图片的每一行都进行翻转,即逆序。例如,水平翻转
[1, 1, 0]
的结果是[0, 1, 1]
。反转图片的意思是图片中的
0
全部被1
替换,1
全部被0
替换。例如,反转[0, 1, 1]
的结果是[1, 0, 0]
。示例 1:
1
2
3
4 输入:[[1,1,0],[1,0,1],[0,0,0]]
输出:[[1,0,0],[0,1,0],[1,1,1]]
解释:首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]];
然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]示例 2:
1
2
3
4 输入:[[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出:[[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释:首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]];
然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]提示:
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
代码
一行 Python
1 | class Solution: |
2.23
题目
1052. 爱生气的书店老板
难度中等
今天,书店老板有一家店打算试营业
customers.length
分钟。每分钟都有一些顾客(customers[i]
)会进入书店,所有这些顾客都会在那一分钟结束后离开。在某些时候,书店老板会生气。 如果书店老板在第
i
分钟生气,那么grumpy[i] = 1
,否则grumpy[i] = 0
。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续
X
分钟不生气,但却只能使用一次。请你返回这一天营业下来,最多有多少客户能够感到满意的数量。
示例:
1
2
3
4
5 输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.提示:
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
思路
首先可以计算出在老板原本不生气情况下,可以满足的顾客数,同时我们将满足的某分钟顾客数置为0,以便后续减少判断。
接下来,考虑老板应该用哪 X
分钟不生气,来使自己能满足的顾客数最大化,很简单,滑动窗口。
可以理解为一个大小为 X 的窗口,从左滑到右,找到最大新增满足顾客数即可。
代码
1 | class Solution: |
2.22
美丽的周一
题目
766. 托普利茨矩阵
难度简单
给你一个
m x n
的矩阵matrix
。如果这个矩阵是托普利茨矩阵,返回true
;否则,返回false
。如果矩阵上每一条由左上到右下的对角线上的元素都相同,那么这个矩阵是 托普利茨矩阵 。
示例 1:
1
2
3
4
5
6 输入:matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
输出:true
解释:
在上述矩阵中, 其对角线为:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是 True 。示例 2:
1
2
3
4 输入:matrix = [[1,2],[2,2]]
输出:false
解释:
对角线 "[1, 2]" 上的元素不同。提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 20
0 <= matrix[i][j] <= 99
简单的语言语法熟悉题
代码
1 | /** |
2.21
好家伙直接延迟一周开学,白嫖一周自习时间,爽到
题目
1438. 绝对差不超过限制的最长连续子数组
难度中等
给你一个整数数组
nums
,和一个表示限制的整数limit
,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于limit
。如果不存在满足条件的子数组,则返回
0
。示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 输入:nums = [8,2,4,7], limit = 4
输出:2
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此,满足题意的最长子数组的长度为 2 。示例 2:
1
2
3 输入:nums = [10,1,2,4,7,2], limit = 5
输出:4
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5 。示例 3:
1
2 输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
思路
滑动窗口 + 双端队列
右指针遍历整个数组,左指针根据右指针的位置不断右移
用两个双端队列,来记录当前窗口内的最大值和最小值
代码
1 | class Solution: |
2.20
再过一个礼拜就要回校啦,美好的寒假生活终于可以结束了。
题目
697. 数组的度
难度简单229
给定一个非空且只包含非负数的整数数组
nums
,数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在
nums
中找到与nums
拥有相同大小的度的最短连续子数组,返回其长度。示例 1:
1
2
3
4
5
6
7 输入:[1, 2, 2, 3, 1]
输出:2
解释:
输入数组的度是2,因为元素1和2的出现频数最大,均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2,所以返回2.示例 2:
1
2 输入:[1,2,2,3,1,4,2]
输出:6
思路
用一个哈希表,记录每个数字的 [出现次数,第一次出现的位置,最后一次出现的位置]
确认出现次数最多有多少次,再次遍历数组,找到最短的子数组长度
代码
1 | class Solution: |
2.19
昨日约会💑,鸽了一天
题目
1004. 最大连续1的个数 III
难度中等
给定一个由若干
0
和1
组成的数组A
,我们最多可以将K
个值从 0 变成 1 。返回仅包含 1 的最长(连续)子数组的长度。
示例 1:
1
2
3
4
5 输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。示例 2:
1
2
3
4
5 输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。提示:
1 <= A.length <= 20000
0 <= K <= A.length
A[i]
为0
或1
思路
滑动窗口,设置两个指针从左滑到右,将窗口设计为不能减小(令K只减不增实现)
滑动的时候计算出现的0的个数
代码
1 | class Solution: |
2.17
最近开始简单题就用 JS 写了
题目
566. 重塑矩阵
难度简单
在MATLAB中,有一个非常有用的函数
reshape
,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。给出一个由二维数组表示的矩阵,以及两个正整数
r
和c
,分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的
reshape
操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。示例 1:
1
2
3
4
5
6
7
8
9 输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。示例 2:
1
2
3
4
5
6
7
8
9
10 输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。注意:
- 给定矩阵的宽和高范围在 [1, 100]。
- 给定的 r 和 c 都是正数。
思路
创建矩阵,遍历原矩阵,用 cnt
来计数(当然也可以边遍历边计算)
- 通过
cnt//c
来求出当前目标矩阵中的行 - 通过
cnt%c
来求出当前目标矩阵中的列
代码
1 | /** |
2.16
题目
561. 数组拆分 I
难度简单
给定长度为
2n
的整数数组nums
,你的任务是将这些数分成n
对, 例如(a1, b1), (a2, b2), ..., (an, bn)
,使得从1
到n
的min(ai, bi)
总和最大。返回该 最大总和 。
示例 1:
1
2
3
4
5
6
7 输入:nums = [1,4,3,2]
输出:4
解释:所有可能的分法(忽略元素顺序)为:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4示例 2:
1
2
3 输入:nums = [6,2,6,5,1,2]
输出:9
解释:最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9提示:
1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104
思路
排序,计算 index
为偶数的数字和
代码
现学现用 JS
1 | /** |
2.15
题目
485. 最大连续1的个数
难度简单
给定一个二进制数组, 计算其中最大连续1的个数。
示例 1:
1
2
3 输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.注意:
- 输入的数组只包含
0
和1
。- 输入数组的长度是正整数,且不超过 10,000。
思路
非常简单的一道初学者题目,遍历一遍数组即可。
代码
1 | class Solution: |
2.14
情人节 Leetcode 也虐狗,可惜我不是🐕
题目
765. 情侣牵手
难度困难144
N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人,让他们站起来交换座位。
人和座位用
0
到2N-1
的整数表示,情侣们按顺序编号,第一对是(0, 1)
,第二对是(2, 3)
,以此类推,最后一对是(2N-2, 2N-1)
。这些情侣的初始座位
row[i]
是由最初始坐在第 i 个座位上的人决定的。示例 1:
1
2
3 输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。示例 2:
1
2
3 输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位,所有的情侣都已经可以手牵手了。说明:
len(row)
是偶数且数值在[4, 60]
范围内。- 可以保证
row
是序列0...len(row)-1
的一个全排列。
思路
虽然是困难题,但我用的是简单题的方法(偷懒了),时间复杂度是O(N²)
标准解法应该使用官方题解的并查集思路,时间复杂度是O(N²)
我纯粹地假设位置0,2,4…这些偶数位置的 index 位置上的人都不会移动,只判断 ta 右边的人是否正确,然后进行交换即可
代码
1 | class Solution: |
2.13
题目
448. 找到所有数组中消失的数字
难度简单
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为*O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
1
2
3
4
5 输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
代码
1 | class Solution: |
2.12
牛年大吉!
题目
杨辉三角第k行
代码
1 | class Solution: |
2.11
美赛结束已经两天了,其实昨天的每日一题也刷了,不过懒得写题解
今天开始恢复写刷题日志,除夕快乐!
题目
703. 数据流中的第 K 大元素
难度简单
设计一个找到数据流中第
k
大元素的类(class)。注意是排序后的第k
大元素,不是第k
个不同的元素。请实现
KthLargest
类:
KthLargest(int k, int[] nums)
使用整数k
和整数流nums
初始化对象。int add(int val)
将val
插入数据流nums
后,返回当前数据流中第k
大的元素。示例:
1
2
3
4
5
6
7
8
9
10
11
12
13 输入:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出:
[null, 4, 5, 5, 8, 8]
解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8提示:
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
- 最多调用
add
方法104
次- 题目数据保证,在查找第
k
大元素时,数组中至少有k
个元素
思路
之所以难度是简单嘛,因为可以调用 python 的包,用小顶堆的优先队列形式实现增删改查
小顶堆,顾名思义,就是一个二叉树,这个二叉树的根节点是最小的
init
步骤
我们维护一个小顶堆,在初始化的时候,把
nums
里的数字全放到小顶堆里可以理解为做了一个排序,在堆的顶部是最小的数,然后越往下越大
因为我们最终的目标只需要找到第
k
大的数字,所以我们只需要保留小顶堆底部的k
个数字,把顶部的数字依次pop
出去
add
步骤
- 每次往小顶堆里加一个数字,这个数据结构会自动找到合适的位置插入这个数字,所以不需要担心插入后是否有序
- 现在的小顶堆多了一个数字,如果堆的大小比
k
大,就需要扔掉多余的数字 - 最后范围堆顶的数字,就是我们需要的当前第
k
大的是数字
代码
1 | class KthLargest: |
2.4
美赛前的最后一天寒假了
题目
643. 子数组最大平均数 I
难度简单
给定
n
个整数,找出平均数最大且长度为k
的连续子数组,并输出该最大平均数。示例:
1
2
3 输入:[1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75提示:
- 1 <=
k
<=n
<= 30,000。- 所给数据范围 [-10,000,10,000]。
思路
没啥花里胡哨的,用滑动窗口模拟就行
代码
1 | class Solution: |
2.3
题目
480. 滑动窗口中位数
难度困难
中位数是有序序列最中间的那个数。如果序列的大小是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。
例如:
[2,3,4]
,中位数是3
[2,3]
,中位数是(2 + 3) / 2 = 2.5
给你一个数组 nums,有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。
示例:
给出 nums =
[1,3,-1,-3,5,3,6,7]
,以及 k = 3。
1
2
3
4
5
6
7
8 窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6因此,返回该滑动窗口的中位数数组
[1,-1,-1,3,5,6]
。提示:
- 你可以假设
k
始终有效,即:k
始终小于输入的非空数组的元素个数。- 与真实值误差在
10 ^ -5
以内的答案将被视作正确答案。
思路
暴力法
代码
1 | class Solution: |
2.2
题目
424. 替换后的最长重复字符
难度中等
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
**注意:**字符串长度 和 k 不会超过 104。
示例 1:
1
2
3 输入:s = "ABAB", k = 2
输出:4
解释:用两个'A'替换为两个'B',反之亦然。示例 2:
1
2
3
4
5 输入:s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
思路
双指针,滑动窗口,遍历字符串,用一个数组来维护窗口中字母的出现次数
代码
1 | class Solution: |
2.1
今日简单题,刷完吃寿喜烧去咯
题目
888. 公平的糖果棒交换
难度简单99
爱丽丝和鲍勃有不同大小的糖果棒:
A[i]
是爱丽丝拥有的第i
根糖果棒的大小,B[j]
是鲍勃拥有的第j
根糖果棒的大小。因为他们是朋友,所以他们想交换一根糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)
返回一个整数数组
ans
,其中ans[0]
是爱丽丝必须交换的糖果棒的大小,ans[1]
是 Bob 必须交换的糖果棒的大小。如果有多个答案,你可以返回其中任何一个。保证答案存在。
示例 1:
1
2 输入:A = [1,1], B = [2,2]
输出:[1,2]示例 2:
1
2 输入:A = [1,2], B = [2,3]
输出:[1,2]示例 3:
1
2 输入:A = [2], B = [1,3]
输出:[2,3]示例 4:
1
2 输入:A = [1,2,5], B = [2,4]
输出:[5,4]提示:
1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
- 保证爱丽丝与鲍勃的糖果总量不同。
- 答案肯定存在。
思路
traversing and binary search.
代码
1 | class Solution: |