编程的核心是算法,学习算法不仅能教会你解决问题的方法,而且还能为你今后的发展提供一种可能。
本书面向算法初学者,首先介绍当下流程的编程语言Python,详细讲解了Python语言的变量和顺序、分支、循环三大结构,以及列表和函数的使用,为之后学习算法打好基础。
然后以通俗生动的语言讲解了双指针、哈希、深度优先、广度优先、回溯、贪心、动态规划和最短路径等经典算法。
让你轻松学会、爱不释手的Python算法书,有故事,有思路,有深度!
前 言
为什么要写这本书
算法是编程的核心,就像一台电脑的CPU,算法的好坏决定了一个系统的效率高低。
许多人认为学习编程就是学习最新的编程语言、技术和框架,其实计算机算法更重要。计算机语言和技术日新月异,但万变不离其宗的是算法。修炼好算法这门“内功”,再辅以新技术这些“招式”,才能独霸武林。这也是为什么像Google和Facebook这类大公司在面试中主要会考察算法问题的原因。
目前图书市场上关于算法的图书不少,经典的如《算法导论》。但是大多数算法图书太学术、太复杂,对于初学者来说门槛太高。学习算法本身就不是一件容易的事情,再加上复杂的场景和数学理论,会让算法的学习曲线更陡。因此作者们就萌生了写一本让大家都能看懂的算法书的想法,以生动的语言把算法的思想过程写出来,让学习算法不再那么枯燥。
在本书的创作过程中,王硕老师迎来了人生的第一个宝宝小朗朗。于是几位作者就有了一个心愿,希望青少年朋友也学会算法,因此,在描述算法问题时,尽量用简单、通俗的形式表述,使青少年朋友也能看懂,也希望如此这般能够增加读者的学习兴趣。既然是学习算法,免不了要写代码,对于编程语言的选择,我们选择了Python这门简单易懂的语言作为本书的编程语言。对于初学编程的人来说,Python可以缩短学习编程语言的时间和降低学习编程的难度。
学习算法不易,且行且珍惜。
本书有何特色
1. 以孩子的口吻,生动形象地讲解算法,提高趣味性
为了便于读者理解本书内容,提高学习效率,大部分问题都以孩子的口吻来讲解算法,以解决小朗朗的实际问题作为出发点引出问题,增加了趣味性和可读性。
2. 涵盖核心算法知识点
本书涵盖双指针问题、哈希算法、深度优先遍历、广度优先遍历、回溯算法、贪心算法、动态规划算法、最短路径问题、分治算法等9大算法。帮助读者全面掌握核心算法的知识点。
3. 以Python语言作为载体,降低学习难度
抛弃其他复杂的编程语言,本书采用简单的编程语言Python作为算法的载体,并在第1章介绍了Python语言的语法。
4. 选择经典算法的经典问题,有较高的通用性
本书在简单介绍Python编程语言以后,选择了9大经典算法,重点讲解算法原理,并选择经典问题进行有针对性的练习。
5. 提供完善的技术支持和售后服务
本书提供了专门的邮箱供读者咨询:317977682@qq.com。读者在阅读本书的过程中有任何疑问都可以通过该邮箱获得帮助。
本书内容及知识体系
第1章 编程基础
掌握一门编程语言是学习算法的基础。学习编程语言是为了与计算机“交流”,只有正确的格式才能被计算机成功识别。学习编程语言的起点就是了解这门语言的语法。本书使用Python语言进行算法讲解,本章主要讲解Python 3的编程语法。
第2章 双指针问题
“指针”是编程语言中的一个对象,它存储着一个内存空间的地址,计算机可以通过这个地址找到变量的值。也就是说,这个特定的地址指向这个特定的值。指针最大的优点在于它可以有效利用零碎的内存空间。
第3章 哈希算法
哈希算法又称散列函数算法,是一种查找算法,简单来说,就是把一些复杂的数据,通过某种函数映射关系,映射成更加易于查找的方式。但是这种映射关系有可能会发生多个关键字映射到同一地址的现象,我们称之为冲突。在这种特殊情况下,需要对关键字进行第二次或更多次的处理,在其他的大多数情况下,哈希算法可以实现在常数时间内存储和查找这些关键字。
第4章 深度优先遍历
深度优先遍历算法是经典的图论算法,深度优先遍历算法的搜索逻辑就和它的名字一样,只要有可能,就尽量深入搜索,直到找到答案,或者尝试了所有可能后确定没有解。
第5章 广度优先遍历
广度优先遍历与深度优先遍历类似,也是查询的方法之一,它是从某个状态出发查询可以到达的所有状态。但不同于深度优先遍历,广度优先遍历总是先去查询距离初始状态最近的状态。
第6章 回溯算法
回溯算法可以被看作走迷宫,因为我们不知道出口在哪里,所以只能不断地深入,尝试不同的路线。一旦找到了出口便可以回溯到起点,辨清路线。
第7章 贪心算法
贪心算法就是遵循某种既定原则,不断地选取当前条件下最优的选择来构造每一个子步骤的解决方案,直到获得问题最终的解。即在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做的仅是在某种意义上的局部最优解。
第8章 动态规划算法
动态规划算法将待求解问题拆分成一系列相互交叠的子问题,通过递推关系定义各子问题的求解策略,并随时记录子问题的解,最终获得原始问题的解,避免了对交叠子问题的重复求解。
第9章 最短路径问题
把地点看成节点,道路看成边,整个地图就可以被看成一个加权图。计算加权图中两点间的最短路径是编程的一个重要问题,这一章我们会用以下几个算法解决这个问题:迪可斯特朗算法、Floyd算法、A*算法。
第10章 分治算法
分治算法的核心思想是把一个规模很大的问题化简为多个规模较小的问题,这些子问题虽然独立而不同,但是问题的本质是一致的,从而达到分而治之的目的。
适合阅读本书的读者
? 需要全面学习算法的人员
? 需要学习Python的程序员
? 对编程算法感兴趣的人员
? 希望提高算法水平的程序员
? 专业培训机构的学员
阅读本书的建议
? 没有Python基础的读者,建议从第1章顺次阅读并演练每一个实例。
? 有一定Python基础的读者,可以根据实际情况有重点地选择阅读各个模块和项目案例。
? 对于每一个模块和案例,先自己思考一下实现的思路,然后再阅读,学习效果会更好。这样理解起来也会更加容易、更加深刻。
arr=[1.2.3.4.5.6.7.8.9.10]
for i in range(len(10))
23页这个len函数绝对错了
二分查找的最终代码
二分查找 (数组长度越长越能提现性能)
“””
二分查找需要两个指针,指向数组第一个元素叫头指针,指向数组最后一个元素叫尾指针,
查找范围,包括头指针指向的元素但不包括尾指针指向的元素。
“””
numbers = [200, 20, 30, 40, 50, 60, 700, 710, 800, 900]
head, tail = 0, len(numbers)
查找8的下标
search = 710
ans = 0
查找范围大于1时才会进入while
while tail - head > 1:
mid = (head + tail) // 2
if search < numbers[mid]:
else:
if search == numbers[head]:
ans = mid
pass
else:
ans = -1
pass
print(ans)
么这错多
第四章计算岛的大小的算法描述是没问题的,但是给出的程序是有问题。因为描述中说如果一个搜索点周围不是海水就是已经遍历的陆地时,返回上一搜索点。但是程序里是没有体现的。这会造成错误,比如下面这个岛就算不对。
0 1 1 ////////////////////////////////////////////////////0 2 1
1 1 1 /////////////////////////////////////////////////// 2 2 1
1 1 1 如果按照书上的算法,最后得到 2 2 1 。因为到了0下面那个二时,程序就停止了。但是,事实上,应该逐一返回,这样才能遍历剩下的1.
页码:56 • 行数:13 • 印次 3
ans = ans + arr2[i:]
这里有问题,如果arr2[i]已经插入到列表中时,这里就会多加一次,例如将arr2改为[2,5,8,9]就会出错,或者将arr2改为[2,5,8,11,12]也会出错。修改方案:
i = 0
j = 0
ans = arr1.copy()
while j < len(arr1) and i < len(arr2):
if arr2[i] <= arr1[j]:
ans.insert(j + i, arr2[i])
i += 1
else:
j += 1
else:
ans = ans + arr2[i:]
print(ans)
print(i)
print(j)