the python/JAVA code to solve the leetcode problem
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
1：最直接的方式直接双层遍历该数组，找到两个数相加等于该结果。时间复杂度为O(n^2 )。该方法的变种就是遍历一次数组，然后在该数组中搜索target-x是否存在。但是时间复杂度都是O(n^2 )，空间复杂度是T(n)
2：利用集合或者字典（hash）寻找是否存在的时间复杂度为O(1)的特性。因为该题是返回的索引值，所以只可以用字典，不可以用集合。构建另外一个存储了相同元素的字典，然后判断target-x是不是存在，时间复杂度是先遍历构建字典，然后遍历寻找是否存在O(n)+O(n)+O(1) = O(n)，空间复杂度为数组和字典的键值T(n)+T(n)+T(n) = T(n)
3：是方法2的改进，可以在构建字典的时候同时判断是否存在。遍历x，判断target-x是否存在，若存在，结束。若不存在，将x存入字典中。
第一种和第二种方法的解是一致的，第三种和前两种可能不一致
method1 use time 2.2591547966 s
method1 use time 0.0500032902 s
method1 use time 0.0010178089 s
在JAVA代码中，实现了shuffle的算法，实际可以用Collections.shuffle()来实现。shuffle算法是从数组末尾开始，末尾的数字出现在任意位置的概率是1/N，倒数第二个出现在任意位置的概率是(N-1)/N * 1/(N-1) = 1/N。
利用链表实现多位数的相加,难点是控制不等长的链表,然后需要记得进位。时间复杂度是max{O(N),O(M))。所以是O(N)
难点,怎么去找到最长的子串,第一种是暴力搜索(不用想了,没通过)。换种思路,我们遍历字符串,每次逐一加一个字符到substring中,然后判断有没有重复的,如果有,记录下当前字串长度,然后就从头开始剔除到这个字符的位置的字符串,然后重复上面的工作。参考
难点:首先要确定中位数是分奇数个和偶数个的,然后用多路归并(两路归并)的算法将两个列表有序整合起来,在对应的位置上获取中位数。
难点:回文分两种,一种是奇数个的回文,还有一个是偶数个的回文。
难点:在一个周期里：处于同一行的两个数的位置满足关系(i+j) = 2(numRows-1),该代码是一行一行的遍历整个字符串来实现的,时间复杂度是O(numRows*len(s)),可以考虑一个周期一个周期的处理,这样时间复杂度就是O(len(s))。效率更高
给定一个32位的有符号的整数，需要对数字进行反转。123（321）、-123（-321）、120（21）
实际上存在反转后溢出的情况。溢出时，返回0。
1：利用字符串的特性，先判断数字的正负，然后反转字符串，在判断反转后的数字是否越界。
2：通过取模和取余迅速计算。
这里有几个问题需要注意：
1：取模取余运算，在JAVA和C中，是用的舍弃小数点的方式，但是在python中却是用的向下取整的方式。在正数运算的场合，结果一致，但是在有负数参与的时候就有不一致。
return a-n*int(a/n) # 取模运算在JAVA和C中
return a-n*(a//n) # 在python中
return int(a/n) # 取余运算在JAVA和C中
return a//n # 在python中
2：JAVA在对int下边界取绝对值的时候不会正确的执行，详见api
System.out.println(Math.abs(-2147483648));
-2147483648
3：此类问题因为存在固有的界限，实际问题中可能会使用bigNumber模块，突破长度的限制
偷懒用正则表达式提取的数字
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。同时也要考虑正负号，所以所有的负数都不可能是回文数
1：转化为整型数组或者字符串，依次遍历判断。
2：直接反转数字，看两次的结果是否相等，直接借用第7题的代码。
直接利用正则表达式偷鸡,后面好好的去看看正则表达式的实现
可以用暴力搜索,但是时间复杂度太高。所以换个思路,假设我们从最大的底开始出发,然后我们会有一个面积,然后无论是左边的 +1 右移还是右边的 -1 左移都是为了寻找到一个较高的 高 。当左边不再小于右边的时候结束循环。
将数字转化成罗马数字或者罗马数字转化成整数
其实就是个贪心的过程，每次取出最满足条件的那一块完成转化，最后拼接起来
JAVA和python的字符串切片是一致的，都是左闭右开的
求一个字符串列表的元素的公共前缀序列
1：每次取出第一个元素的第i个位置的字符，然后遍历所有元素的第i个字符，比较是否一致，一致继续，不一致结束。
2：在其它地方抄来的一个巧妙办法，利用python的zip的特性一次性取出第i个的字符，然后利用集合迅速判断是否相同。
判断给定的括号是否都是有效的括号
经典的问题，利用栈的入栈和出栈的配对来完成
将两个有序链表合并
其实思路就是等同于合并两个有序的数组，开始从俩个数组中各拿出最小的元素出来，比较，然后将小的存入结果，然后从那个小数原本的数组中拿出下一个，比较。。。最后将没有遍历完的那个数组全部输出。
进阶：多个有序的数组合并，第一次取出每个数组的第一个元素，排序，将最小的结果输出到结果，然后将原本的那个数组中取出下一个元素，排序（用选择排序来完成比较好），最后将还有剩余的数组输出到结果。
该方法多用于超大数据和多线程排序。对于超大文件，假设内存限制我们一次最多可以提取N行数据，我们可以每次提取规模为N的数据出来，排序，输出到文件，然后读取下个N行。这样我们可以得到M（M<N）个文件，然后我们每次都只用比较每个文件的当前读取的最小数来比较，这样内存中的数目是M（文件的个数）。假设M>N了，那我们也可以分组，将N个文件先合并，合并完后那么还剩下M/N个文件，最后再合并剩下的文件。
除了最后一步的合并是需要读取并且比较的，其余的步骤均可独立完成，互不影响，所以可以用多线程来开辟多个线程去完成，大大的节省时间。
另外提一下合并的时间复杂度：假设有M个文件，我们需要维持一个长度为M的有序数组（用选择排序），时间复杂度是O(MlogM),所有的文件都要遍历一遍。所以总时间是O(MlogM)+O(N)。N>>M，O(N)。基本上是个线性的时间。
python代码中mergeTwoLists2是针对LeetCode的，mergeTwoLists1是针对我自己的代码，贴进LeetCode是错误的。我的链表的实现见SingleLinkedList.py。JAVA代码可以直接使用。查看他人代码的时候发现，不用去新建新的node，可以直接修改原有的node的指向。不用维护传入的两个链表。
二路归并
aa = [1,3,5]
bb = [2,4]
i = 0
j = 0
while i<len(aa) and j<len(bb):
if aa[i] >= bb[j]:
print(bb[j])
j += 1
else:
print(aa[i])
i += 1
if i < len(aa):
for t in range(i,len(aa)):
print(aa[t])
if j < len(bb):
for t in range(j,len(bb)):
print(bb[t])
多路归并
去除有序列表中的重复项，要求本地修改
我们可以用一个变量记录不重复的数量，同时它也是不重复数的索引，每当碰到新数的时候，将新数赋值给该索引，该变量+1。
第一次注意到java的变量必须要要初始化（不人为的话也会默认初始化），不像在perl语言中还可以用defined来判断那种声明但没赋值的对象。
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
跟26一模一样的思路，我们可以用一个变量记录不删除的数量，同时它也是不删除数的索引，每当碰到新数的时候，将新数赋值给该索引，该变量+1。
实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
KMP算法，日后实现
我其实没什么好思路，就是用的切片来完成的。有点投机，翻看了一下其它人的答案基本上也是用的切片。遇到这种需求最正确的做法应当是用正则表达式。还可以用KMP算法来实现
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
这种类型的题目比较简单，其实就是要确定target在数组中的位置。比如在JAVA中自带的二分查找（Collections.binarySearch()）就可以很好的完成这种任务，当目标存在就返回目标的位置，当目标不存在，就返回排序后理应在的位置（然后取负值表示没有找到，实际应用）。
考察点是二分查找。二分查找算法，基本和JAVA自带的是一致的。
public static int searchInsert(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
int med = (low+high)/2;
while(low <= high){
if(target > nums[med]){
low = med + 1;
} else if(target < nums[med]) {
high = med - 1;
} else {
return med;
}
med = (low+high)/2;
}
return -(low+1); // 这里返回值是-(low+1)而不是-low，是为了区分0的情况。一旦target等于第一个数，返回值是0，但是一旦target小于第一个数，返回值依然是0，为了避免这个模糊的情况，选择-(low+1)
}
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：1、 11、 21、 1211、 111221。
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。。
其实就是判断字符串中连续数字。eg：11114，就是4个1和1个4：4114
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
这道题其实偏难，不是简单的类型，可以用动态规划来解决，思路比较简单，就是我们假定当前执行到n，那么此时我们有第n-1时的最大值S(n-1)和n的值。我们只需要判断S(n)=max{n,S(n-1)+n}。当n更大说明之前的最大子序列是不需要的，当S(n-1)+n更大说明这个n是值得添加到这个最大子序列的。整个问题的最优解是每个子问题的最优解，这是个典型的动态规划类型的题目
JAVA代码对应python代码的maxSubArray2，maxSubArray1是将maxpre存入了原来的字典，节约一点空间吧。maxSubArray3则是输出子序列的起点和终点
给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。如果不存在最后一个单词，请返回 0 。
说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。
直接将字符串切分成数组，然后提取最后一个元素计算长度就行了。
当我提交了python代码之后，看到执行的速度排名其实很靠后，我就开始意识到利用split可能不是一个好的选择，因为题中只要求我们取最后一个字母，我们大可利用索引从后往前来遍历，开始碰到的空格都不管，碰到字母的时候开始计数，碰到空格结束。JAVA代码的思路就是这个
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
输入: [1,2,3]
输出: [1,2,4]
其实通用做法是设置一个进位标识符(flag=0)，每一位上的数字是digits[i]+add[i]+flag 和 10的比较，小于10就是直接相加，flag=0；大于10就是上述和-10，flag=1。
在JAVA代码中，代码的通式更强，可以计算任意两个整形数组的和。推广到N个整型数组相加。其实很简单，依旧是每一位上的和+flag，此时flag不再是1或者0，而是(a[i]+b[i]+c[i]+...+flag)/10。而该位的数字应该是(a[i]+b[i]+c[i]+...+flag)%10。用栈来实现代码看着更加的简单，用数组需要每次判断，时间消耗一致，代码量少很多。另外是一点题外的，每次把新元素添加到列表最后，最后反转数组的速度远快于每次将新元素插入第一个。
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字1和0。
输入: a = "11", b = "1"
输出: "100"
和66一模一样。略
实现int sqrt(int x)函数。计算并返回x的平方根，其中x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
可以尝试把JAVA代码中的double a改成float a试试。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
楼高1，只有一种方式；楼高2，有两种（一步2格上去，两次1格上去）；楼高3，有两种方式，楼高1的方式+2格上来，和楼高2的方式+1格上来。同理，楼高4，楼高2的方式+2格上来，和楼高3的方式+1格上来。f(n) = f(n-1)+f(n-2)。斐波拉契数列。
一般来说，递归的程序在反复压栈和出栈计算会导致效率极低，我们可以用循环来记录每次生成的结果，而不是递归的时候临时计算。
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
当链表长度少于1的时候，不用删除任何东西。当前节点c，下格节点n，当c=n的时候，让c=n.next。就删掉n了，此时需要令n=c.next。
给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。说明:
初始化nums1 和 nums2 的元素数量分别为m 和 n 。
你可以假设nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
因为nums1自己占据了自己低索引的数据，所以，我们用merge的倒算法，从大往小的排序。思路见T21的介绍。
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
比较简单的类型，就是遍历每个节点，如果当前节点的值不一样，就是false，同时要判断是否同时具有左节点或者右节点，如果一个树有左，另一个没有，那就false。循环判断。
更多的采用JAVA代码的样子来完成功能。python中如果用递归来实现，代码更加少而且清楚
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p == None and q == None:
return True
if (p == None and q != None) or (q == None and p != None):
return False
if p.val != q.val:
return False
else:
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
非递归版本
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
def check(node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
if node1.val != node2.val:
return False
return True
queue = []
queue.append((p, q))
while queue:
tempp, tempq = queue.pop(0)
if not check(tempp, tempq):
return False
if tempp:
queue.append((tempp.left, tempq.left))
queue.append((tempp.right, tempq.right))
return True
给定一个二叉树，检查它是否是镜像对称的。
要想判断root是不是对称，我们首先需要判断两个子树root.left和root.right是不是对称的。而判断root.left和root.right是不是对称的，则需要判断更下级的子树：root.left.right和root.right.left以及root.left.left和root.right.right。所以用递归实现就很简单了。才知道JAVA不可以嵌套函数。
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
root的高度的子问题就是某个节点到left和right，可以到就+1，不可以就结束了。
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
略