《Algorithms》学习 No1 总结思路与零星笔记

学习思路总结

反思学习策略-——算法在于图像记忆与多练习

在学习算法之前，我依然沿袭了以前的思路，就是一定扎实基础，所以原计划是每一章节认真学习，认真做笔记总结。扎实基础没有错，认真做笔记也是个办法，但不是一个最有效率的办法。

做笔记的思路来源于很多人的体验，通过技术博客的形式将知识表达出来。要能够准确表达思路，就得首先将知识点加工内化，这个过程也就能较好地掌握知识点。嗯，这点没错。确实实践下来感觉自己学的很通透，或者说主要的脉络还比较清晰。

但是，并不是所有知识领域都适合这样做，或者说有更好的办法，比如算法。 这是因为一方面内容太多了！无疑，如果我扎扎实实地完全学很耗时间。而且，学东西如果不能立体多维度的知识点是很容易忘掉的，所以比方说我认为已经学得很不错的，认真研读书本和做笔记的Java以及汇编，虽然大部分重要的依然清楚，但不够熟悉，且还有很多细节会忘掉，这是必然的，细节没法一次性完全记住。

那么解决之道我觉得是快速学习以及大量练习。

算法学习要点

算法第一要点在图像记忆，好在我图像记忆天生不错，看完算法跟着视频看图像，很快就内化成知识了。而且我发现算法基本上都是一些图形结构的变化。insert search、shell search、quick search、heap search都有对应图象。直接看图像一目了然。

算法第二要点是分治和递归。稍微难一点的算法用到了分治的思想，将一个复杂的问题清晰地划分成不同情况，从最简单的情况入手，然后是复杂的，而且复杂的情况很有可能包含了简单的情况，所以又简化了一下。比如shell search，quick search分治递归的思想。 或者稍微看上去难一点的BST树的删除就是先考虑最简单的没有子节点的节点，然后是一个节点的节点，最后才是复杂的两个子节点的节点的删除。而且很多递归在里面。

算法第三个要点是辅助变量，比如对于interval search而言，通过对每一个节点上增加一个变量的方法。变量的含义是所以子节点的最大值，当查找量大于该最大值时，下面的值根本不需要查找了，因为连最大值都在外面。这就是该思路的核心内容了。

算法第四要点合适的解法，这个真的很难说，我觉得需要大量的练习才能实现，就是针对现实问题的大量实践获得的灵感，就像张小龙所言用户体验的大量积淀一样。看似简单，一点就通，但是想要达到一定基于大量的练习、琢磨。

比如用扫描线的办法解决多个方块是否重叠的问题，比如空间查找中的KD树，我觉得当初相当这一点真的匪夷所思，如果才能想到？这个灵感哪来的啊？算法真的有无穷的魅力值得探索。

还有Sedgwick的红黑树，left-link-red-black-tree，将红黑树大大简化了！得瑟一下的是学红黑树前我也冒出了这个想法，当然，停留在概念上，实现起来没那么简单。

我觉得一句诗最能体现算法的特点：纵里寻它千百度，蓦然回首，那人却在灯火阑珊处。

方法2 好教材

我看的视频教程： 算法 I by Sedgwick | 算法 II by Sedgwick

因为有图像的原因，所以学习速度非常快，我觉得最长大概一周时间可以攻略算法了。也有配套书，但是其实回过头来看，直接看书要理解内容效果太差。而先看了视频之后再看书，事半功倍。

方法3 多实践，多练习，多码代码来培养感觉

一句话，实践出真知，实践才能巩固知识，实践才能培养灵感。

以下是内容陆续摘录自《算法》中一些片段，为我觉得有意思的地方，比较杂。

辗转相除法

为什么辗转相除法可以得到最大公约数和最小公倍数呢？

递归

编写递归代码时有以下特点：

1. 递归总有一个最简单的情况，作为第一条return语句。也是递归的终止条件。
2. 递归总是尝试调用一个规模更小的子问题。
3. 递归的父问题和子问题不应该有交集。也就是划分的界限分明，该父问题解决的父问题解决，该子问题解决的子问题解决。

递归一方面是思路清晰，使用递归另一个原因是我们可以使用数学模型来评估程序性能。

API

模块化编程的一个重要组成部分是记录库方法的用法，并提供他人参考的文档，用应用程序接口的方式列出每个库方法名、签名和简短描述。所以API可以理解为一种书写格式。

API的目的是将调用和实现分离。可将API看出调用与实现之间的一份契约。

重定向与管道

管道命令可以看出是一个输入输出流。它的影响深远的优点是突破了传统输入输出流的长度限制。即使计算机没有足够空间来存储十亿个数，仍然可以被管道命令处理。即就像管道一下，虽然容不下大海，但是要多少水就有多少水可以流过，上游输出数据，下游处理并消耗掉这些数据。

二分查找

代码就不列了，很简单，就是对于一个有序列，不断取中间比较，判断大小，确定范围是在更小的一半还是更大的一半。这样查找范围每次都能缩小一半。

面向对象编程

面向对象编程或者称为数据抽象，主要思想是鼓励程序定义自己的数据类型（一系列值以及对这些值的操作），而不是全局方法。

面向对象有以下优点：

1. 允许通过模块化编程复用代码。
2. 可以轻易构造链表等链式数据结构。
3. 能准确定义所面对的算法问题（暂时不明白其中的奥义）。

另外其他书籍也对面对对象有其他解释，

我的理解是，面向过程将以整个程序流程为主体，作为处理某种线性的流程比较合适，某些函数方法可以复用。但是方法与数据之间的界定不明确，或者说哪些方法是针对哪些数据不明确。

而面向对象则是以数据为主体，定义操作这些数据的方法（从封装的角度）。以及继承、多态提高复用的灵活性。

简单的代码用面向过程，复杂的用面向对象。

正整数N用二进制表示，并转换为String类型

String s = "";
for (i = N; i > 1; i /= 2) {
    return (i % 2) + s;
}