leetcode
64
class Solution(object):
def minPathSum(self, grid):
dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
# print(dp)
dp[0][0] = grid[0][0]
for i in range(1,len(grid)):
dp[i][0] = grid[i][0] + dp[i-1][0]
for j in range(1,len(grid[0])):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(len(grid)):
for j in range(len(grid[0])):
if i != 0 and j != 0:
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
動態(tài)規(guī)劃的思想。
因為每次只能向下或者向右移動一步免猾，所以(m,n)的最優(yōu)解就是：
min （（m，n-1）的最優(yōu)解囤热，（m-1猎提，n）的最優(yōu)解）+ 當前（m，n）的值
根據(jù)此狀態(tài)轉移方程寫出dp算法即可旁蔼。
image.png
image.png
class Solution(object):
def processQueries(self, queries, m):
P = []
for i in range(1,m+1):
P.append(i)
# print(P)
def changeP(P,num):
p = [num]
index = -1
for i in range(len(P)):
if P[i] != num:
p.append(P[i])
else:
index = i
return p,index
indexs = []
for item in queries:
P,index = changeP(P,item)
indexs.append(index)
return indexs
設計一個函數(shù)changeP來模擬每一次對list P的操作锨苏，返回的是操作后的P和取到的index值。沒有在元數(shù)組P上直接操作棺聊，而是構建了一個p
image.png
image.png
class Solution(object):
def printVertically(self, s):
"""
:type s: str
:rtype: List[str]
"""
if s == '':
return []
if len(s) == 1:
return [s]
strList = []
now = ''
for i in range(len(s)):
if s[i] != ' ':
now += s[i]
if s[i] == ' ':
strList.append(now)
now = ''
if i == len(s) - 1:
# now += s[i]
strList.append(now)
print(strList)
out = []
maxlen = 0
for item in strList:
if len(item) >= maxlen:
maxlen = len(item)
for i in range(maxlen):
inow = ''
for item in strList:
if (len(item)-1) >= i:
inow += item[i]
else:
inow += ' '
inow = inow.rstrip()
out.append(inow)
return out
先利用一個for loop來把str轉化成list
再找出最長的單詞
以這個最長單詞的長度進行遍歷伞租，縱向拼接新字符串
利用rstrip()把右側空格清除
image.png
image.png
class Solution(object):
def numTeams(self, rating):
if len(rating) < 3:
return 0
allN = 0
for i in range(1,len(rating)-1):
bigL = 0
bigR = 0
smaL = 0
smaR = 0
for j in range(i):
if rating[j] < rating[i]:
smaL += 1
else:
bigL += 1
for k in range(i+1,len(rating)):
if rating[k] < rating[i]:
smaR += 1
else:
bigR += 1
allN += (bigR * smaL + bigL*smaR)
return allN
思路：遍歷從第二個數(shù)至倒數(shù)第二個數(shù)，假設當前被遍歷到的這個數(shù)為作戰(zhàn)單位的中間士兵限佩，統(tǒng)計他左邊有多少比他小的葵诈，有多少比他大的裸弦，右邊也類似。要組成作戰(zhàn)單位作喘，需要左小右大或者左大右小理疙，把這兩種的乘積做和即可。
image.png
image.png
class Solution(object):
def countSquares(self, matrix):
mat = matrix
used = []
flag = 0
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j] == 1:
used.append([i,j])
flag += 1
for nums in range(2,min(len(mat),len(mat[0])) + 1 ):
linshi = []
for item in used:
flag_now = 0
if (item[0]+nums -1) <=(len(mat)-1) and (item[1]+nums-1) <=(len(mat[0])-1):
for i in range(nums):
if mat[item[0] + i][item[1] + nums-1] == 0:
flag_now = 1
for i in range(nums):
if mat[item[0] + nums -1][item[1]+i] == 0:
flag_now = 1
if flag_now == 0:
linshi.append(item)
flag += 1
used = linshi
return flag
如果用暴力解法的話徊都，本題寫出來有五重循環(huán)沪斟，提交將會超時广辰。
于是考慮到以步長為最外層的循環(huán)暇矫，且用一個used數(shù)組，來記錄上一個步長中滿足條件的矩形的左上角坐標择吊。
依據(jù)：如果一個point向右下延伸李根，無法構造n*n有效矩陣，那么顯然也不可能構造出n+1 * n+1的有效矩陣來几睛，這個操作大大減少了運算房轿。且此時不必驗證該n+1 * n+1矩陣中每個點是否為1，只需驗證其最外層所森，一定程度上減少了計算囱持。
image.png
image.png
class Solution(object):
def findLucky(self, arr):
mydict = {}
luky = []
for i in arr:
if mydict.get(i,'no') == 'no':
mydict[i] = 1
else:
mydict[i] += 1
for item in mydict.items():
if item[0] == item[1]:
luky.append(item[0])
if len(luky) == 0:
return -1
return max(luky)
利用一個dict來記錄各個數(shù)字的出現(xiàn)次數(shù)，最后遍歷即可
image.png
image.png
class Solution(object):
def findTheDistanceValue(self, arr1, arr2, d):
nums = 0
def abs(num):
return max(num,-num)
for i in arr1:
flag = 0
for j in arr2:
if abs(i-j) <= d:
flag = 1
break
if flag == 0:
nums += 1
flag = 0
return nums
image.png
