Skip to content

Commit 108294c

Browse files
heqin-zhuheqin-zhu
committed
Add nege weight num and dp examples
1 parent 247df5f commit 108294c

6 files changed

Lines changed: 195 additions & 0 deletions

File tree

‎dynamicProgramming/last-stone-weight.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#coding: utf-8
2+
''' mbinary
3+
#######################################################################
4+
# File : last-stone-weight.py
5+
# Author: mbinary
6+
# Mail: zhuheqin1@gmail.com
7+
# Blog: https://mbinary.xyz
8+
# Github: https://github.com/mbinary
9+
# Created Time: 2019-05-28 23:30
10+
# Description:
11+
leetcode 1049: https://leetcode-cn.com/problems/last-stone-weight-ii/
12+
13+
有一堆石头，每块石头的重量都是正整数。
14+
15+
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
16+
17+
如果 x == y，那么两块石头都会被完全粉碎；
18+
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
19+
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
20+
21+
#######################################################################
22+
'''
23+
24+
class Solution:
25+
def lastStoneWeightII(self, stones: List[int]) -> int:
26+
sm = sum(stones)
27+
ans = sm//2
28+
dp = [0]*(ans+1)
29+
for x in stones:
30+
for j in range(ans,x-1,-1):
31+
dp[j] = max(dp[j],dp[j-x]+x)
32+
return sm-2*dp[ans]

‎dynamicProgramming/max-len-of-repeated-subarray.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#coding: utf-8
2+
''' mbinary
3+
#######################################################################
4+
# File : max-len-of-repeated-subarray.py
5+
# Author: mbinary
6+
# Mail: zhuheqin1@gmail.com
7+
# Blog: https://mbinary.xyz
8+
# Github: https://github.com/mbinary
9+
# Created Time: 2019-05-27 08:25
10+
# Description:
11+
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
12+
#######################################################################
13+
'''
14+
def findLength(A,B):
15+
n,m = len(A),len(B)
16+
dp = [[0]*(m+1) for i in range(n+1)]
17+
for i in range(1,n+1):
18+
for j in range(1,m+1):
19+
if A[i-1]==B[j-1]:
20+
dp[i][j]=dp[i-1][j-1]+1
21+
return max(max(row) for row in dp)

‎graph/dfs.py‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#coding: utf-8
2+
''' mbinary
3+
#######################################################################
4+
# File : dfs.py
5+
# Author: mbinary
6+
# Mail: zhuheqin1@gmail.com
7+
# Blog: https://mbinary.xyz
8+
# Github: https://github.com/mbinary
9+
# Created Time: 2019-05-27 10:02
10+
# Description:
11+
from leetcode-cn #1048: https://leetcode-cn.com/problems/longest-string-chain/
12+
给出一个单词列表，其中每个单词都由小写英文字母组成。
13+
14+
如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
15+
16+
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
17+
18+
从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
19+
20+
#######################################################################
21+
'''
22+
23+
class Solution:
24+
def longestStrChain(self, words: List[str]) -> int:
25+
def isAdj(s1,s2):
26+
if len(s1)>len(s2):
27+
s1,s2 = s2,s1
28+
n1,n2 = len(s1),len(s2)
29+
if n2-n1!=1:
30+
return False
31+
i=j=0
32+
flag = False
33+
while i<n1 and j<n2:
34+
if s1[i]!=s2[j]:
35+
if flag:
36+
return False
37+
flag = True
38+
j+=1
39+
else:
40+
i+=1
41+
j+=1
42+
return True
43+
44+
def dfs(begin):
45+
ans = 1
46+
w = words[begin]
47+
n = len(w)
48+
if n+1 in lenDic:
49+
for nd in lenDic[n+1]:
50+
#print(w,words[nd],isAdj(w,words[nd]))
51+
if isAdj(w,words[nd]):
52+
ans = max(ans,1+dfs(nd))
53+
return ans
54+
lenDic = {}
55+
for i in range(len(words)):
56+
n = len(words[i])
57+
if n in lenDic:
58+
lenDic[n].add(i)
59+
else:
60+
lenDic[n]={i}
61+
62+
lens = sorted(lenDic)
63+
n = len(lens)
64+
ans = 0
65+
for i in range(n):
66+
if ans < n-i:
67+
for nd in lenDic[lens[i]]:
68+
ans = max(ans,dfs(nd))
69+
return ans
70+

‎math/numWeight/addNegaBin.py‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#coding: utf-8
2+
''' mbinary
3+
#######################################################################
4+
# File : addNegaBin.py
5+
# Author: mbinary
6+
# Mail: zhuheqin1@gmail.com
7+
# Blog: https://mbinary.xyz
8+
# Github: https://github.com/mbinary
9+
# Created Time: 2019-06-02 22:32
10+
# Description:
11+
12+
给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。
13+
14+
数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 的数字也同样不含前导零：以 arr 为例，这意味着要么 arr == [0]，要么 arr[0] == 1。
15+
16+
返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
17+
18+
eg
19+
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
20+
输出：[1,0,0,0,0]
21+
解释：arr1 表示 11，arr2 表示 5，输出表示 16
22+
#######################################################################
23+
'''
24+
from nega import nega
25+
26+
def addNegaBin(arr1: list, arr2: list) -> list:
27+
if len(arr1) < len(arr2):
28+
arr1, arr2 = arr2, arr1
29+
for i in range(-1, -len(arr2) - 1, -1):
30+
if arr1[i] == 1 and arr2[i] == 1:
31+
arr1[i] = 0
32+
mux = 0
33+
for j in range(i - 1, -len(arr1) - 1, -1):
34+
if arr1[j] == mux:
35+
mux = 1 - mux
36+
arr1[j] = mux
37+
else:
38+
arr1[j] = mux
39+
break
40+
else:
41+
arr1 = [1, 1] + arr1
42+
43+
elif arr1[i] == 0 and arr2[i] == 1:
44+
arr1[i] = arr2[i]
45+
#print(arr1,arr2,i)
46+
while len(arr1) > 1 and arr1[0] == 0:
47+
arr1.pop(0)
48+
return arr1
49+
50+
if __name__=='__main__':
51+
while 1:
52+
print("input q to quit or input x1 x2: ")
53+
s = input()
54+
if s=='q':
55+
break
56+
n1,n2 =[int(i) for i in s.split()]
57+
l1,l2 = nega(n1),nega(n2)
58+
print(n1,l1)
59+
print(n2,l2)
60+
print(f'{n1}+{n2}={n1+n2}: {addNegaBin(l1,l2)}')

math/convertWeight.py renamed to math/numWeight/convertWeight.py

File renamed without changes.

‎math/numWeight/nega.py‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
def nega(n:int,base=-2:int)->:list:
2+
'''return list of num, the first is the highest digit'''
3+
if base>-2:
4+
raise Exception(f"[Error]: invalid base: {base}, base should be no more than -2")
5+
ans = []
6+
while n:
7+
k = n%base
8+
if k<0:
9+
k-=base
10+
ans.append(k)
11+
n = (n-k)//base
12+
return ans[::-1]

0 commit comments

Comments
 (0)