似乎，，，，返回结果的空间不会算在空间复杂度上
思维的全面性（各种边界条件）
索引与中点的关系：
设最后元素的索引为n，则中点的索引为n/2【对于奇数正好是中点，对于偶数个元素，则是前面的一个元素】（除以2可以考虑采用移位）
/2问题???？？？
设长度为n,索引值：0 ~ n/2-1？？？？
返回值为java内置类型时，返回null则会报错；
而返回值为自定义类型或数组类型时，返回null不会报错。
常用：
Collections.sort(res);
无穷等特殊值
double：Double.POSITIVE_INFINITY，Double.NEGATIVE_INFINITYInt：
Integer.MIN_VALUE，Integer.MAX_VALUE
好题
unique-binary-search-trees-ii（看起来没有一点头绪）：
排序
选择排序（冒泡）
插入排序
希尔排序（基于插入排序）
归并排序
快排
利用快排思想：
最小的k个数【此外若要求不能改变数组，则需要采用其他方法,红黑树】
数组中出现次数超过一半的数【此外若要求不能改变数组，则需要采用其他方法：该数字出现的次数要大于其他所有数字出现次数总和 】
优先队列
查找
顺序查找
二分查找（排序数组、部分排序数组）
二叉树查找
哈希表查找
树总结
树就用遍历与递归知识！
若要求处理一棵二叉树的遍历序列，则可先找到根节点，然后在分为左右子树，递归地处理两子树。
层序遍历就是广度优先搜索。
遍历
https://blog.csdn.net/workformywork/article/details/21628351
前序遍历、中序遍历、后序遍历的非递归实现，时间复杂度为n,空间复杂度为1的Morris方法
preorder
inorder
postorder
怎么变成后序的呢？？？
http://blog.csdn.net/whzyb1991/article/details/44278723
3步走：
1.左右翻转
2.前序遍历
3.反转顺序
void InOrderTraversal( BinTree BT )
{
BinTree T BT;
Stack S = CreatStack( MaxSize ); /*
创建并初始化堆栈 S*/
Stack Q = CreatStack( MaxSize ); /*
创建并初始化堆栈 Q，用于输出反向*/
while( T || !IsEmpty(S) ){
while(T){ /*
一直向右并将沿途结点压入堆栈*/
Push(S,T);
Push(Q,T);/*将遍历到的结点压栈，用于反向*/
T = T->Right;
}
if(!IsEmpty(S)){
T = Pop(S); /*
结点弹出堆栈*/
T = T->Left; /*
转向左子树*/
}
}
while( !IsEmpty(Q) ){
T = Pop(Q);
printf(“%5d”, T->Data); /*
（访问）打印结点*/
}
}
解释是： 先序的访问顺序是 root, left, right 假设将先序左右对调，则顺序变成 root, right, left，暂定
称之为
“反序” 。
后序遍历的访问顺序为 left, right,root ，刚好是“反序”结果的逆向输出。于是方法如下：
1、反序遍历二叉树，具体方法为：将先序遍历代码中的 left 和 right 对调即可。
数据存在堆栈
S 中。
2、在先序遍历过程中，每次 Push 节点后紧接着 print 结点。
对应的，在反序遍历时，将
print 结点改为把当前结点 PUSH 到堆栈 Q 中。
3、反序遍历完成后，堆栈 Q 的压栈顺序即为反序遍历的输出结果。
此时再将堆栈
Q 中的结果 pop 并 print，即为“反序”结果的逆向，也就是后序遍历的结果。
缺点是堆栈
Q 的深度等于数的结点数，空间占用较大。
level:又分为
1.正常的【利用Queue，虽然顺序是对的，但层之间已混在一块】
2.cur与next的【此时需要明确区分层级之间的关系，用cur与next得以区分层与层，但是忘记哪个题目了】
时间复杂度为n,空间复杂度为1的Morris方法：（中序遍历）
https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
Morris算法与递归和使用栈空间遍历的思想不同，它使用二叉树中的叶节点的right指针来保存后面将要访问的节点的信息，当这个right指针使用完成之后，再将它置为NULL，但是在访问过程中有些节点会访问两次，所以与递归的空间换时间的思路不同，Morris则是使用时间换空间的思想，先来看看Morris中序遍历二叉树的算法实现：[cpp] view plain copy
第一个print为打印左子节点，第二个为打印当前根节点
前序遍历：
动态规划总结------------------------------------------------------------------
常见问法：有无，有多少条（并不求出具体形式）。
（若要求寻找各种组合的具体形式，则是回溯问题）
任何动态规划都是拥有“吓人的”外壳，但还有一颗柔软的内心。
本质就是：
1.状态（找到）
2.状态转移。(本状态与上一次或周边状态的转换关系）
（然后找到初值，即可）
很多动态规划可以采用滚动数组的形式以减少空间复杂度（对于一般动归，空间复杂度从n2降到n）
状态表示方法比较重要，主要有：
1.每个位置一个状态；
2.每一段一个状态。
另外比较高端的解释：
1.最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可独立求解。
2.重叠子问题：递归算法反复求解相同的子问题，动态规划算法中使用数组来保存子问题的解
算法-动态规划 Dynamic Programming--从菜鸟到老鸟
知乎文章：
每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
广搜
采用Queue（记为q）记录当前的元素，采用visited记录是否被访问过，并寻找q中每一元素（不断pop出来）的neighbors，根据visited对neighbors进行判重，若不重复，则加入q;否则舍弃。（有时，可能使用HashSet等代替Stack）
有时可以使用双队列的方式，从两头开始，每次采用size小的一遍寻找neighbors。
回溯------------------------------------------------------------------------------
问题形式：
问题：
求各种组合（可能）：
https://blog.csdn.net/versencoder/article/details/52071930【写的非常好！！！】
n皇后问题（典型深搜问题）：
同一个循环中不能有同样的元素，而嵌套循环中可有：
字符串字符前后交换：
心得：
任何回溯都是拥有“吓人的”外壳，但还有一颗柔软的内（套）心（路）。
都是套路。。。
收敛条件(有时收敛条件和终止条件会合二为一)
终止条件
剪枝
所有可能扩展操作
数组-------------------------------------------------------------------------
注意边界条件，异常情况
1.两已排好序数组第k大数
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
2.合并空间
链表
注意&常使用：
异常和边界检查
常使用dummy节点进行反转 【ListNode dummy=new ListNode(-1); dummy.next=head;】
快慢指针（寻找链表中点，寻找环，寻找环的起点（https://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad））
某一指针多走几步
原地复制形成双重链表（复制复杂链表https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking）
1.前插法反转链表
很多题目都使用该思想！
示意图
反转部分节点
2.形成一个环可能会减少工作量
一块一块的顺序未变。
3.快慢指针
字符串
相互转化：
Arrays.sort()
String<->int：
Integer.parseInt(str)
Integer.toString(n)
String<->double：
Double.parseDouble(str)
Double .toString(n)
Char->String:
1. String s = String.valueOf('c');//效率最高的方法
2. String s = String.valueOf(new char[]{'c'});//将一个char数组转换成String
3. String s = Character.toString('c');// Character.toString(char)方法实际上直接返回String.valueOf(char)
4. String s =newCharacter('c').toString();
5. String s = "" + 'c';// 虽然这个方法很简单，但这是效率最低的方法
// Java中的String Object的值实际上是不可变的，是一个final的变量。
// 所以我们每次对String做出任何改变，都是初始化了一个全新的String Object并将原来的变量指向了这个新String。// 而Java对使用+运算符处理String相加进行了方法重载。
// 字符串直接相加连接实际上调用了如下方法：
// new StringBuilder().append("").append('c').toString();
6. String s =newString(newchar[]{'c'});
String-> Char:
1.String.charAt(index)
2.String.toCharArray()
没有什么难度，主要是考虑到各种极限情况。掌握了下面常用的函数即可
s.substring(s,e);//不包含e
s.split("/");
Arrays
在Java中Arrays工具类实现功能的六种方法
使用Arrays工具类，要先导入包即：import.java.util.Arrays
以下是实现六种功能的方法：
1、toString方法是把数组转换成字符串进行输出。（参数是数组，返回的是字符串）
int[] a1={1,2,3,4};
System.out.println(Arrays.toString(a1));
原理：【 String s1=Arrays.toString(a1);
System.out.println(s1);】
2、sort方法，把数组中的元素按升序排序。【参数：除了布尔型都可以，类也可以】
Arrays.sort(a); //排序,a为数组
//如果h是字符串的话
String[]s1={"c","ab","d","e"};
Arrays.sort(s1);
for(String s:s1){
System.out.println(s);
}
3、BinarySearch:找到元素在数组当中的下标。
String[]s3={"a","b","c","d","e","w"};
int index=Arrays.binarySearch(s3,"g");
System.out.println("该元素的下标是："+index);
//运行结果：下标为：-6.（找不到g；-（插入点5）-1)=-6
4、比较两个数组值是否相等：结果为true、false.(布尔型不能比较)
int []a={10,20,30};
int []b={10,20,30};
int []c={1,2,3};
boolean isEqual=Arrays.equals(a,b); //定义boolean型变量isEqual，
System.out.println(isEqual); //isEqual只能是true或是flase,将a,b比较的值赋给isEqual，并打印
//或者直接用 System.out.println(Arrays.equals(a,b));
System.out.println(Arrays.equals(a,c));
5、copyOf把一个数组复制出一个新数组（新数组的长度为length）
int[]s1={11,22,33,44};
int[]s2=Arrays.copyOf(s1,2); //将s1数组中的前面的两个元素复制到s2中
System.out.println(Arrays.toString(s2));
6、fill方法：把整个数组里的每一个元素的值进行替换为val。函数原理：（void fill(Arrays,val)）
int[]s1={11,22,33,44};
Arrays.fill(s1,10);
String初始化细节（挺好）
StringBuffer，StringBuilder
String，StringBuffer，StringBuilder区分
两者常用函数：
http://www.runoob.com/java/java-stringbuffer.html
当对字符串进行修改的时候，需要使用 StringBuffer 和 StringBuilder 类。
和 String 类不同的是，StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。
StringBuilder 类在 Java 5 中被提出，它和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的（不能同步访问）。
由于 StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使用 StringBuilder 类。然而在应用程序要求线程安全的情况下，则必须使用 StringBuffer 类。
StringBuffer 的几个函数比较重要：setCharAt，charAt，setLength
删除stringbuilder最后一个元素：res.setLength(res.length()-1); 或者res.deleteCharAt(res.length()-1);
导入的包
import java.util.*;
常用的
数组的大小：a.length;
字符串的大小：s.length();
对象、数组做参数，传过去的是地址。基本数据类型传递的是值。
所以你在你调用的方法里面可以修改对象的某些属性（值），基本数据类型就不可以。Java中数组也是传递地址的。
因此我们如果在某些地方调用其他方法时，需要用传进去的参数把结果带回来，就可以用对象或者数组做参数，但用基本数据类型，就不能把结果带回来
基本数据类型
byte：8位，最大存储数据量是255，存放的数据范围是-128~127之间。默认值是 0；
short：16位，最大数据存储量是65536，数据范围是-32768~32767之间。默认值是 0；
int：32位，最大数据存储容量是2的32次方减1，数据范围是负的2的31次方到正的2的31次方减1。默认值是 0；
long：64位，最大数据存储容量是2的64次方减1，数据范围为负的2的63次方到正的2的63次方减1。默认值是 0L；
float：32位，数据范围在3.4e-45~1.4e38，直接赋值时必须在数字后加上f或F。默认值是 0.0f；
double：64位，数据范围在4.9e-324~1.8e308，赋值时可以加d或D也可以不加。默认值是 0.0d；
boolean：只有true和false两个取值。默认值是 false；
char：16位，存储Unicode码，用单引号赋值。判断是否相等时，可直接用==来判断
ck
如果要求输出所有可能的解，往往都是要用深度优先搜索。如果是要求找出最优的解，或者解的数量，往往可以使用动态规划。
需要new动态数组
res.add(new ArrayList(path));//**如果不new，则在path，remove后，则res就没有了。
数组
判断二维数组是否为空
1.二维board
if(board==null || board.length==0 || ( board.length==1 && board[0].length==0 )) return;
2.
长度为0的数组（空数组） int[] arr = new int[0]，也称为空数组，虽然arr长度为0，但是依然是一个对象
null数组，int[] arr = null；arr是一个数组类型的空引用。
则： if (nums == null || nums.length == 0) { ............. }
位运算
相关题目：
1.移位
>>
对于正数，左侧补0；
对于负数，左侧补1。
2.常用操作
就是常见的操作
一个正数减去1，则该数最右边的1变为0，而右侧还有0的话，则全部变为1，左侧则保持不变.因此，操作前后的数相与，则相当于把最右边的1变为0.【很多二进制问题均可以采用本思路】
其他
判断两个double是否相等：
private boolean equal(double n1,double n2)
{ return ((n1-n2)<0.0000001 && (n1-n2)>-0.0000001); }
判断是否为奇数
if(n & 0x01==1)
/2 (整除)
n>>1
循环打印：https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
内部类
？？？？？？？？？？？？？？？？？？
publicclassStringChar {
publicstaticvoidmain(String[] args) {
//字符串--》字符
String str1 = "风云";
charc1 = str1.charAt(0);//风， 如果要得到云。那么charAt(1);
System.out.println(c1);
char[] cs1 = str1.toCharArray();//字符串转字符数组
System.out.println(Arrays.toString(cs1));
//字符--》字符串
charc2 = '明';
String str2 = String.valueOf(c2);//字符转字符串
//String str2 = c2+""; //也可以把字符转换成字符串类型
System.out.println(str2);
char[] cs2 = {'明','月'};
String str3 = String.copyValueOf(cs2);//字符数组变字符串
System.out.println(str3);
String str4 = newString(cs2);//字符数组变字符串
System.out.println(str4);
}
}
网友评论