- 二、一些基本的数据结构及 *** 作
- 1、链表数据结构
- 2、对一个链表进行翻转
- 3、给定一个值，删除链表中与该值相同的所有节点
- 4、用数组实现栈
- 5、用已有栈结构实现pop、push、getMin都是常数的 *** 作
- 6、用数组实现队列
- 7、用队列实现栈
- 8、用栈实现队列
- 9、Master公式（计算递归时间复杂度）
- 10、哈希表和有序表
- 10.1 哈希表
- 10.2 有序表
- 包括一个数值域和指向下一个节点的引用
package list; public class Node2、对一个链表进行翻转{ public T value; public Node next; public Node(T value) { this.value = value; this.next = null; } }
- 思路：新建立一个链表，对原链表依次遍历每个位置采用头插法插入到新链表的头部，最后返回新链表的头，采用三个变量。
- pre ：新链表的头结点
- head：原链表的头结点
- next：原链表下一个待翻转节点
package list;
public class ReverseList {
public static Node reverseList(Node head){
//做一些边界处理
if(head == null || head.next == null){
return head;
}
//pre 新链表的头结点
Node pre = null;
//next 记录原链表的下一个待翻转节点
Node next = null;
while (head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
- 双向链表同理，只需要在更改一个last指针即可
- 必须带有返回值，因为可能删除第一个节点
package list;
public class DeleteElement {
public static Node deletevalue(Node head, T value) {
//边界处理
if (head == null) {
return head;
}
//使head来到第一个不需要删除的位置
while (head != null) {
if (!head.value.equals(value)) {
break;
}
head = head.next;
}
//1.对于head == null，即链表全部删除，这是返回head 直接为null
//2.对于head != null，从该位置开始，遍历整个链表，删除对于节点
//删除某个位置元素需要前一个节点
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value.equals(value)) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
4、用数组实现栈
- 栈：先进后出，加入和d出都是在栈顶
- push、pop、peek都是常数 *** 作
package stack; public class ArrayToStack5、用已有栈结构实现pop、push、getMin都是常数的 *** 作{ private V[] data; private int size; public ArrayToStack(int size) { data = (V[]) new Object[size]; this.size = 0; } public boolean isEmpty(){ return size == 0; } public boolean isFull(){ return data.length == size; } public int size(){ return size; } public boolean push(V value){ if(!isFull()){ data[size++] = value; return true; } return false; } public V pop() throws Exception { if(isEmpty()){ throw new Exception("当前栈为空......"); } return data[--size]; } public V peek() throws Exception { if(isEmpty()){ throw new Exception("当前栈为空......"); } return data[size - 1]; } }
- getMIn为d出当前栈的最小元素
- 思路：准备两个栈，一个正常栈，一个最小栈。每次待加入元素若比最小栈顶的元素小则两个栈都加入该元素，若待加入元素大与最小栈顶元素则最小栈仍然加入它的栈顶元素，这样保证最小栈永远为当前栈里的最小元素。
package stack;
import java.util.Stack;
public class MinStack{
private Stack stack;
private Stack minStack;
public MinStack() {
this.stack = new Stack<>();
this.minStack = new Stack<>();
}
public Integer getMin() throws Exception {
if(minStack.isEmpty()){
throw new Exception("当前栈为空......");
}
return minStack.peek();
}
public Integer pop(){
minStack.pop();
return stack.pop();
}
public void push(Integer value) throws Exception {
if(stack.isEmpty()){
minStack.push(value);
}else if(value < getMin()){
minStack.push(value);
}else {
minStack.push(minStack.peek());
}
stack.push(value);
}
}
6、用数组实现队列
- 循环利用数组实现队列
- 加入两个辅助遍历pushIndex和popIndex记录下次出队和入队的位置，这样不用每次都进行判断
package queue; public class ArrayToQueue7、用队列实现栈{ //存储真实元素 private V[] data; //存储队列的大小 private int size; //队列的最大容量 private int limit; //下一次待插入位置 private int pushIndex; //下一次d出位置 private int pollIndex; public ArrayToQueue(int limit) { this.limit = limit; this.size = 0; data = (V[]) new Object[limit]; pollIndex = 0; pushIndex = 0; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == limit; } public void push(V value) throws Exception { if (isFull()) { throw new Exception("当前队列已满......"); } size++; data[pushIndex] = value; //每次只能从数组头部出队，尾部入队列，所有当尾部满后但头部还有位置就可以在头部进行插入 pushIndex = (pushIndex + 1) % limit; } public V poll() throws Exception { if (isEmpty()) { throw new Exception("当前队列为空......"); } size--; V ans = data[pollIndex]; pollIndex = (pollIndex + 1) % limit; return ans; } }
- 队列先进先出，栈先进后出
- 思路：两个队列。一个queue，一个help。每次元素进入help队列，这时候把queue队列的元素依次插入help队列尾部，在互换queue和help的引用。
package stackandqueue; import java.util.linkedList; import java.util.Queue; public class QueueToStack{ private Queue queue; private Queue help; public QueueToStack() { queue = new linkedList<>(); help = new linkedList<>(); } public void push(V value){ help.offer(value); while (!queue.isEmpty()){ help.offer(queue.poll()); } Queue tmp = queue; queue = help; help = tmp; } public V poll(){ return queue.poll(); } }
- 上面做法是在每次加入时进行元素转换，下面还可以用在d出时进行元素移动
package stackandqueue;
import java.util.linkedList;
import java.util.Queue;
public class QueueToStackChange {
public class QueueToStack {
private Queue queue;
private Queue help;
public QueueToStack() {
queue = new linkedList<>();
help = new linkedList<>();
}
public void push(V value) {
queue.offer(value);
}
public V poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
V ans = queue.poll();
Queue tmp = queue;
queue = help;
help = tmp;
return ans;
}
}
}
8、用栈实现队列
- 栈：先进后出
- 队列：先进先出
- 思路：用两个栈，一个push栈，一个pop栈。需要加入时元素从push加入，d出时检查pop栈是否为空，不空直接返回pop栈顶元素，空的话需要将push栈的元素d到pop中再从pop中d出，感兴趣可以自己画图理解，这里不再画图。
package stackandqueue; import java.util.Stack; public class StackToQueue9、Master公式（计算递归时间复杂度）{ private Stack pushStack; private Stack popStack; public StackToQueue() { popStack = new Stack<>(); pushStack = new Stack<>(); } public boolean isEmpty(){ return pushStack.isEmpty() && popStack.isEmpty(); } public void push(V value){ pushStack.push(value); } public V poll() throws Exception { if(isEmpty()){ throw new Exception("当前队列为空......"); } if(popStack.isEmpty()){ while (!pushStack.isEmpty()){ popStack.push(pushStack.pop()); } } return popStack.pop(); } }
- 对于类似 T(N) = aT(N/b) + O(Nd) 的递推形式而言(即子问题规模一致)
- log(ba) < d ,O(Nd)
- log(ba) > d ,O(Nlog(ba))
- log(ba) = d ,O(NdlogN)
- 增删改查都是O(1) *** 作
- 哈希表的基础类型：String、基础类型及其包装类在Hash表下按值传递
- 在Java中为一个接口：TreeMap（用红黑树实现）
- 红黑树、avl、sb树、跳表N
- CRUD时间复杂度O(logN)
- 自定义类型需要重写排序算法
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）