80471267

牢记：

输入、输出、包。

Math.pow(double m, double n)

乘除2用移位；看奇偶用相与【n&1==1是错误的，应该为(n&1)==1】

编号与mid：

n为数组编号：n>>1是偏

前的中点索引

n为个数编号：n>>1是偏后的中点索引

树

题型：

思想：

递归（根据根节点区分左右子树）

层序遍历（1.常规LinkedList；2.cur，next）

链表

题型：倒数第几个节点、重合节点、反转链表

重要思想：dummy，递归，环的数学计算

动态规划

去掉虚伪的外壳，寻找最真心的“表达式”。

各种排序

冒泡

归并

插入

快排

希尔排序

----------------------具体题目-------------------------

替换空格

主要是

从后网往前的思想；

StringBuffer的使用：

str.setLength(j+1);

str.setCharAt(j--,'0');

从尾到头打印链表

1#使用Stack

2#递归本质就是一种Stack，但是层数比较多时会容易爆内存。

重建二叉树

不可以：if(pre1==pre2 && in1==in2) return new TreeNode(pre[pre1]);

可以：if(i1>i2 || j1>j2) return null;

因为某些时候可能会出现这种情况，如，只有左子树而没有右子树。

旋转数组的最小数字

3个情况：

if(array[i]==array[j] && array[mid]==array[i])

if(array[mid]>=array[i])

else if(array[mid]<=array[j])

变态跳台阶

以下两个语句效果相同。。

return (int)Math.pow(2,target-1);

return 1<<(target-1);

二进制中1的个数

【最优方法】将数字二进制的最后一个1变为0：n=n&(n-1)

若将数字n不停的右移与1相与，则可能会陷入死循环（负数不停的补1）；则反过来让1不停左移，然后相与，则没问题。

数值的整数次方

注意基数是0时：if(equal(b,0.0) && e<0) return 0.0;

指数为0：

判断double是否为0：return ((n1-n2)<0.0000001 && (n1-n2)>-0.0000001)

计算连乘:

调整数组顺序使奇数位于偶数前面

若仅仅是要求奇数在前不要求保证顺序：i，j从两名行进

要求保证顺序：i，j同时从左边行进

【骚操作】：考虑可扩展性,对于C++则可以直接将函数指针传进去，而对于Java好像需要传入一个实现某接口的类的对象，

树的子结构

关键是第一句放在前面。如下

顺时针打印矩阵

下的条件：m-1-k>k

左的条件：n-1-k>k

和为S的连续正数序列

利用“连续”这个性质，简化问题。

左旋转字符串

str.substring(0,n)

注意n=n%len;

翻转单词顺序列

res.deleteCharAt(res.length()-1)

二叉搜索树的后序遍历序列

一般的递归思想

二叉树中和为某一值的路径

每一次添加路径则需要new一下path
new ArrayList(path)

new ArrayList<Integer>(path)

复杂链表的复制

三种方法：

1. 时间复杂度为n*n的传统方法

2. 使用map，空间换时间

3.原地复制双重链表

二叉搜索树与双向链表

中序遍历

字符串的排列

Collections.sort()

String.valueOf(array)

res.contains()

数组中出现次数超过一半的数字

【注意check 有效性】

1#先排序，在取中值

2#利用次数

最小的K个数

if (k==0||input==null|| input.length==0 || input.length<k) return res;

1#使用最大堆

2#使用快排的思想，寻找处于第k位的数字。（时间复杂度为n）

2018-09-02