双向链表 Doubly Linked List 前面介绍过的单向链表有几个缺点. 第一个就是它的addLast操作非常慢。单向链表只有一个变量保存列表头的地址, 以及每个节点对后面节点的单向引用(链接). 对于很长的列表，addLast方法必须遍历整个列表, 直到找到列表末尾才能执行插入操作. 最直观的优化方案就是加个’车尾’ 这样我们就可以直接通过last.next引用末尾位置. 不过另一个问题并没有解决, 就是删除列表最后一项removeLast这个操作还是很慢。因为在目前的结构设计下, 我们需要先找到倒数第二项，然后将其下一个指针设置为null。而要找到倒数第二节点, 我们就得先找到倒数第三个节点…… 以此类推。也就是说，对于删除末尾的操作，还是要几乎遍历整个列表。 反方向的链接 基于前面单向链表构建双向链表, 一个比较有效的方法是额外为每个节点添加一个指向前面节点的链接 - 指针. public class OneNode { public OneNode prev; //指向前 public int item; public OneNode next; //指向后 } 增加这些额外的指针会导致额外的代码复杂度, 以及额外的内存开销, 这就是追求时间效率的代价. Sentinel 与尾节点 双向链表的一个设计初衷，就是为了解决单向链表针对列表末尾位置的操作效率不高的问题，除了sentinel和反方向的链接还不够，我们还需要一个节点（指针）能够直接帮我们定位到列表末端。可以考虑添加一个的尾节点last 这样的列表就可以支持O(1)复杂度的addLast,getLast 和 removeLast操作了。 循环双端队列 Circular double ended queue 上面的尾节点设计虽然没什么错误，但有点瑕疵：最后一个尾节点指针有时指向前哨节点，有时指向一个真正的节点。更好的方法是使双向链表首尾相连, 构成一个循环，即前后节点共享唯一的一个前哨节点。 这样的设计相对更整洁，更美观(主观上的), sentinel的prev就指向列表最后一个节点, sentinel的next指向列表第一个节点. public class LinkedListDeque<GType> { private class OneNode { public OneNode prev; public GType item; public OneNode next; public OneNode(OneNode p, GType i, OneNode n) { prev = p; item = i; next = n; } } } Sentinel’s forward link always points to the last element....

链表 Linked List 前面有介绍以array为基础搭建的列表，支持自动扩容, 各种插入，删除速度都很快. 这里再介绍另一种方案, 链表, 也可以实现列表自动扩容. 带链接的节点 链表的核心组成是带链接的节点, 每个节点就像火车车厢, 有钩子连接下一节车厢. 以int节点为例: public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } next就是这个链接, 每一个节点就是其上一个节点的next. 使用嵌套类 这个节点作为一个相对独立的数据结构, 我们更希望让他单独作为一个类来维护. 再另外创建一个名为LinkedList的class与用户进行交互. 这样还有另一个好处就是提供一个命名为LinkedList的类给用户交互，用户更直观地知道自己是在调用链表。如果直接与node类交互，用户可能会困扰. 但同时考虑到这个node类只有LinkedList会调用，所以我们可以把node类嵌套进LinkedList中。 public class LinkedList<XXX> { private class OneNode { public XXX item; public OneNode next; public OneNode(XXX i, OneNode n) { item = i; next = n; } } private OneNode first; private int size; public LinkedList(XXX x) { first = new OneNode(x, null); size = 1; } //下面是各种方法....

我学习CS历程，也包含基础知识的总结以及编程实现的整理。 每一阶段里面, 都有很多个性化选项, 仅供参考 入门 CS入门 学习编写(至少)一种面向对象编程语言(C ++，Java®，Python®) 测试你的代码 夯实基础 你可以跳过这些而直接进入下面的进阶实践环节，并根据自己需要查漏补缺。 但是这些都是非常重要的基础，任何时候，只要有时间，就可以去学习了解。 逻辑推理和离散数学 熟悉计算机操作系统 学习计算机网络 掌握数据库 了解编译器和优化 了解计算理论 学习其他编程语言 进阶与实践 深入了解算法和数据结构 分布式，并行和大数据 安卓开发 iOS开发 网页开发 加密与区块链 参与项目 English template 英文模板 CS入门 现在的入门课基本都是用Python语言。 计算机科学导论，优达学城 CS50x 哈佛，语言包括C，Python，SQL和JavaScript加CSS和HTML CMU 15213: Introduction to Computer Systems (ICS) 面向对象编程语言 一般而言，建议先学Java 或 Python，再学C++。 这三种语言都基本掌握后，再根据自身的职业需求，选择其中一个语言（或者其他语言）进一步深入练习。 面向初学者程序员的在线资源： 编程方法学，斯坦福CS106A，Java 伯克利大学CS 61A计算机程序的结构与解读，Python Java编程简介，MIT Google Python Class 面向有经验的程序员的在线资源： 数据结构，伯克利大学 CS 61B，Java 计算机程序设计，Udacity，Python 抽象编程，斯坦福 CS106B，C ++, 最新作业 http://web.stanford.edu/class/cs106b/ 《数据结构与算法分析:C++描述》, Mark A. Weiss 测试你的代码 了解如何捕获错误，创建测试和破解软件....

记录学习AI的学习笔记，内容包含基础知识的总结以及编程实现的整理。 English template 英文模板 机器学习 Coursera Machine Learning， 吴恩达的简化版机器学习 Machine Learning, 吴恩达的机器学习课程 这个比较深入 Deep Learning, 吴恩达的深度学习课程 Neural Networks for Machine Learning, Hinton的神经网络课程 深度学习 Deep learning, Coursera Machine Learning Practical: DNN, CNN, RNN 每个lab的答案在下一个lab 分支，即lab1的答案可以在lab2 branch里面看到。这个代码全部用Python class，比coursera的难度高点。 自然语言处理 自然语言处理, 斯坦福 加速自然语言处理, 爱丁堡大学 深度学习处理自然语言，斯坦福 计算机视觉 图像识别：卷积神经网络，李飞飞，斯坦福 机器人 机器人入门，斯坦福

列表 List 前面说到Java的数组无法更改长度，那么也就无法实现插入或者删除数组成员。Java提供了功能更丰富的数据结构 - 列表（list）。所谓列表，即有序的集合（序列），用户可以精确地控制每个元素插入到列表中的哪个位置。用户可以通过整数索引（列表中的位置）来访问元素，并搜索列表中的元素（详细可进一步参考oracle官网）。 这里我们尝试以java的array为基础实现一个列表，目标是实现自动扩容 (Java中的ArrayList不仅仅有自动扩容, 也继承了[List]的其他功能)。在探索的过程中, 可以顺带学习很多相关的内容. 使用自上而下的设计思想搭建一个框架: 先写出最基础的部分, 也就是一个构造器，前面学过了整数数组，我们直接拿来用 /** Array based list. */ // index 0 1 2 3 4 5 6 7 // items: [6 9 -1 2 0 0 0 0 ...] // size: 5 public class AList { private int[] items; private int size; /** 构造一个初始容量100的数组，初始有效数据成员为0. */ public AList() { items = new int[100]; size = 0; } /** 下面添加其他方法 */ } 然后思考我们需要什么功能，把功能需求转化为实例方法instance method的形式，先把方法的外壳描绘出来，注释上该方法的功能（目的），输入值，返回值是什么之类的。具体的功能实现可以先空着，之后一步步丰富。...

数组（Array） 数组是一种特殊的对象，有一个固定的数组长度参数N，由一连串（N个）连续的带编号的内存块组成，每个都是相同的类型(不像Python可以包含不同类型)，索引从0到N-1编号。A[i]获得数组A的第i个元素。这与普通的类实例不同，类实例有具体变量名命名的内存块。 数组实例化，包含对象的数组 Array Instantiation, Arrays of Objects 要创建最简单的整数数组, 有三种方式: x = new int [3]; //创建一个指定长度的数组，并用默认值（0）填充每个内存块。 y = new int [] {1，2，3，4，5}; //创建一个合适大小的数组，以容纳指定的初始值 int [] z = {9，10，11，12，13}; //省略了new，只能结合变量声明使用。 创建一组实例化对象: public class DogArrayDemo { public static void main(String[] args) { /* Create an array of two dogs. */ Dog[] dogs = new Dog[2]; dogs[0] = new Dog(8); dogs[1] = new Dog(20); /* Yipping will result, since dogs[0] has weight 8. */ dogs[0]....

数据类型 数据类型是程序设计语言描述事物、对象的方法。Java数据类型分为基本类型（内置类型）和引用类型(扩展类型）两大类。基本类型就是Java语言本身提供的基本数据类型，比如，整型数，浮点数，字符，布尔值等等。而引用类型则是Java语言根据基本类型扩展出的其他类型，Java要求所有的引用扩展类型都必须包括在类定义里面，这就是Java为什么是面向对象编程语言的原因… 上面的定义有点抽象，要理解数据类型，需要先理解一个问题: 神秘的海象问题 尝试预测下面的代码运行时会发生什么。b的变化是否会影响a？提示：类似Python。 Walrus a = new Walrus(1000, 8.3); Walrus b; b = a; b.weight = 5; System.out.println(a); System.out.println(b); 同样尝试预测下面的代码运行时会发生什么。x的改变是否影响y？ int x = 5; int y; y = x; x = 2; System.out.println("x is: " + x); System.out.println("y is: " + y); 答案是b的变化会影响a, 但x的改变不影响y，具体见可视化过程. 这里的差别虽然微妙, 但其背后的原理对于数据结构的效率来说是非常重要的，对这个问题的深入理解也将引导我们写出更安全，更可靠的代码。 基本类型 Primative Types 计算机中的所有信息都以一系列1和0的形式存储在内存中，这些二进制的0和1就是比特位（bits）。比如72和“H”在内存一般以01001000的形式存储，对他们的形式是一样的。一个引申问题就是：Java代码如何解释01001000，怎么知道应该解释为72还是“H”？ 通过类型types，预先定义好类型即可, 以下代码 char x = 'H'; int y = x; System.out.println(x); System.out.println(y); 会分别得到“H”和72. 在这种情况下，x和y变量都包含几乎相同的bits，但是Java解释器在输出时对它们进行了不同的处理。 Java有8种基本类型：byte，short，int，long，float，double，boolean和char。 变量声明 Declaring Variables...

嵌套类 我们经常需要在某个类A中使用另一个类B，如果设计时我们知道类B只有在类A中有被使用的可能性, 那么我们可以把类B定义在类A中, 作为类A的嵌套类, 类A就称之为外部类. 这样做可以隐藏类名，减少全局的标识符，从而限制用户能否使用该类建立对象。这样可以提高类的抽象能力，并且强调了两个类(外围类和嵌套类)之间的主从关系。 A nested class is any class whose declaration occurs within the body of another class or interface. A top level class is a class that is not a nested class. 嵌套类分为两类：静态和非静态。声明为static的嵌套类简称为静态嵌套类。非静态嵌套类称为内部类(inner class)。 class OuterClass { ... static class StaticNestedClass { ... } class InnerClass { ... } } 作为OuterClass的成员，嵌套类可以声明为private，public，protected或package private。外部类只能声明为public或package private。更多详情参考官网. 内部类 内部类可以直接访问外部类的方法和变量(即使是private的也可以)。如果从外部类程序代码中初始化内部类, 此内部对象会绑在该外部对象上. 一个内部类的实例作为成员存在于所属外部类的实例中。 public class Outer { private int outVar; class Inner { public int inVar; void go() { outVar += inVar; } } Inner myInner = new Inner(); public void do() { myInner....

Class 类的方法和变量细分为静态的和非静态的. 静态就是可以被类调用，所以静态方法/变量也称之为类方法/变量；非静态只能由实例调用，所以也称之为实例方法/变量。 静态变量 类变量 Class Variables 有static声明(静态变量). 静态变量一般是类本身固有的属性, 被该类所有实例共享。例如，我们可能需要用狗类的另一种生物学的统称“犬科”来作为类的说明， 这个时候可以用public static String binomen = "犬科";，这个变量理论上是由类来访问的。静态方法也类似. 以下代码定义了一个类来模拟狗，包含一个类变量作为这个类的说明，一个类方法用于发出叫声： public class Dog { public static String instruction = "狗类实例"; //类变量, 说明 public static void makeNoise() { System.out.println("汪!"); } } 这里没有定义main(), 在这种情况下如何直接运行这个类(java Dog), 程序是会报错的 错误: 在类 Dog 中找不到 main 方法, 请将 main 方法定义为: public static void main(String[] args) 否则 JavaFX 应用程序类必须扩展javafx.application.Application. 你可以选择在里面添加一个main()方法. 但这次我们选择不定义具体的main(). 具体要如何运行, 我们可以另写一个类定义一个main()方法来调用这个类. public class DogLauncher { public static void main(String[] args) { Dog....

Class Java的语法是为了更容易地模拟真实世界而设计的. 比如用程序实现一只狗, 可以用定义一个类class来描述它. 类class里面包括变量Variable，方法method（可以理解为Python的函数function）。变量可以储存数据，方法可以处理数据。变量必须在类中声明(即不能离开类独立存在)，不像Python或Matlab这样的语言可以在运行时添加新的变量。 构造对象的过程: 声明(declaration)引用变量: Dog smalldog; 创建对象：实例化 new Dog(20), 如果没有把它作为值赋给一个类声明变量, 那么这个实例化的值会被垃圾回收. 连接对象和引用：赋值对象给引用Dog smalldog = new Dog(5) 创建对象这一步，调用了Dog(), 不是普通的方法, 而是类的构造函数 Constructors. 构造函数 构造函数在初始化一个对象时执行, 构造函数与类名同名且没有返回类型, 而且可以带参数： /** 注意：构造函数与class类同名 但没有返回类型 */ public Dog(int w) { weight = w; } 然后在DogLauncher里实例化一只狗时, 直接Dog d = new Dog(20);即可. 在以上代码的基础上, 后续当我们想使用new和参数创建一只狗时，可以随时调用public Dog(int w)构造函数。对于熟悉Python的人来说，你可以理解java的构造函数为Python的__init__。 Java可以有与类同名的方法，只是要指明返回类型。 构造函数无法被继承 如果类有一个以上的构造函数，则参数一定要不一样，包括参数顺序和类型 构造函数链 执行new指令会启动构造函数的连锁反应(Constructor Chaining), 首先会执行其父类的构造函数, 依此类推连锁反应到Object类为止. 就算是抽象类, 也会有构造函数, 虽然不能被直接实例化, 但也会被唤醒. 理论上，每个类的构造函数需要先调用其父类的构造函数super()，依次入栈 public class Duck extends Animal { int size; public Duck(int newSize) { super(); // 调用父类构造函数, 且必须是在函数中的第一行 size = newSize; } } 如果明确写了super();, 则必须位于构造函数第一行....