1.二维数组中的查找是在一个二维数组中（每个一维数组长度相同），每一行从左到右升序排列，每一列从上到下升序排列底部。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否包含整数。这个想法类似于二进制搜索。根据题目，如果将数组中的任何元素与目标值进行比较，如果该元素小于目标值，则目标值必须在该元素的下方或右侧。如果大于目标值，则目标值必须在元素的上方或左侧。对于二分查找，每次比较只能移动一个指针。在二维数组的查找中，两个指针之一上下移动，另一个指针左右移动。两个指针可以从同一个角开始。假设我们从左上角开始，即row=0，col=0，如果元素小于目标值，我们将row向下移动或col向右移动，这样被屏蔽的区域可能就是目标元素位于区域。例如row+=1，则忽略第一行左上角以外的元素，如果col+=1，则忽略第一列左上角以外的元素。所以这是不可行的。所以这道题从右上角开始找答案。Code#-*-coding:utf-8-*-class解法：#数组二维列表defFind(self,target,array):ifarray==[]:returnFalsem=len(array)-1n=len(array[0])-1i,j=0,n#这道题的重点是弄清楚起点，把最后一个数放在第一行同时i<=nandj>=0:ifarray[i][j]>target:j-=1elifarray[i][j]最右边元素，最小元素在后半部分。否则，最小元素在前半部分。classSolution:defminNumberInRotateArray(self,rotateArray):ifnotrotateArray:return0minval=rotateArray[0]foriinrange(len(rotateArray)):#不能直接foriinlen()因为int类型需要加上range如果minval>rotateArray[i]:minval=rotateArray[i]返回minval6。斐波那契数列现在需要一个整数n，请输出斐波那契数列的第n项（从0开始，第0项为0，第1项为1）。classSolution:defFibonacci(self,n):ifn<=0:return0a=b=1foriinrange(2,n):#因为前两个数已经存在，所以都是1，所以从以a+b开头的三个数a,b=b,a+b#这里不能写成a=bb=a+b，如果这样写，b不是前两位相加的值，而是已经被b赋值a和b的相加值返回b13。调整数组的顺序，使奇数在偶数的前面。输入一个整数数组，实现一个函数，调整数组中数字的顺序，使所有奇数在数组的前半部分，所有偶数在数组的前半部分。它位于数组的后半部分，保证奇数与奇数、偶数与偶数的相对位置不变。#-*-coding:utf-8-*-classSolution:defreOrderArray(self,array):#在这里写代码ifnotarray:return[]adv=[]end=[]foriinrange(len(array)):#也可以直接写成foriinarray:theneachnumberisiifarray[i]%2==0:end.append(array[i])ifarray[i]%2==1:adv.append(array[i])returnadv+end#数组拼接，直接+19。顺时针打印矩阵输入一个矩阵，从外到内按顺时针顺序打印出每一个数，例如输入如下4X4矩阵：12345678910111213141516数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.#-*-coding:utf-8-*-class解:#矩阵类型是二维列表，需要返回列表defprintMatrix(self,matrix):#这里写代码ifnotmatrix:return[]result=[]while(matrix):result+=matrix.pop(0)#取出第一行ifnotmatrixornotmatrix[0]:breakmatrix=self.turn(matrix)#取出第一行后，剩下的带数据的矩阵逆时针转90度return结果defturn(self,matrix):mid=[]foriinrange(len(matrix[0])):midd=[]forjinrange(len(matrix)):#外列内行，用于垂直变换这个矩阵midd.append(matrix[j][i])mid.append(midd)mid.reverse()#将列表中的值从当前顺序改为倒序returnmid28.数组中有一个数出现次数超过数组的一半，请找出这个数例如输入一个数组{1,2,3,2,2,2,5,4,2}长度为9，由于数字2在数组中出现了5次，超过了数组长度的一半，所以输出2。如果不存在则输出0。#-*-coding:utf-8-*-classSolution:defMoreThanHalfNum_Solution(self,numbers):#在这里写代码a={}n=len(numbers)foriinnumbers:a[i]=1ifinotinaelsea[i]+1#这句话最关键，字典初始化，可以用notinifa[i]>n/2:returnireturn032输入出现过半的数字timeinthearray一个正整数数组，将数组中的所有数字串接成一个数，打印所有可以串接的数中最小的一个。比如输入数组{3,32,321}，然后打印出这三个数能排成的最小数是321323。#-*-coding:utf-8-*-classSolution:deftheMax(self,str1,str2):'''定义字符串比较函数'''returnstr1ifstr1+str2>str2+str1elsestr2defPrintMinNumber(self,numbers):"""使用冒泡排序（最大的放在最后）"""string=[str(num)fornuminnumbers]#将数字转换成字符串res=[]flag=Truecount=len(string)-1whileflagandcount>0:flag=Falseforiinrange(len(string)-1):ifself.theMax(string[i],string[i+1])==string[i]:temp=string[i]delstring[i]string.insert(i+1,temp)#string[i],字符串[i+1]=string[i+1],string[i]为什么一定要像上面这样交换呢？为什么不？flag=Truecount-=1string=''.join(string)返回string35。搜索插入位置leetcodeclass解决方案：defsearchInsert(self,nums:List[int],target:int)->int:fori,jinenumerate(nums):如果目标-j<=0：返回i返回len(nums)53。最大子序列和leetcodeclass解决方案：defmaxSubArray(self,nums:List[int])->int:n=len(nums)temp=nums[0]max_=tempforiinrange(1,n):iftemp+nums[i]>nums[i]:#最重要的思路是当前sum加上这个数是小于还是大于这个数，如果小，需要从这个数开始相加max_=max(max_,temp+nums[i])temp=temp+nums[i]else:max_=max(max_,temp,nums[i])temp=nums[i]returnmax_和上面的问题很像：最大的区别是返回值且无基本格式importsysif__name__=="__main__":nums=list(map(int,input().strip().split(',')))n=len(nums)temp=nums[0]max_=tempforiinrange(1,n):iftemp+nums[i]>nums[i]:#最重要的思路是这个数相加后当前的和是小于还是大于这个数。如果小，就需要从这个数开始，重新累加。max_=max(max_,temp+nums[i])temp=temp+nums[i]否则：max_=max(max_,temp,nums[i])temp=nums[i]print(max_ifmax_>0else0)56。合并区间类解决方案：defmerge(self,intervals):ifnotintervals:return[]intervals.sort()left=intervals[0][0]right=intervals[0][1]n=len(intervals)res=[]foriinrange(1,n):if(intervals[i][0])<=right:如果(intervals[i][1])>=right:right=intervals[i][1]否则：res.append([left,right])left=intervals[i][0]right=intervals[i][1]res.append([left,right])返回res498。对角线穿越类解决方案：deffindDiagonalOrder(self,matrix:List[List[int]])->List[int]:iflen(matrix)==0:return[]m,n=len(matrix),len(matrix[0])re=[]foriinrange(m+n-1):row_begin=0ifi+1<=nelsei-n+1row_end=iifi+1<=melsem-1如果i%2==1:forjinrange(row_begin,row_end+1):re.append(matrix[j][i-j])else:forjinrange(row_end,row_begin-1,-1):re.append(matrix[j][i-j])返回re724。寻找数据组的中心索引leetcodeclassSolution:defpivotIndex(self,nums:List[int])->int:total=sum(nums)part_sum=0fori,jinenumerate(nums):ifpart_sum==(total-j)/2:returnipart_sum+=jreturn-1面试题01.07。旋转矩阵类解决方案：defrotate(self,matrix:List[List[int]])->None:"""不返回任何东西，就地修改矩阵。"""length=len(matrix)matrix[:]=matrix[::-1]foriinrange(length):forjinrange(i):matrix[j][i],matrix[i][j]=matrix[i][j],matrix[j][i]面试题01.08。零矩阵类解决方案：defsetZeroes(self,matrix:List[List[int]])->None:"""不要返回任何东西，而是就地修改矩阵。"""length=len(matrix)length1=len(matrix[0])row=[]col=[]iflength!=0:foriin范围（长度）：对于范围内的j（长度1）：如果矩阵[i][j]==0：row.append（i）col.append（j）对于行中的i：对于范围内的j（长度1）：matrix[i][j]=0forjincol:foriinrange(length):matrix[i][j]=0
