第一周学习总结

关于算法

算法重要的是思维，要掌握算法需要有扎实的基础知识，尤其是数学，复杂度分析也是必不可少的手段。

解题只是训练，分析问题的思维才是重点。掌握了分析问题的方法，才能在纷繁复杂的现实世界中，对实际问题抽丝剥茧发现规律，然后应用合适的算法高效地解决它。

知其然容易，知其所以然很难。

• 做题之前先看清楚题目条件，并且要充分利用已知条件
• 写完代码要代入几个边界条件的case 去测试一下
• 有条件一定要画图，帮助自己思考

第一周学习总结

本周主要是对基本数据结构（数组，链表，栈，队列等）以及简单排序搜索算法的复习

学习总结：

1. 链表部分：
   • 首先链表的结构比较简单，高效增删改，但查询效率极低。
   • 算法题目要注意边界问题，要考虑增删改时对头结点和尾结点的特殊处理。或者使用哨兵结点。
   • 指针的指向问题一定要梳理清楚，防止出现野指针或者无限循环的指向。
2. 数组部分：
   • 数组是连续内存空间，查询效率高，增删改效率低。
   • 在复杂的算法中，可用于临时存放查找频率高的数据来降低算法复杂度（空间换时间）
   • 要注意边界问题，不能越界！
3. 栈部分：
   • 栈属于特殊的线性结构，先进后出。
   • 一般用于对顺序有要求的场景
4. 递归部分：
   • 最重要的是一定要画递归树，然后推出递推公式。
   • 找到退出条件。
   • 在考虑递归时不要层层展开，抽象考虑。自顶向下或者自底向上分析
   • 可以考虑用循环代替
5. 排序部分：
   • 基础排序算法**，快排的**，归并的**，以及桶排序的**。**很重要，可以应用到别的算法上
6. 动态规划：
   • 问题可以分解为子问题，优先考虑动态规划。
   • 优先分析题目，找到子问题的分解方式
   • 如果有重复计算，可以通过HashMap或者其他数据结构记录，降低时间成本

作业总结：

作业任务基础部分压力不大，在递归，动规上需要加大练习量。

1. 链表、数组、栈部分问题不大。从递归往后开始很吃力，需要加大练习，多分析。
2. 687，698虽然有想法但是依旧没有解出来。后续参考别人的算法分析调整
3. 174采用动态规划，递归解决子问题。有解，但是超时，需要优化时间复杂度。

第一周最重要的学习是两天的下线大课。两天的课程紧张有序，这两天最大的感慨就是，原来我对数据结构和算法竟如此一无所知？
就连自己曾经用过递归，也是用的那么不堪，小样本还能通过，数据一多就直接堆栈溢出了。学完两天的线下课我才知道，原来数据结构和算法是这么的基础，这么的简单，但我对他们又这么陌生。
老师把数据结构和算法比作砖头石子，这些简单的材料通过设计师灵活的运用可以堆砌出形形色色的建筑。在我看来，数据机构和算法是**，是我们处理数据的根本法则和手段。或许我们工作中遇到的问题比这个问题要复杂100倍，但是只要按照这样的**将问题拆分，最终都能在数据结构和算法中找到方案和思路（曾经解决过一个工作中的问题，上完课才知道叫深度优先算法）
另外一个最大的感触就是自己太眼高手低了。很多概念和**都很简单，以为自己知道方法就能熟练的运用，现在才明白，光知道概念没有用，能实际动手操作，才算真正理解了，才能知道具体会遇到的问题有哪些。

针对自己做的删除有序链表中重复节点做个升华。

删除无序链表中重复节点

哈希表：时间复杂度：O(N)，空间复杂度：O(N)
选择排序：时间复杂度：O(N^2)，空间复杂度：O(1)

1. 学号：033 Username：FollowMyHeart
2. 第一周作业链接：
3. 学习感言：83

学习过程中，你遇到哪些问题，都可以在此条 issue 下提问，我们的助教或者其他学员看到你的问题后会帮你解答。

提问之前，建议先了解下 如何进行有效的提问？

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

正文部分，字数不限。

写完之后请将本 issue 的链接和代码作业链接一并提交至第一周作业征集的 issue 内。

本周投入算法学习的时间有限，碎片时间重读了几篇专栏之外，总共完成了5道较简单的题目。因为周六又有满满的安排，无法进行算法学习，所以在今晚pull作业以及编写总结，希望下周开始可以投入更多时间，完成所有列出的算法题。

上一次刷leetcode已经是好多年前，最近拾起来还有些新手的新鲜感。
本周的收获：

审题非常重要，除了准确理解题目逻辑之外，对题目的范围、潜在边界值都应当格外留意，虽然题目实现不难，但是一次性通过概率并不高，遇到了多次 integer overflow之类的问题。
重点关注思路和方法，不要沉迷于题目本身。做题很多时候是挺有乐趣的，但是此处的乐趣并不一定于效率成正比，有的时候反而会被带入狭隘的想法中。未来希望能够思维更加清晰全面，积攒通用的经验，熟悉经典套路。
练习要与学习原理相结合，做完一类题目要随时做好总结归纳，将算法的精髓提炼出来。
提交代码之后主动记下 时间和空间 排位，为以后优化提供方向，查找不足。

编算法题的**：
不要妄图编写一步到位的算法
按照正常逻辑 一步一步实现
最后 在进行优化

