2.28

题目

896. 单调数列

难度简单89

如果数组是单调递增或单调递减的,那么它是单调的

如果对于所有 i <= jA[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= jA[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. 1 <= A.length <= 50000
  2. -100000 <= A[i] <= 100000

思路

遍历数组,利用flag记录下当前的趋势(递增 1,递减 -1,或者全都一样 0)

若当前的趋势和flag的趋势相反,即之前为递增现在递减,或者之前递减现在递增,就说明不单调。

反之,到最后没有出现不同趋势,则说明单调。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number[]} A
* @return {boolean}
*/
var isMonotonic = function(A) {
if(A.length<=2){
return true;
}
var flag = 0;
for(var i = 1;i<=A.length;i++){
var diff = A[i]-A[i-1];
if(diff*flag<0){
return false;
}else if(diff>0){
flag = 1;
}else if(diff<0){
flag = -1;
}
}
return true;
};

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
2
3
4
5
6
7
8
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
if not s:
return 0
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t, k) for t in s.split(c))
return len(s)

2.25

题目

867. 转置矩阵

难度简单163

给你一个二维整数数组 matrix, 返回 matrix转置矩阵

矩阵的 转置 是指将矩阵的主对角线翻转,交换矩阵的行索引与列索引。

img

示例 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
2
3
4
5
6
7
8
class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
m, n = len(matrix), len(matrix[0])
res = [[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
res[i][j] = matrix[j][i]
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var transpose = function(matrix) {
var m = matrix.length;
var n = matrix[0].length;
var res = new Array(n);
for (var i = 0;i<n;i++){
res[i] = new Array(m);
}
for (var i = 0;i<n;i++){
for (var j = 0;j<m;j++){
res[i][j] = matrix[j][i];
}
}
return res;
};

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
2
3
class Solution:
def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
return [[j ^ 1 for j in i[::-1]] for i in A]

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
n = len(customers)
if n == 1: return customers[0]
res = 0
for i in range(n):
if not grumpy[i]:
res += customers[i]
customers[i] = 0
tmp = []
cnt = 0
for i in range(X-1,n):
if i == X-1:
for j in range(X-1):
cnt += customers[j]
cnt += customers[i]
tmp.append(cnt)
cnt -= customers[i-X+1]
res += max(tmp)
return res

2.22

美丽的周一

题目

766. 托普利茨矩阵

难度简单

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵,返回 true ;否则,返回 false

如果矩阵上每一条由左上到右下的对角线上的元素都相同,那么这个矩阵是 托普利茨矩阵

示例 1:

img

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:

img

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[][]} matrix
* @return {boolean}
*/
var isToeplitzMatrix = function(matrix) {
var row = matrix.length;
var col = matrix[0].length;
for(var i = 1;i<row;i++){
for(var j = 1;j<col;j++){
if(matrix[i-1][j-1] != matrix[i][j]){
return false;
}
}
}
return true;
};

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
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 longestSubarray(self, nums: List[int], limit: int) -> int:
n = len(nums)
min_que, max_que = deque(), deque()
left = right = res = 0
while right < n:
while min_que and nums[right] < min_que[-1]:
min_que.pop()
while max_que and nums[right] > max_que[-1]:
max_que.pop()

min_que.append(nums[right])
max_que.append(nums[right])

while min_que and max_que and max_que[0]-min_que[0] > limit:
if max_que[0] == nums[left]:
max_que.popleft()
if min_que[0] == nums[left]:
min_que.popleft()
left += 1
res = max(res, right-left+1)
right += 1
return res

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
dic = dict()
targets = []
max_cnt = 0
for i, num in enumerate(nums):
if num not in dic: dic[num] = [0, len(nums)+1, -1]
dic[num][0] += 1
dic[num][1] = min(dic[num][1], i)
dic[num][2] = max(dic[num][2], i)
max_cnt = max(max_cnt, dic[num][0])
res = len(nums)
for i in dic.keys():
if dic[i][0] == max_cnt:
left, right = dic[i][1], dic[i][2]
res = min(res, right-left+1)
return res

2.19

昨日约会💑,鸽了一天

题目

1004. 最大连续1的个数 III

难度中等

给定一个由若干 01 组成的数组 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. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i]01

思路

滑动窗口,设置两个指针从左滑到右,将窗口设计为不能减小(令K只减不增实现)

滑动的时候计算出现的0的个数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestOnes(self, A: List[int], K: int) -> int:
cnt = 0
left = right = 0
while right<len(A):
if A[right] == 0:
cnt += 1
right += 1
if cnt>K:
if A[left]==0:
cnt -= 1
left += 1
return right - left

2.17

最近开始简单题就用 JS 写了

题目

566. 重塑矩阵

难度简单

在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。

给出一个由二维数组表示的矩阵,以及两个正整数rc,分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的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. 给定矩阵的宽和高范围在 [1, 100]。
  2. 给定的 r 和 c 都是正数。

思路

