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

?

?