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,2,3] 输出：true示例 2：
输入：[6,5,4,4] 输出：true示例 3：
输入：[1,3,2] 输出：false示例 4：
输入：[1,2,4,5] 输出：true示例 5：
输入：[1,1,1] 输出：true提示：
1 <= A.length <= 50000-100000 <= A[i] <= 100000
思路
遍历数组，利用flag记录下当前的趋势（递增 1，递减 -1，或者全都一样 0）
若当前的趋势和flag的趋势相反，即之前为递增现在递减，或者之前递减现在递增，就说明不单调。
反之，到最后没有出现不同趋势，则说明单调。
代码
/**
* @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:
输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。示例 2:
输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
思路
分治法，根据字母的出现次数，找到出现次数小于k的字母，将字符串进行分割。
例如s = 'aaabbbbccbaaaadbbb', k = 3，第一次会把s分割成三段'aaabbbb','baaaa'(事实上),'bbb'。
然后需要对子串也进行同样地切割，保证子串中所有字母的出现次数大于等于k，例如上面的baaaa就会被分割成aaaa。
最后就能知道最大字串长度为7，即aaabbbb子串的长度。
代码
参考的一个大佬的分治法代码
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的 转置矩阵 。矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[1,4,7],[2,5,8],[3,6,9]]示例 2：
输入：matrix = [[1,2,3],[4,5,6]] 输出：[[1,4],[2,5],[3,6]]提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10001 <= m * n <= 105-109 <= matrix[i][j] <= 109
代码
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
/**
* @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,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,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 <= 200 <= A[i][j] <= 1
代码
一行 Python
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分钟不生气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：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 <= 200000 <= customers[i] <= 10000 <= grumpy[i] <= 1
思路
首先可以计算出在老板原本不生气情况下，可以满足的顾客数，同时我们将满足的某分钟顾客数置为0，以便后续减少判断。
接下来，考虑老板应该用哪 X 分钟不生气，来使自己能满足的顾客数最大化，很简单，滑动窗口。
可以理解为一个大小为 X 的窗口，从左滑到右，找到最大新增满足顾客数即可。
代码
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：
输入：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：
输入：matrix = [[1,2],[2,2]] 输出：false 解释： 对角线 "[1, 2]" 上的元素不同。提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200 <= matrix[i][j] <= 99
简单的语言语法熟悉题
代码
/**
* @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：
输入：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：
输入：nums = [10,1,2,4,7,2], limit = 5 输出：4 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
思路
滑动窗口 + 双端队列
右指针遍历整个数组，左指针根据右指针的位置不断右移
用两个双端队列，来记录当前窗口内的最大值和最小值
代码
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, 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,2,3,1,4,2] 输出：6
思路
用一个哈希表，记录每个数字的 [出现次数，第一次出现的位置，最后一次出现的位置]
确认出现次数最多有多少次，再次遍历数组，找到最短的子数组长度
代码
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
难度中等
给定一个由若干
0和1组成的数组A，我们最多可以将K个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：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：
输入：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 <= 200000 <= K <= A.lengthA[i]为0或1
思路
滑动窗口，设置两个指针从左滑到右，将窗口设计为不能减小（令K只减不增实现）
滑动的时候计算出现的0的个数
代码
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，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。给出一个由二维数组表示的矩阵，以及两个正整数
r和c，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的
reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。示例 1:
输入: nums = [[1,2], [3,4]] r = 1, c = 4 输出: [[1,2,3,4]] 解释: 行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。示例 2:
输入: 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来求出当前目标矩阵中的列
代码
/**
* @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)，使得从1到n的min(ai, bi)总和最大。返回该 最大总和 。
示例 1：
输入：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：
输入：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 <= 104nums.length == 2 * n-104 <= nums[i] <= 104
思路
排序，计算 index 为偶数的数字和
代码
现学现用 JS
/**
* @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,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.注意：
- 输入的数组只包含
0和1。- 输入数组的长度是正整数，且不超过 10,000。
思路
非常简单的一道初学者题目，遍历一遍数组即可。
代码
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 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用
0到2N-1的整数表示，情侣们按顺序编号，第一对是(0, 1)，第二对是(2, 3)，以此类推，最后一对是(2N-2, 2N-1)。这些情侣的初始座位
row[i]是由最初始坐在第 i 个座位上的人决定的。示例 1:
输入: row = [0, 2, 1, 3] 输出: 1 解释: 我们只需要交换row[1]和row[2]的位置即可。示例 2:
输入: row = [3, 2, 0, 1] 输出: 0 解释: 无需交换座位，所有的情侣都已经可以手牵手了。说明:
len(row)是偶数且数值在[4, 60]范围内。- 可以保证
row是序列0...len(row)-1的一个全排列。
思路
虽然是困难题，但我用的是简单题的方法（偷懒了），时间复杂度是O(N²)
标准解法应该使用官方题解的并查集思路，时间复杂度是O(N²)
我纯粹地假设位置0，2，4…这些偶数位置的 index 位置上的人都不会移动，只判断 ta 右边的人是否正确，然后进行交换即可
代码
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)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入: [4,3,2,7,8,2,3,1] 输出: [5,6]
代码
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行
代码
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大的元素。示例：
输入： ["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 <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104- 最多调用
add方法104次- 题目数据保证，在查找第
k大元素时，数组中至少有k个元素
思路
之所以难度是简单嘛，因为可以调用 python 的包，用小顶堆的优先队列形式实现增删改查
小顶堆，顾名思义，就是一个二叉树，这个二叉树的根节点是最小的
init 步骤
-
我们维护一个小顶堆，在初始化的时候，把
nums里的数字全放到小顶堆里 -
可以理解为做了一个排序，在堆的顶部是最小的数，然后越往下越大
-
因为我们最终的目标只需要找到第
k大的数字，所以我们只需要保留小顶堆底部的k个数字，把顶部的数字依次pop出去
add 步骤
- 每次往小顶堆里加一个数字，这个数据结构会自动找到合适的位置插入这个数字，所以不需要担心插入后是否有序
- 现在的小顶堆多了一个数字，如果堆的大小比
k大，就需要扔掉多余的数字 - 最后范围堆顶的数字，就是我们需要的当前第
k大的是数字
代码
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,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]。
思路
没啥花里胡哨的，用滑动窗口模拟就行
代码
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 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以内的答案将被视作正确答案。
思路
暴力法
代码
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：
输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。示例 2：
输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。
思路
双指针，滑动窗口，遍历字符串，用一个数组来维护窗口中字母的出现次数
代码
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：
输入：A = [1,1], B = [2,2] 输出：[1,2]示例 2：
输入：A = [1,2], B = [2,3] 输出：[1,2]示例 3：
输入：A = [2], B = [1,3] 输出：[2,3]示例 4：
输入：A = [1,2,5], B = [2,4] 输出：[5,4]提示：
1 <= A.length <= 100001 <= B.length <= 100001 <= A[i] <= 1000001 <= B[i] <= 100000- 保证爱丽丝与鲍勃的糖果总量不同。
- 答案肯定存在。
思路
traversing and binary search.
代码
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]