所谓递归，就是自己调用自己。函数入参是肯定要变化的，不然就是死循环了。
而参数的变化，一般是向已知值靠拢，也就是说，知道了已知值，就知道了任意值。（这个过程中，有时候难免会出现重复计算，而我理解，动态规划就是用来解决重复子问题的算法**。）
最难理解的点，在于第一次递归的时候，人脑很难搞的定递归栈，或者说是递归细节。
这里我觉得有两种解决方式。
1 从起点（边界已知条件）开始扣递归的细节
2 总之递归是要返回一个结果的，只不过不能立即得到而已，不去想细节，就把它当做子问题的结果直接使用
第一种方式比较难，但是心里有底。第二种方式，算是解题套路了，是不求甚解的做事方式。
多练多思，没啥好办法。

突然发现自己把一些算法忘记了，所以报名了算法培训班，想要减起以前学过的基础算法，希望提高自己的编程能力。因为最近时间比较忙，所以只能在晚上比较晚下班回才来看看LeetCode算法方面练习。准备先从简单的算法开始刷起，尽量培养自己的逻辑思维能力，努力学会去正确的思考问题。希望自己多努力刷下算法题，逐渐提高编程能力和解决问题的能力。

                                                 关于数组的一些新的理解

数组是数据结构中最常见也最基础的一种数据结构，在所有编程语言中都有数组的实现。 作为一种随机访问的数据结构，对于初学者来说非常困惑的一点是数组是从下标0开始计数的，这似乎非常的反常规思维。从语言学的历史来讲，这种设计方式始于C语言，之后为了兼容历史，各种语言都选择了和C语言相通的设计方式。那么C语言的设计者为什么要这么做呢。
我们知道，在C语言诞生的年代，硬件的局限性非常大，为了有效的利用那有效的CPU, 内存，IO，语言设计者们往往绞尽脑汁。那么假设我们让数组从1开始计数，那么数组寻址公式是这样的：
K address = base address + (k – 1) * typesize
那么如果从0开始计数呢，寻址公式是这样的：
K address = base address + k * typesize
这样就节约了一次CPU操作， 那么大量的计算累积下来，在有限的硬件背景下，带来的性能提升是非常可观的。 这大概就是数组从0开始计数的原因吧。

测试啊测试啊

还不错 ，物有所值。

学习笔记

本周投身项目,时间不是很充足,只做了两道简单的算法题,周日如果没事,会补做第一周的其他作业
做了两道题:83(合并有序链表)和21(删除有序链表中的重复元素)
心得:

• ListNode *p 只是指针,如果引用未初始化的p, 比如p->next 就会发生访问访问野指针,编译器报segment fault
• 构造测试数据可以通过命令行传参: int main(int argc, char *argv[])

对于传统算法，自己算是新人，自己之前只接触实践过机器学习方面的算法，所以对于现在学习的算法，算是还在探索中。
在老师讲课的过程中，以及自己实践的过程中发现，双指针（python中类似的双变量）在算法解体过程中是非常有用的。

这周最大的收获从线下课开始。报名培训时候正在找工作的我，其实此时已经换了新单位。面试时遇到过的题目耗子哥和王老师已经都讲了，早前开始这个课说不定我都进大厂了。。。二分查找是面试题之一，也是看似简单却很容易出bug的题。边界条件是重点难点。递归是算法的入门，数组、链表是重要的数据结构，此外LRU也是在数据量大时高效索引的数据结构。代码实现包括两个阶段，一是功能二是优化。任何工作的思路都是这样。换工作这件事像耗子哥说的，要把自己扔到一个没有退路的地方去，逼自己一把。只有这样才能发挥出最大的学习能力和潜力吧，祝正在找工作的小伙伴们成功去理想的公司啦。

学号：097 Username: alxjerr (侯玉麟)
第一周作业链接：https://github.com/alxjerr/algorithm/tree/master/Week_01/id_97
学习感言：https://github.com/algorithm001/algorithm/issues/122#issue-435360761

快慢指针的理解.pdf

1. 程序的基础语法长时间不用已经退化，需要更加深入的练习。
2. 程序中有一些已经实现好的类库（自带非第三方）在算法练习中是否可以使用(特别是工作较忙有好多其他事情需要做)？
3. 如果可以的话还是希望能从工作中找实例去完成作业。

总结：

本周完成11道习题, Link: https://github.com/speng975/LeetCode/tree/master/cpp

排序完成3道题：
leetcode 242: https://leetcode-cn.com/problems/valid-anagram/
题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
解法：通过开辟两个26字节大小的数组，分别存'a'--'z'对应字符的个数，最后比较数组存放字符及其个数，完全相等则返回TRUE。
leetcode 324：https://leetcode-cn.com/problems/wiggle-sort-ii/
题目：给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
解法: 申请一个和nums一样的临时数组tmp,对数组tmp进行排序，找到中间位置，遍历数组nums，奇数位填入中间数，偶数位填入末尾数，指针向左移动。
leetcode 164：https://leetcode-cn.com/problems/maximum-gap/
题目：给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。
解法：对数组进行排序，申请一个临时变量存当前遍历到的最大值，比较数组相邻元素，计算差值，决策是否更新最大值。

