python | 算法大神左神(左程云)算法课程 第二节
2022/8/11 14:25:54
本文主要是介绍python | 算法大神左神(左程云)算法课程 第二节,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
针对的是b站视频-算法大神左神(左程云)算法课程第二节相关算法
由于python中关于递归有些踩坑,所以不搞对数器,就贴上单个例子验证正确的代码
视频笔记戳这里
1. 归并排序
归并排序-戳这里
#归并排序-递归 class solution(): def mergeSort(self, array): """ 归并排序 :param array: List[int] :return: None """ self.process(array, 0, len(array)-1) def process(self, array, left, right): """ 递归过程 :param array: List[int] :param left: int :param right: int :return: None """ if left == right: return mid = left + (right-left)>>1 self.process(array, left, mid) self.process(array, mid+1, right) self.merge(array, left, mid, right) def merge(self, array, left, mid, right): #整一个辅助空间,存放已经排好序的部分 help = [] #比较 i = left j = mid+1 while i <= mid and j <= right: #判断 if array[i] <= array[j]: help.append(array[i]) i += 1 else: help.append(array[j]) j += 1 #谁还剩,就都copy到help中 while i <= mid: help.append(array[i]) i += 1 while j <= right: help.append(array[j]) j += 1 #将help中的排好序的数再copy回array中 for i in range(len(help)): array[left+i] = help[i]
2.归并排序扩展-小和问题
归并排序扩展-小和问题-戳这里
# 归并排序扩展 # 小和问题 class solution(): def lowerSum(self, array): """ 求数组的array的小和 :param array: List[int] :return: int """ if len(array) < 2: return 0 return self.process(array, 0, len(array)-1) def process(self, array, left, right): """ 递归过程 :param array: List[int] :param left: int :param right: int :return: int """ if left == right: return 0 mid = left + (right-left)>>1 return self.process(array, left, mid)+self.process(array, mid+1, right)+self.merge(array, left, mid, right) def merge(self, array, left, mid, right): """ 将排好序且求出小和的左右两个部分整合 :param array: List[int] :param left: int :param mid: int :param right: int :return: int """ help = [] sum = 0 i = left j = mid + 1 while i <= mid and j <= right: if array[i] < array[j]: sum += array[i]*(right-j+1) help.append(array[i]) i += 1 else: help.append(array[j]) j += 1 while i <= mid: help.append(array[i]) i += 1 while j <= right: help.append(array[j]) j += 1 for i in range(len(help)): array[left+i] = help[i] return sum
这篇关于python | 算法大神左神(左程云)算法课程 第二节的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-28Python编程基础教程
- 2024-12-27Python编程入门指南
- 2024-12-27Python编程基础
- 2024-12-27Python编程基础教程
- 2024-12-27Python编程基础指南
- 2024-12-24Python编程入门指南
- 2024-12-24Python编程基础入门
- 2024-12-24Python编程基础:变量与数据类型
- 2024-12-23使用python部署一个usdt合约,部署自己的usdt稳定币
- 2024-12-20Python编程入门指南