https://naotu.baidu.com/file/85cb52f2adfc009bfadcfa25ee060c6f?token=f896d9b5cd738c93

点击以上的百度脑图查看

脑图中从 “什么是* 、 使用场景、有什么更好的优化办法” 这3个角度解决问题
对数组、链表、跳表写了具体的思考

开局一张图 = =

Week01目标：熟练掌握复杂度分析
一，
拆分知识点、刻意练习、反馈
五步刷题法（五毒神掌）做算法题的最大误区：只做一遍
二，
环境设置、编码技巧和 Code Style
工欲善其事，必先利其器
自顶向下的编程方式
时间复杂度、空间复杂度
三，
数组、链表、跳表的基本实现和特性
数组操作时复杂度分析
如何写好链表
跳表：升维** + 空间换时间

1.报名这个训练营之前也纠结过，最后下决心就报了。以前对算法一直很感兴趣但一直没系统的学习过，只是用到哪个了就上网查一下或看看书，没有形成体系，导致在工作中用到某些算法时手足无措，没有头绪。
2.通过这周的学习领会了覃超老师的五遍刷题法，觉得很受启发，通过反复的练习确实能加深记忆和理解，其中要尽可能想到用更多的解法来实现。有些题刚开始想不出来不甘心，想继续死磕，可能是我有强迫症吧，但想到覃超老师的话就放弃死磕了，习惯了leetcode上看高手的代码，最后能达到熟练默写下来。
3.学习算法确实很枯燥，但我认为我是个有耐心的人，修炼好的话一定对工作中有很大帮助，我要坚定在算法道路上一直走下去。

多练习才能够掌握，遇到不会的题目，看题解先不看代码，看完思路后自己尝试着去按照思路用代码实现。写完代码运行通过后再和别人的代码做比较，看看哪里有需要优化的地方，进行改进。 会了以后，过两天再回来做题，可能还是无法一次性把代码写对，过两天再来写。由此往复，看题目就亲切了好多。

题目：移动零、移除排序数组中的重复元素
解题思路：这些数组相关问题的前提条件都是不开辟新的存储空间，原地进行数组变换。大部分都可以采用双指针（double point）的方式进行解决，其中一个指针用于遍历原数组元素判断数组元素是否符合条件，另一个指针用于新数组元素存放，符合条件则进行指针递推

• 数组类型题目
  一般最优解采用双指针法

• 链表类型题目
  大多需要迭代、递归来处理，可以适当加上哨兵节点，这样可以简化代码，LinkedList也是如此实现

• 跳表
  实现代码简单，使用空间换时间，建立多级索引，很适合查询；修改时索引也需要修改，时间复杂稍微高一点

• 一维数据结构常见解法
  空间换时间
  一维升二维

• 补充：
  思维导图
  

学习笔记
这个星期重点学习了Array和LinkedList。Array和LinkedList的理论并不是很难，各自的特点也比较鲜明。

• Array的内存是连续的，通过下面这个公式就能以O(1)的时间复杂度访问Array中的任意一个元素。

a[i]address = baseAddress + i * dataTypeSize

与此同时，其缺点也比较鲜明，如果是申请一些小的内存空间没什么问题，但是如果要申请1G，2G甚至更大的内存就有问题了。当内存中没有这么大的连续内存空间的时候，就会出现申请失败的情况。而且，删除或者是向Array中插入元素，为了维护内存空间的连续性，需要搬移大量的元素，时间复杂度是比较高的，平均下来都是O(N)的时间复杂度。

• LinkedList与Array相反，内存不连续，插入和删除都是O(1)的时间复杂度，但是查找则是O(N)的时间复杂度。

掌握了这些理论，只能说是在宏观上对Array和LinkedList有了一定的认识，距离真正掌握Array和LinkedList仍有不小的距离。特别是在做题的时候就会发现，即便对于这些理论已经很熟悉了，依然写不出优美的LinkedList的代码。需要大量且重复的练习，需要将其从掌握理论的阶段上升到看到题就能产生条件反应的阶段，才能真正掌握Array和LinkedList。
我将这星期学习过程中的心得和思考总结如下：

• 在做LinkedList的题目的时候，一定少不了纸和笔，少不了勾勾画画。只有通过这种画图的方式，对于哪个指针指向哪个节点，进行删除或者插入的时候先动哪个指针，再动哪个指针，才能了然于胸。人脑很难处理太过复杂的问题，所以我们需要将一个个的问题划分开，逐个击破，通过在纸上画图，打草稿，能将代码以及执行过程走一个流程。在这个过程中，不仅会加深自己的印象，更会对执行过程中的脉络有一个更深的理解。
• 在做LinkedList的时候，大部分问题都可以通过递归的方法去解决。我对递归的理解如下：以两两交换链表中的节点为例，在一次代码的执行中，我们只需要负责本次代码所需要交换的两个节点，而对于其他节点，我只负责传入下一次递归。以交换下面一个链表中相邻的元素为例，对于我个人来说，我的思维是从左到右。1→2→3→4→Null
  因此，拿到这样的题目，我第一感觉是先交换1和2节点，1和2交换完毕以后再继续往下走。对于递归代码则不是从左到右，而是从右到左的顺序进行执行。
  我模拟一下机器的思维：要交换1和2节点很简单，但是我交换完1和2节点以后再去指向3则不对，因为3和4也要交换，我应该要去指向4才对。但是我只能管我当前两个节点的交换，我管不了3和4呀。怎么办？等着呗，我等3和4交换完毕以后我再进行交换，然后就可以顺利成章的指向交换过后的4了。上面的例子比较简单。当3和4准备交换的时候，发现自己是最后两个节点，本来是指向Null，交换完毕还是指向Null。那就没有1和2节点的后顾之忧了，可以大胆交换了。若3和4节点并非最后的节点，它们也会重复1和2的动作，等下面两个节点交换完毕，再进行交换。所以对于机器来说则是从右到左开始执行的。我觉得明白了这些，在理解递归代码的时候还是比较容易的，但是距离写出优雅的递归代码，还有很多路要走。
