Skip to content

Commit b15dd20

Browse files
heqin-zhuheqin-zhu
committed
Add sort codes and notes
0 parents  commit b15dd20

82 files changed

Lines changed: 15965 additions & 0 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
# 算法笔记
2+
记录学习算法的一些笔记, 想法, 以及代码实现 :smiley:

‎codes/dataStructure/8Astar.py‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
isVisited = [0]*362880 # 0 for not visited,1 for occured,2 for visited
2+
fac = [1,1,2,6,24,120,720,5040,40320]
3+
lf = len(fac)
4+
h = [[0,1,2,1,2,3,2,3,4],
5+
[1,0,1,2,1,2,3,2,3],
6+
[2,1,0,3,2,1,4,3,2],
7+
[1,2,3,0,1,2,1,2,3],
8+
[2,1,2,1,0,1,2,1,2],
9+
[3,2,1,2,1,0,3,2,1],
10+
[2,3,4,1,2,3,0,1,2],
11+
[3,2,3,2,1,2,1,0,1],
12+
[4,3,2,3,2,1,2,1,0]]
13+
14+
def cantor(s):
15+
sum = 0
16+
ls = len(s)
17+
for i in range(ls):
18+
count = 0
19+
for j in range(i+1,ls):
20+
if s[i] > s[j]: count +=1
21+
sum += count*fac[lf-i-1]
22+
return sum
23+
24+
que = []
25+
dir = {-3:'u',1:'r',3:'d',-1:'l'}
26+
class state:
27+
flag = True
28+
def __init__(self,s,x,f,step=0,last=0):
29+
self.x = x
30+
self.s = list(s)
31+
self.step = step
32+
self.path = []
33+
self.last = last
34+
self.f = f
35+
def can(self):
36+
cans = [-1,1,3,-3]
37+
if self.last in cans :
38+
cans.remove(-self.last)
39+
if self.x<3:
40+
cans.remove(-3)
41+
if self.x>5:
42+
cans.remove(3)
43+
if self.x%3 is 0:
44+
cans.remove(-1)
45+
if self.x%3 is 2:
46+
cans.remove(1)
47+
return cans
48+
def move(self):
49+
cans = self.can()
50+
for i in cans:
51+
s = list(self.s)
52+
tmp = self.x + i
53+
s[self.x] = s[tmp]
54+
s[tmp] = '9'
55+
ct = cantor(s)
56+
if isVisited[ct] != 2 :
57+
val = int(s[self.x])
58+
f = h[8][tmp] +h[val-1][self.x]-h[8][self.x]-h[val-1][tmp]+self.step+1
59+
new = state(s,tmp,f,self.step +1,i)
60+
new.path = self.path + [dir[i]]
61+
if isVisited[ct] == 1:
62+
for i,node in enumerate(que):
63+
if mew.s == node.s:
64+
del que[i]
65+
break
66+
else:isVisited[ct] = 1
67+
if que == []:
68+
que.append(new)
69+
continue
70+
for i,node in enumerate(que):
71+
if new.f<=node.f:
72+
que.insert(i,new)
73+
def solvable(s):
74+
reverse = 0
75+
for i in range(8):
76+
if s[i] is '9':continue
77+
for j in range(i+1,9):
78+
if s[i]>s[j]:reverse +=1
79+
if reverse % 2 is 0:return True
80+
else:return False
81+
def getPath(s,index):
82+
f = 0
83+
for i,j in enumerate(s):
84+
f+=h[int(j)-1][i]
85+
que.append(state(s,index,f,0,0))
86+
while que != []:
87+
cur = que.pop(0)
88+
ct = cantor(cur.s)
89+
isVisited[ct] = 2
90+
if ct is 0:
91+
return cur.path
92+
cur.move()
93+
94+
if __name__ == '__main__':
95+
s=input()
96+
index = s.find('x')
97+
s =list(s)
98+
s[index] = '9'
99+
if solvable(s):print(''.join(getPath(s,index)))
100+
else:print('unsolvable')

