[toc]
图算法
static int[][] a; // 邻接矩阵存储图信息； Integer.MAX_Value代表两个节点不相邻； 0 代表该节点本身，其余值代表路径长度
private static int n, m;
// 深搜算法，从 u 节点开始遍历；
void dfs(int u, boolean[] bool) {
bool[u] = true;
visit(u);
for(int i=0; i<n; i++) {
if(!bool[i] && a[u][i] != Integer.MAX_VALUE) dfs(i, bool);
}
}
//广搜算法， 从u节点开始遍历；
void bfs(int u) {
boolean[] bool = new boolean[n];
Queue<Integer> q = new LinkedList<>();
q.offer(u);
while(!q.isEmpty()) {
int v = q.poll();
bool[v] = true;
visit(v);
for(int i=0; i<n; i++) {
if(!bool[i] && a[v][i] != Integer.MAX_VALUE) q.offer(i);
}
}
}
void visit(int u) {
System.out.println("遍历到了节点：" + u);
}
// 拓扑排序算法；
void topology() {
int[] num = new int[n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(a[i][j] != 0 && a[v][i] != Integer.MAX_VALUE) num[j] ++;
}
}
Queue<Integer> q = new LinkedList<>();
for(int i=0; i<n; i++) {
if(num[i] == 0) q.offer(i);
}
while(!q.isEmpty()) {
int u = q.poll();
visit(u);
for(int i=0; i<n; i++) {
if(i != u && a[u][i] != Integer.MAX_VALUE && num[i] > 0) {
num[i] --;
if(num[i] == 0) q.offer(i);
}
}
}
}
以及最短路径算法
void dijkstra(int s, int n) {
vector<int> dis;
dis.resize(n+1, maxn);
dis[s]=0;
vector<bool> b;
b.resize(n+1, false);
for (int i=1; i<=n; i++) {
int u=-1, min=maxn;
for (int j=1; j<=n; j++) {
if (!b[j] && dis[j]<min) {
min=dis[j];
u=j;
}
}
if (u==-1) printf("图并非连通...");
b[u]=true;
for (int j=1; j<=n; j++) {
if (dis[u]+a[u][j]<dis[j]) dis[j]=dis[u]+a[u][j];
}
}
}
树算法
import java.util.*;
public class Tree {
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
public static void main(String[] args) {
int[] a = {4, 2, 6, 1, 3, 5, 7};
Tree t = new Tree();
TreeNode root = t.creatTree(a);
t.after2(root);
}
TreeNode creatTree(int[] a) {
if(a == null || a.length == 0) return null;
TreeNode head = null;
for (int i = 0; i<a.length; i++) {
head = insert(head, a[i]);
}
return head;
}
TreeNode insert(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(val >= root.val) root.right = insert(root.right, val);
else root.left = insert(root.left, val);
return root;
}
void pre(TreeNode root) {
if (root == null) return;
Stack<TreeNode> s = new Stack<>();
s.push(root);
while(!s.isEmpty()) {
TreeNode p = s.pop();
visit(p);
if(p.right != null) s.push(p.right);
if(p.left != null) s.push(p.left);
}
}
void mid(TreeNode root) {
if (root == null) return;
Stack<TreeNode> s = new Stack<>();
TreeNode p = root;
while(p != null || !s.isEmpty()) {
while(p != null) {
s.push(p);
p = p.left;
}
if(!s.isEmpty()) {
p = s.pop();
visit(p);
p = p.right;
}
}
}
void after(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
//System.out.println("push:" + node.val);
stack.push(node);
node = node.left;
}
if (stack.size() > 0) {
TreeNode temp = stack.peek().right;
if (temp == null || temp == prev) {
//if(temp == null)
//System.out.println("temp = null");
//else
//System.out.println("pre=" + prev.val);
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
void after2(TreeNode root) {
TreeNode p = root;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
while(p != null || !s1.isEmpty()) {
while(p != null) {
s1.push(p);
s2.push(p);
p = p.right;
}
if(!s1.isEmpty()) {
p = s1.pop();
p = p.left;
}
}
while(!s2.isEmpty()) {
p = s2.pop();
visit(p);
}
}
void visit(TreeNode r) {
System.out.println("visit:" + r.val);
}
}
手写LRU
package com.gastby.utils;
import java.util.*;
public class MyLRUCache<K, V> {
class CacheNode {
Object key;
Object value;
CacheNode pre, next;
CacheNode(Object key, Object o) {
this.key = key;
value = o;
}
public String toString() {
return "key:" + key + ", value:" + value;
}
}
private CacheNode head, tail;
private HashMap<K, CacheNode> map;
private int MaxSize;
MyLRUCache(int n) {
MaxSize = n;
map = new HashMap<>();
}
public void put(K key, V value) {
CacheNode node = map.get(key);
if(node == null) {
if(map.size() >= MaxSize) {
map.remove(tail.key);
removeTail();
}
node = new CacheNode(key, value);
map.put(key, node);
}
moveToHead(node);
}
public Object get(K key) {
CacheNode node = map.get(key);
if (node == null) return null;
moveToHead(node);
return node.value;
}
public void moveToHead(CacheNode node) {
if(node == head) return;
if(node.pre != null) node.pre.next = node.next;
if(node.next != null) node.next.pre = node.pre;
if(node == tail) tail = tail.pre;
if(head == null) {
head = tail = node;
return;
}
node.next = head;
head.pre = node;
head = node;
head.pre = null;
}
public Object delete(K key) {
CacheNode node = map.get(key);
if(node == null) return null;
if(node.pre != null){
node.pre.next=node.next;
}
if(node.next != null){
node.next.pre=node.pre;
}
if(node == head){
head = node.next;
}
if(node == tail){
tail = node.pre;
}
map.remove(key);
return node.value;
}
public void removeTail() {
if (tail != null) {
map.remove(tail.key);
tail = tail.pre;
if (tail == null) {
head = null;
} else {
tail.next = null;
}
}
}
public int getSize() {
return map.size();
}
public void showNodes() {
CacheNode p = head;
while(p != null) {
System.out.print(p + ",");
p = p.next;
}
System.out.println();
}
public static void main(String[] args) {
MyLRUCache<Integer, String> m = new MyLRUCache<>(5);
m.put(1, "tom");
m.put(2, "july");
m.put(3, "lily");
m.put(4, "sandy");
m.put(5, "peter");
m.showNodes();
m.get(3);
m.showNodes();
m.put(6, "jane");
m.showNodes();
m.delete(3);
m.showNodes();
m.removeTail();
m.showNodes();
}
}
排序算法
//快速排序，k从0到a.lenght-1取值；
//利用快排思想找第k个数字，在内部排好序了，直接取值a[k]即可；
void quickSort(int[] a, int k) {
int l=0, r = a.length-1;
while (l < r) {
int j = patition(a, l, r);
if (k == j) break;
else if (k < j) r = j - 1;
else l = j + 1;
}
}
int patition(int[] a, int l, int r) {
int p = a[r], index = l - 1;
for (int i=l; i<r; i++) {
if (a[i] < p) {
int temp = a[++index];
a[index] = a[i];
a[i] = temp;
}
}
int temp = a[++index];
a[index] = a[r];
a[r] = temp;
return index;
}
void heapSort(int[] a) {
int n = a.length-1;
for (int i=n; i>0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
sink(a, 0, i-1);
}
}
void createHeap(int[] a) {
int k = a.length/2-1;
for (int i=k; i>=0; i--) {
sink(a, i, a.length-1);
}
}
void sink(int[] a, int i, int n) {
int l = 2*(i+1)-1, r = 2*(i+1), max = i;
if (l<= n && a[l] > a[i]) {
max = l;
}
if (r<= n && a[r] > a[max]) {
max = r;
}
if (max != i) {
int temp = a[i];
a[i] = a[max];
a[max] = temp;
sink(a, max, n);
}
}
链表算法
public class Main{
public static void main(String[] args) {
int[] a = {1, 4, 4, 4, 13, 13, 24, 35};
Node root = create(a);
print(root);
root = clearDuplicate(root);
print(root);
}
static void print(Node root) {
Node p = root;
while (p != null) {
System.out.print(p.val + " ");
p = p.next;
}
System.out.println();
}
// 创建一个链表
static Node create(int[] a) {
Node head = null, p = head;
for(int i=0; i<a.length; i++) {
Node temp = new Node(a[i]);
if(p == null) {
p = temp;
head = p;
} else {
p.next = temp;
p = p.next;
}
}
return head;
}
Node paritialReverse(Node head, int start, int end) {
if(start < 1 || start >= end || head == null) return head;
Node fakeHead = new Node(-1);
fakeHead.next = head;
int i = 0;
Node p = fakeHead, q = p;
while(i < start-1 && p != null) {
if(p.next == null) return fakeHead.next;
p = p.next;
i ++;
}
i = 0;
while(i < end && q != null) {
if(q.next == null) break;
q = q.next;
i ++;
}
Node temp = q.next;
q.next = null;
q = temp;
p.next = reverse(p.next);
while(p.next != null) p = p.next;
p.next = q;
return fakeHead.next;
}
// 逆转链表
static Node reverse(Node root) {
Node p = root, q = null, r;
while(p != null) {
r = q;
q = p;
p = p.next;
q.next = r;
}
return q;
}
// sort two sorted linkedlist to one linkedlist;
static Node compute(Node r1, Node r2) {
Node head = new Node(-1), p = head;
while(r1 != null || r2 != null) {
if(r1 == null) {
p.next = r2;
break;
} else if(r2 == null) {
p.next = r1;
break;
} else {
if (r1.val < r2.val) {
p.next = r1;
r1 = r1.next;
} else {
p.next = r2;
r2 = r2.next;
}
p = p.next;
p.next = null;
}
}
return head.next;
}
// remove all the duplicated elements to make sure the number is 1;
static Node deleteDuplicate(Node root) {
if(root == null) return root;
Node temp = root;
Node p = temp.next;
while(p != null) {
if(p.val == temp.val) {
while(p != null && p.val == temp.val) p = p.next;
temp.next = p;
if(p == null) return root;
temp = temp.next;
} else {
temp = p;
}
p = p.next;
}
return root;
}
// remove all the elements whose numbers is more than once;
static Node clearDuplicate(Node root) {
if(root == null) return root;
Node head = new Node(-1);
Node p = head, temp = root;
while(temp != null) {
if(temp.next == null || temp.next.val != temp.val) {
p.next = temp;
p = p.next;
temp = temp.next;
p.next = null;
} else {
while (temp.next != null && temp.next.val == temp.val) temp = temp.next;
temp = temp.next;
}
}
return head.next;
}
//复制任意链表节点
static RandomListNode Clone(RandomListNode head) {
if(head == null) return head;
RandomListNode r = head;
while (r != null) {
RandomListNode temp = new RandomListNode(r.label);
temp.next = r.next;
r.next = temp;
r = temp.next;
}
r = head;
while(r != null) {
RandomListNode clone = r.next;
if(r.random != null)
clone.random = r.random.next;
r = clone.next;
}
r = head;
RandomListNode clone = head.next;
while(r.next != null) {
RandomListNode next = r.next;
r.next = next.next;
r = next;
}
return clone;
}
}
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
