leetcode13

Spiral Matrix

#coding=utf-8 class Solution(object): def spiralOrder(self, matrix): """ :type matrix: List[List[int]] :rtype: List[int] """ res=[] while matrix: if len(matrix)==0: break for i in matrix[0]: res.append(i) matrix.pop(0) if len(matrix)==0: break for i in range(len(matrix)): res.append(matrix[i][-1]) matrix[i].pop() if len(matrix[0])==0: break for i in matrix[-1][::-1]: res.append(i) matrix.pop() if len(matrix)==0: break for i in range(len(matrix)-1,-1,-1): res.append(matrix[i][0]) matrix[i].pop(0) if len(matrix[0])==0: break return res

Sudoku Solver 牛客上做过一遍，结果忘了。。。

class Solution(object): def solveSudoku(self, board): """ :type board: List[List[str]] :rtype: void Do not return anything, modify board in-place instead. """ def isValid(x,y): temp=board[x][y] board[x][y]='D' for i in range(9): if board[i][y]==temp: return False for i in range(9): if board[x][i]==temp: return False for i in range(3): for j in range(3): if board[x/3*3+i][y/3*3+j]==temp: return False board[x][y]=temp return True def dfs(board): for i in range(9): for j in range(9): if board[i][j]=='.': for k in '123456789': board[i][j]=k if isValid(i,j) and dfs(board): return True board[i][j]='.' return False return True dfs(board)

Jump Game 自己用动态规划，结果超时了，这O(n)的方法真强。。。

class Solution: # @param A, a list of integers # @return a boolean def canJump(self, A): step = A[0] for i in range(1, len(A)): if step > 0: step -= 1 step = max(step, A[i]) else: return False return True

Count Primes 使用埃拉托斯特尼筛法

class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ n=max(n,2) isPrime=[True for i in range(n)] isPrime[0],isPrime[1]=False,False temp=2 while temp**2<n: if isPrime[temp]: p=temp**2 while p<n: isPrime[p]=False p+=temp temp+=1 count=0 for i in range(n): if isPrime[i]==True: count+=1 return count