创建矩阵,遍历原矩阵,用 cnt 来计数(当然也可以边遍历边计算)

  • 通过 cnt//c 来求出当前目标矩阵中的行
  • 通过 cnt%c 来求出当前目标矩阵中的列

代码

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
/**
* @param {number[][]} nums
* @param {number} r
* @param {number} c
* @return {number[][]}
*/
var matrixReshape = function (nums, r, c) {
var rows = nums.length;
var cols = nums[0].length;
if (rows * cols != r * c) {
return nums;
}
var res = new Array(r);
for (var i = 0; i < r; i++) {
res[i] = new Array(c);
}
var cnt = 0;
for (var i = 0; i < rows; i++) {
for (var j = 0; j < cols; j++) {
var curR = Math.floor(cnt / c);
var curC = cnt % c;
res[curR][curC] = nums[i][j];
cnt += 1;
}
}
return res;
};

2.16

题目

561. 数组拆分 I

难度简单

给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从 1nmin(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
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @return {number}
*/
var arrayPairSum = function(nums) {
nums.sort(function(a,b){
return a-b;
});
var sum = 0;
for(var i = 0;i<nums.length;i+=2){
sum += nums[i];
}
return sum;
};

2.15

题目

485. 最大连续1的个数

难度简单

给定一个二进制数组, 计算其中最大连续1的个数。

示例 1:

1
2
3
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.

注意:

  • 输入的数组只包含 01
  • 输入数组的长度是正整数,且不超过 10,000。

思路

非常简单的一道初学者题目,遍历一遍数组即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
res = 0
cnt = 0
for i in nums:
if i == 1:
cnt += 1
else:
res = max(cnt, res)
cnt = 0
res = max(res, cnt)
return res

2.14

情人节 Leetcode 也虐狗,可惜我不是🐕

题目

765. 情侣牵手

难度困难144

N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 次交换可选择任意两人,让他们站起来交换座位。

人和座位用 02N-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
解释: 无需交换座位,所有的情侣都已经可以手牵手了。

说明:

  1. len(row) 是偶数且数值在 [4, 60]范围内。
  2. 可以保证row 是序列 0...len(row)-1 的一个全排列。

思路

虽然是困难题,但我用的是简单题的方法(偷懒了),时间复杂度是O(N²)

标准解法应该使用官方题解的并查集思路,时间复杂度是O(N²)

我纯粹地假设位置0,2,4…这些偶数位置的 index 位置上的人都不会移动,只判断 ta 右边的人是否正确,然后进行交换即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
def find_another(x):
if x%2==0:
return x+1
else:
return x-1
count = 0
n = len(row)
for i in range(0,n,2):
partner = find_another(row[i])
if row[i+1] == partner:
continue
else:
j = row.index(partner)
row[i+1], row[j] = row[j], row[i+1]
count += 1
return count

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
2
3
4
5
6
7
8
9
10
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
res = []
n = len(nums)
for i, num in enumerate(nums):
nums[(num-1)%n] += n
for i, num in enumerate(nums):
if num<=n:
res.append(i+1)
return res

2.12

牛年大吉!

题目

杨辉三角第k行

代码

1
2
3
4
5
6
7
8
9
10
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
nums = [1]
for i in range(rowIndex):
cur = [1]
for i in range(len(nums)-1):
cur.append(nums[i]+nums[i+1])
cur.append(1)
nums = cur
return nums

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
2
3
4
5
6
7
8
9
10
11
12
13
14
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.pool = nums
heapq.heapify(self.pool)
self.k = k
while len(self.pool) > k:
heapq.heappop(self.pool)

def add(self, val: int) -> int:
if len(self.pool) < self.k:
heapq.heappush(self.pool, val)
elif val > self.pool[0]:
heapq.heapreplace(self.pool, val)
return self.pool[0]

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
2
3
4
5
6
7
8
9
10
11
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
cur_sum = 0
for i in range(k-1):
cur_sum += nums[i]
cur_max = -float('inf')
for i in range(k-1,len(nums)):
cur_sum += nums[i]
cur_max = max(cur_max, cur_sum)
cur_sum -= nums[i-k+1]
return cur_max/k

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
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
n = len(nums)
res = []
for i in range(n-k+1):
tmp = nums[i:i+k]
tmp.sort()
if len(tmp)%2 == 1:
res.append(tmp[k//2])
else:
res.append((tmp[k//2]+tmp[k//2-1])/2)
return res

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
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
cnts = [0]*26
left = right = maxn = 0
n = len(s)
while right < n:
cnts[ord(s[right]) - ord('A')] += 1
maxn = max(maxn, cnts[ord(s[right]) - ord('A')])
if right - left + 1 - maxn > k:
cnts[ord(s[left]) - ord('A')] -= 1
left += 1
right += 1
return right - left

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
2
3
4
5
6
7
8
9
class Solution:
def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
sum_a = sum(A)
sum_b = sum(B)
diff = sum_a-sum_b
for i in A:
j = int(i-diff/2)
if j in B:
return [i,j]