Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb6c4471

Browse files
committed
Update
Update
1 parent6bd7dc3 commitb6c4471

6 files changed

+205
-0
lines changed
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Given a sorted array of integers, find the starting and ending position of a given target value.
5+
6+
Your algorithm's runtime complexity must be in the order of O(log n).
7+
8+
If the target is not found in the array, return [-1, -1].
9+
10+
For example,
11+
Given [5, 7, 7, 8, 8, 10] and target value 8,
12+
return [3, 4].
13+
'''
14+
15+
16+
classSolution(object):
17+
defsearchRange(self,nums,target):
18+
"""
19+
:type nums: List[int]
20+
:type target: int
21+
:rtype: List[int]
22+
"""
23+
foriinrange(len(nums)):
24+
ifnums[i]==target:
25+
left=i
26+
break
27+
else:
28+
return [-1,1]
29+
# find the index of the rightmost appearance of `target` (by reverse
30+
# iteration). it is guaranteed to appear.
31+
forjinrange(len(nums)-1,-1,-1):
32+
ifnums[j]==target:
33+
right=j
34+
break
35+
return [left,right]
36+
37+
38+
39+
40+
41+
if__name__=="__main__":
42+
assertSolution().searchRange([5,7,7,8,8,10],8)== [3,4]
43+
assertSolution().searchRange([5,7,7,8,8,10],5)== [0,0]
44+
assertSolution().searchRange([5,7,7,8,8,10],7)== [1,2]
45+
assertSolution().searchRange([5,7,7,8,8,10],10)== [5,5]

‎Python3/038_Count_and_Say.py

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
The count-and-say sequence is the sequence of integers beginning as follows:
5+
1, 11, 21, 1211, 111221, ...
6+
7+
1 is read off as "one 1" or 11.
8+
11 is read off as "two 1s" or 21.
9+
21 is read off as "one 2, then one 1" or 1211.
10+
Given an integer n, generate the nth sequence.
11+
12+
Note: The sequence of integers will be represented as a string.
13+
'''
14+
15+
16+
classSolution(object):
17+
defcountAndSay(self,n):
18+
"""
19+
:type n: int
20+
:rtype: str
21+
"""
22+
result="1"
23+
for__inrange(1,n):
24+
result=self.getNext(result)
25+
returnresult
26+
27+
defgetNext(self,s):
28+
result= []
29+
start=0
30+
whilestart<len(s):
31+
curr=start+1
32+
whilecurr<len(s)ands[start]==s[curr]:
33+
curr+=1
34+
result.extend((str(curr-start),s[start]))
35+
start=curr
36+
return"".join(result)
37+
38+
39+
if__name__=="__main__":
40+
assertSolution().countAndSay(5)=="111221"
41+
42+
43+

‎Python3/050_Pow(x, n).py

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Implement pow(x, n).
5+
'''
6+
7+
8+
classSolution(object):
9+
defmyPow(self,x,n):
10+
"""
11+
:type x: float
12+
:type n: int
13+
:rtype: float
14+
"""
15+
flag=1ifn>=0else-1
16+
result=1
17+
n=abs(n)
18+
whilen>0:
19+
ifn&1==1:
20+
result*=x
21+
n>>=1
22+
x*=x
23+
ifflag<0:
24+
result=1/result
25+
returnresult
26+
27+
28+
if__name__=="__main__":
29+
assertSolution().myPow(2,5)==32
30+
assertSolution().myPow(2.1,2)==4.41

‎Python3/062_Unique_Paths_method1.py

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
5+
6+
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).
7+
8+
How many possible unique paths are there?
9+
10+
11+
Above is a 3 x 7 grid. How many possible unique paths are there?
12+
13+
Note: m and n will be at most 100.
14+
'''
15+
16+
17+
classSolution(object):
18+
defuniquePaths(self,m,n):
19+
"""
20+
:type m: int
21+
:type n: int
22+
:rtype: int
23+
"""
24+
dp= [[1for__inrange(n)]for__inrange(m)]
25+
foriinrange(1,n):
26+
forjinrange(1,m):
27+
dp[j][i]=dp[j-1][i]+dp[j][i-1]
28+
returndp[m-1][n-1]
29+
30+
31+
if__name__=="__main__":
32+
assertSolution().uniquePaths(3,7)==28

‎Python3/062_Unique_Paths_method2.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
5+
6+
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).
7+
8+
How many possible unique paths are there?
9+
10+
11+
Above is a 3 x 7 grid. How many possible unique paths are there?
12+
13+
Note: m and n will be at most 100.
14+
'''
15+
importmath
16+
17+
18+
classSolution(object):
19+
defuniquePaths(self,m,n):
20+
"""
21+
:type m: int
22+
:type n: int
23+
:rtype: int
24+
"""
25+
m-=1
26+
n-=1
27+
returnint(math.factorial(m+n)/ (math.factorial(m)*math.factorial(n)))
28+
29+
30+
if__name__=="__main__":
31+
assertSolution().uniquePaths(3,7)==28

‎Python3/069_Sqrt(x).py

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#!usr/bin/env python3
2+
# -*- coding:utf-8 -*-
3+
'''
4+
Implement int sqrt(int x).
5+
6+
Compute and return the square root of x.
7+
'''
8+
9+
10+
classSolution(object):
11+
defmySqrt(self,x):
12+
"""
13+
:type x: int
14+
:rtype: int
15+
"""
16+
result=1.0
17+
whileabs(result**2-x)>0.1:
18+
result= (result+x/result)/2
19+
returnint(result)
20+
21+
22+
if__name__=="__main__":
23+
assertSolution().mySqrt(5)==2
24+
assertSolution().mySqrt(0)==0

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp