51. N-Queens (Hard)

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

#answer way of writing
class Solution(object):
   def solveNQueens(self, n):
       """
       :type n: int
       :rtype: List[List[str]]
       """
       
       board = [-1]*n
       
       
       def conflict(board, row, col):
           
           for row_i in range(n):
               #if has Queue in row_i  col != -1 
               if  board[row_i] != -1 and ( col==board[row_i] or row==row_i or row+col==row_i+ board[row_i] or  row-col==row_i- board[row_i]):
                   #same row
                   return True
               
           return False
       
       res = []
       def bt(board,row):
           if row==n:
               res.append(board[:])
           else:
               for col in range(n):
                   if not conflict(board,row,col):
                       board[row]=col
                       bt(board,row+1)
                       board[row]=-1
       bt(board,0)

       result = []
       for solution in res:
           s = []
           for i in solution:
               row = ['.']*n
               row[i]='Q'
               s.append(''.join(row))
           result.append(s)
       return  result

#
class Solution:
   def solveNQueens(self, n: int) -> List[List[str]]:

       def conflict(res,row,col):
          
           if col in res:
               return True
           if res[row]!=-1:
               return True
           if row+col in [ i+n for i,n in enumerate(res) if n!=-1]:
               return True
           if row-col in [ i-n for i,n in enumerate(res) if n!=-1]:
               return True
           
           return False

       result = []
       def solve(tmp,i):
           if i==n:
               result.append(tmp[:])
               return
           for j in range(n):
               if not conflict(tmp,i,j):
                   tmp[i]=j
                   solve(tmp,i+1)
                   tmp[i]=-1 
       
       solve([-1]*n,0)

       res = []
       for r in result:
           tmp = [['.']*n for _ in range(n)]
           for row, col in enumerate(r):
               tmp[row][col]='Q'
           tmp = [''.join(row) for row in tmp]
           res.append(tmp)

       return res               

ith queens at row i， start已经可以表示ith quene了。。。

52. N-Queens II （Hard）

和之间一样求出所有组合然后求length。。。

53. Maximum Subarray （Medium）

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum
A subarray is a contiguous part of an array.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp[i] means to sum up to nums[i] is the maxinum
        # dp[i] = max(dp[i-1]+nums[i], nums[i])
        # return max(dp)

        dpi = nums[0]
        res = nums[0]
        for i,n in enumerate(nums):
            if i==0: continue
            dpi = max(dpi+n,n)
            res = max(res,dpi)
        return res

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        #O（n）方法， 
        #  dp[i] 表示 在i包含i元素的最大和
        #  dp[i] = max(nums[i],dp[i-1]+nums[i])
        if len(nums)==1: return nums[0]
        res = nums[0]
        dpi1 = nums[0]
        for i in range(1,len(nums)):
            dpi=max(nums[i],dpi1+nums[i])
            if dpi>res:
                res=dpi
            dpi1=dpi
        return res

54. Spiral Matrix （Medium）

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res.extend(matrix.pop(0))
            matrix = list(zip(*matrix))[::-1]
        return res

#answer way of writting
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix: return []
        
        visited = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
        
        moveX = [1,0,-1,0]
        moveY = [0,1,0,-1]
        res = []
        moveOption = 0
        row = len(matrix)
        col = len(matrix[0])
        r = 0
        c = 0
        for _ in range(row*col):
            res.append(matrix[r][c])
            visited[r][c]=True
            rr = r + moveY[moveOption]
            cc = c + moveX[moveOption]
            if (rr>=0 and rr<row and cc>=0 and cc<col) and not visited[rr][cc]
                r=rr
                c=cc
            else:
                moveOption = (moveOption+1)%4
                r = r+moveY[moveOption]
                c = c+moveX[moveOption]
        return res        

55. Jump Game (Medium)

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        cur = 0
        right = nums[0]

        for i in range(1,len(nums)):
            if cur<i:
                if right==cur: return False
                cur = right
            
            right = max(right, i+nums[i])

        return cur>=len(nums)-1


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        right=nums[0]
        cur = 0
        for i,n in enumerate(nums):
            #form 1th index
            if i==0: continue
            if right>=i:
                #if I can reach Ith pos, update right
                right = max(right,i+n)
        
        return right>=len(nums)-1

56. Merge Intervals (Medium)

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        #[sort by start
        # scan if < append, else  continue til end
        # case1)
        #    al    ar   
        #    |      |
        #       bl|    |br
        #
        # case2)
        #    al    ar   
        #    |      |
        #              bl|    |br
        # case3)
        #    al               ar   
        #    |                |
        #       bl|    |br
        
        if len(intervals)==1: return intervals
        intervals = sorted(intervals, key=lambda x: x[0])
        res = []
        pre_left = intervals[0][0]
        pre_right = intervals[0][1]
        for i,interval in enumerate(intervals):
            if i==0: continue
            local_left = interval[0]
            local_right = interval[1]
            if local_left > pre_right:
                #case 2)
                res.append([pre_left,pre_right])
                pre_left=local_left
                pre_right=local_right
            else:
                #case 1,3)
                pre_right=max(pre_right,local_right)
                
            if i==len(intervals)-1:
                res.append([pre_left,max(pre_right,local_right)])
                
        return res

#answer way of writting
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        intervals.sort(key=lambda x:x[0])
        
        if not intervals: return []
        
        cur=intervals.pop(0) 
        res=[cur]
        
        while intervals:
            cur=intervals.pop(0)
            res_1=res[-1]
            # a   b
            #  cd       case 1  drop cur
            #   c  d    csse 2  extend res[-1] to d
            #        cd case 3  add cur to res
            
            if cur[1]<=res_1[1]: 
                continue
            elif    cur[0]<=res_1[1] and cur[1]>res_1[1]:
                res[-1][1]=cur[1]
            else:
                res.append(cur)
        return res

sort by 起始元素， 总共有3种情况很容易想到， 答案写的代码比较简单。。。

57. Insert Interval （Medium）

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        
        intervals.append(newInterval)
        intervals.sort(key=lambda x: x[0])
        if not intervals or len(intervals)==1: return intervals
        
        res = []
        cur = intervals.pop(0)
        res.append(cur)
        
        while intervals:
            cur=intervals.pop(0)
            cur_left = cur[0]
            cur_right= cur[1]
            pre_left = res[-1][0]
            pre_right = res[-1][1]
            
            if cur_right<=pre_right:
                # a  b b  a
                continue
            elif cur_left<=pre_right and cur_right>=pre_right:
                # a  b  a  b
                res[-1][1]=cur_right
            else:
                # a  a  b b
                res.append(cur)
        
        return res

把区间插入， 排序， 然后重复上题代码。

58. Length of Last Word （Easy）

Given a string s consisting of some words separated by some number of spaces, return the length of the last word in the string.

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        while s[-1]==' ':
            s=s[:-1]
        c=0
        while s and s[-1]!=' ':
            c+=1
            s =s[:-1]
        return c

先去尾部空格，然后从尾部开始计数，如果碰到空格就break return。

59. Spiral Matrix II （Medium）

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        
        matrix = [['NULL']*n for _ in range(n)]
        visited= [[False]*n for _ in range(n)]
        move_X = [1,0,-1,0]
        move_Y = [0,1,0, -1]
        
        r=0
        c=0
        moveOption = 0
        for i in range(1,n*n+1):
            matrix[r][c]=i
            visited[r][c]=True
            #calculate next pos
            rr=r+move_Y[moveOption]
            cc=c+move_X[moveOption]
            #print(rr,cc)
            if not (n>rr>=0 and n>cc>=0 and not visited[rr][cc]):
                moveOption = (moveOption+1)%4
                rr=r+move_Y[moveOption]
                cc=c+move_X[moveOption]
            r=rr
            c=cc
        return matrix

60. Permutation Sequence （Hard）

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        
        # "123"             0
        # "132"             1
        # "213"             2
        # "231"             3
        # "312"             4
        # "321"             5
        #      3!  2!  1! 0!
        #      a*6  + b2   c1  d1
        #   4= 0      2     0   0
        #             3     1   2
        if n==1: return "1"
        bignumber=[0]*n
        bignumber[0]=1
        bignumber[1]=1
        for i in range(2,n):
            bignumber[i]=i*bignumber[i-1]
        select=[str(i) for i in range(1,n+1)]
        res=[]
        k=k-1
        for i in range(n-1,-1,-1):
            index=k//bignumber[i]
            k=k-index*bignumber[i]
            res.append(select[index])
            select.remove(select[index])
        
        return "".join(res)

不会做， 没思路，要是按照求下一个permutation方法肯定time limit exceeded。backtracking too 。
答案思路是： k看作为以阶乘进制计数。eg. 3个数的阶乘进制base为 3! 2! 1! 0!
某个k只是这个阶乘进制计数的值，所以先算bignumber阶乘计数base。
k的最大位阶乘计数对应的值为 index=k//bignumber[i] i~n-1:0。知道index就能定位出当前位应该放哪个值，由于是无放回抽样。需要删除值。 然后算下一个index。