二分查找完成1题：
leetcode 441: https://leetcode-cn.com/problems/arranging-coins/
题目: 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
解法: 循环n-=k, k++, 最后计算出来就是总行数。

栈完成1题：
leetcode 20: https://leetcode-cn.com/problems/valid-parentheses/
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
解法：

1. “左” 压栈
2. “右” 在栈顶查找匹配的括号, 如果找到弹出栈顶字符，否则返回false
3. 最终"栈" 为空, 返回true, "栈" 非空, 返回false
   注意，对于第一次输入是')','}'或者']'的情况，一定要判断堆栈是否为空，否则会数组越界。

数组完成4道题：
leetcode 905: https://leetcode-cn.com/problems/sort-array-by-parity/
题目: 给定一个非负整数数组 A，返回一个由 A 的所有偶数元素组成的数组，后面跟 A 的所有奇数元素。
解法：前后指针。

leetcode 922: https://leetcode-cn.com/problems/sort-array-by-parity-ii/
题目: 给定一个非负整数数组 A，返回一个由 A 的所有偶数元素组成的数组，后面跟 A 的所有奇数元素。
解法：另外申请数组，偶数位存偶数，奇数位存奇数。

leetcode 81: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
题目: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
解法：排序后再二分查找。

leetcode 153: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
题目: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。。
解法：前后指针，注意边界条件。

链表2题：
leetcode 83: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
题目：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
解法：两个指针，循环遍历，相同指针则移动指针跳过。

leetcode 24: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
解法：第一个结点指向第三个结点，第二个结点指向第一个，递归调用。

本周主要是通过专栏以及周末上的课程对基本的数据结构数组 链表，队列，栈以及简单的搜索排序等进行复习
着重复习了时间复杂度和空间复杂度分析
对最好，最坏，平均，均摊时间复杂度进行梳理
以及算法稳定性

学习总结：
链表：
针对删除链表元素时候，不能简单认为其是O（1），而是要看删除方法传入的参数是什么，如果是待删除的节点则我们是需要遍历找到他的前置节点，才能删除这个时候是O(N)

数组部分：
数组是连续内存空间，查询效率高，增删改效率低。
一般数组算法都要遍历数组
如果数组有顺序则一般采用二分
如果没顺序一般用hash
一般外层的循环省不掉，考虑内层遍历优化

栈部分：
栈属于特殊的线性结构，先进后出。
一般用于对顺序有要求的场景
递归部分：
递归一般可以都可以用栈转换
递归的时间复杂度分析方法：递归树，然后推出递推公式。
找到退出条件。
两种递归方式：自顶向下或者自底向上分析

排序部分：
基础排序算法**，快排的**，归并的**，以及桶排序的**。**很重要，可以应用到别的算法上

当海量数据时候散列表会占用很大内存，这个时候不如顺序扫描
原地排序：原地排序不是空间复杂度为O(1)的算法，不一定，知识不需要额外空间，在原数组上进行排序

LeetCode 905. 按奇偶排序数组
思路：
（1）新建一个数组
（2）对原数组进行遍历，如果为奇数则添加到末尾，如果为偶数则添加到前面

之前用过sort,还真没不知道竟然是这样的sort！他会将元素转换为字符串，再根据字符串的第一个字母对应的ASCLL码来排序的。
弄不懂为什么和其他的高阶函数不一样，他直接修改了原数组。

以前看一道算法题，首先做的是打开百度，看思路，然后看大神们的实现代码，自己在模仿一遍。
结果大家也猜到了，过两天就忘。

听了皓哥的课最大的感受就是从实际角度来解决算法的问题。比如有搜索一般就想到哈希表，虽然可能不是最好的解，但较优解总是逃不掉的。再比如查找链表有没有循环，没有经过训练的人能想到快慢指针的几率有多少？如果自己碰到特别的问题，也不会有人来帮你想到这种奇特的解法。

拿出纸和笔，从问题的第一步画起，往往就能归纳到核心的问题，使用朴素的**和解法，随后再来思考和调优。对于我来说，这才是比较好的实践。

感谢皓哥，从白纸开始一步步给我们展示解决的思路，受益良多。

链表：

1. 合并有序链表时，为了代码清晰，尽量使用新的链表
2. 两两交换链表中的节点时，注意抽象和递归实现，尽量使用通用解法，方便在解决后续问题时的复用。
3. 处理环形链表时注意画图，快慢指针检测环的原理，和相遇节点位置的推导，能够分情况画出慢指针进入环时，快指针所处的位置。
4. k个一组翻转链表，本质上也只是翻转链表，只是做了分段而已，分段翻转后在进行链接即可

数组:

1. 数组按奇数偶数排序只要对数组进行分组即可，采用临时数组有点类似归并排序组后的组合
2. 搜索旋转排序数组在数组中首尾有重复元素是情况会变得异常复杂，可以直接去除首尾重复元素在进行处理，找到最大值，分段使用二分查找即可，暂时这样处理，后续思考更优解，没有重复元素时直接使用二分查找找到最大值索引，然后分段进行二分查询即可。

栈：

1. 检查括号得有序性直接利用栈存储左边符号，遇到右边符号就从栈中去除相应字符匹配即可。

还没开始就已经结束了

如果忙,事多,懒惰,困难是自己坚持不下去的理由,那就说明自己对胜利,对成功的渴望不够强烈.
同行的朋友就是一种解决孤独,懒惰的好方法,善始最好善终.
借着这次机会,立下flag: 把常见的数据结构和算法练成99乘法口诀

