算法学习 - Python（持续更新）

二分查找法 - 递归实现

def binSearch(nums, key, low, high):
    mid = (low + high) // 2
    if low > high:
        return -1
    if nums[mid] > key:
        return binSearch(nums, key, low, mid-1)
    elif nums[mid] < key:
        return binSearch(nums, key, mid+1, high)
    else:
         return mid

nums = [2, 4, 5, 9, 11, 16, 19]
print(binSearch(nums, 17, 0, len(nums)))

约瑟夫环问题

def josephRing(num, start):
    result = []
    nums = [i for i in range(1, num + 1)]
    while len(nums) > 0:
        
        result.append(nums[start%len(nums)-1])
        nums.remove(nums[start%len(nums)-1])
        nums = nums[start-1:] + nums[0: start-1]
    return result

print(josephRing(8, 7))

汉诺塔问题（递归）

def hanoi(n, x, y, z):
    """
    汉诺塔问题可以分解成一下三个步骤：
        将n-1个盘子从x轴借助y轴移动到z轴上；
        将第n个盘子从x轴移动到z轴上；
        将n-1个盘子从y轴借助x轴移动到z轴上；
    """
    if n == 1:
        print(x, ' --> ', z)
    else:
        hanoi(n-1, x, z, y)
        print(x, ' --> ', z)
        hanoi(n - 1, y, x, z)

hanoi(3, 'X', 'Y', 'Z')

旋转列表（Python）：列表原地修改，参考Leetcode189. 旋转数组

def rotate(nums, target):
        for i in range(3):
            """
            必须写成nums[:]，否则无法得到正确的值
            """
            nums[:] = [nums[-1]] + nums[: -1]

nums = [i for i in range(1, 8)]
rotate(nums, target = 3)
print(nums)

def rotate(nums, k):
        k=k%len(nums)       #保证循环次数在0-len(nums)之间  
        """
        必须写成nums[:],否则无法原地修改list，返回值为传入的参数值
        """
        nums[:]=nums[len(nums)-k:]+nums[:len(nums)-k]       #切割成两块重新组合