#第3章 算法

"""
    二分查找
"""
def binary_search(arr, target):
    """二分查找，arr序列必须是从小到大排序的"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 测试
if __name__ == '__main__':
    print(binary_search([1, 12, 13, 24, 35, 46, 57, 68, 79], 5))
    print(binary_search([1, 12, 13, 24, 35, 46, 57, 68, 79], 68))

def binary_search(arr, target):
    """二分查找，arr序列必须是从小到大排序的"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            start = mid - 1
            end = mid + 1
            while arr[start] == target and start >= 0:
                start -=1
            while arr[end] == target and end < len(arr):
                end +=1
            return (start+1,end-1)
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 测试
if __name__ == '__main__':
    print(binary_search([1, 3, 3, 3, 3, 3, 3,  8, 9, 12, 15], 3))
    print(binary_search([1, 3, 3, 3, 3, 3, 3,  8, 9, 12, 15], 15))
    print(binary_search([1, 3, 3, 3, 3, 3, 3,  8, 9, 12, 15], 2))

def binary_search(arr, target):
    start = -1
    end = len(arr)-1

    # 查找target的左边界
    left,right = 0,len(arr)-1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            start = mid
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            end = right

    if start == -1:
        return (-1,)

    # 在[start, end]范围内继续二分查找target的右边界
    left = start
    right = end
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            end = mid
            left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return (start,end) if start != end else (start,)

# 测试
if __name__ == '__main__':
    print(binary_search([1, 3, 3, 3, 3, 3, 3,  8, 9, 12, 15,20,25,26,29,30,35,38,40], 3))
    print(binary_search([1, 3, 3, 3, 3, 3, 3,  8, 9, 12, 15], 15))
    print(binary_search([1, 3, 3, 3, 3, 3, 3,  8, 9, 12, 15], 2))

"""
    摩尔投票法
"""
def majorityElement(nums):
    """
    找出数量超过半数的元素
    """
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

# 测试
if __name__ == '__main__':
    print(majorityElement([3,2,3]))
    print(majorityElement([2,2,2,1,1,1,2,4]))