说点让自己难受的部分吧

本周知识点主要有链表,数组,栈,排序,递归,二分查找, 说起来挺亲切,写起来很懵懂,唯有练习,道理大家都明白,无需赘言;
让自己难受的部分还是在于多种数据结构的联合查询,感觉这就是一门艺术, 洋溢着魅惑,充满着挑战.

本周做题时，脑子里响起最多的声音竟然是“又忘了判断边界条件”。

在工作中很少写递归的代码。一是因为写起来可能不好写，二是因为别人读起来可能也不好读，三是觉得递归的方法会比较占用栈空间。

但是对于刷题来讲，总不写就会手生。把“下面的递归调用的结果作为此次的一个操作对象”的意识找了好久才找回来。

链表一直都是我的弱项，这次特意去练习了几道链表题，从简单到中等，后续还会有复杂的更新。
链表练习最主要的就是缕清next,next.next的关系，画图最为直观。还有就是一些边界值的设置技巧。

21题解题思路：
技巧一：初始化的时候把head节点初始化一个给定的值，这样，后续操作就不用考虑头节点问题，直接排序好了，把最小的赋值给head.next就可以了。
技巧二：两个链表为空和不为空的判断，循环逻辑依赖判断条件

83题：
刚开始没有注意到排序以后的链表，所以走了弯路。

24题：
交换节点的时候next.next的值比较重要，缕清后会豁然开朗

。。。后续还会有更新

总的解题思路：链表和递归真的很搭

https://join.slack.com/t/geek-universitygroup/shared_invite/enQtNTk3ODAxODA5MjUwLTUwNDYxZjUxYjc4YzU1YjNjZWY4ZDA2YjBlOGY5YTNjNjVlYmY4NjE3MmE1MzJmYTM0ZWZlN2RlMDY4YzZjNmQ

本周算法学习总结

本周没有对哪个具体的技术进行深入的思考。所以，以下内容均为对本周学习到的内容进行总结。

链表

链表相关问题的汇总如下：

• 判断链表是否有环

  使用快慢指针 —— 快指针每次走两步，慢指针每次走一步，如果最后两指针相遇，那么表示链表含有环。

• 计算含环链表中环的大小

  找到环中任意一结点后，继续遍历并累加其循环次数，再次回到该结点时候，则计算出环的大小。

• 计算有环链表中入环的结点

  使用两个指针。指针p先走l步（环的大小），指针p再与指针p同速前行。两指针相遇的点就是链表中入环的结点。

• 链表插入和删除相关的技巧

  在链表中删除和添加结点的时候，非常容易出错。为此可以构造一个带头的链表，头结点的next指向要修改的链表的第一个结点。

递归

递归相关问题汇总如下：

• 使用递归求解‌划分 k 个相等子集的问题

  依次尝试将数组中的元素放入到 k 个子集当中。

测试用例

当编写测试用例发愁的时候，可以朝着这三个方面来编写：

1. 功能测试

2. 边界条件测试

3. 特殊输入测试

解题过程的分解与优化

面对一个复杂的问题，有效的办法就是将其进行分解成子任务。所以，将过去的编码和测试改成了以下的过程：

1. 明确问题
2. 输出相关的边界条件
3. 绘制相关的图表
4. 为测试用例编写辅助的函数
5. 编写测试用例
6. 方案汇总（时间复杂度和空间复杂度）
7. 确定执行方案
8. 伪代码设计
9. 编写代码
10. 执行测试用例
11. 重构优化
12. 提交代码
13. 相关总结（知识点 & 技巧）

收获：
1，从事测试工作，接触算法很少。通过这段时间对算法的学习，对数据结构（数组，链表，二叉树，哈希表，跳表。。。），时间复杂度，空间复杂度和一些简单的算法有了大致了解。
2，平时测试时，会去思考代码的时间复杂度和空间复杂度是否有优化的空间（虽然还很菜，但是这种思维培养起来了）
3，很喜欢两位老师对算法性能优化那块的讲解，原来算法还能这样玩，有种提壶灌顶的感觉。
4，逻辑思维能力感觉提升了一点
困难：
1，平时写代码时间较少，上手写代码还是感觉比较困难，比如链表，删除一个节点，一开始简单的以为head=head.next.next就好了，但其实我把head之前的节点全去掉了。应该是head.next=nead.next.next.
2，时间管理比较差，以为有时间多练习几个题，但最终结果是只完成了2道。时间管理能力需要提升。

04.19

基础

数组

• 内存中连续的存储空间
• 适合指定下标获取元素
• 中间插入、删除后，移动后续的元素，都需要较高的时间成本
• 固定大小，需要扩容时，需要一块新的内存空间，而且需要复制元素的时间成本
• 无序数组，
• 有序数组，要使用二分查找，都必须是有序的数组，如果是不变化的数组，要多次查找，一般采用1次排序，多次查询
• 典型场景

固定范围(可以通过O(1)映射到具体的数组下标)，比如只有小写字母的一个字符串，每个a-z的字符k，可以通过k-a直接映射到数组下标，再通过下标直接获取元素

链表

