avatar

LeetCode-202102
dummy

566. 重塑矩阵 - 20210217

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

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

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

如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

其实numpy就可以做这个事,但是自己写一下也行

class Solution:
def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
raw_r = len(nums)
raw_c = len(nums[0])
if raw_c * raw_r != r * c or raw_c == c:
return nums
cnt = 0
ret = []
for i in range(raw_r):
for j in range(raw_c):
if cnt % c == 0:
ret.append([nums[i][j]])
else:
ret[-1].append(nums[i][j])
cnt += 1
return ret

995. K 连续位的最小翻转次数 - 20200218

莽就完事

from typing import *
def minKBitFlips(A: List[int], K: int) -> int:
truelength = len(A)
trueflip = [0] * length
truei, cnt = 0, 0
truewhile i <= length - K:
truetrueif (A[i] + flip[i]) % 2 == 0:
truetruetruecnt += 1
truetruetruefor j in range(i, i+K):
truetruetruetrueflip[j] += 1
truetruei += 1
trueprint(flip)
truefor i in range(length):
truetrueflip[i] += A[i]
truetrueflip[i] %= 2
trueprint(flip)
trueif flip.count(0) > 0:
truetruereturn -1
trueelse:
truetruereturn cnt
truetruetrue
A = [0,0,0,1,0,1,1,0]
K = 3
print(minKBitFlips(A, K))

但是超时了。。。

这道题用到了差分数组的思想,详细讲解见https://blog.csdn.net/qq_44786250/article/details/100056975

对于区间操作,在差分数组中只要对数组的两端进行操作即可

创建差分数组

for i in range(len(A)):
diff[i] = A[0] if i == 0 else A[i] - A[i-1]

反过来,从差分数组还原,由于A[i] = diff[i] + A[i-1] = diff[i] + diff[i-1] + A[i-2] = ... = sum j from 0 to i diff[j]

image-20210218211454533

image-20210218211454533

从这张图可以看出,如果对A[i:j]都加上3,就是对diff[i]+3, diff[j]-3

所以如果之前的代码进行转换,有3个地方需要转换

  1. 是否需要进行翻转:我们可以在遍历的时候维护一个变量,变量等于diff中一直累加到当前位置的和,即new_A[i],这样就可以巧妙地将A[i] +flip[i]转换为这个变量,所以直接判断这个变量^1是否是1即可。
  2. 进行翻转操作:将遍历+1转换为两端操作即可
  3. 判断是否无解:将变量继续累加,如果剩余的值都为1,则有解
class Solution(object):
def getDiff(self, A):
diff = [0] * len(A)
for i in range(len(A)):
diff[i] = A[0] if i == 0 else A[i] - A[i-1]
return diff

def minKBitFlips(self, A: List[int], K: int) -> int:
length = len(A)
diff = self.getDiff(A)
cur = 0
i, cnt = 0, 0
while i < length - K + 1:
if not (cur + diff[i]) & 1:
cnt += 1
diff[i] += 1
if i + K < length:
diff[i+K] -= 1
cur += diff[i]
i += 1
while i < length:
cur += diff[i]
i += 1
if not cur & 1:
return -1
return cnt

1004. 最大连续1的个数 III - 20200219

给定一个由若干 01 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长(连续)子数组的长度。

滑动窗口模板题,有点类似于快慢指针?

N = len(A)
res = 0
left, right = 0, 0
zeros = 0
while right < N:
if A[right] == 0:
zeros += 1
while zeros > K:
if A[left] == 0:
zeros -= 1
left += 1
res = max(res, right - left + 1)
right += 1
return res

697. 数组的度 - 20210220

给定一个非空且只包含非负数的整数数组 nums,数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。

简单题

def findShortestSubArray(nums: List[int]) -> int:
truefreq = {}
trues_e = {}
truefor i, num in enumerate(nums):
truetrueif freq.get(num):
truetruetruefreq[num] += 1
truetruetrues_e[num][1] = i
truetrueelse:
truetruetruefreq[num] = 1
truetruetrues_e[num] = [i, i]
truefreq = sorted(freq.items(), key=lambda x:x[1])
truemax_freq = freq[-1][1]
truemax_freq_list = []
truei = -1
truewhile True:
truetrueif len(freq) >= abs(i) and freq[i][1] == max_freq:
truetruetruemax_freq_list.append(freq[i][0])
truetruetruei -= 1
truetrueelse:
truetruetruebreak
truemin_len = s_e[max_freq_list[0]][1] - s_e[max_freq_list[0]][0]
truefor i in max_freq_list:
truetruemin_len = min(min_len, s_e[i][1] - s_e[i][0])
truereturn min_len + 1

1438. 绝对差不超过限制的最长连续子数组 - 20200221

给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit

如果不存在满足条件的子数组,则返回 0

这个方法很妙,维护了两个极值的双向队列,这样能够快速判断当前极值,核心思想还是滑动窗口。

class Solution:
def longestSubarray(self, nums, limit):
r = l = res = 0
min_q = collections.deque()
max_q = collections.deque()
for num in nums:
while len(min_q) and num < min_q[-1]: min_q.pop()
while len(max_q) and num > max_q[-1]: max_q.pop()
min_q.append(num)
max_q.append(num)
r += 1;
while max_q[0] - min_q[0] > limit:
if min_q[0] == nums[l]: min_q.popleft()
if max_q[0] == nums[l]: max_q.popleft()
l += 1
res = max(res, r - l)
return res

766. 托普利茨矩阵 - 20200222

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

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

简单题

class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
from collections import deque
dq = deque(matrix[0])
for i in range(1, len(matrix)):
dq.pop()
if list(dq) != matrix[i][1:]:
return False
dq.appendleft(matrix[i][0])
return True

1052. 爱生气的书店老板 - 20200224

今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。

在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。

请你返回这一天营业下来,最多有多少客户能够感到满意的数量。

文章作者: X Mεl0n
文章链接: http://www.zrzz.site/posts/bc12231a/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论