LeetCode 剑指

无所事事过了整个寒假，应该战斗起来了。暑假还没着落，从实习开始吧。争取20天刷完

数组中重复的数字

不小心看到了提示，知道要用hash表就觉得思路非常清晰了。重要的是没有提示的情况下要自己想出来。对这种确定范围的查重问题，往往可以考虑一下哈希表。

运行出来复杂度似乎不太理想，再思考一下有没有优化方案。

看评论区的意思，这题在限制时间/空间复杂度的前提下就会比较困难，思路有很多种。与此同时对hash表的写法好像也可以更加简洁。运用in / not in做判断，就不需要一个个加了。这样对大序列次数可能会少。

换成了”原地交换“的算法，时间显著减少，但是内存消耗却还是差不多。有点没想明白，不过这个方式比较精妙，值得复习。看到题解里萝卜坑的解释，写的很好，一下就懂了。

替换空格

这题乍一看思路就很清楚，直接逐个往后面加就行了。意外的是写出来效率没有特别的差。

讨论区学到了一个新的库函数return s.replace(" ","%20")，比自己写的效率差，算增长知识了

从头到尾打印链表

感觉自己的思路有点邪门，结果忘了处理空链表的情况。想来想去咋处理不了了，懵了。看了下评论，原来if head就行了啊，淦。

歪门邪道写出来结果好像还行，不算特别捞。看了下别人的发现自己是个憨憨，完全可以正着存进数组，最后反着输出就行了！服了(这样并没有让代码变快) 辅助栈法

惊了，看到评论区竟然还有递归的！开拓思路了，这样的确可以，因为做的是一个反序，恰恰也是递归擅长解决的事情。(然而慢得离谱)

左旋转字符串

先用常规方法求解，前n个另存，然后删掉再加在末尾。两次遍历同理

考虑到列表的种种特性，复习了一下截取，切片等操作，重写，略有提升。

注意，字符串也可做切片操作。但是由于Python中字符串是不可变对象，没法原地翻转

如果用C++可以实现空间复杂度O(1)

用两个栈实现队列

这题有点看不懂，反复琢磨。看了评论区才明白。不过好像还是不太会做。拖延太久了，直接看题解。写的还是很清楚，思想就是两个栈实现两类操作，一个是入队，一个是出队。搞清楚题目的意思其实就觉得这题比较简单了。不过也是在先入为主看答案的前提下，还要再复习。这题算是水过去了。

二叉树的镜像

观察题目，想到等比数列。或许可以把整个列表分log2(n+1)次局部翻转后相加.发现求对数指数都要引入math库，可能要再想办法。

节点为0时需不需要特殊考虑？

简单写了一下，发现好像不能把二叉树当作列表考虑，没法求长度？

换个思路，从最尾端开始换。观察到第n和(n+1)/2对称。问题仍然是总长度呀。有点没辙。

递归？琢磨了半天有思路了，但是感觉太复杂，也不是很会写递归，决定放弃。

看了看别人的题解，递归确实可以，不过从上往下递归是更顺思路合情理的做法，我有点胡思乱想。在C++的解法里也可以看到迭代做的，用栈或者队列。

感觉自己对递归的理解还不是很深，或者说对二叉树的认识有点问题。精妙的地方在于从上往下，子节点经过多次交换之后的确到了自己对应的位置，而我没有考虑出这一点。

注意细节，需要用temp暂存，python平行赋值则避免此问题。

读了下栈的代码，感觉和从上而下的递归逻辑好像基本是一样的

这题还需要过段时间再复习。

打印从1到最大的n位数

先按常规思路写了一个。首先根据n得到最大位数，然后循环输出。时间和空间复杂度似乎太高了

读了下讨论，有一些点。对python3来说，range的返回值可以当作list用(严格说不是list的class，现在已经不能通过了)，然后运算符**就是求乘方(指数运算，幂运算之类的，anyway)，不用一次次乘！当然，正经来说第二个循环append还是有意义的。

看起来在剑指的原题里这题是涉及到了大数？似乎很难，后面可以找原题学习一下

看了下题解，因为用字符串拼接表示数，也是一个递归问题，逐位遍历过去然后拼起来。还需要额外注意首位0的问题。似懂非懂，还需复习。

斐波拉契数列

这题和下一题其实是一模一样的，

青蛙跳台阶问题

经典的递归题目。因为对递归不熟悉还是摸索了半天写出来。数字变大的时候超出时间限制，可能算法设计的有问题？

看了下评论区，的确就是个斐波拉契，用迭代要比递归效率更高。此题涉及动态规划，是陌生的知识点，趁机学习一下。求余时，使用循环求余法，可以避免大数越界(python不担心)

最后的代码相当简洁！警惕，递归虽然思路简单，效率太低，迭代则巧妙灵活，要多思考！

NOTE 2.26：明天回学校，可能要少做。后面拉起来。

旋转数组的最小数字

这题最简单的思路就是直接遍历，写出来结果中上。我想间隔遍历可能更快一些，不过复杂度好像没有本质区别。二分法呢？好像实现不了？看评论的确还是有二分法的，思路没错，没能自己实现，主要是对二分法有些遗忘了。搞笑今天还和焕聊到了。(奇怪的是用二分法运行时间变慢了hhh)注意在相等的情况下，缩小区间来重新判断，这个地方需要想清楚为什么可行。值得复习！

冷知识，python有min函数。