文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python算法系列知识点有哪些

2023-06-02 02:19

关注

这篇文章主要讲解了“Python算法系列知识点有哪些”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Python算法系列知识点有哪些”吧!

主要思想

分治算法,即分而治之:把一个复杂问题分成两个或更多的相同或相似子问题,直到最后子问题可以简单地直接求解,最后将子问题的解合并为原问题的解。

归并排序就是一个典型的分治算法。

三步走

和把大象塞进冰箱一样,分治算法只要遵循三个步骤即可:分解 -> 解决 -> 合并。

分解:分解原问题为结构相同的子问题(即寻找子问题)

解决:当分解到容易求解的边界后,进行递归求解

合并:将子问题的解合并成原问题的解

Python算法系列知识点有哪些

这么一说似乎还是有点抽象?那我们通过经典的排序算法归并排序来体验一下分治算法的核心思想。

归并排序

思想

归并排序的思想是:欲使序列有序,必先使其子序列有序。即先使得每个子序列有序,然后再将子序列合并成有序的列表。

因此,在归并排序中的子问题就是:使子序列有序。

三步走

既然已经找到了问题的子问题,是时候套用我们上述的三步走方法了。归并排序的「三步走」如下:

分解:将序列划分为两部分

解决:递归地分别对两个子序列进行归并排序

合并:合并排序后的两个子序列

举例

来看一个具体的例子。

现在有一个待排序的序列:

10, 4, 6, 3, 8, 2, 5, 7

先对序列进行分解,把该序列一分为二,直到无法拆分为止。整个拆分过程如下:

Python算法系列知识点有哪些

然后对分解出的序列进行两两排序与合并:

10, 4 排序合并后:4, 10
6, 3 排序合并后:3, 6
8, 2 排序合并后:2, 8
5, 7 排序合并后:5, 7
……

整个归并排序完整过程如下:

Python算法系列知识点有哪些

实现

def merge_sort(lst): # 从递归中返回长度为1的序列 if len(lst) <= 1: return lst  middle = len(lst) / 2 # 1.分解:通过不断递归,将原始序列拆分成 n 个小序列 left = merge_sort(lst[:middle])  right = merge_sort(lst[middle:]) # 进行排序与合并 return merge(left, right)def merge(left, right): i, j = 0, 0 result = [] # 2.解决:比较传入的两个子序列,对两个子序列进行排序 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 # 3.合并:将排好序的子序列合并 result.extend(left[i:])  result.extend(right[j:]) return result

真题演练

为运算表达式设计优先级

题目描述

给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 + , - 以及 *。

示例 1:

输入: "2-1-1"输出: [0, 2]解释: ((2-1)-1) = 0 (2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"输出: [-34, -14, -10, -10, 10]解释: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10

思路

对于一个形如 x op y(op 为运算符,x 和 y 为数) 的算式而言,它的结果组合取决于 x 和 y 的结果组合数,而 x 和 y 又可以写成形如 x op y 的算式。

因此,该问题的子问题就是 x op y 中的 x 和 y:以运算符分隔的左右两侧算式解。

然后我们来进行分治算法三步走:

分解:按运算符分成左右两部分,分别求解

解决:实现一个递归函数,输入算式,返回算式解

合并:根据运算符合并左右两部分的解,得出最终解

其实算法相关的Python面试教程前面有跟大家讲到,也可以找一下前面的内容。

实现

class Solution: def diffWaysToCompute(self, input: str) -> List[int]: # 如果只有数字,直接返回 if input.isdigit(): return [int(input)] res = [] for i, char in enumerate(input): if char in ['+', '-', '*']: # 1.分解:遇到运算符,计算左右两侧的结果集 # 2.解决:diffWaysToCompute 递归函数求出子问题的解 left = self.diffWaysToCompute(input[:i]) right = self.diffWaysToCompute(input[i+1:]) # 3.合并:根据运算符合并子问题的解 for l in left: for r in right: if char == '+': res.append(l + r) elif char == '-': res.append(l - r) else: res.append(l * r) return res

感谢各位的阅读,以上就是“Python算法系列知识点有哪些”的内容了,经过本文的学习后,相信大家对Python算法系列知识点有哪些这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是编程网,小编将为大家推送更多相关知识点的文章,欢迎关注!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