【2019-06-17】leetcode(61-70)
61、回转列表
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
"""
回转链表
给定一个链表，回转k个位置
ex.Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
"""
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if k==0:
return head
if head==None:
return head
dummy=ListNode(0)
dummy.next=head
p=dummy #定义指针
count=0
while p.next:
p=p.next
count+=1 #链表的长度
p.next=dummy.next
step=count-(k%count)#循环右移的次数
for i in range(0,step):
p=p.next
head=p.next
p.next=None
return head
62、uniquePath
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?
"""
路径
机器人在左上方，棋盘m*n
机器人每次只能往下或往右走，走到右下角（标记finish的格子）结束。
ex.m=3,n=2, 3列，2行
step1:right /down
step2:right/down right
step3:dowm/right right.
结果有3种可能
动态规划，状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]
"""
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
list=[[0 for i in range(n)] for i in range(m)]
for i in range(0,n):
list[0][i]=1
for i in range(0,m):
list[i][0]=1
for i in range(1,m):
for j in range(1,n):
list[i][j]=list[i-1][j]+list[i][j-1]
return list[m-1][n-1]
63、Unique Paths II 有障碍物的路径
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?
"""
路径
有障碍物的情况下有几种路径结果
障碍物标识为1，可走的点标识为0
动态规划
"""
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m=len(obstacleGrid)#行
n=len(obstacleGrid[0])#列
dp=[[0]*n for _ in range(m)] #初始化 m*n 的0矩阵
if obstacleGrid[0][0]==0:
dp[0][0]=1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j]==1:
dp[i][j]=0
else:
if i!=0:
dp[i][j]+=dp[i-1][j]
if j!=0:
dp[i][j]+=dp[i][j-1]
return dp[m-1][n-1]
64、 Minimum Path Sum
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.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
"""
最小路径和
m*n 矩阵
一组非负整数，从左上方到右下方的最小的路径和
动态规划
"""
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m=len(grid)#行
n=len(grid[0])#列
dp=[[0]*n for _ in range(m)] #初始化 m*n 的0矩阵
dp[0][0]=grid[0][0]
for i in range(1,n):
dp[0][i] = dp[0][i-1] + grid[0][i]
for i in range(1,m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
65、Valid Number
Validate if a given string can be interpreted as a decimal number.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:
Numbers 0-9
Exponent - "e"
Positive/negative sign - "+"/"-"
Decimal point - "."
"""
验证给定字符串是否可以解释为十进制数。
"""
解法1：
class Solution:
def isNumber(self, s: str) -> bool:
import re
return bool(re.match("^\s*[\+\-]?((\d+(\.\d*)?)|\.\d+)([eE][+-]?\d+)?\s*$",s))
解法2:
class Solution:
# @param s, a string
# @return a boolean
# @finite automation
def isNumber(self, s):
INVALID=0; SPACE=1; SIGN=2; DIGIT=3; DOT=4; EXPONENT=5;
#0invalid,1space,2sign,3digit,4dot,5exponent,6num_inputs
#行代表了9种状态，列代表了6种输入方式也就是6种跳转方式。
transitionTable=[[-1, 0, 3, 1, 2, -1], #0 no input or just spaces
[-1, 8, -1, 1, 4, 5], #1 input is digits
[-1, -1, -1, 4, -1, -1], #2 no digits in front just Dot
[-1, -1, -1, 1, 2, -1], #3 sign
[-1, 8, -1, 4, -1, 5], #4 digits and dot in front
[-1, -1, 6, 7, -1, -1], #5 input 'e' or 'E'
[-1, -1, -1, 7, -1, -1], #6 after 'e' input sign
[-1, 8, -1, 7, -1, -1], #7 after 'e' input digits
[-1, 8, -1, -1, -1, -1]] #8 after valid input input space
state=0; i=0
while i<len(s):
inputtype = INVALID
if s[i]==' ': inputtype=SPACE
elif s[i]=='-' or s[i]=='+': inputtype=SIGN
elif s[i] in '0123456789': inputtype=DIGIT
elif s[i]=='.': inputtype=DOT
elif s[i]=='e' or s[i]=='E': inputtype=EXPONENT
state=transitionTable[state][inputtype]
if state==-1: return False
else: i+=1
return state == 1 or state == 4 or state == 7 or state == 8
66、 Plus One
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
"""
给定一个非负数组整数，给整数加1
"""
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
a=len(digits)-1
flag=0
for i in range(a,-1,-1):
if digits[i]+1==10:
digits[i]=0
flag=1
else:
digits[i]+=flag
flag=0
if flag==1:
digits.insert(0,1) #list(index,obj)插入的位置和对象
return digits
67、addBinary
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
"""
二进制加法
"""
方法1:
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
if not a or not b:
return a if a else b
if a[-1] == '1' and b[-1] == '1':
return self.addBinary(self.addBinary(a[:-1], b[:-1]), '1') + '0'
elif a[-1] == '0' and b[-1] == '0':
return self.addBinary(a[:-1], b[:-1]) + '0'
else:
return self.addBinary(a[:-1], b[:-1]) + '1'
方法2:
class Solution:
def addBinary(self, a: str, b: str) -> str:
la=len(a)-1
lb=len(b)-1
flag=0
res=''
while (la>=0 and lb>=0):
n=int(a[la])+int(b[lb])+flag
flag=n/2
n%=2
res=str(n)+res
la-=1
lb-=1
while la>=0:
n=int(a[la])+flag
flag=n/2
n%=2
res=str(n)+res
la-=1
while lb>=0:
n=int(b[lb])+flag
flag=n/2
n%=2
res=str(n)+res
lb-=1
if flag==1:
res='1'+res
return res
68、Text Justification
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
"""
文本判断
"""
class Solution:
# @param words, a list of strings
# @param L, an integer
# @return a list of strings
def fullJustify(self, words, L):
res=[]
i=0
while i<len(words):
size=0; begin=i
while i<len(words):
newsize=len(words[i]) if size==0 else size+len(words[i])+1
if newsize<=L: size=newsize
else: break
i+=1
spaceCount=L-size
if i-begin-1>0 and i<len(words):
everyCount=spaceCount//(i-begin-1)
spaceCount%=i-begin-1
else:
everyCount=0
j=begin
while j<i:
if j==begin: s=words[j]
else:
s+=' '*(everyCount+1)
if spaceCount>0 and i<len(words):
s+=' '
spaceCount-=1
s+=words[j]
j+=1
s+=' '*spaceCount
res.append(s)
return res
69、Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
"""
sqrt(x)
开方
class Solution:
def mySqrt(self, x: int) -> int:
import math
return int(math.sqrt(x))
"""
"""
sqrt(x)
开方
二分查找
"""
class Solution:
def mySqrt(self, x: int) -> int:
if x==0:
return 0
i=1
j=x//2+1
while (i<=j):
mid=i+(j-i)//2
sq=x/mid
if sq>mid:
i=mid+1
elif sq<mid:
j=mid-1
else:
return mid
return j
70、Climbing stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
"""
爬楼梯
每次一到两阶，一共n阶
动态规划
f(n)=f(n-1)+f(n-2)
"""
class Solution:
def climbStairs(self, n: int) -> int:
dp=[1 for i in range(n+1)]
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
