leetcode 41-50

41.缺失的第一个正整数

给定一个未排序的整数数组，找出其中没有出现的最小正整数。

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = set(nums)
        i = 1
        while i in s:
            i += 1
        return i

42.接雨水

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少水。

class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        height.insert(0, 0)
        height.append(0)
        L = [0] * (n+5)
        R = [0] * (n+5)
        for i in range(1, n+1):
            L[i] = max(L[i-1], height[i])
        for i in range(n, 0, -1):
            R[i] = max(R[i+1], height[i])
        ans = 0
        for i in range(1, n+1):
            ans += max(0, min(L[i-1], R[i+1]) - height[i])
        return ans

43.字符串相乘

给定两个以字符串形式表示的非负整数num1和num2，求其乘积，也用字符串表示。

class Solution:
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        return str(int(num1) * int(num2))

44. 通配符匹配

给定一个字符串s和一个字符模式p，实现一个支持'?'和'*'的通配匹配。

class Solution(object):
    def isMatch(self, s, p):
        ls, lp = len(s), len(p)
        dp = [[False for c in range(ls+1)] for r in range(lp+1)]
        dp[0][0] = True
        for i in range(1, lp+1):
            dp[i][0] = p[i-1] == '*' and dp[i-1][0]
        for i in range(1, lp+1):
            for j in range(1, ls+1):
                if p[i-1] == s[j-1] or p[i-1] == '?':
                    dp[i][j] = dp[i-1][j-1]
                elif p[i-1] == '*':
                    dp[i][j] = dp[i-1][j] or dp[i][j-1]
        return dp[lp][ls]

45.跳跃游戏

给定一个非负整数数组，最初位于数组的第一个位置，数组中每个元素代表在该位置可以跳跃的最大长度，用最少的步数到达最后一个位置。

class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        C, R = 0, 0
        ans = 0
        for i, j in enumerate(nums):
            if i > C:
                ans += 1
                C = R
            R = max(R, i+j)
        return ans

46.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        def dfs(idx, tmp, nums, ans):
            if idx == len(nums):
                ans.append(tmp[::])
                return
            for i in range(idx, len(nums)):
                nums[idx], nums[i] = nums[i], nums[idx]
                dfs(idx+1, tmp+[nums[idx]], nums, ans)
                nums[idx], nums[i] = nums[i], nums[idx]
            
        ans = []
        dfs(0, [], nums, ans)
        return sorted(ans)

47.全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(idx, tmp, nums, ans):
            if idx == len(nums):
                ans.add(tuple(tmp))
                return
            for i in range(idx, len(nums)):
                nums[idx], nums[i] = nums[i], nums[idx]
                dfs(idx+1, tmp+[nums[idx]], nums, ans)
                nums[idx], nums[i] = nums[i], nums[idx]
        
        ans = set()
        dfs(0, [], nums, ans)
        return sorted(list(ans))

48.旋转图像

给定一个nxn的二维矩阵表示一个图像，将图像顺时针旋转90度。

class Solution:
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(n):
            L, R = 0, n-1
            while L < R:
                matrix[i][L], matrix[i][R] = matrix[i][R], matrix[i][L]
                L += 1
                R -= 1

49.字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

class Solution:
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        mp = {}
        for i in strs:
            k = ''.join(sorted(i))
            if k in mp:
                mp[k].append(i)
            else:
                mp[k] = [i]
        ans = []
        for v in mp.values():
            ans.append(v)
        return ans

50.求幂

实现pow(x,n)，即计算x的n次幂。

class Solution:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        return pow(x, n)