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

Commit791f343

Browse files
committed
resolve
2 parents50ecf32 +64c3d84 commit791f343

File tree

13 files changed

+230
-0
lines changed

13 files changed

+230
-0
lines changed

‎EPI/EPI.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,10 @@
22
solutions to problems in EPI
33
"""
44

5+
<<<<<<<HEAD
6+
=======
7+
8+
>>>>>>>7488e4d602261a8615cebaf51ea6ebaac4ccb207
59
#naive recursion
610
defcc(n,denoms):
711
minCoins=100

‎EPI/EPI_ch5_arrays.py‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,8 +50,11 @@ def partition_opt(arr, i):
5050
Write a program which takes an array of digits representing a number N
5151
and update the array to represent N+1.
5252
"""
53+
<<<<<<<HEAD
5354

5455

5556
defknapsack(items,weights,W):
5657

58+
=======
59+
>>>>>>>7488e4d602261a8615cebaf51ea6ebaac4ccb207
5760

‎EPI/exploration.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
defcomposeRanges(nums):
2+
3+
4+
5+
#3/9
6+
# def permutation(a):
7+
# res = []
8+
# pHelper(a, res, [])
9+
# return res
10+
11+
# def pHelper(a, res, temp):
12+
# if len(temp) == len(a):
13+
# res.append(temp[:])
14+
# for n in a:
15+
# if n in temp:
16+
# continue
17+
# temp.append(n)
18+
# pHelper(a, res, temp)
19+
# temp.pop()
20+
21+
# print permutation([1, 2, 3])

‎Kangli/.DS_Store‎

6 KB
Binary file not shown.
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
classSolution(object):
2+
deffindMaxAverage(self,nums,k):
3+
a= [0]*(len(nums))
4+
temp=0
5+
foriinrange(len(nums)):
6+
temp+=nums[i]
7+
a[i]=temp
8+
a= [0]+a
9+
maxKSum=min(a)
10+
foriinrange(k,len(nums)+1):
11+
maxKSum=max(maxKSum,a[i]-a[i-k])
12+
returnmaxKSum/k

‎Kangli/DP/.Rhistory‎

Whitespace-only changes.

‎Kangli/DP/decodeWays.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#first solution, O(N) time and space
2+
classSolution(object):
3+
defnumDecodings(self,s):
4+
ifnots:
5+
return0
6+
dp= [0]*(len(s)+1)
7+
dp[0]=1
8+
foriinrange(1,len(s)+1):
9+
ifs[i-1]!='0':
10+
dp[i]+=dp[i-1]
11+
ifi!=1:
12+
ifint(s[i-2:i])inrange(10,27):
13+
dp[i]+=dp[i-2]
14+
returndp[len(s)]
15+
16+
17+
#O(N) time, O(1) space DP via "general fibonacci numbers"
18+
classSolution(object):
19+
defnumDecodings(self,s):
20+
iflen(s)==0ors[0]=='0':
21+
return0
22+
prev,prev_prev=1,0
23+
foriinxrange(len(s)):
24+
cur=0
25+
ifs[i]!='0':
26+
cur=prev
27+
ifi>0and (s[i-1]=='1'or (s[i-1]=='2'ands[i]<='6')):
28+
cur+=prev_prev
29+
prev,prev_prev=cur,prev
30+
returnprev
31+
32+

‎Kangli/DP/editDistance.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,4 +13,28 @@ def minDistance(self, word1, word2):
1313
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(word1[i-1]!=word2[j-1]))
1414
returndp[-1][-1]
1515

16+
#sample 282 ms submission
17+
classSolution(object):
18+
defminDistance(self,word1,word2):
19+
"""
20+
:type word1: str
21+
:type word2: str
22+
:rtype: int
23+
"""
24+
m=len(word1)
25+
n=len(word2)
26+
dp= [[0forxinxrange(n+1)]forxinxrange(m+1)]
27+
28+
foriinxrange(m+1):
29+
forjinxrange(n+1):
30+
ifi==0:
31+
dp[i][j]=j
32+
elifj==0:
33+
dp[i][j]=i
34+
elifword1[i-1]==word2[j-1]:
35+
dp[i][j]=dp[i-1][j-1]
36+
else:
37+
dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
38+
39+
returndp[m][n]
1640

‎Kangli/DP/perfectSquares.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
sample3626mssubmission
2+
classSolution(object):
3+
defnumSquares(self,n)
4+
#這題用dp來做 dp[i]儲存數字i由幾個square number組成 dp[i]=min(dp[i-1*1],dp[i-2*2],...)+1
5+
dp=[0foriinrange(n+1)]
6+
foriinrange(1,n+1):
7+
j=1
8+
minv=2147483647
9+
ifmath.sqrt(i)-int(math.sqrt(i))==0:
10+
dp[i]=1
11+
continue
12+
whilei-j*j>=0:
13+
ifminv>dp[i-j*j]:
14+
minv=dp[i-j*j]
15+
j+=1
16+
dp[i]=minv+1
17+
returndp[n]

‎Kangli/LinkedList/addTwoNumbers.py‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
classListNode(object):
2+
def__init__(self,x):
3+
self.val=x
4+
self.next=None
5+
6+
classSolution(object):
7+
defaddTwoNumbers(self,l1,l2):
8+
dummy=cur=ListNode(0)
9+
carry=0
10+
whilel1orl2orcarry:
11+
ifl1:
12+
carry+=l1.val
13+
l1=l1.next
14+
ifl2:
15+
carry+=l2.val
16+
l2=l2.next
17+
cur.next=ListNode(carry%10)
18+
cur=cur.next
19+
carry//=10
20+
returndummy.next
21+
s=Solution()
22+
l1=ListNode(2)
23+
l1.next=ListNode(4)
24+
l2=ListNode(5)
25+
l2.next=ListNode(6)
26+
s.addTwoNumbers(l1,l2)

0 commit comments

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