【2019-06-16】leetcode(50-60)

50、Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xⁿ).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/2^2 = 1/4 = 0.25
分析

"""
计算pow(x,n)
"""

class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def myPow(self, x, n):
        if n == 0:
            return 1.0
        elif n < 0:
            return 1 / self.myPow(x, -n)
        elif n % 2:
            return self.myPow(x*x,n//2)*x
        else:
            return self.myPow(x*x,n//2)

51、N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

class Solution:
    # @return a list of lists of string
    def solveNQueens(self, n):
        def check(k, j):  # check if the kth queen can be put in column j!
            for i in range(k):
                if board[i]==j or abs(k-i)==abs(board[i]-j):
                    return False
            return True
        def dfs(depth, valuelist):
            if depth==n: res.append(valuelist); return
            for i in range(n):
                if check(depth,i): 
                    board[depth]=i
                    s='.'*n
                    dfs(depth+1, valuelist+[s[:i]+'Q'+s[i+1:]])
        board=[-1 for i in range(n)]
        res=[]
        dfs(0,[])
        return res

52、N-Queens II
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.

"""
N 皇后问题2
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
"""
class Solution:
    # @return an integer
    def totalNQueens(self, n):
        def check(k, j):  # check if the kth queen can be put in column j!
            for i in range(k):
                if board[i]==j or abs(k-i)==abs(board[i]-j):
                    return False
            return True
        board=[-1 for i in range(n)]
        row=0; col=0; sum=0
        while row<n:
            while col<n:
                if check(row, col):
                    board[row]=col
                    col=0
                    break
                else:
                    col+=1
            if board[row]==-1:             #如果为真，即为在这一行找不到位置放置皇后
                if row==0:                 #如果在第0行也找不到位置放置皇后了，说明所有的情况已经迭代完毕了，执行break跳出操作。
                    break
                else:
                    row-=1                                            #这条语句用来回溯到上一行
                    col=board[row]+1                      #回溯到上一行时，皇后放置的位置要加1，也就是开始试验下一列
                    board[row]=-1                      #然后将这一行的值重置为-1，也就是说要重新寻找皇后的位置了
                    continue
            if row==n-1:                      #当row==n-1时，说明最后一行的皇后位置也确定了，得到了一个解
                sum+=1
                col=board[row]+1
                board[row]=-1
                continue
            row+=1
        return sum

53、Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
分析
Maximum Subarray
和最大的子串
基本思路是这样的，在每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。
动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。
假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第i+1步的表达式是：
local[i+1]=Math.max(A[i], local[i]+A[i])，
就是局部最优是一定要包含当前元素，所以不然就是上一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），
但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]；
global[i+1]=Math(local[i+1],global[i])，
有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优
（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        ThisSum = 0
        MaxSum = -10000
        
        for i in range( 0, len(A) ):
            if ThisSum < 0:
                ThisSum = 0
            ThisSum = ThisSum + A[ i ]
            MaxSum = max( ThisSum, MaxSum )

        return MaxSum

54、Spiral Matrix螺旋矩阵
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
分析

#回字形输出矩阵
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m=len(matrix)#行
        n=len(matrix[0])#列
        if m==0:
            return []
        r,l=0,0 
        m-=1
        n-=1
        ans=[]
        while r<=n and l<=m:
            for i in range(r,n+1):
                ans.append(matrix[l][i])
            l+=1
            if l>m:
                break
            for i in range(l,m+1):
                ans.append(matrix[i][n])
            n-=1
            i=n
            if n<r:
                break
            while i>=r:
                ans.append(matrix[m][i])
                i-=1
            m-=1
            i=m
            if m<1:
                break
            while i>=l:
                ans.append(matrix[i][r])
                i-=1
            r+=1
        return ans
        

55、Jump Game跳跃游戏
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

分析：
Jump Game
给定一个非负整数数组，最初定位在数组的第一个索引处。
数组中的每个元素表示该位置的最大跳转长度。
确定您是否能够到达最后一个索引。

[3,2,2,0,4]
b=3
a=5
(1)i=1, b=2,b=max(2,nums[1])=max(2,2)=2 3,2,2
(2)i=2, b=1,b=max(2,nums[2])=max(1,2)=2 3,2,2,0,4 //结束

[3,5,1,0,4]
b=3
a=5
(1)i=1, b=2,b=max(2,nums[1])=max(2,5)=5. 3,5,1,0,4 //结束

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        a=len(nums)
        b=nums[0]
        for i in range(1,a):
            if b>0:
                b-=1
                b=max(b,nums[i])
            else:
                return False
        return True

56、Merge Intervals区间合并
Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x : x[0]) #按照每个list的第一个数字排序
        ans,size = [],len(intervals)
        if size==0:
            return ans
        tmp=intervals[0]
        for i in intervals:
            if i[0]<=tmp[1]:
                tmp[1]=max(i[1],tmp[1])
            else:
                ans.append(tmp)
                tmp=i
        ans.append(tmp)
        return ans 

57、 Insert Interval区间插入
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

分析：
插入区间
一组非负数据区间，插入一个新的区间，如果可以，合并
ex.intervals=[[1,3],[6,9]], newInterval=[2,5] =====[[1,5],[6,9]]
intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]===== [[1,2],[3,10],[12,16]]
思路：将新的区间插入到list中，数组排序合并

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])
        length=len(intervals)
        res=[]
        for i in range(length):
            if res==[]:
                res.append(intervals[i])
            else:
                size=len(res)
                if res[size-1][0]<=intervals[i][0]<=res[size-1][1]:
                    res[size-1][1]=max(intervals[i][1],res[size-1][1])
                else:
                    res.append(intervals[i])
        return res

58、 Length of Last Word最后一个字符的长度
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Input: "Hello World"
Output: 5
分析：

最后一个单词的长度
思路：splitt

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

59、Spiral Matrix II螺旋矩阵
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
分析：

螺旋矩阵
给定一个正数n，生成一个方阵，填充的元素为1到n^2

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        A=[]
        x=n*n+1
        while x>1:
            x,y=x-len(A),x
            A=[list(range(x,y))]+list(zip(*A[::-1]))
        return A

60、Permutation Sequence全排列取指定的返回值

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.

分析：

序列全排列

按照顺序排列，返回第k个序列

n=3,k=3

123

132

213 ====k

231

312

321

n个正数，每个数在最高位出现(n-1)!次，最高位确定后，在第二高位出现(n-2)!次，最高位和次高位确定后，在第三高位出现次数(n-3)!次。。。。。依次类推，数字不会超过9。

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res=''
        k-=1
        fac=1
        for i in range(1,n):
            fac*=i
            num=[1,2,3,4,5,6,7,8,9]
        for i in reversed(range(n)):
            curr=num[int(k//fac)]
            res+=str(curr)
            num.remove(curr)
            if i!=0:
                k%=fac
                fac/=i
        return res