566. 重塑矩阵 - 20210217

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

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

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

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

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

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

莽就完事

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import *
def minKBitFlips(A: List[int], K: int) -> int:
	length = len(A)
	flip = [0] * length
	i, cnt = 0, 0
	while i <= length - K:
		if (A[i] + flip[i]) % 2 == 0:
			cnt += 1
			for j in range(i, i+K):
				flip[j] += 1
		i += 1
	print(flip)
	for i in range(length):
		flip[i] += A[i]
		flip[i] %= 2
	print(flip)
	if flip.count(0) > 0:
		return -1
	else:
		return cnt
			
A = [0,0,0,1,0,1,1,0]
K = 3
print(minKBitFlips(A, K))

但是超时了。。。

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

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

创建差分数组

1
2
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

从这张图可以看出，如果对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，则有解
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
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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 拥有相同大小的度的最短连续子数组，返回其长度。

简单题

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
def findShortestSubArray(nums: List[int]) -> int:
	freq = {}
	s_e = {}
	for i, num in enumerate(nums):
		if freq.get(num):
			freq[num] += 1
			s_e[num][1] = i
		else:
			freq[num] = 1
			s_e[num] = [i, i]
	freq = sorted(freq.items(), key=lambda x:x[1])
	max_freq = freq[-1][1]
	max_freq_list = []
	i = -1
	while True:
		if len(freq) >= abs(i) and freq[i][1] == max_freq:
			max_freq_list.append(freq[i][0])
			i -= 1
		else:
			break
	min_len = s_e[max_freq_list[0]][1] - s_e[max_freq_list[0]][0]
	for i in max_freq_list:
		min_len = min(min_len, s_e[i][1] - s_e[i][0])
	return min_len + 1

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

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

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

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

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

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

简单题

1
2
3
4
5
6
7
8
9
10
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 分钟不生气，但却只能使用一次。

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