leetcode write up for 31-60 problems

31Next 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]

32Longest 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
            

33Search 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


34Find 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]

36Valid 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))


38Count 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


39Combination 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)                

40Combination 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)

41First 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

43Multiply 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)


47Permutations II

class Solution(object):
    def permuteUnique(self, nums):
        a = itertools.permutations(nums, len(nums))
        return set(list(a))

48Rotate 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]))

49Group 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())

50Pow(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


54Spiral 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])

55Jump 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



56Merge 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

57Insert 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

59Spiral 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




Popular posts from this blog

Phonebook - Hack the box Write up -- Web LDAP injection

wafwaf -- Hack The Box -- Web SQL injection

Cheat sheet for security+