算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# -*- coding: utf-8 -*-

def merge(array, start, middle, end):
n1 = middle - start + 1 # 第一个子序列长度
n2 = end - middle # 第二个子序列长度
left_array = []
right_array = []
for i in range(n1):
left_array.append(array[start + i])
for i in range(n2):
right_array.append(array[middle + i + 1])
left_array.append(float('Inf')) # float('Inf') 表示正无穷
right_array.append(float('Inf'))
i = j = 0
for index in range(start, end + 1):
if (left_array[i] <= right_array[j]):
array[index] = left_array[i]
i += 1
else:
array[index] = right_array[j]
j += 1
return array

def merge_sort(array, start, end):
if start < end:
middle = (start + end) // 2
merge_sort(array, start, middle)
merge_sort(array, middle + 1, end)
merge(array, start, middle, end)

array = [1, 9, 2, 6, 7, 8, 8, 7, 9, 11, 18, 12, 13]
merge_sort(array, 0, len(array) - 1)
print(array)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# -*- coding: utf-8 -*-

# 在 list 前补 0
def complement_short_num(num, length):
for i in range(length):
num.insert(0, 0)
return num

def add_binary_number(num1, num2):
length1 = len(num1)
length2 = len(num2)
min_length = length1 if length1 < length2 else length2
max_length = length1 if length1 > length2 else length2
different_length = max_length - min_length

if length1 < length2:
num1 = complement_short_num(num1, different_length)
else:
num2 = complement_short_num(num2, different_length)

# 初始化结果数组
num3 = complement_short_num([], max_length + 1)

carry = 0 # 进位
for i in range(1, max_length + 1):
sum = num1[-i] + num2[-i] + carry # 得益于 python 特性从 list 尾部开始计算
if sum > 1:
num3[-i] = sum % 2
carry = 1
else:
num3[-i] = sum
carry = 0

# 为结果加进位
if carry == 1:
num3[0] = 1

return num3

sum = add_binary_number([1, 1, 0], [1, 1, 1, 1, 1])
print(sum)
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×