1. 求一个数的阶乘
def factorial(n):
if n == 1:
return 1
else:
return n * factorial (n-1)
2. 求任意输入字符的全排列
def permutation(xxs, y):
"""
: xxs: 已经排好的序列list，例如["ab", "ba"]
: y : 新添的元素，例如'c'
: return: yys: 新的序列list，例如["cab", "acb", "abc", "cba", "bca", "bac"]
"""
yys = []
for xx in xxs:
for i in range(len(xx) + 1):
yy = "{}{}{}".format(xx[:i], y, xx[i:])
yys.append(yy)
return yys
def full_permutation(s):
yys = []
if len(s) > 1:
yys = permutation(full_permutation(s[:-1], s[-1]))
else:
yys = [s]
return yys
# Test
test_str = "abc"
new_str = full_permutation(test_str)
new_str结果 = ['cba', 'bca', 'bac', 'cab', 'acb', 'abc']
3. 求两个有序数列的并集
例如，A = [2, 4, 4, 6, 9], B = [4, 5, 7], 输出[2, 4, 5, 6, 7, 9]
注意A和B中可能会有重复元素
def union(A, B):
C = []
c = None
cc = None # Candidate of c
ia, ib, ic = 0, 0, 0
while (ia < len(A) and ib < len(B)):
if A[ia] <= B[ib]:
cc = A[ia]
ia += 1
else:
cc = B[ib]
ib += 1
# 去重复
if cc != c:
c = cc
C.append(c)
# 看A或B是否还有残余
if ia <= len(A):
if A[ia] != c:
c = A[ia]
C.append(c)
ia += 1
elif ib <= len(B):
if B[ib] != c:
c = B[ib]
C.append(c)
return C
