做图文的网站,电子商务网站特色,注册500万公司实缴多少钱,十大设计网站文章目录链表反转链表删除点链表中给定值的结点栈和队列双向链表实现栈和队列数组实现队列获取栈的最小值用两个栈实现一个队列用两个队列实现一个栈递归链表
反转链表
#xff08;反转单链表 反转双向链表#xff09;
public class Code01_ReverseList {public static cl…
文章目录链表反转链表删除点链表中给定值的结点栈和队列双向链表实现栈和队列数组实现队列获取栈的最小值用两个栈实现一个队列用两个队列实现一个栈递归链表
反转链表
反转单链表 反转双向链表
public class Code01_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {value data;}}public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value data;}}// head// a - b - c - null// c - b - a - nullpublic static Node reverseLinkedList(Node head) {Node pre null;Node next null;while (head ! null) {next head.next;head.next pre;pre head;head next;}return pre;}public static DoubleNode reverseDoubleList(DoubleNode head) {DoubleNode pre null;DoubleNode next null;while (head ! null) {next head.next;head.next pre;head.last next;pre head;head next;}return pre;}
}删除点链表中给定值的结点
public class Code02_DeleteGivenValue {public static class Node {public int value;public Node next;public Node(int data) {this.value data;}}// head removeValue(head, 2);public static Node removeValue(Node head, int num) {// head来到第一个不需要删的位置while (head ! null) {if (head.value ! num) {break;}head head.next;}// 1 ) head null// 2 ) head ! nullNode pre head;Node cur head;while (cur ! null) {if (cur.value num) {pre.next cur.next;} else {pre cur;}cur cur.next;}return head;}
}栈和队列
双向链表实现栈和队列
public class Code03_DoubleEndsQueueToStackAndQueue {public static class NodeT {public T value;public NodeT last;public NodeT next;public Node(T data) {value data;}}public static class DoubleEndsQueueT {public NodeT head;public NodeT tail;public void addFromHead(T value) {NodeT cur new NodeT(value);if (head null) {head cur;tail cur;} else {cur.next head;head.last cur;head cur;}}public void addFromBottom(T value) {NodeT cur new NodeT(value);if (head null) {head cur;tail cur;} else {cur.last tail;tail.next cur;tail cur;}}public T popFromHead() {if (head null) {return null;}NodeT cur head;if (head tail) {head null;tail null;} else {head head.next;cur.next null;head.last null;}return cur.value;}public T popFromBottom() {if (head null) {return null;}NodeT cur tail;if (head tail) {head null;tail null;} else {tail tail.last;tail.next null;cur.last null;}return cur.value;}public boolean isEmpty() {return head null;}}public static class MyStackT {private DoubleEndsQueueT queue;public MyStack() {queue new DoubleEndsQueueT();}public void push(T value) {queue.addFromHead(value);}public T pop() {return queue.popFromHead();}public boolean isEmpty() {return queue.isEmpty();}}public static class MyQueueT {private DoubleEndsQueueT queue;public MyQueue() {queue new DoubleEndsQueueT();}public void push(T value) {queue.addFromHead(value);}public T poll() {return queue.popFromBottom();}public boolean isEmpty() {return queue.isEmpty();}}
}数组实现队列
public class Code04_RingArray {public static class MyQueue {private int[] arr;private int pushi;// endprivate int polli;// beginprivate int size;private final int limit;public MyQueue(int limit) {arr new int[limit];pushi 0;polli 0;size 0;this.limit limit;}public void push(int value) {if (size limit) {throw new RuntimeException(队列满了不能再加了);}size;arr[pushi] value;pushi nextIndex(pushi);}public int pop() {if (size 0) {throw new RuntimeException(队列空了不能再拿了);}size--;int ans arr[polli];polli nextIndex(polli);return ans;}public boolean isEmpty() {return size 0;}// 如果现在的下标是i返回下一个位置private int nextIndex(int i) {return i limit - 1 ? i 1 : 0;}}}获取栈的最小值
public class Code05_GetMinStack {public static class MyStack1 {private StackInteger stackData;private StackInteger stackMin;public MyStack1() {this.stackData new StackInteger();this.stackMin new StackInteger();}public void push(int newNum) {if (this.stackMin.isEmpty()) {this.stackMin.push(newNum);} else if (newNum this.getmin()) {this.stackMin.push(newNum);}this.stackData.push(newNum);}public int pop() {if (this.stackData.isEmpty()) {throw new RuntimeException(Your stack is empty.);}int value this.stackData.pop();if (value this.getmin()) {this.stackMin.pop();}return value;}public int getmin() {if (this.stackMin.isEmpty()) {throw new RuntimeException(Your stack is empty.);}return this.stackMin.peek();}}public static class MyStack2 {private StackInteger stackData;private StackInteger stackMin;public MyStack2() {this.stackData new StackInteger();this.stackMin new StackInteger();}public void push(int newNum) {if (this.stackMin.isEmpty()) {this.stackMin.push(newNum);} else if (newNum this.getmin()) {this.stackMin.push(newNum);} else {int newMin this.stackMin.peek();this.stackMin.push(newMin);}this.stackData.push(newNum);}public int pop() {if (this.stackData.isEmpty()) {throw new RuntimeException(Your stack is empty.);}this.stackMin.pop();return this.stackData.pop();}public int getmin() {if (this.stackMin.isEmpty()) {throw new RuntimeException(Your stack is empty.);}return this.stackMin.peek();}}
用两个栈实现一个队列
public class Code06_TwoStacksImplementQueue {public static class TwoStacksQueue {public StackInteger stackPush;public StackInteger stackPop;public TwoStacksQueue() {stackPush new StackInteger();stackPop new StackInteger();}// push栈向pop栈倒入数据private void pushToPop() {if (stackPop.empty()) {while (!stackPush.empty()) {stackPop.push(stackPush.pop());}}}public void add(int pushInt) {stackPush.push(pushInt);pushToPop();}public int poll() {if (stackPop.empty() stackPush.empty()) {throw new RuntimeException(Queue is empty!);}pushToPop();return stackPop.pop();}public int peek() {if (stackPop.empty() stackPush.empty()) {throw new RuntimeException(Queue is empty!);}pushToPop();return stackPop.peek();}}
}用两个队列实现一个栈
public class Code07_TwoQueueImplementStack {public static class TwoQueueStackT {public QueueT queue;public QueueT help;public TwoQueueStack() {queue new LinkedList();help new LinkedList();}public void push(T value) {queue.offer(value);}public T poll() {while (queue.size() 1) {help.offer(queue.poll());}T ans queue.poll();QueueT tmp queue;queue help;help tmp;return ans;}public T peek() {while (queue.size() 1) {help.offer(queue.poll());}T ans queue.poll();help.offer(ans);QueueT tmp queue;queue help;help tmp;return ans;}public boolean isEmpty() {return queue.isEmpty();}}
}递归
用递归求数组求arr中的最大值
public class Code08_GetMax {// 求arr中的最大值public static int getMax(int[] arr) {return process(arr, 0, arr.length - 1);}// arr[L..R]范围上求最大值 L ... R Npublic static int process(int[] arr, int L, int R) {// arr[L..R]范围上只有一个数直接返回base caseif (L R) { return arr[L];}// L...R 不只一个数// mid (L R) / 2int mid L ((R - L) 1); // 中点 1int leftMax process(arr, L, mid);int rightMax process(arr, mid 1, R);return Math.max(leftMax, rightMax);}}log(b,a) 是log 以 b 为底 a 的对数
