1.String/Array
toCharArray() //get char array of a String Arrays.sort() //sort an array Arrays.toString(char[] a) //convert to string charAt(int x) //get a char at the specific index length() //string length length //array size substring(int beginIndex) substring(int beginIndex, int endIndex) Integer.valueOf()//string to integer String.valueOf()/integer to string
2.链表
在Java中实现链表是非常简单的，每个节点都有一个值，然后把它链接到下一个节点。
class Node { int val; Node next; Node(int x) { val = x; next = null; } }
比较流行的两个链表例子就是栈和队列。
栈Stack
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; } } }
队列Queue
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; }
下面是一些与二叉树有关的概念：
- 二叉树搜索：对于所有节点，顺序是：left children <= current node <= right children；
- 平衡vs.非平衡：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；
- 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点；
- 完美二叉树（Perfect Binary Tree）：一个满二叉树，所有叶子都在同一个深度或同一级，并且每个父节点都有两个子节点；
- 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
堆（Heap）是一个基于树的数据结构，也可以称为优先队列（ PriorityQueue），在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
4.排序
不同排序算法的时间复杂度，大家可以到wiki上查看它们的基本思想。
BinSort、Radix Sort和CountSort使用了不同的假设，所有，它们不是一般的排序方法。
5.递归和迭代
下面通过一个例子来说明什么是递归。
问题：
这里有n个台阶，每次能爬1或2节，请问有多少种爬法？
步骤1：查找n和n-1之间的关系
为了获得n，这里有两种方法：一个是从第一节台阶到n-1或者从2到n-2。如果f(n)种爬法刚好是爬到n节，那么f(n)=f(n-1)+f(n-2)。
步骤2：确保开始条件是正确的
f(0) = 0;
f(1) = 1;
|
1
2
3
4
5
|
public static int f(int n){
if(n <= 2) return n;
int x = f(n-1) + f(n-2);
return x;
} |
递归方法的时间复杂度指数为n，这里会有很多冗余计算。
|
1
2
3
4
|
f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)
|
该递归可以很简单地转换为迭代。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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;
}
本文转自TBHacker博客园博客，原文链接：http://www.cnblogs.com/jiqing9006/p/3658017.html，如需转载请自行联系原作者
|