• 每个节点，独立存在内存中(可以不连续)，通过指针/引用建立节点之间的关系
• 插入、删除节点容易
  • 如果指定一个节点value去删除一个元素，首先得通过遍历，查找到这个节点
  • 如果指定一个节点的前序指针/应用，那么删除就不需要遍历查找(单链表，双链表都可以)，
  • 如果指定一个节点的指针/引用 ，单链表还是需要遍历找到该节点的前序节点，才能删除；这种情况双向链表就不再需要遍历查询的步骤

栈

特殊的后进先出，常用的场景对栈的操作也比较简单，入栈push，出栈pop，查看栈顶元素peek，使用场景也比较特殊，比如常见的：表达式的合法性检查、浏览器的前进后退；基本也不会对栈进行排序、查找等操作。可以进一步自己使用数组、链表自己实现一个栈。(后面根据Leetcode的题练习一下其他的使用场景)

递归
有2点真的很重要

• 终止条件
• 思维上一定要"信任"下一层的递归结果，不用把自己带入下一层的逻辑中

排序

以前学习排序，老是去记各种排序算法的具体实现，没有总结特殊、使用背景，一段时间就忘记。这次根据老师分析的时间复杂度、是否是稳定性排序、是否是原地排序；为什么要用稳定排序，像订单排序中，先用订单号(不重复)排序，再用金额(重复)排序，后面的用金额排序就需要用稳定排序。归并、快排都是利用分治**，快排不稳定，归并不是原地排序，都需要根据场景来决定排序，不死记硬背。

二分查找

基本都是使用在排序好的数组上？

• 有序的才有意义，否则不好比较
• 数组能快速容易的用下标折半定位

进阶

• 更多的场景是有相同的元素，注意边界条件
• 大于某个数的第一个元素的查找等

学习态度

追求掌握，训练思维，有没学会自己最清楚;一定要动手实现

链表题的思考

通过自己做的几道链表题，我觉得解决链表题首先应该要画图，画图的目的是为了搞清楚链表指针的变化，
不管是用递归的方式还是循环的方式，一张图都能够清晰的理清思路。

比如要交换两个节点，可以画一张如下的图：

然后通过作图分析链表指针应该以何种顺序去变化，最终能让节点达到某个状态，就像图中标注的1，2，3的步骤，这样就能很容易写出部分代码，找到解题思路

边界条件

另外我觉得链表题的边界条件很重要，尤其是头尾节点的指针变化，非空判断，以及循环/递归的结束条件，如果没有解决所有的边界条件问题，那么代码的运行结果往往不符合预期。

关于排序

通过这周学习常见排序算法，觉得之前陈皓老师讲的内外层循环的思路非常好，排序问题的外层循环基本都不能省略，但是内层循环却是可以进行优化的，另外对分治算法和递归的编程方式的理解也对解题有很大帮助。

1.算法的知识点有很多，要掌握他们，最好的办法是各个击破，也就是说针对每个知识点，每次做大量的题，总结和体会；最怕的是，每个知识点浅尝辄止，初学的时候，每天都做跨多个知识点的题目；
2.算法的难易，考验的是对这个知识点的掌握程度，体会理解越深越简单，本次做了一个树的题目，题目难易度是“简单”，可我却觉得异常困难，原因其实是，树的题目，我基本没练习过，基础不牢导致；
3.以上是本周做题总结出来的，现在打算每周单独练习各个知识点，知道掌握和熟悉；

本周重点学习知识点

跳表、散列表、哈希算法、二叉树、红黑树

要求

1. 每周至少完成给定题目中的两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章（字数不限）

注意事项

1. 下面列出的题目中，按照知识点进行了简单分类，但并不意味着使用相应的数据结构或算法一定是解决该题目的最优解，这样分类只是为了方便大家有针对性的练习；
2. 有的题目可能需要结合多个算法或数据结构进行求解。

第二周题目

哈希表

简单：https://leetcode-cn.com/problems/valid-anagram/
中等：https://leetcode-cn.com/problems/top-k-frequent-words
中等：https://leetcode-cn.com/problems/find-duplicate-file-in-system/
困难：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
困难：https://leetcode-cn.com/problems/number-of-atoms/

二叉树

简单：https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
中等：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
中等：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree/
困难：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
困难：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

二叉搜索树

简单：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
中等：https://leetcode-cn.com/problems/range-sum-of-bst/
中等：https://leetcode-cn.com/problems/contains-duplicate-iii/
困难：https://leetcode-cn.com/problems/count-of-range-sum/
困难：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

作业提交规则

1. 在提交作业之前，请先阅读这里的 README 文档：https://github.com/algorithm001/algorithm/blob/master/README.md
2. 然后在此 Issues 下按照如下格式回复:

1. 学号 + GitHub Username
2. 作业代码的 GitHub 链接（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request）
3. 发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week2】+文章标题”，格式参考：#9

要求

1. 每周至少完成给定题目中的两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章（字数不限）

注意事项

1. 下面列出的题目中，按照知识点进行了简单分类，但并不意味着使用相应的数据结构或算法一定是解决该题目的最优解，这样分类只是为了方便大家有针对性的练习；
2. 有的题目可能需要结合多个算法或数据结构进行求解。

第一周题目

链表

简单：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
简单：https://leetcode-cn.com/problems/merge-two-sorted-lists
中等：https://leetcode-cn.com/problems/swap-nodes-in-pairs/
中等：https://leetcode-cn.com/problems/linked-list-cycle-ii
困难：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