"""
    冒泡排序
"""
def bubble_sort(arr):
    """冒泡排序"""
    for i in range(len(arr)):
        for j in range(0, len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    # return arr

# 测试
if __name__ == '__main__':
    nums = [3, 1, 5, 4, 2]
    bubble_sort(nums)
    print(nums)

def bubble_sort_better(arr):
    """冒泡排序"""
    for i in range(len(arr)):
        flag = True
        for j in range(0, len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = False
        if flag:
            break

# 测试
if __name__ == '__main__':
    nums = [1,2,3,4,5]
    bubble_sort_better(nums)
    print(nums)

"""
    选择排序
"""
def select_sort(arr):
    """选择排序"""
    for i in range(len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

# 测试
if __name__ == '__main__':
    arr = [1, 5, 3, 2, 4]
    select_sort(arr)
    print(arr)

def insert_sort_one(arr):
    """插入排序"""
    for i in range(1, len(arr)):
        key = arr[i]
        j = i
        while j > 0 and arr[j-1] > key:
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = key

# 测试
if __name__ == '__main__':
    arr = [1, 5, 3, 2, 4]
    insert_sort_one(arr)
    print(arr)

def insert_sort_two(arr):
    """插入排序"""
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j] < arr[j - 1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1

# 测试
if __name__ == '__main__':
    arr = [1, 5, 3, 2, 4]
    insert_sort_two(arr)
    print(arr)

"""
    归并排序
"""
def merge(left,right):
    """合并两个有序的子序列"""
    i, j = 0, 0
    result = []
    # 比较两个子数组的元素，按升序放入 result 数组
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 将数组中剩余元素加入 result
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    """归并排序"""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# 测试
if __name__ == '__main__':
	print(merge_sort([3,1,5,8,4,7,6,2]))

"""
    快速排序
"""
def partition(nums, left, right):
    """选择基准并按基准划分"""
    pivot = nums[left] # 选择第一个数为基准，nums[left]位置可以被覆盖
    while left < right:
        # 从右向左找第一个比 pivot 小的数
        while left < right and nums[right] >= pivot:
            right -= 1
        nums[left] = nums[right] # 把比pivot小的数放到左边[left]位置，空出nums[right]位置
        # 从左向右找第一个比 pivot 大的数
        while left < right and nums[left] <= pivot:
            left += 1
        nums[right] = nums[left] # 把比pivot大的数放到右边[right]位置，空出nums[left]位置
    # while循环结束，left = right，[left]左边的数都比pivot小，[right]右边的数都比pivot大
    nums[left] = pivot # 把pivot放到中间位置
    return left # 返回中间值下标

def quick_sort(nums, left, right):
    """快速排序"""
    if left < right:
        # 划分，nums[mid]为中间值, 左边的数都比它小，右边的数都比它大
        mid = partition(nums, left, right)
        # 继续对左右两边进行排序
        quick_sort(nums, left, mid - 1)
        quick_sort(nums, mid + 1, right)

# 测试
if __name__ == '__main__':
    # nums = [3,1,5,8,4,7,6,2]
    nums = [8,10,2,5,14,4,12,1,6,9,15,3,7,13,11]
    quick_sort(nums, 0, len(nums) - 1)
    print(nums)

def partition(nums,left,right):
    key = nums[left] #选择基准值
    i = left
    j = right
    while i < j:
        while i<right and nums[i]<=key:#在左边找比key大的元素位置
            i += 1
        while j>left and nums[j]>=key:#在右边找比key小的元素位置
            j -= 1
        if i < j:#把 左边比key大的元素 与 右边找比key小的元素 交换
            nums[i],nums[j] = nums[j],nums[i]
    #上面的循环实现了[left+1,j]范围的元素 < key < [j+1, right]范围的元素
    #把基准值，换到中间
    nums[left],nums[j] = nums[j],nums[left]
    return j

def quick_sort(nums, left,right):
    if left < right:
        mid = partition(nums,left,right)
        quick_sort(nums, left,mid-1)
        quick_sort(nums, mid+1,right)

# 测试
if __name__ == '__main__':
    # nums = [3,1,5,8,4,7,6,2]
    nums = [8,10,2,5,14,4,12,1,6,9,15,3,7,13,11]
    # nums = [3,1,5,8,7]
    quick_sort(nums, 0, len(nums) - 1)
    print(nums)

"""
    堆排序
"""
def heapify(arr, len, parent):
    """
    堆化操作
    :param arr: 需要进行堆化操作的序列
    :param len: 序列中元素的个数
    :param parent: 当前需要进行堆化操作的子树的根结点索引
    :return:
    """
    largest = parent  # 最大结点指向父结点
    left = 2 * parent + 1  # 左子结点
    right = 2 * parent + 2  # 右子结点

    # 如果左子结点大于父结点,最大结点指向左子结点
    if left < len and arr[left] > arr[largest]:
        largest = left

    # 如果右子结点大于当前最大结点，最大结点指向右子结点
    if right < len and arr[right] > arr[largest]:
        largest = right

    # 如果最大结点不是父结点，则交换并递归堆化
    if largest != parent:
        arr[parent], arr[largest] = arr[largest], arr[parent]
        heapify(arr, len, largest)

def heap_sort(arr):
    """堆排序"""
    n = len(arr)
    # 自底向上开始堆化
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 依次将堆顶元素放在末尾，并重新堆化
    for i in range(n - 1, 0, -1): # 堆大小递减
        arr[i], arr[0] = arr[0], arr[i]
        # 自顶向下开始堆化
        heapify(arr, i, 0)

# 测试
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    heap_sort(arr)
    print("排序后的数组:", arr)

"""
    汉诺塔问题
"""
def print_abc():
    """打印3个柱子"""
    print("a:", a)
    print("b:", b)
    print("c:", c)
    print()

def hanota(n, source, target, buffer):
    # 只有一个盘子时，直接从源柱子移动到目标柱子
    if n == 1:
        target.append(source.pop())
        return

    # 1. 将 n-1 个盘子从源柱子移动到缓冲柱子
    hanota(n - 1, source, buffer, target)
    print_abc()

    # 2. 将第 n 个盘子从源柱子移动到目标柱子
    hanota(1, source, target, buffer)
    print_abc()

    # 3. 将 n-1 个盘子从缓冲柱子移动到目标柱子
    hanota(n - 1, buffer, target, source)
    print_abc()

if __name__ == "__main__":
    n = 3
    a = list(range(n, 0, -1))
    b = []
    c = []
    print("初始状态：")
    print_abc()

    print("开始移动...")
    hanota(n, a, c, b)

"""
    卡拉楚巴算法
"""
def karatsuba(x, y):
    """
    karatsuba 乘法算法
    """
    if x == 0 or y == 0: # 递归结束条件，0乘以任何数都等于0
        return 0

    if abs(x) < 10 and abs(y) < 10: # 递归结束条件，1位数相乘直接返回结果
        return x * y

    # 处理负数，转为正数相乘
    if x < 0 and y < 0:
        return karatsuba(-x, -y)
    elif x < 0:
        return -karatsuba(-x, y)
    elif y < 0:
        return -karatsuba(x, -y)

    # 将 x 和 y 转换为字符串
    x_str, y_str = str(x), str(y)
    n = max(len(x_str), len(y_str))
    m = int(n / 2)

     # 补齐较短的数字，使其长度相同
    x_str = x_str.zfill(n)
    y_str = y_str.zfill(n)

    # 将数字划分为高位部分和低位部分
    high1, low1 = int(x_str[:-m]), int(x_str[-m:])
    high2, low2 = int(y_str[:-m]), int(y_str[-m:])

    # 递归调用 karatsuba
    z0 = karatsuba(low1, low2)
    z1 = karatsuba(low1 + high1, low2 + high2)
    z2 = karatsuba(high1, high2)

    return pow(10, 2 * m) * z2 + pow(10, m) * (z1 - z2 - z0) + z0

if __name__ == "__main__":
    print(karatsuba(1234, 6785 ))
    print(karatsuba(-1234, 6785 ))
    print(karatsuba(-1234, -6785 ))
    print(karatsuba(0, -6785 ))

"""
    爬楼梯
"""
def climb_recursive(n):
    """使用递归的方式计算爬楼梯问题"""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_recursive(n - 2) + climb_recursive(n - 1)

def climb_loop_one(n):
    """使用循环的方式计算爬楼梯问题"""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    # 计算3级（含）台阶以上
    last_step_one = 2 # 最后一步爬1级台阶的初始值
    last_step_two = 1 # 最后一步爬2级台阶的初始值
    current = 0
    for _ in range(3, n + 1):
        current = last_step_one + last_step_two #走到第n级台阶的方法数
        last_step_two = last_step_one # 缓存，这次爬1级台阶到第n级台阶的方法数，就是下次爬2级台阶到第n+1级台阶的方法数
        last_step_one = current # 缓存，这次走到第n级台阶的方法数，就是下次爬1级台阶到第n+1级台阶的方法数
    return current

def climb_loop_two(n):
    """使用循环的方式计算爬楼梯问题"""
    if n <= 0:
        return 0
    previous = 1
    current = 1
    """
    n = 1 ,for循环不执行， current = 1
    n = 2 ,for循环执行1次， previous = 1, current = 1+1 = 2
    n = 3 ,for循环执行2次， 
                        previous = 1, current = 1+1 = 2
                        previous = 2, current = 1+2 = 3
    n = 4 ,for循环执行1次， 
                        previous = 1, current = 1+1 = 2
                        previous = 2, current = 1+2 = 3
                        previous = 3, current = 2+3 = 5
    """
    for _ in range(1, n):
        previous, current = current, previous + current
    return current

if __name__ == "__main__":
    for step in range(1, 10):
        print("爬 %d 阶楼梯的方法数：" % step)
        print("递归：%d" % climb_recursive(step))
        print("循环1：%d" % climb_loop_one(step))
        print("循环2：%d" % climb_loop_two(step))
        print()

def max_subarray_sum(nums):
    """最大的连续子数组之和"""
    max_result = f = nums[0]
    for i in range(1, len(nums)):
        # 连续子数组之和若小于0，则中断连续
        f = max(nums[i], f + nums[i])
        max_result = max(max_result, f)
    return max_result

if __name__ == "__main__":
    print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4,2]))

