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]
动态规划的思想。
因为每次只能向下或者向右移动一步，所以(m,n)的最优解就是：
min （（m，n-1）的最优解，（m-1，n）的最优解）+ 当前（m，n）的值
根据此状态转移方程写出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
设计一个函数changeP来模拟每一次对list P的操作，返回的是操作后的P和取到的index值。没有在元数组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
思路：遍历从第二个数至倒数第二个数，假设当前被遍历到的这个数为作战单位的中间士兵，统计他左边有多少比他小的，有多少比他大的，右边也类似。要组成作战单位，需要左小右大或者左大右小，把这两种的乘积做和即可。
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
如果用暴力解法的话，本题写出来有五重循环，提交将会超时。
于是考虑到以步长为最外层的循环，且用一个used数组，来记录上一个步长中满足条件的矩形的左上角坐标。
依据：如果一个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来记录各个数字的出现次数，最后遍历即可
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
