leetcode 51-60

51.N皇后

将n个皇后放在nxn的棋盘上，使皇后之间不能相互攻击，求所有可行解。

class Solution:
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        
        def ok(x, y, tab, n):
            for i in range(x):
                if tab[i][y] == 'Q':
                    return False
            i, j = x-1, y-1
            while i >= 0 and j >= 0:
                if tab[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            i, j = x-1, y+1
            while i >= 0 and j < n:
                if tab[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True
        
        def dfs(x, tab, ans, n):
            if x == n:
                t = []
                for i in tab:
                    t.append(''.join(i))
                ans.append(t)
                return
            for y in range(n):
                if ok(x, y, tab, n):
                    tab[x][y] = 'Q'
                    dfs(x+1, tab, ans, n)
                    tab[x][y] = '.'
        
        ans = []
        tab = [['.' for i in range(n)] for j in range(n)]
        dfs(0, tab, ans, n)
        return ans

52.N皇后II

将n个皇后放在nxn的棋盘上，使皇后之间不能相互攻击，求所有解的数量。

class Solution:
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        def ok(x, y, tab, n):
            for i in range(x):
                if tab[i][y] == 'Q':
                    return False
            i, j = x-1, y-1
            while i >= 0 and j >= 0:
                if tab[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            i, j = x-1, y+1
            while i >= 0 and j < n:
                if tab[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True
        
        def dfs(x, tab, n, ans):
            if x == n:
                ans.append(1)
                return
            for y in range(n):
                if ok(x, y, tab, n):
                    tab[x][y] = 'Q'
                    dfs(x+1, tab, n, ans)
                    tab[x][y] = '.'
        
        ans = []
        tab = [['.' for i in range(n)] for j in range(n)]
        dfs(0, tab, n, ans)
        return len(ans)

53.最大子序和

给定一个非空的整数数组，找出一个具有最大和的连续非空子数组，返回其最大和。

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [nums[0]]
        for i in range(1, len(nums)):
            dp.append(max(nums[i], nums[i]+dp[i-1]))
        return max(dp)

54.螺旋矩阵

给定一个包含mxn个元素的矩阵，按顺时针螺旋顺序，返回矩阵中的所有元素。

class Solution:
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        ans = []
        if not matrix: return []
        m, n = len(matrix), len(matrix[0])
        tab = [[0 for i in range(n)] for j in range(m)]
        x, y = 0, -1
        while len(ans) < m*n:
            while y+1 < n and tab[x][y+1] == 0:
                y += 1
                ans.append(matrix[x][y])
                tab[x][y] = 1
            while x+1 < m and tab[x+1][y] == 0:
                x += 1
                ans.append(matrix[x][y])
                tab[x][y] = 1
            while y-1 >= 0 and tab[x][y-1] == 0:
                y -= 1
                ans.append(matrix[x][y])
                tab[x][y] = 1
            while x-1 >= 0 and tab[x-1][y] == 0:
                x -= 1
                ans.append(matrix[x][y])
                tab[x][y] = 1
        return ans

55.跳跃游戏

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

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        mx = 0
        for i, x in enumerate(nums):
            if i > mx:
                return False
            mx = max(mx, i+nums[i])
        return True

56.合并区间

给出一个区间的集合，合并所有重叠的区间。

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals.sort(key = lambda x: x.start)
        ans = []
        t = None
        for i in intervals:
            if t is None:
                t = i
            else:
                if t.end >= i.start:
                    t.end = max(t.end, i.end)
                else:
                    ans.append(t)
                    t = i
        if t:
            ans.append(t)
        return ans

57.插入区间

给出一个元重复的，按照区间起始端点排序的区间列表，在列表中插入一个新的区间，要确保插完后新的列表中的区间仍然有序且不重复（如有必果，可以合并区间）。

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        intervals.append(newInterval)
        intervals.sort(key = lambda x: x.start)
        ans = []
        t = None
        for i in intervals:
            if t is None:
                t = i
            else:
                if t.end >= i.start:
                    t.end = max(t.end, i.end)
                else:
                    ans.append(t)
                    t = i
        if t: ans.append(t)
        return ans

58.最后一个单词的长度

给定一个仅包含大小写字母和空格的字符串，返回其最后一个单词的长度。如不存在最后一个单词，返回0.

class Solution:
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        w = s.split()
        return len(w[-1]) if w else 0

59.螺旋矩阵II

给定一个正整数n，生成一个包含1到n*n所有元素，且元素按顺时针螺旋排列的方形矩阵。

class Solution:
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        ans = [[0 for i in range(n)] for j in range(n)]
        x, y = 0, -1
        cnt = 0
        while cnt < n*n:
            while y+1 < n and ans[x][y+1] == 0:
                y += 1
                cnt += 1
                ans[x][y] = cnt
            while x+1 < n and ans[x+1][y] == 0:
                x += 1
                cnt += 1
                ans[x][y] = cnt
            while y-1 >= 0 and ans[x][y-1] == 0:
                y -= 1
                cnt += 1
                ans[x][y] = cnt
            while x-1 >= 0 and ans[x-1][y] == 0:
                x -= 1
                cnt += 1
                ans[x][y] = cnt
        return ans

60.第k个排列

给出集合[1,2,3,…,n]，其所有元素共有n!种排列，求第k小的排列。

class Solution:
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        z = [i for i in range(1, n+1)]
        p = 1
        for i in range(1,n):
            p *= i
        k -= 1
        ans = ''
        for i in range(n):
            x, y = divmod(k, p)
            ans += str(z.pop(x))
            k = y
            if n-1 > i:
                p //= n-1-i
        return ans