def max_subarray(nums):
    """最大的连续子数组之和及其子数组"""
    max_result = f = nums[0]
    index_start = 0
    index_end = 0
    for i in range(1, len(nums)):
        # 连续子数组之和若小于0，则中断连续
        if f<0:
            f = nums[i]
            index_start = i
        else:
            f = f + nums[i]
        if f > max_result:
            index_end = i
            max_result = f
    return max_result,nums[index_start:index_end+1]

if __name__ == "__main__":
    print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4,2]))

"""
 0-1背包问题
"""
def knapsack(weights, values, W):
    n = len(weights)
    # 创建n 行 W + 1 列的二维数组 ，用于保存中间结果
    # 初始化二维数组dp，dp[i][j]表示前i个物品中，背包容量为j时的最大价值
    dp = [[0] * (W + 1) for _ in range(n)]

    # 创建一个列表，用于保存不同总容量的列表
    w_list = list(range(W + 1))

    # 每次增加一个可选物品，增加物品后遍历一次背包重量
    for i in range(n):
        for j in w_list:
            # 如果当前物品放的进背包，进行比较
            if weights[i] <= j: # 选择当前物品[i]后还有剩余容量
                dp[i][j] = max(dp[i - 1][j], values[i] + dp[i - 1][j - weights[i]])
            # 如果当前物品放不进背包，使用上轮相同j的状态
            else: # 当前物品[i]放不进背包
                dp[i][j] = dp[i - 1][j]

        # print(f"前{i + 1}个物品")
        # print("重量：",w_list)
        # for row in range(0,i+1):
        #     print("价值：",dp[row])

    return dp[n - 1][W]

