递归的应用：求输入字符串的全排列

求输入字符串的全排列
递归完成，也可以直接使用库函数

from itertools import permutations


def my_permutation(s):
    str_set = []
    ret = []  # 最后的结果

    def permutation(string):
        for i in string:
            str_tem = string.replace(i, '')
            str_set.append(i)
            if len(str_tem) > 0:
                permutation(str_tem)
            else:
                ret.append(''.join(str_set))
            str_set.pop()

    permutation(s)
    return ret


if __name__ == '__main__':
    s = '321'
    print(my_permutation(s))
    print ([''.join(p) for p in permutations(s)])

结果展示：

['321', '312', '231', '213', '132', '123']
['321', '312', '231', '213', '132', '123']

——————————————————————————————————————————————————————————————————

求数组中最小的k个数

思路：使用heapq，该模块是一个最小堆，需要转化成最大堆，只要在入堆的时候把值取反就可以转化成最大堆，仅适用于数字

import random
import heapq


def get_least_k_nums(nums, k):
    # 数组比较小的时候可以直接使用
    return heapq.nsmallest(k, nums)


class MaxHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []

    def push(self, elem):
        elem = -elem  # 入堆的时候取反，堆顶就是最大值的相反数了
        if len(self.data) < self.k:
            heapq.heappush(self.data, elem)
        else:
            least = self.data[0]
            if elem > least:
                heapq.heapreplace(self.data, elem)

    def get_least_k_nums(self):
        return sorted([-x for x in self.data])


if __name__ == '__main__':
    test = random.sample(xrange(100000), 100)
    print(get_least_k_nums(test, 4))
    h = MaxHeap(4)
    for t in test:
        h.push(t)
    print(h.get_least_k_nums())

—————————————————————————————————————————————————————————————————

调整数组顺序使奇数位于偶数前面

使用两个指针，前后各一个，为了更好的扩展性，可以把判断奇偶部分抽取出来

def reorder(nums, func):
    left, right = 0, len(nums) - 1
    while left < right:
        while not func(nums[left]):
            left += 1
        while func(nums[right]):
            right -= 1
        if left < right:
            nums[left], nums[right] = nums[right], nums[left]


def is_even(num):
    return (num & 1) == 0


if __name__ == '__main__':
    tests = [1, 2, 3, 5, 7, 12]
    reorder(tests, is_even)
    print(tests)

结果展示：

[1, 7, 3, 5, 2, 12]

—————————————————————————————————————————————————————————————————

找出数组中出现次数超过一半的数字

思路: 使用hash，key是数字，value是出现的次数
注意: 列表的len方法的时间复杂度是O(1)

def get_more_half_num(nums):
    hashes = dict()
    length = len(nums)
    for n in nums:
        hashes[n] = hashes[n] + 1 if hashes.get(n) else 1
        if hashes[n] > length / 2:
            return n


if __name__ == '__main__':
    test = [1, 2, 3, 4, 1, 1, 1, 1]
    print(get_more_half_num(test))

—————————————————————————————————————————————————————————————————

判断某数是否在给定的数组中

遍历数组

def find_integer(matrix, num):
   """
   :param matrix: [[]]
   :param num: int
   :return: bool
   """
   if not matrix:
       return False
   rows, cols = len(matrix), len(matrix[0])
   row, col = rows - 1, 0
   while row >= 0 and col <= cols - 1:
       if matrix[row][col] == num:
           return True
       elif matrix[row][col] > num:
           row -= 1
       else:
           col += 1
   return False


if __name__ == '__main__':
   matrix = [[1, 2, 3],
             [2, 3, 6],
             [3, 6, 7]]
   num = 6
   print (find_integer(matrix, num))

结果展示：

True

—————————————————————————————————————————————————————————————————

按从外到里的顺序顺时针打印矩阵

每一圈的开始位置总是坐上角元素[0, 0], [1, 1]...

def print_matrix(matrix):
    """
    :param matrix: [[]]
    """
    rows = len(matrix)
    cols = len(matrix[0]) if matrix else 0
    start = 0
    ret = []
    while start * 2 < rows and start * 2 < cols:
        print_circle(matrix, start, rows, cols, ret)
        start += 1
    print(ret)


def print_circle(matrix, start, rows, cols, ret):
    row = rows - start - 1  # 最后一行
    col = cols - start - 1
    # left->right
    for c in range(start, col+1):
        ret.append(matrix[start][c])
    # top->bottom
    if start < row:
        for r in range(start+1, row+1):
            ret.append(matrix[r][col])
    # right->left
    if start < row and start < col:
        for c in range(start, col)[::-1]:
            ret.append(matrix[row][c])
    # bottom->top
    if start < row and start < col:
        for r in range(start+1, row)[::-1]:
            ret.append(matrix[r][start])


if __name__ == '__main__':
    mat = [[1, 3],
           [5, 7],
           [9, 13]]
    print_matrix(mat)