julyアルゴリズムレッスンノート
37526 ワード
# coding=utf-8
#
'''
S， ，
， ；
O(N)， O(1)。
：“I_have_a___dream!”， “Ihaveadream”
： 。
'''
import copy
import pprint
import random
import re
import collections
def is_remove(a_str):
pattern = re.compile(r"[\u4e00-\u9fa5]")
find_list = pattern.findall(a_str)
if find_list:
return False
else:
return True
def remove_blank(a_in_str, is_remove):
size = len(a_in_str)
str_list = list(a_in_str)
i = 0 #
j = 0 # ， j<=i
while (i < size):
if is_remove(str_list[i]):
i += 1
else:
if j < i:
str_list[j] = str_list[i]
i += 1
j += 1
return "".join(str_list[:j])
# print remove_blank("asdb dfd",is_remove)
# ：
'''
， 。
'''
def find_max(a_int_list):
if not a_int_list:
return
max = a_int_list[0]
for i in a_int_list:
if i > max:
max = i
return max
# print find_max([1,3,4,5,6,4,5])
#
'''
，
。
'''
def find_two_max(a_int_list):
if not a_int_list:
return
if len(a_int_list) < 2:
return
max = a_int_list[0]
max_2 = a_int_list[1]
for i in a_int_list:
if i > max:
max = i
elif i > max_2:
max_2 = i
return max, max_2
# print find_two_max([1,3,4,5,6,4,5])
#
'''
Huffman
Huffman 。
： ( )
， ，
，
。
Huffman ：
。
，
； ， 。
'''
#
def calc_frequency(a_in_str):
counter = collections.defaultdict(lambda: 0)
for a_char in a_in_str:
counter[a_char] += 1
return counter
#
class HuffmanNode():
def __init__(self):
self.value = 0
self.parent = None
self.left_child = None
self.right_child = None
def select_two_mini(hn_list):
#
#
if not hn_list:
return
mini_1 = None
mini_2 = None
i = 0
for node in hn_list:
if not node.value or node.parent is not None:
# , continue
i = i + 1
continue
else:
if mini_1 is None:
mini_1 = i
i += 1
continue
if mini_2 is None:
mini_2 = i
i += 1
continue
elif node.value < hn_list[mini_1].value:
mini_1 = i
elif node.value < hn_list[mini_2].value:
mini_2 = i
i += 1
return mini_1, mini_2
def HuffmanCoding(char_counter_dict):
if not char_counter_dict:
return
#
char_list = char_counter_dict.keys()
#
value_list = char_counter_dict.values()
leaf = len(char_counter_dict)
# 2n-1
node_num = 2 * leaf - 1
#
hn_list = [HuffmanNode() for _ in range(node_num)]
# leaf hn_list n
for i in range(leaf):
hn_list[i].value = value_list[i]
# ， hn_list,parent,child
for i in range(leaf, node_num):
node1, node2 = select_two_mini(hn_list)
hn_list[node1].parent = hn_list[node2].parent = i
hn_list[i].left_child = node1
hn_list[i].right_child = node2
hn_list[i].value = hn_list[node1].value + hn_list[node2].value
print hn_list
#
huffman_codding = []
for i in range(leaf):
a_codding = ""
child = i
pt = hn_list[i].parent
while (pt):
if hn_list[pt].left_child == child:
a_codding += "0"
else:
a_codding += "1"
child = pt
pt = hn_list[pt].parent
a_codding = a_codding[::-1]
huffman_codding.append(a_codding)
return dict(zip(char_list, huffman_codding))
# a_dict = {"A": 15, "B": 7, "C": 6, "D": 6, "E": 5}
# print HuffmanCoding(a_dict)
'''
：
S[0…N-1]， S k
S ， “abcdef”
2 ‘a’、‘b’
， “cdefab”：
k。
n+k k 。
： k n-k 。
：
O(n)， O(1)。
：
a , i b， c，
bc，
i cb，
bc cb。
b b'， c c'，
(b'c')' cb。
'''
def reverse_str(a_str_list, start, end):
if not a_str_list:
return
while (end > start):
tem = a_str_list[start]
a_str_list[start] = a_str_list[end]
a_str_list[end] = tem
start += 1
end -= 1
def circulation(a_in_str, k_len):
a_list = list(a_in_str)
reverse_str(a_list, 0, k_len - 1)
reverse_str(a_list, k_len, len(a_in_str) - 1)
reverse_str(a_list, 0, len(a_in_str) - 1)
return "".join(a_list)
# print circulation("abcde",2)
############################################## 、 、 #####################################################
'''
Eratosthenes
N， N 。
Eratosthenes
2 N ；
x， x ； x ， x
；
， ，
N 。
， “ ”。
'''
# : a ，a*a , a*a
#
def Eratosthenes(end_num):
all_num_flags = [True for i in xrange(1, end_num + 2)]
all_num_flags[0] = False # ，0
#
p = 2 #
end_range = p * p
while end_range <= end_num:
# p p*p
cp = end_range
while cp <= end_num:
all_num_flags[cp] = False
cp += p
#
p += 1
while not all_num_flags[p]:
p += 1
end_range = p * p
i = 0
prime_num_list = []
for flag in all_num_flags:
if flag:
prime_num_list.append(i)
i += 1
return prime_num_list
'''
， 。
，
， ，
。
： ：2→4→3、5→6→4， ：7→0→8
'''
class AddNode():
def __init__(self):
self.value = None
self.next = None
def add_node_list(nl1, nl2):
if not nl2:
return nl1
if not nl1:
return nl2
head = AddNode()
cur = head
carry = 0 #
while (nl1 and nl2):
value = nl1.value + nl2.value + carry
carry = value // 10
value = value % 10
new_node = AddNode()
new_node.value = value
cur.next = new_node
cur = cur.next
nl1 = nl1.next
nl2 = nl2.next
#
if nl1:
long_nl = nl1
else:
long_nl = nl2
while (long_nl):
value = long_nl.value + carry
new_node = AddNode()
new_node.value = value
long_nl = long_nl.next
cur.next = new_node
cur = cur.next
return head.next
def print_node_list(nl):
head = nl
while (head):
print head.value,
head = head.next
print "
"
def test_add_node_list():
nl1 = AddNode()
cur = nl1
for i in range(3):
new_node = AddNode()
new_node.value = random.randint(1, 9)
cur.next = new_node
cur = cur.next
nl2 = AddNode()
cur = nl2
for i in range(4):
new_node = AddNode()
new_node.value = random.randint(1, 9)
cur.next = new_node
cur = cur.next
print_node_list(nl1.next)
print_node_list(nl2.next)
head = add_node_list(nl1.next, nl2.next)
print_node_list(head)
# test_add_node_list()
"""
， m n 。
。
： ^-1→2→3→4→5，m=2，n=4，
^-1→4→3→2→5。
：1≤m≤n≤ 。
"""
class int_node():
def __init__(self):
self.value = None
self.next = None
def part_reverse(nl, start, end):
if end <= start:
return
p_head = nl #
for i in range(start - 1):
p_head = nl.next
p_end = p_head.next #
p_cur = p_end.next #
for _ in range(end - start):
#
# 1 p_cur.next :
p_end.next = p_cur.next
# 2 p_cur.next ：
p_cur.next = p_head.next
# 3 p_head.next ：
p_head.next = p_cur
# 4 ， p_cur
p_cur = p_end.next
def test_part_reverse():
head = int_node()
p_cur = head
head.value = -1
for i in range(10):
new_node = int_node()
new_node.value = random.randint(1, 9)
p_cur.next = new_node
p_cur = new_node
print_node_list(head)
part_reverse(head, 1, 10)
print " "
print_node_list(head)
# test_part_reverse()
'''
， Longest Common
Subsequence，LCS。
S T， T
S ；
X Y ，
， X Y 。
13455 245576 455
acdfg adfc adf
(Longest Common Substring)
：
，
:
LCS(X,0) = 0
：
LCS(Xm,Yn)=LCS(Xm-1,Yn-1) xm = ym
LCS(Xm,Yn)=MAX(LCS(Xm-1,Yn),LCS(Xm,Yn-1)) xm ！= ym
，
：
Xm Yn ， （m+1）*（n+1）
（i，j） Xm[:i],Yn[:j]
（i，j） ， 、
（i，j） ， +1
， ，
'''
def lcs(Xm, Yn):
m = len(Xm)
n = len(Yn)
chess = []
first_row = []
for j in range(n + 1):
first_row.append(0)
for i in range(m + 1):
chess.append(copy.deepcopy(first_row))
for i in range(1, m + 1):
for j in range(1, n + 1):
if Xm[i - 1] == Yn[j - 1]:
chess[i][j] = chess[i - 1][j - 1] + 1
else:
chess[i][j] = max([chess[i - 1][j], chess[i][j - 1]])
# pprint.pprint (chess)
return chess
def recall_lcs(Xm, Yn, chess):
print chess
m = len(Xm)
n = len(Yn)
result = []
while (m != 0 and n != 0):
if Xm[m - 1] == Yn[n - 1]:
result.append(Yn[n - 1])
m -= 1
n -= 1
else:
if chess[m][n - 1] >= chess[m - 1][n]:
n -= 1
else:
m -= 1
result.reverse()
print "".join(result)
# Xm="abcdefg"
# Yn="bcafegd"
# chess = lcs(Xm,Yn)
# recall_lcs(Xm,Yn,chess)
def recall_lcs_dfs(Xm, Yn, m, n, chess, result):
'''
, ，
， n ，
n-1 ， ， ，
:param Xm:
:param Yn:
:param m:
:param n:
:param chess:
:param result:
:return:
'''
rl = list(result)
while (m != 0 and n != 0):
if Xm[m - 1] == Yn[n - 1]:
rl.append(Yn[n - 1])
m -= 1
n -= 1
else:
if chess[m][n - 1] > chess[m - 1][n]:
n -= 1
elif chess[m][n - 1] == chess[m - 1][n]:
# ， ，
recall_lcs_dfs(Xm, Yn, m - 1, n, chess, "".join(rl))
#
n -= 1
else:
m -= 1
rl.reverse()
print "".join(rl)
def test_recall_lcs_dfs():
Xm = "efghab"
Yn = "egfahb"
chess = lcs(Xm, Yn)
print chess
result = ""
recall_lcs_dfs(Xm, Yn, 6, 6, chess, result)
#
'''
A {5，6，7，1，2，8}
：A’{1，2，5，6，7，8}
， A ，
A’ ， ，
。 ， A
， A
A’ 。
， /
： ， 。
： ， ， ！
: ：
'''
#
def lis_dp(a_int_list):
#
results = []
# for i in range(len(a_int_list)):
# results.append([])
j = 0
max = 0
# ， ，
for i in a_int_list:
results.append([i])
# j ， ，
for h in range(j):
if i > results[h][-1] and len(results[h]) + 1 > len(results[j]):
temp2 = copy.deepcopy(results[h])
temp2.append(i)
if len(temp2) > len(results[j]):
results[j] = temp2
if len(results[j]) > len(results[max]):
max = j
j += 1
print results
print max
return results[max]
# a_int_list = [3, 5, 8, 7, 4, 9, 12, 6]
# print lis_dp(a_int_list)
#
def greedy_lis(a_int_list):
temp = []
fl = []
for _ in a_int_list:
fl.append(False)
fl[0] = True
for num in a_int_list:
if not temp:
temp.append(num)
continue
if num > temp[-1]:
temp.append(num)
else:
# temp num
# for i in range(len(temp)):
# if temp[i]>num:
# temp[i]=num
# ：
low = 0
high = len(temp) - 1
while (low < high):
mid = (low + high) / 2
if num < temp[mid]:
high = mid - 1
else:
low = mid + 1
if temp[low] > num:
temp[low] = num
else:
temp[low + 1] = num
print temp
print len(temp)
# a_int_list = [3, 5, 8, 7, 4, 9, 12, 6]
# greedy_lis(a_int_list)
'''
S[0…N-1]， ， S
，
：
'''
def swap(a_int_list, a, b):
if a == b:
return
else:
temp = a_int_list[a]
a_int_list[a] = a_int_list[b]
a_int_list[b] = temp
def is_duplicate(a_int_list,i_start,i):
while(i_startif a_int_list[i_start] == a_int_list[i]:
return True
i_start+=1
else:
return False
#
def Permutation(a_int_list,size,i_start):
# i_start size ，
# i_start ， size
# i_start ，
#i_start 0
if i_start == size-1:
print a_int_list
return
swaped = set([])
for i in range(i_start,size): # a[i]
# if is_duplicate(a_int_list,i_start,i):
# # a[i] [i_start,i) ， ， ，
# continue
#
if a_int_list[i] in swaped:
continue
swaped.add(a_int_list[i] )
swap(a_int_list,i,i_start)
Permutation(a_int_list,size,i_start+1)
swap(a_int_list,i_start,i)
#Permutation([1,2,3,2],4,0)
# KMP , ， ！
'''
text pattern， text
pattern 。
(Brute Force) ： O(m*n)
KMP
， BF 。
： N， M
BF O(M*N)， O(1)
KMP O(M+N)， O(M)
'''
#
def brute_force_search(src_str, aim_str):
src_size = len(src_str)
aim_size = len(aim_str)
remove_len = src_size - aim_size
src_cur = 0 #
aim_cur = 0 #
while src_cur < remove_len and aim_cur < aim_size:
if src_str[src_cur+aim_cur] == aim_str[aim_cur]:
aim_cur += 1
else:
src_cur += 1
aim_cur = 0
if aim_cur >= aim_size:
return src_cur
return -1
# print brute_force_search("abcdefg", "cde")
# KMP
# step1 next
'''
a b a a b c a b a
next -1 0 0 1 1 2 0 1 2
：j=5 ，
“abaab”
k k ab， c next 2
， 5 next ， c next
b 1， ， ，
1+1，
'''
def get_next(src_str):
size = len(src_str)
next_list = [-1, ]
# k next
# ，k=next[j-1]
k = -1
# j
j = 0
while j < size - 1:
if k == -1 or src_str[k] == src_str[j]:
j += 1
k += 1
next_list.append(k)
else:
k = next_list[k]
return next_list
# print get_next("abaa")
# get next ，
def kmp(src_str,aim_str):
next_list = get_next(aim_str)
ans = -1
src_size = len(src_str)
aim_size = len(aim_str)
src_cur = 0 #
aim_cur = 0 #
while src_cur < src_size :
if aim_cur==-1 or src_str[src_cur] == aim_str[aim_cur]:
src_cur += 1
aim_cur += 1
else:
# aim_cur ， aim ，
aim_cur = next_list[aim_cur]
if aim_cur == aim_size:
ans = src_cur - aim_size
break
return ans
# print kmp("acfcfeccfcecfcfecdcdefg", "cfcfecd")