if __name__ == "__main__":
    weights = [1, 2, 3]  # 物品的重量
    values = [3, 2, 6]  # 物品的价值
    W = 5  # 背包的最大容量
    print(knapsack(weights, values, W))

"""
 0-1背包问题
"""
def knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):  # 从后往前遍历，j>=weights[i]
            dp[j] = max(dp[j], values[i] + dp[j - weights[i]])
    return dp[W]

if __name__ == "__main__":
    weights = [1, 2, 3]  # 物品的重量
    values = [3, 2, 6]  # 物品的价值
    W = 5  # 背包的最大容量
    print(knapsack(weights, values, W))

"""
    完全背包问题
"""
def knapsack(weights, values, W):
    n = len(weights)
    # 初始化二维数组dp，dp[i][j]表示前i个物品中，背包容量为j时的最大价值
    dp = [[0] * (W + 1) for _ in range(n)]

    # 创建一个列表，用于保存不同总容量的列表
    w_list = list(range(W + 1))

    # 每次增加一个可选物品，增加物品后遍历一次背包重量
    for i in range(n):
        for j in w_list:
            # 如果当前物品放的进背包，进行比较
            if weights[i] <= j:
                dp[i][j] = max(dp[i - 1][j], values[i] + dp[i][j - weights[i]])
            # 如果当前物品放不进背包，使用上轮相同j的状态
            else:
                dp[i][j] = dp[i - 1][j]

        print(f"前{i + 1}个物品")
        print("重量：",w_list)
        for row in range(0,i+1):
            print("价值：",dp[row])

    return dp[n - 1][W]

if __name__ == "__main__":
    weights = [1, 2, 3]  # 物品的重量
    values = [3, 2, 6]  # 物品的价值
    W = 5  # 背包的最大容量
    print(knapsack(weights, values, W))

    weights = [1, 2, 3]  # 物品的重量
    values = [3, 7, 11]  # 物品的价值
    W = 5  # 背包的最大容量
    print(knapsack(weights, values, W))

"""
    完全背包问题
"""
def knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(weights[i], W + 1):  # 从前往后遍历， 要求j>=weights[i]
            dp[j] = max(dp[j], values[i] + dp[j - weights[i]])
    return dp[W]

if __name__ == "__main__":
    weights = [1, 2, 3]  # 物品的重量
    values = [3, 2, 6]  # 物品的价值
    W = 5  # 背包的最大容量
    print(knapsack(weights, values, W))

    weights = [1, 2, 3]  # 物品的重量
    values = [3, 7, 11]  # 物品的价值
    W = 5  # 背包的最大容量
    print(knapsack(weights, values, W))

def permute(nums):
    result = []

    def backtrack(start):
        # 到达末尾，将此时排列结果添加到最终结果中
        if start == len(nums):
            result.append(nums[:])
            return

        # 从当前位置i开始，依次选取元素进行排列
        for i in range(start, len(nums)):
            # 选取当前位置的元素：将要选取的元素与此位置的元素互换
            if start != i:
                nums[start], nums[i] = nums[i], nums[start]
            # 递归处理下一个位置的元素
            backtrack(start + 1)
            # 回溯，恢复原始数组
            if start != i:
                nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