‎codes/dataStructure/EIGHT.py‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
from colectons import deque
2+
isVisted = [0]*362880
3+
fac = [1,2,6,24,120,720,5040,40320]
4+
lf = len(fac)
5+
x= '9'
6+
def cantor(s):
7+
sum = 0
8+
ls = len(s)
9+
for i in range(ls):
10+
count = 0
11+
for j in range(i+1;ls):
12+
if s[i] > s[j]: count +=1
13+
sum += count*fac[lf-i-1]
14+
return sum
15+
16+
que = deque()
17+
class state:
18+
def __init__(self,s,p,step=0,last=0):
19+
self.x = p
20+
self.s = list(s)
21+
self.step = step
22+
self.path = []
23+
self.last = last
24+
def move(self):
25+
dir = [-3:'u',1:'r',3:'d',-1:'l']
26+
if self.last in dir :
27+
del dir[-self.last]
28+
if self.x<3:
29+
del dir[-3]
30+
if self.x>5:
31+
del dir[3]
32+
if self.x%3 is 0:
33+
del dir[-1]
34+
if self.x%3 is 2:
35+
del dir[1]
36+
for i in dir.keys():
37+
s = list(self.s)
38+
tmp = self.x + i
39+
s[self.x] = s[tmp]
40+
s[tmp] = x
41+
if not isVisted[cantor(s)]:
42+
new = state(s,tmp,self.step +1,i)
43+
new.path = self.path + [dir[i]]
44+
que.append(new)
45+
46+
def getPath(s):
47+
index = s.find('x')
48+
s =list(s)
49+
s[index] = '9'
50+
que.append(state(s,index,0,0))
51+
while que != deque():
52+
cur = que.popleft()
53+
ct = cantor(cur.s)
54+
if ct is 362879:
55+
return cur.path
56+
isVisted[] = 1
57+
cur.move()
58+
59+
if __name__ == '__main__':
60+
s=input()
61+
print(''.join(getPath(s)))

‎codes/dataStructure/allOoneDS.py‎

