61. Rotate List （Medium）
Given the head of a linked list, rotate the list to the right by k places.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head: return head
def length(head):
c=0
tail=None
while head:
c+=1
tail=head
head=head.next
return c,tail
leng,tail = length(head)
k = k%leng
if k==leng or k==0: return head
p1=head
p2=head
for _ in range(k):
p2=p2.next
while p2.next:
p1=p1.next
p2=p2.next
new_head=p1.next
p1.next=None
tail.next=head
return new_head
#concise writing with dummy head
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if k==0 or (not head): return head
l=0
cur=head
while cur:
l+=1
cur=cur.next
if k%l==0: return head
k=k%l
dummy=ListNode(-1)
dummy.next=head
p1=p2=dummy
for _ in range(k):
p2=p2.next
while p2.next:
p1=p1.next
p2=p2.next
newhead=p1.next
p1.next=None
p2.next=dummy.next
return newhead
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# k=2
# 1->2->3->-4->5
# A
# B
if not head : return head
def length(head):
c=0
while head:
c+=1
head = head.next
return c
k= k% length(head)
if k==0: return head
head_backup = head
A=head
B=head
for _ in range(k):
A = A.next
while A.next:
A =A.next
B= B.next
res = B.next
A.next=head_backup
B.next=None
return res
细心。。。
62. Unique Paths (Medium)
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
### 0 1 1 1 1 1 1
### 1 2 3 4 5 6 7
### 1
### 1
### 1
# m rows n cols
# dp[i][j] = dp[i][j-1]+dp[i-1][j]
#
dp = [[0]*n for _ in range(m)]
for i in range(n):
if i==0: continue
dp[0][i]=1
for i in range(m):
if m==0: continue
dp[i][0]=1
for row in range(1,m):
for col in range(1,n):
dp[row][col]=dp[row][col-1]+dp[row-1][col]
return dp[m-1][n-1]
63. Unique Paths II (Medium)
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and space is marked as 1 and 0 respectively in the grid.
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
### 0 1 1 1 1 1 1
### 1 2 3 4 5 6 7
### 1 O
### 1
### 1
# m rows n cols
# dp[i][j] = dp[i][j-1]+dp[i-1][j]
#
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[m-1][n-1]==1 or obstacleGrid[0][0]==1 : return 0
dp = [[0]*n for _ in range(m)]
for i in range(n):
if i==0: continue
if obstacleGrid[0][i]!=1:
dp[0][i]=1
else:
break
for i in range(m):
if m==0: continue
if obstacleGrid[i][0]!=1:
dp[i][0]=1
else:
break
for row in range(1,m):
for col in range(1,n):
rowcol1 = dp[row][col-1] if obstacleGrid[row][col-1]!=1 else 0
row1col = dp[row-1][col] if obstacleGrid[row-1][col]!=1 else 0
dp[row][col]=rowcol1+row1col
return dp[m-1][n-1]
dp去解， 注意edge case， 在起始和终止位置blok。
64. Minimum Path Sum (Medium)
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
m=len(grid)
n=len(grid[0])
dp = [[0]*n for _ in range(m)]
for i in range(n):
if i==0:
dp[0][0]=grid[0][0]
else:
dp[0][i] = dp[0][i-1]+grid[0][i]
for i in range(m):
if i==0:
dp[0][0]=grid[0][0]
else:
dp[i][0]=dp[i-1][0]+grid[i][0]
for row in range(1,m):
for col in range(1,n):
dp[row][col]=min(dp[row-1][col],dp[row][col-1])+grid[row][col]
return dp[m-1][n-1]
65. Valid Number (Hard)
Finite state machine, but hard to write ..... 试了半天。。。。没试出来。。。
class Solution:
def isNumber(self, s: str) -> bool:
s = s.lower()
#define DFA(determinstic finite automation) state transition tables
states = [{},
# State (1) - initial state (scan ahead thru blanks)
{'blank': 1, 'sign': 2, 'digit':3, '.':4},
# State (2) - found sign (expect digit/dot)
{'digit':3, '.':4},
# State (3) - digit consumer (loop until non-digit)
{'digit':3, '.':5, 'e':6, 'blank':9},
# State (4) - found dot (only a digit is valid)
{'digit':5},
# State (5) - after dot (expect digits, e, or end of valid input)
{'digit':5, 'e':6, 'blank':9},
# State (6) - found 'e' (only a sign or digit valid)
{'sign':7, 'digit':8},
# State (7) - sign after 'e' (only digit)
{'digit':8},
# State (8) - digit after 'e' (expect digits or end of valid input)
{'digit':8, 'blank':9},
# State (9) - Terminal state (fail if non-blank found)
{'blank':9}]
currentState = 1
for c in s:
# If char c is of a known class set it to the class name
if c in '0123456789':
c = 'digit'
elif c in ' ':
c = 'blank'
elif c in '+-':
c = 'sign'
# If char/class is not in our state transition table it is invalid input
if c not in states[currentState]:
return False
# State transition
currentState = states[currentState][c]
# The only valid terminal states are end on digit, after dot, digit after e, or white space after valid input
if currentState not in [3,5,8,9]:
return False
return True
66. Plus One (Easy)
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
res = []
carry=0
First=True
for i in digits[::-1]:
if First:
val = carry+i+1
First=False
else:
val = carry+i
carry = val//10
val = val%10
res.append(val)
if carry!=0:
res.append(carry)
return res[::-1]
67. Add Binary （Easy）
Given two binary strings a and b, return their sum as a binary string.
class Solution:
def addBinary(self, a: str, b: str) -> str:
res = []
carry=0
a = [int(e) for e in a][::-1]
b = [int(e) for e in b][::-1]
while a or b:
inta = a[0] if a else 0
intb = b[0] if b else 0
val = carry+inta+intb
carry=val//2
res.append(val%2)
a=a[1:] if a else None
b=b[1:] if b else None
if carry:
res.append(1)
return ''.join([str(e) for e in res[::-1]])
68. Text Justification (Hard)
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
# W1+1 W2+1 W3
level = []
res = []
c_level = 0
while words:
word = words.pop(0)
lw = len(word)
c_level+=(lw+1)
if c_level-1>maxWidth:
words = [word]+words
res.append(level[:])
level=[]
c_level=0
else:
level.append(word)
if level:
res.append(level)
result = []
for rowid,row in enumerate(res):
l = len(row)
ngap =l-1
if rowid!=len(res)-1:
if ngap!=0:
i=0
while sum([len(w) for w in row])<maxWidth:
ind = i%ngap
row[ind] = row[ind]+' '
i+=1
row = ''.join(row)
else:
row = row[0]+' '*(maxWidth-len(row[0]))
else:
row=' '.join(row)
row = row+' '*(maxWidth-len(row))
result.append(row)
return result
round robin 分配除了最后一行外的空格。。。
69. Sqrt(x) （Easy）
Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
class Solution:
def mySqrt(self, x: int) -> int:
l=0
r=x
while l<=r:
m=(l+r)//2
if m**2<=x and (m+1)**2>x:
return m
elif m**2>x:
r=m-1
else:
l=m+1
直接二分法了。。
70. Climbing Stairs （Easy）
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
class Solution:
def climbStairs(self, n: int) -> int:
#
# 0 step to climit to 0 0
# 1 step to clime to 1 1
# 1+1 to clime to 2
if n==1: return 1
if n==2: return 2
dp = [0]*(n+1)
dp[1]=1
dp[2]=2
# dp[n] = dp[n-1]+dp[n-2]
for i in range(3,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
class Solution:
def climbStairs(self, n: int) -> int:
# n = 1 1
# n = 2 2
# dp[n] = dp[n-1]+dp[n-2]
if n==1: return 1
if n==2: return 2
dpn1 =2
dpn2 =1
dpn = 0
for i in range(3,n+1):
dpn = dpn1+dpn2
dpn1_old=dpn1
dpn1 = dpn
dpn2 = dpn1_old
return dpn
简单dynamic programming应用。