# 测试
if __name__ == "__main__":
    print(permute([1, 2, 3]))

"""
    最大交换
"""
def maximumSwap(num):
    result = num
    num_list = list(str(num))
    max_index = -1  # 最大值的索引
    for i in range(len(num_list) - 2, -1, -1):
        # 当前值大于最大值时，更新最大值的索引
        if num_list[i] > num_list[max_index]:
            max_index = i
        # 当前值小于最大值时，交换，更新result，再交换回来
    	elif num_list[i] < num_list[max_index]:
            num_list[i], num_list[max_index] = num_list[max_index], num_list[i]
            result = int("".join(num_list))
            num_list[i], num_list[max_index] = num_list[max_index], num_list[i]
    return result

# 测试
if __name__ == '__main__':
    print(maximumSwap(2736))
    print(maximumSwap(1993))
    print(maximumSwap(9099))
    print(maximumSwap(98368))
    print(maximumSwap(79831265))
    print(maximumSwap(9831265))

"""
    最大交换
"""
def maximumSwap(num):
    result = num
    num_list = list(str(num))
    max_index = -1  # 最大值的索引
    for i in range(len(num_list) - 2, -1, -1):
        # 当前值大于最大值时，更新最大值的索引
        if num_list[i] > num_list[max_index]:
            max_index = i
        # 当前值小于最大值时，交换，更新result，再交换回来
        else:
            num_list[i], num_list[max_index] = num_list[max_index], num_list[i]
            result = max(result, int("".join(num_list)))
            num_list[i], num_list[max_index] = num_list[max_index], num_list[i]
    return result

# 测试
if __name__ == '__main__':
    print(maximumSwap(2736))
    print(maximumSwap(1993))
    print(maximumSwap(9099))
    print(maximumSwap(98368))
    print(maximumSwap(79831265))
    print(maximumSwap(9831265))

"""
    分糖果1
"""
def candy(ratings):
    n = len(ratings)

    # 每个孩子先分发1个糖果
    candy_num = [1] * len(ratings)

    # 从左向右遍历，如果右边评分更高，则右边孩子的糖果数改为左边孩子的糖果数+1
    for pos in range(n - 1):
        if ratings[pos] < ratings[pos + 1]:
            candy_num[pos + 1] = candy_num[pos] + 1

    # 从右向左遍历，如果左边评分更高，则左边孩子的糖果数改为右边孩子的糖果数+1
    total_candies = candy_num[-1]
    for pos in range(n - 2, -1, -1):
        if ratings[pos] > ratings[pos + 1] and candy_num[pos] <= candy_num[pos + 1]:
                candy_num[pos] = candy_num[pos + 1] + 1
        total_candies += candy_num[pos]
    print("糖果数为：", candy_num)
    return total_candies

# 测试
if __name__ == '__main__':
    score = [1,3,2,2,1]
    print("评分数组：", score)
    print(candy(score))

"""
    分糖果2
"""
def candy(ratings):
    # 每个孩子分发一个糖果
    result = len(ratings)
    # 上升区长度
    up_length = 0
    # 上升区长度的记录
    up_num = 0
    # 下降区长度
    down_length = 0
    for i in range(1, len(ratings)):
        # 如果处于上升区
        if ratings[i] > ratings[i - 1]:
            # 上升区长度+1，清空下降区长度，并在result中累加糖果数
            up_length += 1
            up_num = up_length
            down_length = 0
            result += up_length
        # 如果处于下降区
        elif ratings[i] < ratings[i - 1]:
            # 如果上升区长度为0，说明前一个位置已经不在上升区内，下降区长度+1
            if up_length == 0:
                down_length += 1
            # 如果下降区长度已经等于之前上升区长度，说明峰值的糖果数由下降区决定，下降区长度+1
            if down_length == up_num:
                down_length += 1
            # 清空上升区长度
            up_length = 0
            result += down_length
        # 如果处于平缓区
        else:
            # 清空所有记录
            up_length = 0
            down_length = 0
            up_num = 0
    return result


# 测试
if __name__ == '__main__':
    print(candy([1,3,2,2,1]))
    print(candy([1,2,5,4,3,2,1]))
    print(candy([1,2,5,4,3,2,1,2,3,2,1]))