leetcode write up for 31-60 problems
31. Next Permutation
从后往前,后一个数大于前一个数的时候就说明找到了要修改的位置,
但是不能直接置换这两个,要取后面的最小的来置换。
由于后面一个个比较过来的,所以是从大到小排序的。
所以再来一个for循环找到刚好比 i-1 这个数大一点的来置换这个数。
然后最后关键一步,要把后面的从小到大的排序(reverse)。
nums[i:][::-1] 是将i到后面的都反序。
class Solution(object):
def nextPermutation(self, nums):
i = len(nums)-1
while i > 0:
if nums[i] > nums[i-1]:
for j in xrange(len(nums)-1, 0, -1):
if nums[j] > nums[i-1]:
nums[j], nums[i-1] = nums[i-1], nums[j]
break
break
i -= 1
nums[i:] = nums[i:][::-1]
32. Longest Valid Parentheses
使用dp算法, 从第二个数开始循环,如果第二个是' ) ',则看前一个是不是'('。如果是,就把前两个数存的结果加2,如果前两个数有值,则代表连续的,如果是0,也没有关系,相当于是重新开始的。
而对于(())这种情况,当循环的值是’)’ 的时候,我们去查看前面有没有对应的'(' —>elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(‘: ' s[i-dp[i-1]-1] ‘是根据dp[i-1]来找到最近的’(', 并且必须确定这对parentheses之间一定有值的—>if dp[i-1] > 0:,才能保证他们是连续的。dp[i-dp[i-1]-2]代表刚刚找到的’('前面连续的最大的个数,所以当前的值是dp[i-1] + 2 + dp[i-dp[i-1]-2] , 前一个的保持的结果dp[i-1] ,加当前2,加刚刚被处理的’(’ 前面的最大的个数。
class Solution(object):
def longestValidParentheses(self, s):
# use 1D DP
# dp[i] records the longestValidParenthese EXACTLY ENDING at s[i]
dp = [0 for x in xrange(len(s))]
max_to_now = 0
for i in xrange(1,len(s)):
if s[i] == ')':
# case 1: ()()
if s[i-1] == '(':
# add nearest parentheses pairs + 2
dp[i] = dp[i-2] + 2
# case 2: (())
# i-dp[i-1]-1 is the index of last "(" not paired until this ")"
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
if dp[i-1] > 0: # content within current matching pair is valid
# add nearest parentheses pairs + 2 + parentheses before last "("
dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
else:
# otherwise is 0
dp[i] = 0
max_to_now = max(max_to_now, dp[i])
return max_to_now
33. Search in Rotated Sorted Array
由于时间复杂度为logN,所以要用二分法。
要考虑到旋转或者没有旋转的两种可能。
class Solution(object):
def search(self, nums, target):
L=len(nums)
for i in range(L):
if nums[i] == target:
return i
return -1
34. Find First and Last Position of Element in Sorted Array
二分法,最大的那个和最小的那个分两个函数分别 查找。
class Solution(object):
def searchRange(self, nums, target):
if nums==[]:
return [-1,-1]
def searchLeft(A,x):
left, right = 0, len(nums)-1
while right-left>1:
mid = (left + right) >>1
if x <= A[mid]: right = mid
if x > A[mid]: left = mid
if A[left] != x and A[right] ==x:
return right
if left==0 and A[left]==x:
return left
else: return -1
def searchRight(A,x):
left, right = 0, len(nums)-1
while right-left>1:
mid = (left + right) >>1
if x < A[mid]: right = mid
if x >= A[mid]: left = mid
if A[left] == x and A[right] !=x:
return left
if right == len(nums)-1 and A[right]==x:
return right
else: return -1
right = searchRight(nums,target)
left = searchLeft(nums,target)
return (left, right) if left <= right else [-1, -1]
36. Valid Sudoku
只需要把第几行,第几列,第几个框有这个数字。
i/3和j/3都是代表第几个小格子。最后的时候看有没有重复的,用set来计算。
由于点的位置不需要判断,所以不收录进去,并且点的多少会造成后面的误差。
class Solution(object):
def isValidSudoku(self, board):
total = []
for i, row in enumerate(board):
for j, c in enumerate(row):
if c!='.':
total += [(i,c),(c,j),(i/3,j/3,c)]
return len(total)==len(set(total))
38. Count and Say
recursively的读上一次的结果,相当于所有的都要输出。
如果第一个等于第二个,则count加一,如果不等,就放进结果里面,
就把之前的放进结果里面,并把当前的也放进结果里面。
class Solution:
def countAndSay(self, n) :
output = '1'
for i in range(2, n+1):
curr = output[0]
count = 1
res = ''
for x in output[1:]:
if x == curr:
count +=1
else:
res += str(count)+ curr
count = 1
curr = x
res += str(count) + curr
output = ''.join(res)
return output
39. Combination Sum
Dfs的使用,找到了就return,继续找下一个。
class Solution(object):
def combinationSum(self, candidates, target):
res = []
candidates.sort()
self.dfs(candidates,target,0,[],res)
return res
def dfs(self, nums, target, index, path, res):
if target == 0:
res.append(path)
return
for i in xrange(index,len(nums)):
if nums[i]>target:
break
self.dfs(nums,target-nums[i],i,path+[nums[i]],res)
40. Combination Sum II
跟上一道基本一样。更加熟练使用dfs
class Solution(object):
def combinationSum2(self, candidates, target):
candidates.sort()
res = []
self.dsf(candidates,target, 0 , [], res)
return res
def dsf(self,nums, target, index, path, res):
if target == 0 and path not in res:
res.append(path)
return
for i in xrange(index, len(nums)):
if target < nums[i]:
break
self.dsf(nums,target-nums[i],i+1,path+[nums[i]],res)
41. First Missing Positive
不嵌套的2个循环应该也算O(n)吧
class Solution(object):
def firstMissingPositive(self, nums):
dic = {}
res = 1
for v in nums:
if v >0:
dic[v] = 1
while res in dic.keys():res+=1
return res
42. Trapping Rain Water
每个unit都单独计算trap水的数量,我们需要找到该unit它 max(左边),
max(右边) 里面最小的。于是我们用这个第二大的值减去当前unit,
则能得到该unit trap的water数量。由于每次都要计算该unit左右的最大值,
会非常浪费时间,我们可以把每个unit左边和右边最大值存起来使用。
用rightMAX来存该unit右边最大值,leftMAX存左边最大值。
leftMAX我们通过从左至右的方法来找,所以
for i in range(1,n):
leftMAX[i] = max(leftMAX[i-1], height[I])
相应的rightMAX从又往左找
for i in range(n-2,-1,-1):
rightMAX[i] = max(rightMAX[i+1],height[i])
然后再for循环一个一个计算最大trap的水量。
class Solution(object):
def trap(self, height):
res = 0
n = len(height)
rightMAX = [height[n-1] for _ in range(n)]
leftMAX = [height[0] for _ in range(n)]
for i in range(1,n):
leftMAX[i] = max(leftMAX[i-1], height[i])
for i in range(n-2,-1,-1):
rightMAX[i] = max(rightMAX[i+1],height[i])
for i in range(n):
t = min(leftMAX[i],rightMAX[i])
res += t - height[i]
return res
43. Multiply Strings
class Solution(object):
def multiply(self, num1, num2):
res = 0
for k1,v1 in enumerate(num1):
tmp = 0
for k2,v2 in enumerate(num2):
tmp = tmp *10 + int(v1) * int(v2)
res += 10 ** (len(num1) - k1 -1) * tmp
return str(res)
46. Permutations
class Solution(object):
def permute(self, nums):
a = itertools.permutations(nums, len(nums))
return list(a)
47. Permutations II
class Solution(object):
def permuteUnique(self, nums):
a = itertools.permutations(nums, len(nums))
return set(list(a))
48. Rotate Image
Zip() 将多个数组对应的元素组合起来。
name = [ "Manjeet", "Nikhil", "Shambhavi", "Astha" ]
roll_no = [ 4, 1, 3, 2 ]
marks = [ 40, 50, 60, 70 ]
mapped = zip(name, roll_no, marks)
The zipped result is : [('Manjeet', 4, 40), ('Nikhil', 1, 50),
('Shambhavi', 3, 60), ('Astha', 2, 70)]
而map(fun,aug)的作用是每个参数循环去执行fun。
def addition(n):
return n + n
numbers = (1, 2, 3, 4)
result = map(addition, numbers)
print(list(result))
*matrix的意思是自己与自己做zip。
我们拿一个例子来看[[1,2,3],[4,5,6],[7,8,9]],这个矩阵旋转后应该变成[[7,4,1],[8,5,2],[9,6,3]],而[7,4,1]是每个数组的第一个倒序混合而成的。
所以我们先取matrix的倒序*matrix[::-1],然后对它们进行zip转换,变成tuple[(7, 4, 1), (8, 5, 2), (9, 6, 3)],此时我们将tuple转换成list即可,所以我们用map(list,aug)来完成。
class Solution(object):
def rotate(self, matrix):
matrix[:] = map(list,zip(*matrix[::-1]))
49. Group Anagrams
tuple的是immutable的,所以作为dictionary的key比较合适。
dic.get(key,[]) 的作用是:当从dic中获取key不存在时不会报错,
返回空数组[],如果只有一个参数dic.get(key)则返回none。
把所有含有相同元素的作为一个key,来寻找里面存在相同元素的单词。
class Solution(object):
def groupAnagrams(self, strs):
dic = {}
for i in strs:
key = tuple(sorted(i))
dic[key] = dic.get(key,[]) + [i]
return list(dic.values())
50. Pow(x, n)
class Solution(object):
def myPow(self, x, n):
ans = 1
m = -n if n < 0 else n
while m:
if m & 1 :
ans *= x
x *=x
m >>= 1
return ans if n >= 0 else 1/ans
53. Maximum Subarray
class Solution(object):
def maxSubArray(self, nums):
if not nums:
return 0
cur_sum = max_sum = nums[0]
for num in nums[1:]:
cur_sum = max(num, num+cur_sum)
max_sum = max(max_sum, cur_sum)
return max_sum
54. Spiral Matrix
输出每次的第一排,再逆时针旋转90度后再输出每次的第一排。
Self的递归要用return,matrix and的作用是当matrix 有值的时候才继续递归。
class Solution(object):
def spiralOrder(self, matrix):
return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])
55. Jump Game
从后往前找,能到最后一步的,就将其定为最后一步来找。注意range的范围,
从后往前到第一个是-1,不是0.
class Solution:
def canJump(self, nums):
last = len(nums) -1
for i in range(len(nums)-2,-1,-1):
if i + nums[i] >= last:
last = i
return last == 0
56. Merge Intervals
始终和res的最后一组元素进行比较。注意多个case。
class Solution(object):
def merge(self, intervals):
if len(intervals) == 0: return []
intervals = sorted(intervals)
res = [intervals[0]]
for n in intervals[1:]:
if n[0] <= res[-1][1]: res[-1][1] = max(n[1], res[-1][1])
else: res.append(n)
return res
57. Insert Interval
class Solution(object):
def insert(self, intervals, newInterval):
intervals.append(newInterval)
intervals = sorted(intervals)
res = [intervals[0]]
for n in intervals[1:]:
if n[0] <= res[-1][1]: res[-1][1]= max(n[1],res[-1][1])
else: res.append(n)
return res
59. Spiral Matrix II
从里面往外旋转,把每次要加的数据加入到数组里面. Lo- len(A) 代表当有n维完成后开始n+1维。
class Solution(object):
def generateMatrix(self, n):
A, lo = [], n*n+1
while lo > 1:
lo, hi = lo - len(A), lo
A = [range(lo, hi)] + zip(*A[::-1])
return A