• 使用Map和Set的时候，通常思路都是先将元素放入Map和Set中，然后在进行遍历的时候来进行查找看Map和Set中是否包含该元素。我的想法则是这样的，对于Map来说，直接将元素进行put，若put成功，则说明之前Map中没有该元素(针对Map中的Key，因为Key不能重复，但是Value可以重复)，同时会返回一个null，若put不成功，则会返回非null，同时也说明该Map中已经存在了当前想要put进去的元素。这样就可以做到在put的时候就可以进行查找，无需调用额外的containsKey方法进行查询。使用Set的时候也同理，若add成功则会返回true，否则返回false，利用返回值的不同来进行插入+查询。
  Here is my github repository，welcome!

标题格式：【学号后四位_Week01】（如果是第二周就是Week02，以此类推）+文章标题

正文部分，字数不限。

• 数组（array）连续空间 随机访问0(1),尾部插入&删除0(1),中间插入&删除o(n)适合尾部添加&删除或多次随机访问
• 链表 (linked list)不连续空间通过持有后(前)的引用构成的单(双)链，随机访问o(n),插入&删除0(1),适合首(尾)插入删除，多次修改顺序遍历。
• 调表（skip list）是在有序链表的基础上添加辅助定位的索引是取代平衡树的二分查找的一种数据结构 插入删除和查找均为o(logn)

Hi各位同学，俗话说“三人行，必有我师”，因此我们鼓励大家在整个学习期间，多多 Review 同班同学的代码并进行点评。在这个过程中：

1. 可能你会从其他同学的代码中学到一个更优的思路
2. 可能你会因为其他同学给你的评论启发新的灵感
3. 可能你的代码会得到大家纷纷的点赞
4. 有时候也可能因为其他小伙伴的一句“学习了”而备受鼓舞

“让优秀的人一起学习”，大家可以在互相 Review 的过程中思考更多、获得更多。因此，请把你的算法题作业链接（你自己仓库的链接就好）回复在下面，这样大家就可以更方便的进行代码 review 啦！

跟帖格式：

学号后三位：
姓名（你在班里的姓名，便于同学可以跟你讨论）：
你使用的语言：
你的代码链接：

第一周收获
思维篇

• 兵欲善其事，必先利其器，熟悉IDE中编码的快捷键，对写代码的效率会有提高。
• 完全想不出解决方法的题目，直接看题解。
• 算法能力和智商无关，唯手熟尔。
• 实践，实践，反复实践。

方法篇

• 五毒神掌
• 切题四件套

做题总结

• 要刻意注意一些边界条件
• 对于有序数组的题目，均可考虑有没有双指针的思路来解答。
• 多重循环，要注意每一层的循环计数和退出条件的变量不要弄错。
• 在写代码卡住的时候，借助纸和笔来理清逻辑再写。

##题目：
每次跨 一个或两个台阶 上楼梯 第n节台阶有多少种走法?

##思考
典型动态规划题 答案为斐波那契数列,但对于怎么得出第n个是第n-1 和第n-2 的和,这个结论. 还是不太清楚.

##解答
经群友们解答, 第n节台阶的走法必然是其所有可能的走法的分支的和.

• 那么,有几条分支?
• 两条 f(n-1) ,f(n-2).
  所以结果为: f(n-1)+f(n-2).
  fml...

算法英语两条腿，希望在学习算法的同时也能提高自己的英语水平。虽然一开始觉得很难受、很不舒服，但是正所谓万事开头难，走出舒适圈后慢慢习惯就好。
之前有跟着王争老师的专栏学习过数据结构与算法，但由于工作原因（年近年底忙得飞起），有一段时间没刷题，现在看回来基本都不会，不过那时也确实陷入了覃超老师所说的误区，以为自己懂了，同样的题目只刷一两遍，过一段时间基本只记得思路而忘记了具体的实现，其实这也是没有真正掌握吧，希望在以后的这段一起学习的日子，大家共同努力，一起成长，顺利修成这门内功。

关于原地旋转数组的解法分析：

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

题意分析：

首先可以将这个数组想象成首尾相连的环形链表，题目其实就是将这个链表顺时针旋转k位，我们会发现每次旋转是数组的最后一位会旋转到数组的首位。

解法分析：

一、暴力法
有题解可知，要解决旋转问题我们只需要将数组所有数往后移动一位，并将最后一位移动到首位，重复k次即可

for (int i = 0; i < k; i++) {
            int prev = nums[nums.length - 1];
            for (int j = 0; j < nums.length; j++) {
                int tmp = nums[j];
                nums[j] = prev;
                prev = tmp;
            }
        }

二、使用额外数组
解法A：使用一个新的数组将数组的后 k % nums.length 位移动到新数组的前几位然后将数组剩余元素补到新数组后即可

      k = k % nums.length;
      int[] tmp = new int[nums.length];
      int index = 0;
        for (int i = nums.length - k; i < nums.length; i++) {
            tmp[index] = nums[i];
            index++;
        }
        for (int i = 0; i < k; i++) {
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
        }
        for (int i = 0; i < k; i++) {
            nums[i] = tmp[i];
        }

