欲练此功，必先头秃。
## 1.链表
1.链表的增删操作 链表的储存特点：可以用任意一组存储单元来存储单链表中的数据元素（存储单元可以是不连续的）
，而且，除了存储每个数据元素的值以外，还必须存储指示其直接后继元素的信息。这两部分信息组成的数据元素的存储映像称为结点。N个结点链在一块被称为链表，当结点只包含其后继结点的信息的链表就被称为单链表。
class Node{ Node next = null; int data; public Node(int dat) { this.data = data; } }
单链表的插入 操作是将值为x的新结点插入到单链表的第i个结点的位置上，即插入到数据元素ai-1与ai之间。其具体步骤如下：
1) 找到ai-1的引用（存储位置）p
单链表的删除 操作是将单链表的第i个结点删去。
1) 找到ai-1的存储位置p。
实例：
public class MyLinkedList { Node head = null;//链表头的应引用 /** * 向链表中插入数据 * */ public void addNode(int d){ Node newNode = new Node(d); if(head==null) { head = newNode; return; } Node tmp = head; while(tmp.next!=null) { tmp = tmp.next; } tmp.next = newNode; } /** * 返回节点的长度 * */ public int length() { int length = 0; Node tmp = head; while(tmp!=null) { length++; tmp = tmp.next; } return length; } /** * 删除第index个节点 * */ public Boolean deleteNode(int index) { if(index<1||index>length()) { return false; } //删除链表第一个元素 if(index ==1) { head = head.next; return true; } int i = 2; Node preNode = head; Node curNode = preNode.next; while(curNode!=null) { if(i==index) { preNode.next = curNode.next; return true; } preNode = curNode; curNode = curNode.next; i++; } return true; } /** * 对链表进行排序 * 返回排序后的头节点 * */ public Node orderList() { Node nextNode = null; int temp = 0; Node curNode = head; while(curNode.next!=null) { nextNode = curNode.next; while(nextNode!=null) { if(curNode.data>nextNode.data) { temp = curNode.data; curNode.data = nextNode.data; nextNode.data = temp; } nextNode = nextNode.next; } temp = curNode.data; curNode.data = nextNode.data; nextNode.data = temp; } nextNode = nextNode.next; } curNode = curNode.next; } return head; } /** * 打印链表 * */ public void printList() { Node tmp = head; while(tmp!=null) { System.out.println(tmp.data); tmp = tmp.next; } } public static void main(String[] args) { // TODO 自动生成的方法存根 MyLinkedList list = new MyLinkedList(); list.addNode(4); list.addNode(3); list.addNode(9); list.addNode(6); System.out.println("链表长度:"+list.length()); System.out.println("排序前:"); list.printList(); list.deleteNode(2); System.out.println("删除index=2的节点后:"); list.printList(); list.orderList(); System.out.println("排序后:"); list.printList(); } }
运行结果：
1.2 从链表中删除重复数据 1）最容易想到的就是遍历链表，把遍历到的值存储到一个Hashtable中，在遍历过程中，若当前访问的值在Hashtable中已经存在，则是重复的，删除。
/** * 删除链表中的重复数据 * */ public void deleteDupecate(Node head) { Hashtable<Integer, Integer>table = new Hashtable<>(); Node tmp = head; Node pre = null; while(tmp!=null) { if(table.containsKey(tmp.data))//判断是否包含指定的键名 pre.next = tmp.next; else { table.put(tmp.data, 1); pre = tmp; } tmp = tmp.next; } }
优点：时间复杂度低，
2) 为对链表进行双重循环遍历，外循环正常遍历链表，假设外循环当前遍历的结点为cur,内循环从cur开始遍历，若碰到与cur所指向结点值相同，则删除这个重复结点。
/** * 双重循环遍历删除链表中的重复数据 * */ public void deleteDupecateDouble(Node node) { Node p = head; while(p!=null) { Node q = p; while(q.next!=null) { if(p.data == q.next.data) { q.next = p.next.next; }else { q = q.next; } } p = p.next; } }
优点：在遍历过程中不需要额外的存储空间来保存已遍历过的值。
1.3找出单链表中的倒数K个元素 如果沿从头至尾的方向从链表中的某个元素开始，遍历k个元素后刚好达到链表尾，那么该元素就是要找的倒数第k个（Java没有指针概念，但是引用与指针有着非常相似的性质。便于理解，后续都采用指针的概念） 先前移k -1步，然后两个指针同时往前移动。循环直到先行的指针值为NULL时，另一个指针所指的位置就是所要找的位置。
/** * 查询倒数第K个元素 * */ public Node findElem(Node head,int k) { if(k<1||k>this.length()) return null; Node p1 = head; Node p2 = head; for(int i = 0;i<=k;i++)//前移k-1步 p1 = p1.next; while(p1!=null) { p1 = p1.next; p2 = p2.next; } return p2; }
1.4 实现链表的反转
参考：链表翻转的图文讲解
正确地反转一个链表，需要调整指针的指向。下面介绍递归和迭代两种方法的实现。链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。 递归法：
/** * 递归法反转链表 * */ public Node reverseList(Node node) { if(node == null || node.next ==null) { return node; }else { Node newHead = reverseList(node.next); node.next.next = node; node.next = null; this.head = newHead;//将新的头节点设置到static head(打印方法决定) return newHead; } }
递归法图示：
一直递归压栈，直到回归条件，整个过程NewH指针一直指向存放5的地址空间
H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值。
直到最后数据结点方向完全改变，返回到头
遍历法：
/** * 遍历法反转链表 * */ public void reverse(Node head) { Node pReversedHead = head;//存储反转后的头节点 Node pNode =head; Node pPrev = null; while(pNode!=null) { Node pNext = pNode.next; if(pNext==null) pReversedHead = pNode; pNode.next = pPrev; pPrev = pNode; pNode = pNext; } this.head = pReversedHead; }
遍历图示
对于链表设置两个指针：
不可以上来立即将上图中P->next直接指向NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。应设置一个临时指针tmp，暂时指向P->next指向的地址空间，保存原链表后续数据。然后再让P->next指向NewH，最后P=tmp就可以取回原链表的数据了，所有循环访问也可以继续展开下去。
指针继续向后移动，直到P指针指向NULL停止迭代。
最后
1.5 倒序输出单链表 运用递归
/** * 从尾到头输出链表 * */ public void printReversely(Node head) { if(head.next!=null) { printReversely(head.next); } System.out.println(head.data); }
1.6 寻找单链表的中间结点 如果是双向链表，可以首尾并行，利用两个指针一个从头到尾遍历，一个从尾到头遍历， 当两个指针相遇时，就找到了中间元素。单链表，也可以采用双指针的方式来实现中间结点的快速查找。
有两个指针同时从头开始遍历；
一个快指针一次走两步，一 个慢指针一次走一步；第三步，快指针先到链表尾部，而慢指针则恰好到达链表中部
快指针到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针，当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点
/** * 寻找单链表中间节点 * */ public Node serachMid(Node head) { Node pNode = head;//走两步的指针 Node qNode = head;//走一步最后指向中间节点的指针 while(pNode != null && pNode.next != null && pNode.next.next !=null) { pNode = pNode.next.next; qNode = qNode.next; } return qNode; }
1.7 判断链表是否有环
深入理解：判断单链表里面有没有环
** 两个指针从链表头部同时出发，一个每次前进一步，另一个每次前进两步，如果有环，它们一定会相遇**
/** * 检查是否有环 * */ public boolean isLoop(Node head) { Node fast = head; Node slow = head; if(fast==null) { return false; } while(fast != null && fast.next!=null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return false; } } return !(fast == null||fast.next == null); }
1.8 在不知道头指针的情况下删除指定结点 *两种情况来讨论： *
/** * 不知道头指针的情况下删除指定结点 * */ public boolean deleteNode(Node node) { if(node == null || node.next==null) return false; int tmp = node.data; node.data = node.next.data; node.next.data = tmp; node.next = node.next.next; return true; }
1.9 判断两个链表是否相交
深入了解：JAVA 判断两个单链表是否相交并求交点
如果两个链表相交，那么它们一定相同的尾结点 ，因此实现思路为：分别遍历两个链表，记录它们的尾结点，如果它们的尾结点相同，那么这两个链表相交，否则不相交。
/** * 判断两个链表是否相交 * */ public boolean isIntersect(Node n1,Node n2) { if(n1 == null || n2 == null) return false; Node tail1 = n1; //找到n1的尾节点 while(tail1.next!=null) { tail1 = tail1.next; } Node tail2 = n2; //找到n2的尾节点 while(tail2.next!=null) { tail2 = tail2.next; } return tail1 == tail2; }
2. 栈和队列 2.1 栈和队列的基本概念 栈和队列都是比较常用的数据结构。
栈 就像一个很窄的桶，先存进去的数据只能最后被取出来，是L I F O ( Last In First Out ,后进先出），它将进出顺序逆序，即先进后出，后进先出 。
队列 则像人们日常排队买东 西的“队列”，先排队的人先买，后排队的人后买，是FIFO (First In First Out,先进先岀） 的，它保持进岀顺序一致，即先进先出，后进后岀 。
注意区分： 程序的内存分配中的栈区（stack），堆区（heap），全局区（静态区）（static），文字常量区，程序代码区
参考资料：关于堆栈的讲解
2.2 实现栈
扩展：JAVA泛型通配符T，E，K，V区别，T以及Class，Class<?>的区别 数组实现：
import java.util.Arrays; public class MyStack <E>{ private Object [] stack; private int size;//数组中储存元素的个数 public MyStack() { stack = new Object[10];//初始长度为10 } //判断栈是否为空 public boolean isEmpty() { return size == 0; } public E peek() { if(isEmpty()) { return null; } return (E)stack[size-1]; } //出栈 public E pop() { E e = peek(); stack[size-1] = null; size--; return e; } //入栈 public E Push(E item) { ensureCapacity(size+1); stack[size++] = item; return item; } //判断数组容器是否已满，如果满了就扩充 private void ensureCapacity(int size) { int len = stack.length; if(size>len) {//数组满 int newLen = 10;//每次数组扩充的容量 stack = Arrays.copyOf(stack, size+newLen); } } public static void main(String[] args) { // TODO 自动生成的方法存根 MyStack<Integer>s = new MyStack<Integer>(); s.Push(1); s.Push(2); System.out.println("栈中元素个数："+s.size); System.out.println("栈顶元素为："+s.peek()); System.out.println("出栈元素为："+s.pop()); System.out.println("再次出栈元素为："+s.pop()); } }
运行结果：
链表实现：
class Node<E>{ Node<E>next = null; E data; public Node(E data) { this.data = data; } } public class Stack<E> { Node<E>top = null; public boolean isEmpty() { return top == null; } public void push(E data) { Node<E> newNode = new Node<E>(data); newNode.next = top; top = newNode; } public E pop() { if(this.isEmpty()) return null; E data = top.data; top = top.next return data; } public E peek() { if(isEmpty()) { return null; } return top.data; } public static void main(String[] args) { // TODO 自动生成的方法存根 Stack<Integer> s = new Stack<>(); s.push(1); s.push(2); s.push(3); System.out.println("栈顶元素为："+s.peek()); System.out.println("出栈元素："+s.pop()); System.out.println("出栈元素："+s.pop()); System.out.println("出栈元素："+s.pop()); } }
运行结果：
2.3 用O(1)的复杂度求栈中最小元素 可以用另外一个变量来记录栈底的位置，通过遍历栈中的所有元素找出最小值，但是这种方法的时间复杂度为0(n)。
O(1)复杂度具体实现： 使用两个栈结构，一个栈用来存储数据，另一个栈（辅助栈 ）用来存储栈的最小元素。
思路： 如果当前人栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；在岀栈时，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为其人栈之前的那个最小值。
顺便加入求最大值
import java.util.Stack; /** * 栈的使用 高效求栈中的最大最小值 时空复杂度均是O(1) */ public class SpecialStack<E extends Number> { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> stackMin = new Stack<Integer>();// 存放求最小值的栈 Stack<Integer> stackMax = new Stack<Integer>();// 存放求最大值的栈 public void push(Integer l) { stack.push(l); if(stackMin.isEmpty()){ stackMin.push(l); }else{ if(l.intValue() <= stackMin.peek()){ stackMin.push(l); } } if(stackMax.isEmpty()){ stackMax.push(l); }else{ if(l.intValue() > stackMax.peek()){ stackMax.push(l); } } } public Integer pop()// 一定要记着，非空才能pop() { if (!stack.isEmpty() && !stackMin.isEmpty() && !stackMax.isEmpty()) { Integer e = stack.pop(); stackMin.pop(); stackMax.pop(); return e; } else { System.out.println("栈为空了"); return null; } } public Integer getMin() { return stackMin.peek(); } public Integer getMax() { return stackMax.peek(); } public static void main(String[] args) { SpecialStack<Integer> spect = new SpecialStack<Integer>(); spect.push(2); spect.push(1); spect.push(4); spect.push(7); spect.push(5); System.out.println("spect.stack1="+spect.stack); System.out.println("spect.stackMin="+spect.stackMin); System.out.println("spect.getMin()="+spect.getMin()); System.out.println("spect.stackMax="+spect.stackMax); System.out.println("spect.getMax()="+spect.getMax()); } }
运行结果：
2.4 实现队列 队列也可以采用数组和链表两种方式来实现。（先进先出，后进后岀 ）
链表实现：
class Node<E>{ Node<E>next = null; E data; public Node(E data) { this.data = data; } } public class MyQueue<E> { private Node<E>head = null; private Node<E>tail = null; public boolean isEmpty() { return head == tail; } //入列 public void put(E data) { Node<E>newNode = new Node(data); if(head==null && tail==null)//队列为空 head =tail = newNode; else { tail.next = newNode; tail = newNode ; } } //出列 public E pop() { if(this.isEmpty()) return null; E data = head.data; head = head.next; return data; } public int size() { Node<E>tmp = head; int n = 0; while(tmp!=null) { n++; tmp = tmp.next; } return n; } public static void main(String[] args) { // TODO 自动生成的方法存根 MyQueue<Integer>q = new MyQueue<>(); q.put(1); q.put(2); q.put(3); System.out.println("队列长度为:"+q.size()); System.out.println("队列首元素为:"+q.pop()); System.out.println("队列首元素为:"+q.pop()); } }
运行结果：
数组实现：
import java.util.LinkedList; public class MyQueue2<E> { private LinkedList<E>list = new LinkedList<>(); private static int size = 0; public synchronized void put(E e) { list.add(e); size++; } public synchronized E pop() { size--; return list.removeFirst(); } public synchronized boolean empty() { return size==0; } public static void main(String[] args) { // TODO 自动生成的方法存根 MyQueue2<Integer> q = new MyQueue2<>(); q.put(1); q.put(2); q.put(3); System.out.println("队列长度为:"+size); System.out.println("队列首元素为:"+q.pop()); System.out.println("队列首元素为:"+q.pop()); } }
运行结果:
2.5 两个栈模拟队列操作 假设使用栈A与栈B模拟队列Q，A为插入栈，B为弹出栈，以实现队列Q。
要人队列，入栈A即可，而岀队列则需要分两种情况考虑：
1) 若栈B不为空，则直接弹出栈B的数据。
实现代码：
import java.util.Stack; public class MyQueue3<E>{ private Stack<E>s1 = new Stack<>(); private Stack<E>s2 = new Stack<>(); public synchronized void put(E e) { s1.push(e); } public synchronized E pop() { if(s2.isEmpty())//没有s2判断出栈顺序会出错 while(!s1.isEmpty()) s2.push(s1.pop()); return s2.pop(); } public synchronized boolean empty() { return s1.isEmpty()&&s2.isEmpty(); } public static void main(String[] args) { // TODO 自动生成的方法存根 MyQueue3<Integer>q = new MyQueue3<>(); q.put(1); q.put(2); q.put(3); System.out.println("队列首元素为:"+q.pop()); System.out.println("队列首元素为:"+q.pop()); } }
运行结果：
3. 排序 3.1 选择排序 原理：
public class TestSort { public static void selectSort(int[]a) { int i; int j; int tmp = 0; int flag = 0; int n = a.length; for(i=0;i<n;i++) { tmp = a[i]; flag = i; for(j=i+1;j<n;j++) { if(a[j]<tmp) { tmp = a[j]; flag = j; } } if(flag!=1) { a[flag] = a[i]; a[i] = tmp; } } } public static void main(String[] args) { // TODO 自动生成的方法存根 int i = 0; int a[] = {5,4,9,8,7,6,0,1,2,3}; selectSort(a); for(i=0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println("\n"); } }
运行结果：
选择排序的时间复杂度：简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。
所以，综上，简单排序的时间复杂度为 O(N2)。
3.2 插入排序 对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。 接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中， 直至最后一个记录插入到有序序列中为止。想象一下打牌时候理牌的顺序
public class TestSort { public static void InsertSort(int[]a) { int i,j; int n = a.length; int target; //假定第一个元素被放到了正确的位置上 //这样，仅需遍历1 -- n-1 for(i=0;i<n;i++) { j=i; target = a[i]; while(j>0&&target<a[j-1]) { a[j]=a[j-1]; j--; } a[j] = target; } } public static void main(String[] args) { // TODO 自动生成的方法存根 int i = 0; int a[] = {5,4,9,8,7,6,0,1,2,3}; InsertSort(a); for(i=0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println("\n"); } }
运行结果：0 1 2 3 4 5 6 7 8 9
稳定
数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；
3.3 冒泡排序 比较两个相邻的元素，将值大的元素交换至右端。
public static void BubbleSort(int[]a) { int i,j; int n = a.length; int tmp; for(i=0;i<n;i++) { for(j=n-1;j>i;j--) { if(a[j]<a[j-1]) { tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } }
冒泡排序最好的时间复杂度为O(n)。
*冒泡排序总的平均时间复杂度为：O(n2) *
3.4 归并排序 归并的含义是将两个或两个以上的有序表合并成一个新的有序表。(归是指递归）
1.两路归并排序算法思路
public class MergeSort { //两路归并算法，两个排好序的子序列合并为一个子序列 public static void merge(int[]a,int left,int mid,int right) { int []tmp = new int[a.length];//辅助数组 int p1 = left,p2 = mid+1,k=left;//p1、p2是检测指针，k是存放指针 while(p1<=mid&&p2<=right) { if(a[p1]<a[p2]) tmp[k++] = a[p1++]; else tmp[k++] = a[p2++]; } while(p1<=mid) tmp[k++] = a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中 while(p2<=right) tmp[k++]=a[p2++];//同上 //复制回原素组 for (int i = left; i <=right; i++) a[i]=tmp[i]; } public static void mergeSort(int [] a,int start,int end){ if(start<end){//当子序列中只有一个元素时结束递归 int mid=(start+end)/2;//划分子序列 mergeSort(a, start, mid);//对左侧子序列进行递归排序 mergeSort(a, mid+1, end);//对右侧子序列进行递归排序 merge(a, start, mid, end);//合并 } } public static void main(String[] args) { // TODO 自动生成的方法存根 int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 }; mergeSort(a, 0, a.length-1); System.out.println("排好序的数组："); for (int e : a) System.out.print(e+" "); } }
时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
3.5 快速排序
快速排序——JAVA实现 快速排序——JAVA实现
public class QuickSort { public static void quickSort(int[]arr,int low,int high){ int i,j,tmp,t; if(low>high) return; i=low; j=high; //tmp是基准位 tmp = arr[low]; while(i<j) { //先看右边，依次往左递减 while(tmp<=arr[j]&&i<j) { j--; } //再看左边，依次往右递增 while(tmp>=arr[i]&&i<j) { i++; } //如果满足条件则交换 if(i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后将基准为与i和j相等位置的数字交换 arr[low] = arr[i]; arr[i] = tmp; //递归调用左半数组 quickSort(arr, low, j-1); //递归调用右半数组 quickSort(arr, j+1, high); } public static void main(String[] args) { // TODO 自动生成的方法存根 int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19}; quickSort(arr, 0, arr.length-1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } } }
时间复杂度
4. 位运算 4.1 移位操作实现乘法 java中有三种移位运算符
1.左移
例如，5<<3 就是5乘以2的3次方，结果是40。2.右移
例如，16>>3 就是16除以2的3次方，结果是2。
15>>3 就是14(15-1)除以2的3次方，结果是1。3.无符号右移
public class Muti { public static int powerN(int m,int n) {//m乘以2的n次方 for(int i=0;i<n;i++) { m=m<<1; } return m; } public static void main(String[] args) { // TODO 自动生成的方法存根 System.out.println("3乘以8=" +powerN(3, 3)); System.out.println("3乘以16=" +powerN(3, 4)); } }
4.2 判断一个数是否为2的n次方 用1做移位操作，然后判断移位后的值是否与给定的数相等，具体实现代码如下：
public class Test{ public static boolean isPower(int n) { if(n<1) return false; int i = 1; while(i<=n) { if(i==n) return true; i=i<<1; } return false; } public static void main(String[] args) { System.out.println(isPower(4)); System.out.println(isPower(6)); } }
运行结果：改进
例如nunm =00010000,那么num - 1的二 进制表示为num - 1 = 00001111，由于num与num - 1二进制表示中每一位都不相同，因此num&(num-1)
public static boolean isPower(int n) { if(n<1) return false; int m = n&(n-1); return m==0; }
4.3 二进制数中1的个数 首先，判断这个数的最后一位是否为1， 如果为1，则计数器加1,然后，通过右移丢弃掉最后一位。循环执行该操作直到这个数等于 0为止。在判断二进制表示的最后一位是否为1时，可以采用与运算来达到这个目的。
public class Test{ public static int countOne(int n) { int count = 0; while(n>0) { if((n&1)==1) {//判断最后一位是否为1 count++; } n=n>>1; } return count; } public static void main(String[] args) { System.out.println(countOne(7)); System.out.println(countOne(8)); } }
运行结果