Lines changed: 201 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,201 @@
1+
class node:
2+
def __init__(self,val=None,data_mp=None,pre=None,next=None):
3+
self.val=val
4+
self.data_mp = {} if data_mp is None else data_mp
5+
self.pre=pre
6+
self.next=next
7+
def __lt__(self,nd):
8+
return self.val<nd.val
9+
def getOne(self):
10+
if not self.data_mp:
11+
return ''
12+
else:return list(self.data_mp.items())[0][0]
13+
def __getitem__(self,key):
14+
return self.data_mp[key]
15+
def __iter__(self):
16+
return iter(self.data_mp)
17+
def __delitem__(self,key):
18+
del self.data_mp[key]
19+
def __setitem__(self,key,val):
20+
self.data_mp[key]= val
21+
def isEmpty(self):
22+
return self.data_mp=={}
23+
def __repr__(self):
24+
return 'node({},{})'.format(self.val,self.data_mp)
25+
class doubleLinkedList:
26+
def __init__(self):
27+
self.head= self.tail = node(0)
28+
self.head.next = self.head
29+
self.head.pre = self.head
30+
self.chain_mp={0:self.head}
31+
def __str__(self):
32+
li = list(self.chain_mp.values())
33+
li = [str(i) for i in li]
34+
return 'min:{}, max:{}\n'.format(self.head.val,self.tail.val) \
35+
+ '\n'.join(li)
36+
def getMax(self):
37+
return self.tail.getOne()
38+
def getMin(self):
39+
return self.head.getOne()
40+
def addIncNode(self,val):
41+
# when adding a node,inc 1, so it's guranted that node(val-1) exists
42+
self.chain_mp[val].pre= self.chain_mp[val-1]
43+
self.chain_mp[val].next= self.chain_mp[val-1].next
44+
self.chain_mp[val-1].next.pre = self.chain_mp[val-1].next = self.chain_mp[val]
45+
def addDecNode(self,val):
46+
# when adding a node,dec 1, so it's guranted that node(val+1) exists
47+
self.chain_mp[val].next= self.chain_mp[val+1]
48+
self.chain_mp[val].pre= self.chain_mp[val+1].pre
49+
self.chain_mp[val+1].pre.next = self.chain_mp[val+1].pre = self.chain_mp[val]
50+
def addNode(self,val,dec=False):
51+
self.chain_mp[val] = node(val)
52+
if dec:self.addDecNode(val)
53+
else:self.addIncNode(val)
54+
if self.tail.val<val:self.tail = self.chain_mp[val]
55+
if self.head.val>val or self.head.val==0:self.head= self.chain_mp[val]
56+
def delNode(self,val):
57+
self.chain_mp[val].next.pre = self.chain_mp[val].pre
58+
self.chain_mp[val].pre.next = self.chain_mp[val].next
59+
if self.tail.val==val:self.tail = self.chain_mp[val].pre
60+
if self.head.val==val:self.head = self.chain_mp[val].next
61+
del self.chain_mp[val]
62+
def incTo(self,key,val):
63+
if val not in self.chain_mp:
64+
self.addNode(val)
65+
self.chain_mp[val][key] = val
66+
if val!=1 : # key in the pre node
67+
del self.chain_mp[val-1][key]
68+
#print(self.chain_mp[val-1])
69+
if self.chain_mp[val-1].isEmpty():
70+
#print('*'*20)
71+
self.delNode(val-1)
72+
def decTo(self,key,val):
73+
if val not in self.chain_mp:
74+
self.addNode(val,dec=True)
75+
# notice that the headnode(0) shouldn't add key
76+
if val!=0: self.chain_mp[val][key] = val
77+
del self.chain_mp[val+1][key]
78+
if self.chain_mp[val+1].isEmpty():
79+
self.delNode(val+1)
80+
81+
class AllOne:
82+
def __init__(self):
83+
"""
84+
Initialize your data structure here.
85+
"""
86+
self.op = {"inc":self.inc,"dec":self.dec,"getMaxKey":self.getMaxKey,"getMinKey":self.getMinKey}
87+
self.mp = {}
88+
self.dll = doubleLinkedList()
89+
def __str__(self):
90+
return str(self.dll)
91+
def __getitem__(self,key):
92+
return self.mp[key]
93+
def __delitem__(self,key):
94+
del self.mp[key]
95+
def __setitem__(self,key,val):
96+
self.mp[key]= val
97+
def __iter__(self):
98+
return iter(self.mp)
99+
def inc(self, key,n=1):
100+
"""
101+
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
102+
:type key: str
103+
:rtype: void
104+
"""
105+
if key in self:
106+
self[key]+=n
107+
else:self[key]=n
108+
for i in range(n): self.dll.incTo(key, self[key])
109+
def dec(self, key,n=1):
110+
"""
111+
Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
112+
:type key: str
113+
:rtype: void
114+
"""
115+
if key in self.mp:
116+
mn = min( self[key],n)
117+
for i in range(mn): self.dll.decTo(key, self[key]-i-1)
118+
if self[key] == n:
119+
del self[key]
120+
else:
121+
self[key] = self[key]-n
122+
def getMaxKey(self):
123+
"""
124+
Returns one of the keys with maximal value.
125+
:rtype: str
126+
"""
127+
return self.dll.getMax()
128+
129+
def getMinKey(self):
130+
"""
131+
Returns one of the keys with Minimal value.
132+
:rtype: str
133+
"""
134+
return self.dll.getMin()
135+
136+
137+
138+
139+
if __name__ == '__main__':
140+
ops=["inc","inc","inc","inc","inc","dec","dec","getMaxKey","getMinKey"]
141+
data=[["a"],["b"],["b"],["b"],["b"],["b"],["b"],[],[]]
142+
obj = AllOne()
143+
for op,datum in zip(ops,data):
144+
print(obj.op[op](*datum))
145+
print(op,datum)
146+
print(obj)
147+
148+
'''
149+
None
150+
inc ['a']
151+
min:1, max:1
152+
node(0,{})
153+
node(1,{'a': 1})
154+
None
155+
inc ['b']
156+
min:1, max:1
157+
node(0,{})
158+
node(1,{'a': 1, 'b': 1})
159+
None
160+
inc ['b']
161+
min:1, max:2
162+
node(0,{})
163+
node(1,{'a': 1})
164+
node(2,{'b': 2})
165+
None
166+
inc ['b']
167+
min:1, max:3
168+
node(0,{})
169+
node(1,{'a': 1})
170+
node(3,{'b': 3})
171+
None
172+
inc ['b']
173+
min:1, max:4
174+
node(0,{})
175+
node(1,{'a': 1})
176+
node(4,{'b': 4})
177+
None
178+
dec ['b']
179+
min:1, max:3
180+
node(0,{})
181+
node(1,{'a': 1})
182+
node(3,{'b': 3})
183+
None
184+
dec ['b']
185+
min:1, max:2
186+
node(0,{})
187+
node(1,{'a': 1})
188+
node(2,{'b': 2})
189+
b
190+
getMaxKey []
191+
min:1, max:2
192+
node(0,{})
193+
node(1,{'a': 1})
194+
node(2,{'b': 2})
195+
a
196+
getMinKey []
197+
min:1, max:2
198+
node(0,{})
199+
node(1,{'a': 1})
200+
node(2,{'b': 2})
201+
'''

0 commit comments

Comments
 (0)