解法B：通过 k % nums.length 可是算出数组每一位元素共需移动几位，通过 i % k 计算出每位数的新的位置，并将其放置在新数组内，最后将新数组覆盖到老数组即可

        k = k % nums.length;
        int[] tmp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tmp[i % k] = nums[i];
        }
        // 循环替换数组可用下面arraycopy替换
        // for (int i = 0; i < nums.length; i++) {
        //     nums[i] = tmp[i];
        // }
        System.arraycopy(tmp, 0, nums, 0, nums.length);

三、有 a = k % n 个数被移至头部，现将整个数组反转，再将前 a 个数反转，最后将 a - nums.length 个数反转即可得到新的数组

public void rotate2(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

看到了覃超老师的刷题方法，想到了之前看到的一篇文章：https://www.zhihu.com/question/280279208/answer/499663699 ，感觉是将这里面的两种方法有机的结合到了一起，提高刷题效率的同时，也学到了题目的各种解法。自己之前的学习误区就是刷题只刷一遍（在几个月后忘得一干二净），而且在做完题以后，只看了国内站的题解（经过这周的实践，发现国际站里，确实有很多好的题解，也会有一些*操作，可以有效减少代码行数）。个人觉得还需要做的一点就是同类型的题目要多做总结，虽然是五遍刷题法，但是如果好几次遇到相同类型的题目还是直接看的答案，就比较不应该了。
本周学习到的内容：
1.数组：常用的技巧：双指针，和哈希表。
2.链表：快慢指针、双指针、虚拟节点（一个虚拟头结点，这样在写代码的时候，就不需要特殊处理第一个节点）。
3.跳表：在链表的基础上，增加了索引。查找效率远高于链表，类似于数组中的二分查找，也同样需要链表有序这个大前提。

   算法对我来说，是相对业务更纯粹，更有意思的东西。基于算法题所展现的出来的灵活性、巧妙性这种东西更让我着迷。我也想通过它，在业务的建模和表结构组织上更加得心应手。

以下是我带来的总结：

切题四件套：

1. clarification 看题，反复沟通，确保题意
2. possible solution 列出不同的解法，相对的时间和空间复杂度（time/space），比较优劣
3. coding 多写
4. test case 测试案例，显得有始有终

五步解题法

刷题第一遍

    5-10分钟：读题+思考
    无思路，直接看解法：注意！多解法优劣（在于学会解来运用，而不是创造）
    背诵、默写好的解法（背诵、默写能完成，意味可以理解问题了）

刷题第二遍

马上自己写--在LeetCode上提交（了解默写完成后自己写，LeetCode上去跑再debug）
 多种解法比较，体会--》优化

刷题第三遍

     过了一天，再重复做题
    不同解法的熟练程度（不熟练的，针对性再练习）

刷题第四遍

    过了一周后，再反复练习相同的题

刷题第五遍

   面试前一周恢复性练习

290
Ryan
Python
https://github.com/h310558606/algorithm007-class02.git

当前负责的项目中有一个撮合服务，买单、卖单会被放置入深度列表，深度列表采用链表结构，买单或者买单优先匹配深度中的第一个单子，即链表中的头节点，如果价格匹配则成交，删除深度中的第一个挂单（头节点），如果价格不匹配则遍历深度寻找合适价格的挂单，如果有则成交。
看完链表相关内容后，我在思考：是否可以用跳表来替代之前普通的链表结构？跳表是在链表的基础上为节点添加了所以，我们都知道，在mysql中，添加索引会增加增加对内存的消耗，跳表也是这样，但是以空间换时间的做法是值得的。由于添加索引导致的内存消耗可以通过提高服务器配置来解决，但是提高匹配订单的速度却不是可以通过扩容来实现的。
再来看看两种链表结构的复杂度对比。普通的单链表遍历的时间复杂度为O(n)，插入，删除操作均为O(1)，但是由于其在插入时除了头插还需要遍历list，所以也是O(n)。而跳表则是实现了类似二分查找的功能，将遍历的时间复杂度缩小到了O(logN)。下周会开始工程上的我改造，后续会补充demo。

-通过这几天的刷题，对链表的操作又有了新的认识。之前对于链表的操作，脑子里总是乱乱的。现在找到了一点套路，操作链表时，可以新建一个链表（用于存放结果），同时再新建一个指针，指向新建的链表，根据需要可以在原链表上新建指针来操作原链表结点，再将操作后的结点可以存储在新建的链表下，同时移动新链表上的指针用来存放下个结点。

• 链表中是否存在环，可以使用快慢指针。若存在环，快慢指针会重合。

要求

1. 每周从覃超老师布置的题目中，至少完成并提交两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章或总结，切忌流水账。
3. 每周需要 review 并点评至少 5 位同学的代码作业或学习总结

作业提交 Deadline

2020年3月15日 23:59 （以当地时间为准）
未按时提交作业，会在个人作业总分 -2 分

本周作业概述

本周需要完成学习的视频内容：

• 第 3 课 | 数组、链表、跳表

以上视频后，覃超老师都给出了大家可以练手的算法题。

本周算法习题库：

第三课课后习题：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
https://leetcode-cn.com/problems/rotate-array/
https://leetcode-cn.com/problems/merge-two-sorted-lists/
https://leetcode-cn.com/problems/merge-sorted-array/
https://leetcode-cn.com/problems/two-sum/
https://leetcode-cn.com/problems/move-zeroes/
https://leetcode-cn.com/problems/plus-one/

1. 两数之和

方法一：暴力法（两层循环）时间复杂度：O(n^2) ，空间复杂度O(1)

方法二：两遍哈希表（第一遍构造哈希表，第二遍找答案），时间复杂度：O(n) 空间复杂度O(n)

方法三：一遍哈希表（最优解）时间复杂度：O(n) ，空间复杂度O(n)

11. 盛最多水的容器

方法一：暴力法（两层循环）时间复杂度：O(n^2) ，空间复杂度：O(1)

方法二：双指针法（前后两个指针向中间移动，最优解）时间复杂度：O(n) ，空间复杂度：O(1)

15. 三数之和

方法一：暴力法（三层循环），时间复杂度：O(n^3) ，空间复杂度：O(1)

方法二：哈希表（排序+两层循环），时间复杂度：O(n^2) ，空间复杂度：O(1)

方法三：排序+双指针，时间复杂度：O(n^2) ，空间复杂度：O(1)

21. 合并两个有序链表

方法一：迭代，时间复杂度：O(m+n) ，空间复杂度：O(1)

方法二：递归（没看明白），时间复杂度：O(m+n) ，空间复杂度：O(m+n)

24. 两两交换链表中的节点

方法一：迭代， 时间复杂度：O(n) ，空间复杂度：O(1)

方法二：递归，时间复杂度：O(n) ，空间复杂度：O(n)

25. K 个一组翻转链表

方法一：迭代+就地逆置法， 时间复杂度：O(n) ，空间复杂度：O(1)

方法二：迭代+尾插法， 时间复杂度：O(n) ，空间复杂度：O(1)

方式三：递归

26. 删除排序数组中的重复项

方法一：双指针， 时间复杂度：O(n) ，空间复杂度：O(1)

66. 加一

1. 末位无进位，则末位加一即可，因为末位无进位，前面也不可能产生进位，比如 45 => 46
2. 末位有进位，在中间位置进位停止，则需要找到进位的典型标志，即为当前位 %10后为 0，则前一位加 1，直到不为 0 为止，比如 499 => 500
3. 末位有进位，并且一直进位到最前方导致结果多出一位，对于这种情况，需要在第 2 种情况遍历结束的基础上，进行单独处理，比如 999 => 1000

时间复杂度：O(n) ，空间复杂度：O(1)

70. 爬楼梯

方法一：暴力递归， 时间复杂度：O(2^n) ，空间复杂度：O(n)

方法二：记忆化递归，时间复杂度：O(n) ，空间复杂度：O(n)

方法三：动态规划（dp[i] = dp[i-1]+dp[i-2]），时间复杂度：O(n) ，空间复杂度：O(n)

方法四：斐波那契数列 ，时间复杂度：O(n) ，空间复杂度：O(1)

方法五：Binets 方法(矩阵相乘)，时间复杂度：O(logn) ，空间复杂度：O(1)

方法六：斐波那契公式，时间复杂度：O(logn) ，空间复杂度：O(1)

public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}