数组

简单：https://leetcode-cn.com/problems/sort-array-by-parity/
简单：https://leetcode-cn.com/problems/sort-array-by-parity-ii/
中等：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
中等：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
困难：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

栈

简单：https://leetcode-cn.com/problems/valid-parentheses/
中等：https://leetcode-cn.com/problems/next-greater-element-ii/
困难：https://leetcode-cn.com/problems/maximum-frequency-stack/

递归

简单：https://leetcode-cn.com/problems/longest-univalue-path/
中等：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/
困难：https://leetcode-cn.com/problems/special-binary-string/

排序

简单：https://leetcode-cn.com/problems/valid-anagram/
中等：https://leetcode-cn.com/problems/wiggle-sort-ii/
困难：https://leetcode-cn.com/problems/maximum-gap/

二分查找

简单：https://leetcode-cn.com/problems/arranging-coins/
中等：https://leetcode-cn.com/problems/powx-n/
困难：https://leetcode-cn.com/problems/dungeon-game/

作业提交规则

1. 在提交作业之前，请先阅读这里的 README 文档：https://github.com/algorithm001/algorithm/blob/master/README.md
2. 然后在此 Issues 下按照如下格式回复（示例见一楼）:

1. 学号 + GitHub Username
2. 作业代码的 GitHub 链接（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request）
3. 发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week1】+文章标题”，格式参考：#9

本周投入算法学习的时间有限，碎片时间重读了几篇专栏之外，总共完成了5道较简单的题目。因为周六又有满满的安排，无法进行算法学习，所以在今晚pull作业以及编写总结，希望下周开始可以投入更多时间，完成所有列出的算法题。

上一次刷leetcode已经是好多年前，最近拾起来还有些新手的新鲜感。
本周的收获：

1. 审题非常重要，除了准确理解题目逻辑之外，对题目的范围、潜在边界值都应当格外留意，虽然题目实现不难，但是一次性通过概率并不高，遇到了多次 integer overflow之类的问题。
2. 重点关注思路和方法，不要沉迷于题目本身。做题很多时候是挺有乐趣的，但是此处的乐趣并不一定于效率成正比，有的时候反而会被带入狭隘的想法中。未来希望能够思维更加清晰全面，积攒通用的经验，熟悉经典套路。
3. 练习要与学习原理相结合，做完一类题目要随时做好总结归纳，将算法的精髓提炼出来。
4. 提交代码之后主动记下 时间和空间 排位，为以后优化提供方向，查找不足。

1.写完的代码细节会忘
2.理顺的思路回过来再想一遍也会欠缺的地方
3.上两条的原因是，算法代码写的不够多，解题思路缺少总结
4.要多做题，多按照自己的想法先实现代码，然后再去看别人的思路，别人的代码，比较差异，取好的思路，好的代码实现。

用九个字总结一下：
要见多识广，知行合一！

算法训练营总结

算法之外

1. 学习是反人性的，可以通过刻意练习来解决难的知识点。
2. 数据结构中数组 不等于 编程语言中的数组。一些其他的结构，在不通的语言中也不完全一样；但一般具有一定的相似性。
3. 尾递归优化不是解决 递归异常（stackoverflow）的万金油。原因一：需要语言支持；原因二：不是所有递归都能专成尾递归。
4. 数学主要学的是方法，结果无法穷举，唯有掌握方法。掌握方法可以通过反复的训练来解决。（所以需要做大量的数学题）。
5. 解决问题的思路：

• 需求分享（读题）
• 找解决思路（确定相应的数据结构和算法，先找对数据结构）
• 如果思路不明确，可以求助。求助的时候需要说出自己的思路和做过哪些努力。
• 写代码。（写代码前可以将思路转成图）

经典问题的套路

1. 大量数据（无法完全加载到 内存），可以分治，类似map reduce。
2. 链表问题一般思路比较简单，主要很多边界问题。需要通过多编码解决。
3. 数组相关问题，一般解决性能优化。O(n^2)-->O(n*logn)，第一层遍历无法避免，第二层是否可优化成 logn;有序数组查找一般采用二分法。
4. 字符串处理，一般都需要遍历，有限的字符集查询，使用hash；公共前缀的用 trie 树。
5. 二叉树一般用递归实现。
6. 部分问题，需要使用多种数据结构或算法。LRU cache，hash table+ 链表。

相关知识点

1. 排序的稳定性：相同的数据，在排序前后，前后顺序不变。
2. 排序的愿地性：假设 n 个数排序，不另外需要一个n 相关的存储空间。
3. 常规图可以矩阵存储；在内存中，稀疏图可用邻接表或逆邻接表存储（比喻 好友关系）。持久化数据，可用图数据库或者常规关系数据库。
4. 动态规划的解法核心：找到最优字结构，推导出状态转移方程。
5. 动态规划优势，减少重复字问题的重复计算。
6. 数据库索引 B+ tree；
7. redis set 实现 使用跳表。链表建多级索引。空间复杂度索引翻倍；时间复杂度，logn。
8. 映射陷阱，易忽略双向映射。
9. 递归=递推公式+退出条件。

