目录
1.寻找数组的中心索引
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1
class Solution(object):
def pivotIndex(self, nums):
n=len(nums)
sums = sum(nums)
if sums-nums[0]==0:
return 0
flag=n1=n2=0
for i in range(1,n):
n1+=nums[i-1]
n2=sums-n1-nums[i]
if n1==n2:
flag=1
return i
if flag==0:
return -12.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
class Solution(object):
def searchInsert(self, nums, target):
n=len(nums)
y=[0]*n
if target-nums[n-1]>0:
return n
for i in range(n):
y[i]=target-nums[i]
if y[i]<=0:
return i因为给定的是一个排序数组，所以可以使用二分法查找
class Solution(object):
def searchInsert(self, nums, target):
left=0
n=len(nums)
right = n-1
while (left<=right):
mid = left+(right-left)//2
if nums[mid]==target:
return mid
elif nums[mid]<target:
left=mid+1
else:
right=mid-1
return right+1
3.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
输入[[1,3],[2,6],[8,10],[15,18]]------intervals
输出[[1,6],[8,10],[15,18]]-----merges
新建一个列表merges，遍历intervals，判断merges最后一个元素与intervals首元素大小关系，若后者大，直接append到列表中，若前者大，则将两个区间合并（取最大值作为合并列表的最后一个元素）。
class Solution(object):
def merge(self, intervals):
intervals.sort(key=lambda x : x[0])
merges=list()
for inte in intervals:
if not merges or merges[-1][-1] < inte[0]:
merges.append(inte)
else:
merges[-1][-1]=max(merges[-1][-1],inte[1])
return merges
4.旋转（还有问题）
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
class Solution(object):
def rotate(self, matrix):
x=len(matrix)
# m1=matrix#[[0]*(x)]*x
# 对角线翻转
for i in range(x):
for j in range(i+1,x):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
# m1[i][j]=matrix[x-1-j][i]
# 水平翻转
for i in range(x):
for j in range(x/2):
matrix[i][j],matrix[i][x - j - 1] = matrix[i][x - j - 1],matrix[i][j]
# 下标操作还没有实现，题目中说了不能占用额外空间，这里使用m1，但m1=matrix算是占用额外空间吗？
# for i in range(x):
# for j in range(i+1,x):
# m1[i][j]=matrix[x-1-j][i]
return matrix5.零矩阵
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
不需要清楚的知道下标位置，只需要将下表所在的行或者列清零。
class Solution(object):
def setZeroes(self, matrix):
n=len(matrix)#考虑到矩阵不一定是行数=列数
m=len(matrix[0])
row=[0]*m
col=[0]*n
#先找到值为0的下表，存入row和col
for i in range(n):
for j in range(m):
if matrix[i][j]==0:
row[j]=1
col[i]=1
#将下标所在的行和列清零
for i in range(n):
for j in range(m):
if row[j]==1 or col[i]==1:
matrix[i][j]=0
return matrix6.对角线遍历
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
细节：设置上下界限，需要遍历的对角线条数，用到了for、while、if循环
class Solution(object):
def findDiagonalOrder(self, mat):
m=len(mat)
n=len(mat[0])
k=m+n-1
lis=[]
row,col=0,0
for i in range(k):
if i%2==0: #偶数对角线，向右上遍历
while row>=0 and col<n:
lis.append(mat[row][col])
row-=1#向上
col+=1#向右
if col<n: #这时超出了上边界，需要移动到左下角
row+=1
else: #col<n,这时row<0了
row+=2
col-=1
else: #奇数对角线
while col>=0 and row<m:
lis.append(mat[row][col])
row+=1
col-=1
if row<m: #这时超出了下边界，需要移动到右上角
col+=1
else:
row-=1
col+=2
return lis