leetcode日常总结-创新互联
566，581，605，628，643，661，665
566：重塑矩阵
题目描述：
函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
思路：
判断个数一样，把原矩阵写成生成器，一个一个往外出数据，按照行列填充到新矩阵
代码：
class Solution(object):
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
function(){ //XM返佣 http://www.fx61.com/brokerlist/xm.html
"""
if r*c != len(nums)*len(nums[0]):
return nums
def num(nums):
for row in nums:
for element in row:
yield element
g=num(nums)
result=[]
for i in range(r):
row=[]
for j in range(c):
row.append(next(g))
result.append(row)
return result
581：最短无序连续子数组
题目描述：
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。
思路：
从左往右遍历，如果最左位置上的数为数组中最小的值，则pop掉；从右往左遍历，如果最右位置上的数为数组中大的值，则pop掉；最终数组长度为子数组需要排序的长度。
代码：
class Solution(object):
def findUnsortedSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums==sorted(nums):
return 0
while nums[-1]==max(nums):
nums.pop(-1)
while nums[0]==min(nums):
nums.pop(0)
return len(nums)
605：种花问题
题目描述：
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数n。能否在不打破种植规则的情况下种入n朵花？能则返回True，不能则返回False。
思路:
想添加一个数字必须是 1.开头两个0 [0,0,…] 2.结尾两个0 […,0,0] 3.中间三个0 […,0,0,0,…]，所以前后补零处理边界看是否三个连续的位置都为0.
代码：
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
tmp=[0]+flowerbed+[0]
for i in range(1,len(tmp)-1):
if tmp[i]==0 and tmp[i-1]==0 and tmp[i+1]==0:
tmp[i]=1
n-=1
if n<=0:
return True
else:
return False
628：三个数的大乘积
题目描述：
给定一个整型数组，在数组中找出由三个数组成的大乘积，并输出这个乘积。
思路：
1：排序，如果没有负数则后面三个数的乘积为大，若有负数，则可比较前两个值及最后一个大值的乘积与最后三个值乘积谁更大。
2：求出数组中大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。
代码：
class Solution(object):
def maximumProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return max(nums[0]*nums[1]*nums[-1],nums[-1]*nums[-2]*nums[-3])
643：子数组大平均数Ⅰ
题目描述：
给定 n 个整数，找出平均数大且长度为k的连续子数组，并输出该大平均数。
思路：
找出子数组中长度为k的大值，然后除以长度。
滑动窗口 当移动一位的时候 只需要减去前一个i - 1 加上新的一个i + k - 1
代码：
class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
ave=sum(nums[:k])
tmp=ave
for i in range(len(nums)-k):
tmp=tmp-nums[i]+nums[i+k]
if tmp>ave:
ave=tmp
return ave*1.0/k
661：图片平滑器
题目描述：
包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度(向下舍入)，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。
思路：
数组补边法消除特殊状态，将原数组周围用-1填充，构成新数组，结果i行j列的值即为该数组i行j列为左上角元素的3X3矩阵的和+加上-1的个数，再除以9减去-1的个数
代码：
class Solution(object):
def imageSmoother(self, M):
"""
:type M: List[List[int]]
:rtype: List[List[int]]
"""
row=len(M)
clu=len(M[0])
M.insert(0,[-1]*clu)
M.append([-1]*clu)
for i in range(len(M)):
M[i].insert(0,-1)
M[i].append(-1)
res=[]
for i in range(row):
row=[]
for j in range(clu):
lst=[M[i][j],M[i][j+1],M[i][j+2],M[i+1][j],M[i+1][j+1],M[i+1][j+2],M[i+2][j],M[i+2][j+1],M[i+2][j+2]]
n=lst.count(-1)
item=int((sum(lst)+n)/(9-n))
row.append(item)
res.append(row)
return res
665：非递减数列
题目描述：
给定一个长度为 n 的整数数组，你的任务是判断在最多改变1个元素的情况下，该数组能否变成一个非递减数列。
思路：
使前一个数字小于或等于当前数字
使当前数字等于先前的数字
当找到nums[i-1] > nums[i]，采用方式一，通过改变nums[i-1]的值，这样不会影响了后续操作。还有，如果nums[i-2] > nums[i]，采用方式二，改变nums[i]的值。
代码：
class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums)<=2:
return True
for i in range(0,len(nums)-1):
if i==0 and nums[i]>nums[i+1] and nums[i+1]<=nums[i+2]:
nums[i]=nums[i+1]
break
elif i != 0:
if nums[i]>nums[i+1]:
if nums[i+1]>=nums[i-1]:
nums[i]=nums[i+1]
else:
nums[i+1]=nums[i]
break
for i in range(0,len(nums)-1):
if nums[i]>nums[i+1]:
return False
else:
return True
另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
当前文章：leetcode日常总结-创新互联
网址分享：http://6mz.cn/article/cospdp.html