242.有效字母异位词
首先需要确定题目的描述有效字母异位词的含义
刚开始结合例子的理解是字母按顺序交换，1和2换位，3和4换位，依次类推
在这个思路下想的是首先我遍历原串按照次序存储字母，遍历目标串依次交换对比刚才的存储顺序。
后来看评论才理解，易位词指的是相同数量和种类的字母的不同排列，次序不一定是1和2互换，3和4互换，相对来说更简单了，所以我们理解题目
含义很重要，需要先理解题目在去做题。
下面是思路：
1.首先遍历原串s, 把字母存到哈希表source_hash里面，key是字母，value是出现次数
2.遍历目标串t,依次查寻目标串的字母是否出现在source_hash中，如果没出现直接返回false，如果找到了，将其对应的值将其减一，清楚哈希表中值为空的数据
3.遍历完成之后，检查source_hash是否为空，为空说明字符种类和数量一致返回true,不为空返回false。
优化
将哈希表转化为数组，字母的ascll码做下标，出现字数作为数组元素，进一步优化。

83. 删除排序链表中的重复元素
    该问题比较简单，因为链表已经排序，只需要顺序检查next节点的值是否等于当前节点的值，如果相等，删除next节点，移动指针到next节点的next节点，需要注意的问题是注意链表的边界条件，头结点和尾节点的问题。
    看到一个好的方法是使用递归的方案去解决删除重复节点的思路。

84. 最长同值路径
    该问题想到用递归去求解，但是实际递归代码实现有问题，还需要进一步优化。

讨论两个知识点。

• 均摊时间复杂度的一个应用

讨论一下golang 中变长数组(切片的实现)。
初始化一定容量 cap (实际空间) 的数组，里边实际的数据长度为len。 当 len 达到 cap 时，会扩展成为2 * cap 的空间, 会形成一个 cap 规模的数据迁移。 也是均摊时间复杂度的一个应用。
一个x 的搬移，会紧跟 x 个复杂度为1 的插入。 所以 均摊时间复杂度为 O(2n) 。

• 一个链式栈的实现:

考虑到栈结构的特殊性，先插入先出。
一般的单链表插入数据，是往尾节点插入数据。出栈操作为移除尾节点，将数据指针前移，因为，为单链表，则需要从头到尾遍历 一遍才可以找到头指针。
或者把单链表改成多链表。但是，改成双链表，又会增加一些操作复杂度。

所以考虑从头部插入数据的方法来实现操作，每次插入数据，生成一个新的节点作为链表的头结点。 头结点的next 指针指向原来的头结点。

第一周学习总结思考

总结：

• 本周主要回顾了数组、链表、栈、队列、递归、排序及二分查找的一些内容，思考了几道算法题并用不同语言实现了一下

• 在时间空间复杂度上面，在参考了LeetCode的Discuss后分析一道题的四五种解法的时间空间复杂度，参考给出的时间和占用内存进行思考

思考：

1. 要注意边界条件，尤其是链表要思考null或者一个结点的情况

2. 注意终止条件和中止条件，这个细节问题很容易偏差一位导致出问题

3. 递归的一部分要再思考一下，关注递推公式，注意边界和终止条件

4. 排序这一块参考了可视化的动态图解，比较容易理解（https://visualgo.net/en）

5. 思考时间复杂度空间复杂度，多注意时间换取空间和空间换取时间的**在代码中的体现

现在想自己犯了一个最大的“错误”，就是在学习上犯了“完美主义”的毛病。至于现在碰到的许多问题，都是和这个相关的。

一开始想要学习数据结构和算法时，发现网上的博客大多使用C/C++实现的。因为自己是学java的，很多C++语法看不懂，于是花费了大把的时间精力，去学习C/C++语言。学习C++的struct结构，奇怪的导包方式，以及让人头大的一级二级指针还有啥野指针。最终初心也变了，由最初的学习算法，变成了C++从入门到放弃。悔不该当初啊！

其实现在看来，数据结构与算法是语言无关性的。当初能够想到看其他语言实现的算法，然后再用自己熟悉的java语言去实现一遍，那自己对数据结构的理解以及成长是相当有帮助的。

我想，很多同学跟我一样，在学习的路上，被自己的“完美主义”逼得“放弃了”——由于学习中有一点没有做好，遭受了一点点挫折，最终放弃了整个学习计划。

其实，我们每个人应该接受自己的不完美，想开一点：我们都不是小学都考了满分才上初中，也不是中考了满分才上的高中，更不是高考考了满分才可以读大学。不完美是常态，根本不会影响我们学习更深入的内容。

一起加油！

最近，阅读了两位老师的专栏部分文章，参加了线下大课，谈一点小小的感悟：算法学习是一种刻意训练，要花时间去突破，更要去掌握学习的方法，本周我只是做了两道简单的数组题，后面我会平衡好工作和刻意练习算法的时间，去做更多的训练，期望自己能像陈皓老师一样，把算法训练作为一种习惯去保持下去，不断的提升逻辑思维能力，在实际工作中解决更复杂的问题。

这两道数组题比较简单，但是结合老师的授课内容，还是有几点感触：
1.首先要选对数据结构，当然这里就是数组
2.其次，根据选定的数据结构去构思，这两道题就是用了快慢指针、头尾指针的思路去解
3.最后就是编程，先实现，再去不断的优化，吸取优秀的建议去重构

我之前并不知道leetcode，很庆幸参加培训，我会坚持刻意训练，不断提升自己的算法能力。

死磕动态规划1

