转载1.字符串
如果IDE没有代码自动补全功能，所以你应该记住下面的这些方法。
toCharArray() // 获得字符串对应的char数组Arrays.sort() // 数组排序Arrays.toString(char[] a) // 数组转成字符串charAt(int x) // 获得某个索引处的字符length() // 字符串长度length // 数组大小2.链表
在Java中，链表的实现非常简单，每个节点Node都有一个值val和指向下个节点的链接next。
class Node {int val;Node next;Node(int x) {val = x;next = null;}}
链表两个著名的应用是栈Stack和队列Queue。
栈：
class Stack{Node top;public Node peek(){if(top != null){return top;}return null;}public Node pop(){if(top == null){return null;}else{Node temp = new Node(top.val);top = top.next;return temp;}}public void push(Node n){if(n != null){n.next = top;top = n;}}}
队列：
class Queue{Node first, last;public void enqueue(Node n){if(first == null){first = n;last = first;}else{last.next = n;last = n;}}public Node dequeue(){if(first == null){return null;}else{Node temp = new Node(first.val);first = first.next;return temp;}}}3. 树
这里的树通常是指二叉树，每个节点都包含一个左孩子节点和右孩子节点，像下面这样：
class TreeNode{int value;TreeNode left;TreeNode right;}
下面是与树相关的一些概念：
译者注：完美二叉树也隐约称为完全二叉树。完美二叉树的一个例子是一个人在给定深度的祖先图，因为每个人都一定有两个生父母。完全二叉树可以看成是可以有若干额外向左靠的叶子节点的完美二叉树。疑问：完美二叉树和满二叉树的区别？（参考：）
4. 图
图相关的问题主要集中在深度优先搜索（depth first search）和广度优先搜索（breath first search）。
下面是一个简单的图广度优先搜索的实现。
1) 定义GraphNode
class GraphNode{int val;GraphNode next;GraphNode[] neighbors;boolean visited;GraphNode(int x) {val = x;}GraphNode(int x, GraphNode[] n){val = x;neighbors = n;}public String toString(){return "value: "+ this.val;}}
2) 定义一个队列Queue
class Queue{GraphNode first, last;public void enqueue(GraphNode n){if(first == null){first = n;last = first;}else{last.next = n;last = n;}}public GraphNode dequeue(){if(first == null){return null;}else{GraphNode temp = new GraphNode(first.val, first.neighbors);first = first.next;return temp;}}}
3) 用队列Queue实现广度优先搜索
public class GraphTest {public static void main(String[] args) {GraphNode n1 = new GraphNode(1);GraphNode n2 = new GraphNode(2);GraphNode n3 = new GraphNode(3);GraphNode n4 = new GraphNode(4);GraphNode n5 = new GraphNode(5);n1.neighbors = new GraphNode[]{n2,n3,n5};n2.neighbors = new GraphNode[]{n1,n4};n3.neighbors = new GraphNode[]{n1,n4,n5};n4.neighbors = new GraphNode[]{n2,n3,n5};n5.neighbors = new GraphNode[]{n1,n3,n4};breathFirstSearch(n1, 5);}public static void breathFirstSearch(GraphNode root, int x){if(root.val == x)System.out.println("find in root");Queue queue = new Queue();root.visited = true;queue.enqueue(root);while(queue.first != null){GraphNode c = (GraphNode) queue.dequeue();for(GraphNode n: c.neighbors){if(!n.visited){System.out.print(n + " ");n.visited = true;if(n.val == x)System.out.println("Find "+n);queue.enqueue(n);}}}}}
Output:
1
2
value: 2 value: 3 value: 5 Find value: 5
value: 4
5. 排序
下面是不同排序算法的时间复杂度，你可以去wiki看一下这些算法的基本思想。
AlgorithmAverage TimeWorst TimeSpace
冒泡排序n^2n^21
选择排序n^2n^21
Counting Sortn+kn+kn+k
Insertion sortn^2n^2
Quick sortn log(n)n^2
Merge sortn log(n)n log(n)depends
另外，这里有一些实现/演示：:Counting sort、Mergesort、Quicksort、InsertionSort。
《视觉直观感受 7 种常用的排序算法》《视频: 6分钟演示15种排序算法》6.递归vs.迭代
对程序员来说，递归应该是一个与生俱来的思想（a built-in thought），可以通过一个简单的例子来说明。
问题： 有n步台阶，一次只能上1步或2步，，共有多少种走法。
步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。
为了走完n步台阶，只有两种方法：从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数，那么f(n) = f(n-1) + f(n-2)。
步骤2: 确保开始条件是正确的。
f(0) = 0;f(1) = 1;
public static int f(int n){if(n <= 2) return n;int x = f(n-1) + f(n-2);return x;}
递归方法的时间复杂度是n的指数级，因为有很多冗余的计算，如下：
f(5)f(4) + f(3)f(3) + f(2) + f(2) + f(1)f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
直接的想法是将递归转换为迭代：
public static int f(int n) {if (n <= 2){return n;}int first = 1, second = 2;int third = 0;for (int i = 3; i <= n; i++) {third = first + second;first = second;second = third;}return third;}
对这个例子而言，迭代花费的时间更少，你可能也想看看Recursion vs Iteration。
7.动态规划
动态规划是解决下面这些性质类问题的技术：
只有不快的斧，没有劈不开的柴。