88. 合并两个有序数组

方法一：合并排序，时间复杂度：O((m+n)log(m+n)) ，空间复杂度：O(1)

方法二：双指针从前往后，时间复杂度：O(m+n) ，空间复杂度：O(m)

方法三：双指针从后往前，时间复杂度：O(m+n) ，空间复杂度：O(1)

141. 环形链表

方法一：哈希表（set） ，时间复杂度：O(n) ，空间复杂度：O(n)

方法二：快慢指针，时间复杂度：O(n) ，空间复杂度：O(1)

142. 环形链表 II

方法一：哈希表（set） ，时间复杂度：O(n) ，空间复杂度：O(n)

方法二：快慢指针，时间复杂度：O(n) ，空间复杂度：O(1)

189. 旋转数组

方法一：暴力法（嵌套循环），时间复杂度：O(n*k) ，空间复杂度：O(1)

方法二：使用额外空间存储旋转后的数据，时间复杂度：O(n) ，空间复杂度：O(n)

方法三：使用环状替换（最优解），时间复杂度：O(n) ，空间复杂度：O(1)

方法四：三次反转，时间复杂度：O(n) ，空间复杂度：O(1)

方法五：Python切片，（nums[:] = nums[n-k:] + nums[:n-k] ）

206. 反转链表

方法一：就地逆置法， 时间复杂度：O(n) ，空间复杂度：O(1)

方法二：头插法， 时间复杂度：O(n) ，空间复杂度：O(1)

方法三：递归，时间复杂度：O(n) ，空间复杂度：O(n)

283. 移动零

最优解：双指针法（快慢指针，慢指针前都是非0，慢指针和当前指针之间都是0），时间复杂度：O(n) ，空间复杂度：O(1)

由于自己是半路转行，基础比较薄弱，希望在这里能和大家共同成长。
首先是预习周：

1.自上而下的编程**：做相对复杂的题的时候，先不要纠结于小点，先把主框架写出来，写主框架的时候一些子模块可以先用一个subfunction的名称代替，写完主干之后再去写subfunction。

2.五毒神掌，五遍刷题法。

第一周的收获主要有：

三种最基本的数据结构：

array；list； linked list。
关于list 和 linked list的比较：
列表的查找的时间复杂度是O(1)，添加删除的时间复杂度是O（N）。
链表的查找的时间复杂度是O(N)，添加删除的时间复杂度是O（1）。

为了提高链表的性质，介绍了跳表。
他与链表相比，查找的时间复杂度降低了，从O（n）到O(Logn)，空间复杂度增加了，但还是O(N).
用到的核心**是：升维 用空间换时间。 优化时间复杂度的优先级高于空间复杂度.

