50隙笆、Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (xn).
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行也找不到位置放置皇后了，說明所有的情況已經(jīng)迭代完畢了渗鬼，執(zhí)行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
和最大的子串
基本思路是這樣的邓尤，在每一步贴谎，我們維護兩個變量，一個是全局最優(yōu)澈魄，就是到當前元素為止最優(yōu)的解是仲翎，一個是局部最優(yōu)铛漓，就是必須包含當前元素的最優(yōu)的解浓恶。
動態(tài)規(guī)劃的遞推式（這是動態(tài)規(guī)劃最重要的步驟结笨，遞歸式出來了，基本上代碼框架也就出來了）伐憾。
假設我們已知第i步的global[i]（全局最優(yōu)）和local[i]（局部最優(yōu)）赫模，那么第i+1步的表達式是：
local[i+1]=Math.max(A[i], local[i]+A[i])，
就是局部最優(yōu)是一定要包含當前元素扫外，所以不然就是上一步的局部最優(yōu)local[i]+當前元素A[i]（因為local[i]一定包含第i個元素廓脆，所以不違反條件），
但是如果local[i]是負的驾讲，那么加上他就不如不需要的吮铭，所以不然就是直接用A[i]颅停；
global[i+1]=Math(local[i+1],global[i])，
有了當前一步的局部最優(yōu)纸肉，那么全局最優(yōu)就是當前的局部最優(yōu)或者還是原來的全局最優(yōu)
（所有情況都會被涵蓋進來喊熟，因為最優(yōu)的解如果不包含當前元素，那么前面會被維護在全局最優(yōu)里面烦味，如果包含當前元素壁拉，那么就是這個局部最優(yōu)）岩遗。
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
給定一個非負整數(shù)數(shù)組笔诵，最初定位在數(shù)組的第一個索引處姑子。
數(shù)組中的每個元素表示該位置的最大跳轉(zhuǎn)長度。
確定您是否能夠到達最后一個索引谢翎。
[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區(qū)間合并
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的第一個數(shù)字排序
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區(qū)間插入
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].
分析：
插入?yún)^(qū)間
一組非負數(shù)據(jù)區(qū)間谊迄，插入一個新的區(qū)間，如果可以歪脏，合并
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]]
思路：將新的區(qū)間插入到list中粮呢，數(shù)組排序合并
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 ]
]
分析：
螺旋矩陣
給定一個正數(shù)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個正數(shù)秧骑，每個數(shù)在最高位出現(xiàn)(n-1)!次，最高位確定后绒疗，在第二高位出現(xiàn)(n-2)!次骂澄，最高位和次高位確定后，在第三高位出現(xiàn)次數(shù)(n-3)!次磨镶。健提。。矩桂。。依次類推雹锣，數(shù)字不會超過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
