有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例：

输入:

bits = [1, 0, 0]

输出: True

解释:

唯一的编码方式是一个两比特字符和一个一比特字符。

所以最后一个字符是一比特字符。

输入:

bits = [1, 1, 1, 0]

输出: False

解释:

唯一的编码方式是两比特字符和两比特字符。

所以最后一个字符不是一比特字符。

* 从左向右扫描数组

* 如果元素是1，说明是两比特字符，向后跳两步

* 如果元素是0，说明是一比特字符，向后跳一步

* 如果最终落在了 bits.length−1 的位置，那么说明最后一位一定是一比特字符。

class Solution:

def isOneBitCharacter(self, bits: List[int]) -> bool:

i = 0

while i < len(bits) - 1:

if bits[i] == 1:

# 跳两步

i += 2

elif bits[i] == 0:

# 跳一步

i += 1

return i == len(bits) - 1

29. [子数组最大平均数I](子数组最大平均数I.md)

30. [图片平滑器](图片平滑器.md)

31. [非递减数列](非递减数列.md)

32. [最长连续递增序列](最长连续递增序列.md)

33. [数组的度](数组的度.md)

34. [1比特与2比特字符](1比特与2比特字符.md)

35. [寻找数组的中心索引](寻找数组的中心索引.md)

36. [至少是其他数字两倍的最大数](至少是其他数字两倍的最大数.md)

37. [托普利茨矩阵](托普利茨矩阵.md)

38. [ 较大分组的位置]( 较大分组的位置.md)

39. [ 翻转图像]( 翻转图像.md)

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

其实就是求(i,j)周围8个点+(i,j)在内9个点的和的平均值

示例：

输入:

[[1,1,1],

[1,0,1],

[1,1,1]]

输出:

[[0, 0, 0],

[0, 0, 0],

[0, 0, 0]]

解释:

对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0

对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0

对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

代码

def imageSmoother(M):

rows = len(M)

columns = len(M[0])

res = [[0] * columns for _ in range(rows)]

for r in range(rows):

for c in range(columns):

# 计算(r,c)周边8个元素 + (r,c)在内 9个元素的和

count = 0

for nr in (r-1, r, r+1):

for nc in (c-1, c, c+1):

if 0<=nr<rows and 0<=nc<columns:

res[r][c] += M[nr][nc]

count += 1

res[r][c] //= count

return res

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例：

输入: [1,12,-5,-6,50,3], k = 4

输出: 12.75

解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

* 遍历数组，计算原数组nums在索引i位置的累计和，存到新数组中

* 遍历新数组，计算索引 i 和 i-k位置的最大差值。

def findMaxAverage(nums, k):

sum_list = []

sum_ = 0

for index, item in enumerate(nums):

sum_ += item

sum_list.append(sum_)

max_ = float('-inf')

for i in range(k-1, len(sum_list)):

if i == k-1:

value = sum_list[i]

else:

value = sum_list[i] - sum_list[i-k]

max_ = max(max_, value)

return max_/k

[1,2,3,4,5,6,7]

2+3+4+5 = 10+5-1 = 14

3+4+5+6 = 14+6-2 = 18

代码

def findMaxAverage(nums, k):

sum_ = sum(nums[:k])

max_ = sum_

for i in range(k, len(nums)):

sum_ = sum_ + nums[i] - nums[i-k]

max_ = max(sum_, max_)

return max_/k

给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。

中心索引：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例：

输入：

nums = [1, 7, 3, 6, 5, 6]

输出：3

解释：

索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，

与右侧数之和 (5 + 6 = 11) 相等。

同时, 3 也是第一个符合要求的中心索引。

* 特殊情况是数组两边的元素为中心索引

* 当第一个元素是中心索引，则其余元素之和为0，数组的总和=第一个元素。

* 当最后一个元素是中心索引，同理。

* 当中间的元素是中心索引时，数组的和-中心索引元素 = 左边元素和 * 2

class Solution:

def pivotIndex(self, nums: List[int]) -> int:

if not nums:

return -1

sum_ = sum(nums)

# 第一个元素为中心索引的情况

if sum_ == nums[0]:

return 0

# 其他情况

left_sum = 0

for i in range(len(nums)-1):

left_sum += nums[i]

if sum_-nums[i+1] == left_sum * 2:

return i + 1

# 最后一个元素为中心索引的情况

if sum_ == nums[-1]:

return len(nums) -1

return -1

class Solution:

def pivotIndex(self, nums: List[int]) -> int:

sum_ = sum(nums)

left_sum = 0

for i in range(len(nums)):

if left_sum == sum_ - nums[i] - left_sum:

return i

left_sum += nums[i]

return -1

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

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

示例：

输入:

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。

输入:

matrix = [

[1,2],

[2,2]

]

输出: False

解释:

对角线"[1, 2]"上的元素不同。

1234

5123

9512

发现每行[0:-1] 的元素 等于 下一行[1:]

代码

def isToeplitzMatrix(matrix):

if len(matrix) == 1:

return True

for i in range(1, len(matrix)):

if matrix[i][1:] == matrix[i-1][:-1]:

continue

else:

return False

return True

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

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

示例：

输入: [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.

输入: [1,2,2,3,1,4,2]

输出: 6

输入: [1,2,2,1,2,1,1,1,1,2,2,2]

输出: 9

* 具有度数 d 的数组必须有一些元素 x 出现 d 次。如果某些子数组具有相同的度数，那么某些元素 x （出现 d 次）。最短的子数组是将从 x 的第一次出现到最后一次出现的数组。

* 遍历数组，记录元素第一次出现的位置和最后一次出现的位置，以及每个元素出现的次数。

* 找到出现次数最多的元素，计算最短子数组的长度。

def findShortestSubArray(nums):

left, right, count = {}, {}, {}

# 遍历数组，记录元素第一次出现的位置和最后一次出现的位置，以及元素出现的次数

for i, item in enumerate(nums):

if item not in left:

left[item] = i

right[item] = i

count[item] = count.get(item, 0) + 1

min_len = len(nums)

# 找出出现次数最多的元素

max_times = max(count.values())

for item, times in count.items():

if times == max_times:

# 最小子数组的长度

min_len = min(right[item] - left[item] + 1, min_len)

return min_len

给定一个未经排序的整数数组，找到最长且连续的的递增序列，并返回该序列的长度。

示例：

输入: [1,3,5,4,7]

输出: 3

解释: 最长连续递增序列是 [1,3,5], 长度为3。

尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

def findLengthOfLCIS(nums):

if not nums:

return 0

count = 1

max_count = 1

for i in range(len(nums)-1):

if nums[i] < nums[i+1]:

count += 1

max_count = max(max_count, count)

else:

count = 1

return max_count