• 动态规划是一种结合了数学优化及编程技术方法的解题方法。这种数学优化广泛用于管理科学（management science）当中。

• 满足以下两个特性的问题适用于动态规划

  • 最优子结构（optimal structure）：局部最优解能决定全局最优解，如何找出最优子结构是解题关键。
  • 重叠子问题（overlapping subproblems）：构造全局最优解的过程中，可复用的子问题的最优解。

• 编程技术

  • 递归+记忆结果法（top-down）：相对直观，但需要对递归有深刻的了解
  • 递推法（bottom-up）：需要事先弄明白递推方程

• 例题：

切绳子（来自算法导论）
给一段长度为n的绳子，可以切成1到n-1份，也可以不切就是n，求最大收益。

收益表：

按上表，假设绳子长度为4，则有以下切分方法：

• 4 = 1+1+1+1，收益为4
• 4 = 1+1+2，收益为7
• 4 = 2+2，收益为10（最优）
• 4 = 1+3，收益为9
• 4 = 4，收益为9

// 暴力法, bf = brute force
int a[10] = {0, 1, 5 ,8 ,9, 10, 17, 17, 20, 24, 30};
void bf(r)
{
    if (r == 0) return 0;
    int max = 0;
    for(int i = 1; i < r-1; i++)
    {
        current = a[i] + bf(r - i);
        max = max > current ? max : current;
    }
    return max;
}

暴力法需要遍历所有可能的组合，假设n=3它的调用树是：

根据上图观察，可知暴力法的时间复杂度是：O(2^n)

// 暴力+记忆法, bf = brute force
int a[10] = {0, 1, 5 ,8 ,9, 10, 17, 17, 20, 24, 30};
int c[10] = {0};
void bf(r)
{
    if (r == 0) return 0;
    if (c[r] != 0) return c[r];
    int max = 0;
    for(int i = 1; i < r-1; i++)
    {
        current = a[i] + bf(r - i);
        max = max > current ? max : current;
    }
    c[r] = max;
    return max;
}

这样做的话，重复问题解都记录在数组c里，当函数进入的时候就可发现并返回。

一. 第一周学习总结

1. 关于链表题目的做题总结

做了作业中两道关于链表的题目，结合以前做的链表题目，发现自己用的方法基本有三种：

• 遍历：链表和数组一样，基本的遍历是逃不了的，重点是怎么提高遍历效率的问题。
• 反转：反转也是常用的方式，关于反转最主要的是记录三个节点：当前节点，当前节点的 prev 节点和 next 节点。整个反转过程就是这三个节点的不断变化。然后在反转的过程中可能需要做一些特殊的处理，比如本周的 LeetCode 24、25两道题目，都是要在反转的时候要讲前一组的尾节点的 next 指向本次反转后的头节点。
• 快慢指针：包括查看链表是否有环，获取链表的中间节点等题目都可以用快慢指针的方式进行，当快指针到达末尾时，满指针刚好到达链表的中间，有环的话两者最终有机会相遇。

2. pow(x, n) 解题思路与递归简记

最先想到的就是循环相乘了，先暴力搞出来再说，代码如下

public class Solution {
    double myPow(double x, int n) {
        int result = 1;
        for (int i = 1; i <= n; i ++) {
            result *= x;
        }
        return result;
    }
}

这种解法时间复杂度为 O(N)，实际提交可能会超时，因此需要改进。这里用到数学知识：

a^m * a^n = a^(m+n)

因此以 2 的 10 次方为例：

2^10 = 2^5 * 2^5
2^5 = 2^2 * 2^2 * 2
2^2 = 2^1 * 2^1
2^1 = 2^0 * 2

因此每一个指数幂的计算都可以进行折半计算，这样就可以通过递归的形式进行计算。

递归公式为：

n 为偶数： x^n = x^(n/2) * x^(n/2)
n 为奇数： x^n = x^(n/2) * x^(n/2) * x

终止条件为：

n = 0, x^0 = 1

实现代码如下：

public class Solution {
    double myPow(double x, int n) { 
        
        double result = this.pow(x, Math.abs(n));
        
        if (n < 0) {
            return -n;
        }
        return n;
    }

    private double pow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double half = pow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}

最终返回结果要考虑 n 为负数的情况，因此先取绝对值进行计算，如果为负数则返回计算结果的倒数。整个算法的复杂度由 O(N) 变为了 O(logN)。

关于递归最重要的还是要找到递归公式，如王争老师在专栏中提到的三步：

• 分解出子问题，子问题的解题思路通用：这里的 a^m * a^n = a^(m+n) 就是典型的案例。
• 递归过程的计算：每次计算的结果是子问题的结果汇总，这里就是指数为奇数和偶数时的不同的计算公式。
• 终止条件：这里的终止条件就是幂为 0 的时候。

道路阻且长，行则降至

[leetcode83]对链表以前仅限于书本的认识，结果第一题就是链表题，花了1小时时间网上找了个简单的链表实现，然后才做了出来

[leetcode905]数组用到了皓叔提到的双指针思路，确实很有意思，无论是空间复杂度还是时间复杂度都有了明显的提升

PS： 这周杂事比较多（换工作笔记本，搭环境， 译稿feedback etc.），总以为有空会做题，结果拖到最后一天也没做。明天家里有一堆事，只能晚上匆匆忙忙做了。week2争取不拖延了。。。