然后提到了 LRU cash（具体不懂~），它们就是用的多链表实现的，会在之后介绍，

体会最深的刷题方法： 五遍刷题法。
之前想要在算法和数据结构上走远一些，于是会尝试去解题，但即便是标记为简单的题目，硬是想破头都想不出来，一度很怀疑自己根本在coding上毫无天赋，想要放弃。真正是从入门到放弃，才刚开始迈开一条腿，看了一下里面的风景，又把腿收了回去。
但是现在看来，原来学习这个高深的知识点居然也都可以用‘死记硬背’的方式来了，这可是多么大的好消息阿。关键是这个还有理论依据，然后还有高手老师用实际例子支持站台，这等于给自己一个定心丸。
还有就是如果10分钟想不出来，就果断直接看题解，这又给我信心，原来自己那么‘差’，不是真的‘差’，只是不熟练。
总而言之一句话，得到了学习方法和自信心的提升，是自己可以实际上往前走下去的。
当然，自己还是有很多差距需要弥补，本就不是科班出身，逻辑思维训练更要刻意为之，加油了！

数据结构与算法基础：
1、好的程序=时间复杂度+空间复杂度+应用场景
时间复杂度：关键代码的执行次数
空间复杂度：关键代码占用内存
应用场景：
举个简单的例子：
交换 int a=5,int b=6;
在不同应用场景下，可能写出不同的解决方案：如照顾可读性，我们一般解作：
temp=a;
a=b;
b=temp;
但如果在与机器打交道，如跑步机、飞机等硬件存储容量有限，情况下可解为：
a=a^b; b=a^b;a=a^b;
性能上来说，后者是位运算，速度肯定大于前者
2、数组是内存中一段连续的存储空间，利用两个指针来操作，省时省空间，常用于尾部的插入删除以及寻址。
3、冒泡排序与选择排序在n小于5的情况下，速度还是很快的

merge-two-sorted-lists问题，我自己在解题时老想着双链表合并，导致代码越写越复杂。看题解后觉得更应该把链表想象成一个个节点，再加上引入head节点，然后用一个节点指针做偏移不断加入新节点，简化了代码逻辑。另外，题解里有个递归解法挺有意思的，继续看。

题目：给定一个由整数组成的非空数组所表示的非负整数a[]，在该数的基础上加一
解法1:从数组末尾开始+1遍历，如果加后的值可以整除 10，并将取余的数赋值给当前位置，然后继续遍历，否则跳出循环；否则跳出遍历并直接返回；当遍历结束仍然没有返回，说明0位置的数值为0，则新建数组长度为a.length + 1 ,第0为赋值1，后a.length为赋值为遍历后的a[]
时间复杂度为O(n),空间复杂度最差为O(n)
解法2:将被加数1看作为b[],新建数组c[],大小为max(a.length, b.length)，值为较小长度的数组和向前补全0，将c[] 和 a,b 中较小的数组相加，判断c[0] 时候为0 ，如果为0 ，则取相加后对应a,b 的数组，否则取c； 这种方法同时可以解决加b[n]，或者是m 个数组的加法
int[] otherNums = new int[]{1};
int[] tempNums = new int[Math.max(digits.length, otherNums.length) + 1];
if (digits.length > otherNums.length) {
addZero(otherNums, tempNums);
andTwoNums(tempNums, digits);
return tempNums[0] != 0 ? tempNums : digits;
} else {
addZero(digits, tempNums);
andTwoNums(tempNums, otherNums);
return tempNums[0] != 0 ? tempNums : otherNums;
}
时间复杂度为O(n), 空间复杂度为O(n);

第一课

数据结构与算法总结 & 刷题方法

如何精通一个领域

• Chunk it up 切碎知识点
• Deliberate Practicing 刻意练习
• Feedback 反馈

数据结构

• 一维
  • 基础：数组 array (string), 链表 linked list
  • 高级：栈 stack, 队列 queue, 双端队列 deque, 集合 set, 映射 map (hash or map), etc
• 二维：
  • 基础：树 tree，图 graph
  • 高级：二叉搜索树 binary search tree (red-black，AVL), 堆 heap, 并查集 disjoint set, 字典树 Trie, etc
• 特殊：
  • 位运算 Bitwise, 布隆过滤器 BloomFilter
  • LRU Cache

算法

• If-else, switch -> branch
• for, while loop -> Iteration
• 递归 Recursion (Divide & Conquer, Backtrace)
• 搜索 Search: 深度优先搜索 Depth first search, 广度优先搜索 Breadth first search, A*, etc
• 动态规划 Dynamic Programming
• 二分查找 Binary Search
• 贪心 Greedy
• 数学 Math, 几何 Geometry

反馈

• 及时反馈
• 主动型反馈
  • 高手代码（Github, LeetCode, etc.）
• 被动式反馈
  • code review

五步刷题法

• 刷题第一遍
  • 5 分钟：读题 + 思考
  • 直接看解法：注意！多解法，比较解法优劣
  • 背诵、默写好的解法
• 刷题第二遍
  • 马上自己写 -> LeetCode 提交
  • 多种解法比较、体会 -> 优化
• 刷题第三遍
  • 过了一天后，再重复做题
  • 不同解法的熟练程度 -> 专项练习
• 刷题第四遍
  • 过了一周：反复回来练习相同题目
• 刷题第五遍
  • 面试前一周恢复性训练

第二课

训练准备和复杂度分析

电脑设置

