LeetCode-easy-1
将想法付诸实践往往是最困难的，也是最重要的
于是我决定从今天起每周完成10道题，龟兔不限，思考和实践最重要。
像往常一样拉胯，一周我只看了三题半:/
以此记录刷题的思考和经验，复习数据结构，学习python和算法。
第一周，学习为主，龟式。
Python知识点
class(类)
之前做dl的时候就对这个理解的不够深刻，重新补习：
对象是类的实例。
self是必填的形参，内容则被封装到对应的对象中。调用封装时可以通过对象或者self
dictionary(字典)
定义字典： a = {}
d = {key1 : value1, key2 : value2, key3 : value3 } 键唯一不可变，值不唯一，任数据类型
get()函数返回指定键的值： dict.get(key, default=None)
key为查找的键，default为不存在时的默认值
enumerate(枚举)
enumerate()函数将可遍历数据对象组合为索引序列，同时列出数据和数据下标，可以设定下标起始位置
enumerate(sequence, [start=0])
slice(切片)
此处的slice不指函数，而是python对有序序列的一种处理方式
前置知识：python所有有序序列都支持负向索引
a='hello' 的下标正反如下
| 0 | 1 | 2 | 4 | 3 |
|---|---|---|---|---|
| -5 | -4 | -3 | -1 | -2 |
那么对于切片:
b=a[i:j:k] 从下标i开始到j-1结束，步长为k，(k为非零整数，j-1结束是因为j侧为开区间！)
b=a[i:j] 默认k为1
b=a[:j] 默认i为0
k>0时，i默认为0，j默认为len(a) ; k<0时，i默认为-1，j默认为-len(a)-1(同上，j侧是开区间)
那么，b=a[::-1] 按照上述规则，则是从-1开始，直到边界，也就是inverse！
注意，dictionary(字典)和set(集合)是不能通过下标访问的
在numpy中，引入了’’,’符号，用来分隔不同维度。用到时再仔细学习！
if-else 语句的多种写法
基本知识的补习。
常规写法：
if : elif: else:
表达式： c = a if a>b else b
二维表：c = [a,b][a<b] 注意，后面中括号为TRUE时前面取右侧，FALSE取左侧！
逻辑运算符：c = (a>b and a or b) 这个有点意思，理解一下，前真返回and后的值，前假返回or后的值，但是如果and后面是FALSE，即使前真，仍然返回or后的值。即——and 只做否定，or只做肯定。
Problems
1. Two Sum
做第一题的明显感受：python真的还不太会。
于是直接放弃自己求解，有了上面的基础知识补习。还好底子还在，查点资料理解代码没问题。
暴力思路双重循环，很显然的复杂度比较高 $O(n^2)$。
1100ms的思路用一个循环，枚举的过程中if判断是否存在不重合的sum值。
高分答案和考点契合，使用哈希表大幅减少复杂度
(构造方法，冲突解决都还需要再复习)
7. Reverse Integer
第一想法是用数组把每一位存起来然后输出，可以从最远位往回存，然后从第一个非0数开始输出
答案：栈思想？反转是一个经典的入栈出栈操作。答案中实现pop/push用的是模，乘，除。
对于python，显然不需要这么复杂，学习了上面的slice操作之后，答案就一目了然了。
仍然存在的问题是越界判断，按照题目的描述(我的理解)，应该是系统只有32位，所以不能先算出来prevent pseudo-overflows，而是要边加边判断。那么slice的时候怎么解决这个问题？
看了半天讨论和回复，目前我的理解是python本身对数据类型或者说数据长度没有限定，所以本身不会检测出问题。从代码逻辑上讲，slice就不能很好的预判overflow。看到submission里有用答案方法实现的，在每次加数之前预判会不会超，我觉得是比较合理的答案。不过讨论里说的对——
哈哈
9. Palindrome Number
回文数检测(含符号)，follow up让不要转string，那么正常思路顺着也就是把它转成string，然后可能可以读正负下标比较是否相同?
想了一下，直接取绝对值转str，inverse，再转int，比较是否和原数相等即可!第一次自己完成了一道题并且一次accepted，值得庆祝！
仍然需要注意第七题里的overflow问题！这里我没有管也可以通过，因为比较的是是否相等，再加上python是不存在长度限制的，所以就不会有问题。假如要考虑的话，应该要像第七题一样在inverse的时候检查不溢出，这样就麻烦了，不如string一个个对比。
读了一下solution，突然就明白了，其实本质和上一题是一样的，假如用slice的思想，就没法检查溢出，但是如果要检查溢出，也就达到了不用string的目的了，直接做数学运算就好了。
当然，答案的想法也很有意思，revert一半的数字，也就不用查溢出了！对于奇数位的处理则是return x == revertedNumber || x == revertedNumber/10; 确实很精妙。
看了下comments，似乎我的代码还复杂了一点点，反正负数肯定不对，也没必要取绝对值。转成string之后可以直接和temp作比较，就没必要再转来转去了，应该会更快？
不过追求几秒的速度好像没啥意义。下次自己写一下答案这样的解法。
13. Roman to Integer
读完题目，大致感觉一下，最常规的做法应该是把字符串转成对应的整数，然后判断相邻数的关系，若递增则相加，若递减则变号一次。如果算ASCII码会不会比较快？
按自己的思路试试，反正好玩儿么。I73，V86，X88，L76，C67，D68，M77
看了一个答案很厉害，基于这个基础的想法在逻辑上做到了优化。通过右读的方式，假如已有数比“减法”时的大数要小，则必然是加，反之则一定是减(语言有点描述不清，代码很好理解。)
对python，看起来大家都是先用字典转换成整型，再直接从左往右做运算？这样感觉很常规。先加，加完如果加数比上一个加数大，再减两倍加数…
与此同时我发现ASCII码不太靠谱了，这样的话没法儿直接运算，还得先判断是个啥数再换算…
速度更快的答案就是像上面说的逻辑一样，slice取反右读计算，但是好像逻辑上说没啥本质区别…
这个题就这样吧，sigh
14. Longest Common Prefix
最简单的方法应该是二维数组n次比较，假如某位均相等则记录，再到下一个位。这样感觉时间复杂度会比较高，考虑用哈希表存每一位，然后扫描完一位再读一遍哈希表，看有没有等于n的，有就记录清零到下一位。
自以为的常规思路和哈希都写了，哈希稍微快了一些，有一些成就感吧 : /
对比高分答案在我这里跑出来的结果，基本也都是这个水平，还是很满意了，在第一梯队，哈哈！
阅读答案学习了一下，
Horizontal scanning 是两两找出最长同前缀，然后再把这个前缀和第三个找。我好像根本没这样考虑问题，可能是潜意识里觉得这样比较慢？
Vertical scanning 就是我的思路了，逐个字母去比较。
Divide and conquer 分而治之，在1的基础下做了分片
Binary search 对一个字符串二分，然后先比较前一半是否相等。这个有点新颖。
看到一个让我感到精妙的答案， 虽然速度可能没特别快，但是很有意思。用的是list.sort()和zip()函数。前者将列表按字母排序，这样第一个和最后一个一定是最不相同的，即假如他们的某位都一样，那么中间部分这一位一定一样。zip则把这两个字符串转成元组，然后就可以方便的成对比较。高，实在是高！
这一题有一点警示就是一定要先处理异常，比如本题的空集。然后如此多的解法也是很有启发性的，针对不同的具体情况可以采用不一样的解决方案。值得过阵子再来学习一下。
20. Valid Parentheses
第一想法有点奇葩，想用整数和整除来写一个表达式判断。琢磨了半天，发现很难实现。
仔细一想，从中间向两边判断应该是比较合理的，正好长度必须是偶数。
查表发现成对括号的ASCII码差值小于3
写完测试的时候意识到，最中间的一对不一定需要相等！也可以两侧相等
改了半天，发现中间的两侧也不一定就相等了，卧槽…心碎了都。搞不定了，看答案
按intuition，还是应该从左向右寻找，可以成对即删除。啊我为了减少循环次数，弄的太复杂了！把失败品记录一下吧。
突然就意识到自己有多么愚蠢，艹！
按照intuition直接写了，提交上去发现自己太naive，可以({)} !!! 有点想不动了，继续看答案 ==
看了下别人的答案，感觉这题应该用栈来解，括号问题的精髓在于，它必须有两个连续可解的数！或许这样我也可以延续刚刚的想法改一下自己的代码？
于是我得到了一个慢的起飞的答案 : /
改用人家的栈，简直不在一个量级。这就是数据结构的魅力吧。
为啥我就这么傻逼没想到栈？