leetcode日常總結(jié)

566，581，605，628，643，661，665

566：重塑矩陣

題目描述：

函數(shù) reshape，它可以將一個矩陣重塑為另一個大小不同的新矩陣，但保留其原始數(shù)據(jù)。給出一個由二維數(shù)組表示的矩陣，以及兩個正整數(shù)r和c，分別表示想要的重構(gòu)的矩陣的行數(shù)和列數(shù)。重構(gòu)后的矩陣需要將原始矩陣的所有元素以相同的行遍歷順序填充。如果具有給定參數(shù)的reshape操作是可行且合理的，則輸出新的重塑矩陣；否則，輸出原始矩陣。

思路：

判斷個數(shù)一樣，把原矩陣寫成生成器，一個一個往外出數(shù)據(jù)，按照行列填充到新矩陣

代碼：

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：最短無序連續(xù)子數(shù)組

題目描述：

給定一個整數(shù)數(shù)組，你需要尋找一個連續(xù)的子數(shù)組，如果對這個子數(shù)組進行升序排序，那么整個數(shù)組都會變?yōu)樯蚺判?。你找到的子?shù)組應是最短的，請輸出它的長度。

思路：

從左往右遍歷，如果最左位置上的數(shù)為數(shù)組中最小的值，則pop掉；從右往左遍歷，如果最右位置上的數(shù)為數(shù)組中最大的值，則pop掉；最終數(shù)組長度為子數(shù)組需要排序的長度。

代碼：

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：種花問題

題目描述：

假設你有一個很長的花壇，一部分地塊種植了花，另一部分卻沒有?？墒?，花卉不能種植在相鄰的地塊上，它們會爭奪水源，兩者都會死去。給定一個花壇（表示為一個數(shù)組包含0和1，其中0表示沒種植花，1表示種植了花），和一個數(shù) n 。能否在不打破種植規(guī)則的情況下種入 n 朵花？能則返回True，不能則返回False。

思路:

想添加一個數(shù)字必須是 1.開頭兩個0 [0,0,…] 2.結(jié)尾兩個0 […,0,0] 3. 中間三個0 […,0,0,0,…]，所以前后補零處理邊界看是否三個連續(xù)的位置都為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：三個數(shù)的最大乘積

題目描述：

給定一個整型數(shù)組，在數(shù)組中找出由三個數(shù)組成的最大乘積，并輸出這個乘積。

思路：

1：排序，如果沒有負數(shù)則后面三個數(shù)的乘積為最大，若有負數(shù)，則可比較前兩個值及最后一個最大值的乘積與最后三個值乘積誰更大。

2：求出數(shù)組中最大的三個數(shù)以及最小的兩個數(shù)，因此我們可以不用排序，用線性掃描直接得出這五個數(shù)。

代碼：

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：子數(shù)組最大平均數(shù)Ⅰ
題目描述：
給定 n 個整數(shù)，找出平均數(shù)最大且長度為 k 的連續(xù)子數(shù)組，并輸出該最大平均數(shù)。
思路：
找出子數(shù)組中長度為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：圖片平滑器

題目描述：

包含整數(shù)的二維矩陣 M 表示一個圖片的灰度。你需要設計一個平滑器來讓每一個單元的灰度成為平均灰度 (向下舍入) ，平均灰度的計算是周圍的8個單元和它本身的值求平均，如果周圍的單元格不足八個，則盡可能多的利用它們。

思路：

數(shù)組補邊法消除特殊狀態(tài)，將原數(shù)組周圍用-1填充，構(gòu)成新數(shù)組，結(jié)果i行j列的值即為該數(shù)組i行j列為左上角元素的3X3矩陣的和+加上-1的個數(shù)，再除以 9減去 -1的個數(shù)

代碼：

?

?

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：非遞減數(shù)列

題目描述：

給定一個長度為 n 的整數(shù)數(shù)組，你的任務是判斷在最多改變 1 個元素的情況下，該數(shù)組能否變成一個非遞減數(shù)列。

思路：

使前一個數(shù)字小于或等于當前數(shù)字

使當前數(shù)字等于先前的數(shù)字

當找到nums[i-1] > nums[i]，采用方式一，通過改變nums[i-1]的值，這樣不會影響了后續(xù)操作。還有，如果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

?

?