• Google 搜索入口
• Mac: iTerm2 + zsh (oh my zsh)
  Windows: Microsoft new terminal: (https://github.com/microsoft/terminal)
• VSCode; Java: IntelliJ; Python: Pycharm;
• LeetCode plugin (VSCode & IntelliJ)
• https://vscodethemes.com

Code Style

Java、Python…

• Google code style
• Facebook
• Airbnb

指法操作

想成为大牛，首先要学着他们的样子去做事，装也要装的像

• home, end （行头、行尾）
• Word 单词、选单词、选整行
• IDE 的自动补全
• Top tips for

自顶向下的编程方式

用代码块或者空的 method 去绘制思路轮廓，而后再实现具体内容，可降低思维复杂度，也让代码结构清晰整洁

时间复杂度 & 空间复杂度

• O(1): Constant Complexity 常数复杂度
• O(log n): Logarithmic Complexity 对数复杂度

for (int i = 1; i < n; i = i * 2) { }

• O(n): Linear Complexity 线性时间复杂度

for (int i = 1; i <= n; i++) { }

• O(n^2): N square Complexity 平方

for (int i = 1; i <= n; I = i++) {
    for (int j = 1; j <= n; j++) {
    }
}

• O(n^3): N square Complexity 立方
• O(2^n): Exponential Growth 指数

int fib(int n) {
    If (n <= 2) return n;
    Return fib(n - 1) + fib(n - 2);
}

• O(n!): Factorial 阶乘

第三课

数组、链表、跳表

Array（数组）

Array 增加、删除元素，需要挪动平均一半数组长度的元素，所以，对于 Array 来说，增删慢。但 Array 可以随意访问到任意元素，查询速度很快。

Array 时间复杂度：

• prepend O(1)
• append O(1)
• lookup O(1)
• insert O(n)
• delete O(n)

Linked List（链表）

Linked List 增加、删除元素，因为只需要改变 next 指针，增删不需要大量挪动链表中的元素，所以，增删很快，但想找到一个元素必须从头结点或者尾结点一个一个的都查找一遍才能找到目标元素，查询速度就慢了。

Double Linked List 时间复杂度：

• prepend O(1)
• append O(1)
• lookup O(n)
• insert O(1)
• delete O(1)

Skip List（跳表）

为了解决链表查询速度慢的缺陷。添加一级索引、二级索引、多级索引。跳表是在链表的基础上根据升维**和空间换时间的手法。

现实中因为链表元素的增删频繁变化，索引要随着每次的增删进行维护，所以，现实中的索引可能是不规整的，有的跳 2 步，有的可能跳 3 步。

• 跳表时间复杂度 O(logn)
• 跳表空间复杂度为 O(n)

工程中的应用：

• LRU Cache - Linked list
  • https://www.jianshu.com/p/b1ab4a170c3c
• Redis - Skip List
  • https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html

第四课

栈、队列、双端队列、优先队列

Stack（栈）

• First in - Last out（先进后出）
• Last in - First out （后进先出）
• 添加、删除皆为 O(1)

Queue（队列）

• First in - First out（先进先出）
• Last in - Last out（后进后出）
• 添加、删除皆为 O(1)

Deque: Double-End Queue（双端队列）

• 两端可以进出的 Queue
• 添加、删除皆为 O(1) 操作

Priority Queue（优先队列）

• 插入操作：O(1)

• 取出操作：O(logN) - 按照元素的优先级取出

• 底层具体实现的数据结构较为多样和复杂：heap（堆）、bst（二叉搜索树）、treap（树堆）

• java 中的 PriorityQueue https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html

• java:

  • Stack: http://developer.classpath.org/doc/java/util/Stack-source.html
  • Queue: https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
  • Priority Queue: http://developer.classpath.org/doc/java/util/PriorityQueue-source.html

• Python:

  • heapq: https://docs.python.org/2/library/heapq.html
  • 高性能的 container 库: https://docs.python.org/2/library/collections.html

如何查询接口信息？

• google Java + Deque or Python + Deque 查看官方文档或者源码实现

对于数组：如果要求 O(1) 空间，原地操作。多指针没得跑，每次花样还不一样。
对于链表：考虑下除了迭代，是否可以使用递归解决。
旋转数组那个题：多次翻转的**很有意思，好像有个链表的题也可以这么干，有空找出去看看。

之前对算法和数据结构一直不怎么重视，后来慢慢意识到要想敲好代码，打好基础的重要性。之前也有相对性的去学习算法，但是效果不怎么好。之前刷题时就有遇到死磕一道题，一整天都没怎么头绪，效率极低。看了超哥的五毒神掌介绍后，明白不要去死磕题，我们做题为了快速解决问题，可以先把LeetCode上优秀方法理解，吃透，转化为自己的东西，做到举一反三。

作业：绘制自己的数据结构和算法脑图

要求：用脑图的方式把知识的脉络串联起来，不管对于学习新知识还是巩固已有知识，都是一种很好的学习方式。同学们可以将目前自己所掌握的数据结构和算法知识绘制成脑图，在绘制过程中可以查阅资料，补充目前掌握欠缺的部分，找到自己薄弱的地方。后面再通过课程的学习和刻意练习，动态地将自己绘制的脑图逐步补充、完善，从而达到真正的融会贯通。

脑图绘制工具不限。

虽然平时编程一直在实现各种算法，但是没有一个系统的学习，之前也没有在LeetCode上刷过题，现在仿佛打开了一个新世界的大门，刷题还是很爽的，哈哈。
一周的学习后，有很多感悟。
1.五毒神掌是学习的制胜法宝，做的题多并不一定就说明能力强，关键是是否有把知识真正吸收成自己的东西，5遍刷题，层层加深印象和理解，最后融汇贯通。这个方法不仅适用于刷题，也适用于学习任何一门知识，甚至是学习任何一门语言。
2.工欲善其事，必先利其器。要学习使用好工具，并且能熟练使用好工具。掌握了这一点平时工作效率会大大提升，而且给别人一种你很牛逼的印象，是自己的一个加分项。
3.我们的目的是学习算法，不是去创造算法，如果看到题目没有思路，果断看解析，不要和自己较真，不要给自己挫败感，不要打击自己的积极性。

经过一周的学习，对leetcode上的题目有了新的认识，但是有关数组的题目，有的解法仍然不能够很好的理解，慢慢来吧，一步一个脚印的学习，我相信一定可以的

第一周的课程比较简单，但仍然学到了不少东西，在遇到问题时若没有较好思路可以先考虑暴力解法，然后依次出发考虑改进的解法。还有一些小的细节，如一维数据结构升维解决问题，不仅可以让问题变得简单，而且速度也有提升，本周作业以及预习里面的几道题的双指针方法夫对我就很有启发。

解题感悟
从开学前的预习题，到第一周数组链表跳表后的练习题，
很多题都是爆破法，也就是我自己称为傻瓜解法来解的。
因为本身有ACM经验，能A到题就很高兴了，
但是看一下大牛们的解法有的真是特别巧，很多都是带着数学思维去解题，
也就是超哥说的分解子问题，找到规律和公式，这种思维方式是需要积极培养的。
最近在看Redis，对课上说的跳表也是感触良多。
刷题对我们这些已经工作，偏工程的人是一种放松和锻炼，找回了上学时的感觉。
本周一共刷了7道 即所有课后题。
以后难度会增高，还是积极的去看别人的好代码再自己思考，提升的更快。

第一周的课程其他的数据结构多少都知道一些，但是跳表第一次听到，感叹前人的智慧。
覃老师也多次提到，优化的常见思路就是升维，跳表就是很好的体现。再复习一下跳表的特点：
1、跳表是基于链表；
2、跳表只适用于链表的数据是有序的情况下；
3、跳表相当于平衡树实现简单，逻辑更清晰；
4、在数据量不是很大的情况下可以用来取代平衡树二分查找；
5、Redis、LevelDB中使用的就是跳表；

实现思路，在有序链表的基础上，可以每隔N个元素提出一个节点，形成一个新的链表用于索引，这样就可以将链表的查询效率O(n)提升为O(logn)，不过由于新增了索引链表在新增或者删除数据的时候需要维护索引表，导致链表新增或者删除数据O(1)的时间复杂度变成O(n)。

1. 双/多指针常用于解决数组问题；
2. 链表理解起来很容易，但在代码实现时要注意指针指向；
3. 对于求“最xxx”的问题，考虑动态规划，分解最优子问题；

关于环形链表的理解：
1、找到入环点：假设从链表头结点到入环点的距离是D，从入环点到两个指针首次相遇点的距离是S1，从首次相遇点回到入环点的距离是S2，指针P1一次走一步，指针P2一次走两步。当两个是指针首次相遇时，P1走的距离是Pa=D+S1；P2走的距离是Pb=D+S1+S2+S1；由于P2一次走两步故2*Pa=Pb;可求得D=S2；即链表头结点到入环点的距离等于首次相遇点到入环点的距离（可以在纸上画一下容易理解）。这样的话，把一个指针放在链表头部，另一个指针放在首次相遇点，两个指针每次都走一步，下一次相遇的结点就是链表入环结点。
2、求环长：在首次相遇后继续前进，记录指针P1或P2移动次数，终止条件为下一次相遇。步数即为环长。首次相遇后，两个指针都会在环内移动，P2与P1的速度差是1，故两者再次相遇时，P2比P1多走整整一圈。

1.爬楼梯问题确实让我对算法突然眼前一亮，谭超老师说的话已经记录在笔记本里了，希望一直都能受益。
2.最近几天一直在适应训练方式，尽管时间没那么多，也尽量抽时间来看，发现按照五毒神掌的方式每道题真的要花不少时间，希望真能坚持到底。

心得:
一.算法**:
1.升维: 一维变二维,跳表的实现
2.空间换时间:
二.数组
数组的下标表示: index = index % length,具体见题:向右旋转(LeetCode_189)
夹逼法: 使用双指针从数组两端往中间遍历,具体见题:最大面积(LeetCode_283)
快慢指针法: 使用两个指针进行操作,快指针用于遍历,慢指针用于特殊指示,具体见题: 删除重复元素(LeetCode_26)
三.链表
新增一个节点时,一定要先用新节点指向后节点,然后前节点再指向新节点,顺序不能反.
四:扩展
这次重新学习数组,链表,我进行了扩展,把java中基于数组,链表的ArrayList,LinkedList源码进行了阅读与总结,制作成了脑图,放入到代码中.
链接: https://github.com/Gzyequan/algorithm007-class02/tree/master/Week_01/G20200343040042

学号：102
姓名：WY
语言：python3
代码https://github.com/WeiyuZhao/algorithm007-class02

第一周学到了很多有趣的算法解决方法，移动零和的花式下标玩法，盛水最多容器的夹逼方式等，每道题都带来了很多收获，感觉每道题都一个思路，需要重复练习习惯这种思路，在遇到难题时就可以有想法去解决。接下来持续努力吧！

数组本质

数组的本质是把数据存储在计算机内存管理器开辟的连续内存地址中，所以数组的随机访问时间复杂度为O(1)，搜索的时间复杂度为O(n)，插入删除元素由于平均需要移动半个数组的元素，时间复杂度为O(n)。

链表本质

链表的本质是每个元素靠指针指向其相邻元素，随机访问时间复杂度因为需要遍历整个链表，所以访问和搜索的时间复杂度为O(n)，插入删除元素只需要处理相邻元素的指针指向关系，所以时间复杂度为O(1)。

跳表本质

跳表的本质是在链表的基础上进行升维，加入多级索引，每级索引不再是跳向相邻元素，而是跳跃2^k个元素，其底层实现有多种方式，有BST，AVL等，访问和搜索的时间复杂度为O(logn)，增删元素的时间复杂度也是O(logn)。

1.作为一个非科班出身的一年半java小菜来说，这些算法题都是很新鲜呢；
2.因为基础知识的薄弱，需要学习的东西太多了，上班的路上，午休，晚上 学习了第一周相关的数组、链表和跳表知识，还是不够深入，需要更多的时间去练习，学习；
3.预习的知识中：王争老师的《数据结构与算法之美》真是太有意思，太有帮助了，总结的很精炼，对我学习算法起到很大的帮助。
4.超哥讲的很精炼，更多的是讲方法，值得借鉴。
5.班班很负责，助教很热心，同学很有爱，大佬很多，有问题，大家讨论的气氛很有激情，感恩遇到的每一个同学，让我们共同加油。
6.这几天对数组练习较多，链表还是不熟悉，接下来，会更多的练习链表。
加油！加油！加油！

1. 端正态度，不要自己死磕。好好练习五毒神掌！
2. 逆向思考，比如爬楼梯，反着想就简单了。合并两排序数组，从后到前就简单
3. 数组题中，头尾指针收缩是一种思路
4. 数组题中，hash表，set中保存下标是一种思路

数组
数组用一块连续的内存空间，来存储相同类型的一组数据。
支持随机访问，时间复杂度 O(1)
插入、删除操作比较低效，为了满足连续空间需要进行数据的搬移，平均情况时间复杂度为O(n)

链表
链表内存空间可以不连续
链表类型有：单链表、双向链表、循环链表、双向循环链表等
更适合插入、删除操作频繁的场景，时间复杂度 O(1)
但是访问时需要遍历链表 ，平均情况时间复杂度为O(n)
某些情况下双向链表的访问比单链表更高效，如指定访问某个节点前面的节点
为了提高访问效率，用空间换时间的设计思路出现跳表

跳表
通过空间换时间，构建多级索引来提高查询的效率，实现了基于链表的“二分查找”
是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度为O(nlogn)

1. 升维
2. 空间换时间
   这是我第一周的主要收获，空间换时间很早就知道一直不知道升维，知道后才和之前知道的树和图等比一维数组和链表的差别。
   数组的操作有几个地方要注意 1. 数组边界，防止数组下标越界 2. 数组下表从0开始，要算好角标位置
   链表操作主要是注意增加的时候要先把新增的指向到next指向的，防止失去next的地址

1、Array 数组：
1.1：常见写法：
java,C++: int a[100];
python: list = [];
JavaScripty: let x = [1,2,3];
高级语言对数据类型没有严格的区别，泛型。
1.2：数组存储方式：
数组数据存储在一个叫内存管理器的东西里面，每当申请数组的话，计算机会分配一段连续的内存地址。可以随机访问任意元素。
1.3：数组的问题所在：
在于要增加删除数组元素的时候会进行一些相当的操作。
1.3.1：插入操作：
插入数据时，要移动其它数据的相应位置，平均时间复杂度为O(n)
1.3.2 ：删除操作：
同理同上平均时间复杂度为O(n)
2、Linked List 链表：
2.1 背影：
弥补数组的缺点，在增加和删除比较频繁的可以用。
增加删除节点的话，不会造成其它节点的位移和复制的操作，头插，尾插，insert, delete的操作都为O(1)
但是lookup的话，时间复杂度为O(n)
2.2 链表类别：
元素有一个value和next 来组成。串在一起变成了一个类似于数组的结构。
单链表只有一个next 如果还有pre的指针，那就是双向链表。
如果tail指向指向head的话，就是循环链表
2.3 如何轻松写出正确链表代码
1.理解指针或引用的含义
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量
2.警惕指针丢失和内存泄露
插入和删除时注意顺序操作，删除链表时记得手动释放内存。
3.利用哨兵简化实现难度
针对链表的插入、删除操作，需要对插入的第一个结点和删除最后一个结点的情况进行特殊处理。
链表一般用带头节点的来处理。
4.重点留意边界条件处理
1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个结点时，代码是否能正常工作？
3.如果链表只包含两个结点时，代码是否能正常工作？
4.代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
5.举例画图，辅助思考
3、skip list 跳表
3.1 跳表的特点：
注意：只能用于元素有序的情况。
所以，跳表对标的是平衡树和二分查找是一种 插入/删除/搜索 都是O(logn)的数据结构
最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树。
3.2 实现方式：
给链表升维：在原有的基础上，增加一级索引，每隔二个或三个元素，加一个索引，查找时先查索引。
3.3 时间复杂度分析：
n/2, n/4, n/8, 第K级索引结点的个数就是 n/(2的k次方)
假设索引有h级，最高级的索引有2个结点。 n/(2的h 次方) = 2， 从而求得 h = log2(n) -1
3.4 空间复杂度：
O(n)