- 前言
- 一、链表
- 1.单向链表
- 2.双向链表
- 3.练习
- 二、Java和c++在内存释放上的问题
- 三、栈和队列
- 1.逻辑概念
- 2.栈和队列的实际实现
- 四、栈和队列的常见面试题
- 1.pop、push、getMin操作的时间复杂度都是 O(1)。
- 2.如何用栈结构实现队列结构
- 3.如何用队列结构实现栈结构
- 五、递归
- 1.怎么从思想上理解递归
- 2.怎么从实际实现的角度出发理解递归
- 3.求数组arr[L..R]中的最大值，怎么用递归方法实现。
- 六、Master公式
- 七、哈希表
- 八、有序表
- 总结
前言
数据结构和算法笔记
一、链表 1.单向链表
单向链表节点结构（可以实现成范型）
public class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
双向链表节点结构
public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
3.练习单链表和双链表如何反转
// head
// a -> b -> c -> null
// c -> b -> a -> null
public 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;
}
把给定值都删除
// 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 != null
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
二、Java和c++在内存释放上的问题
Jvm会自动释放1节点，而c++不会，必须手动释放。
栈：数据先进后出，犹如弹匣
队列：数据先进先出，好似排队
2.栈和队列的实际实现双向链表实现
public static class Node{ public T value; public Node last; public Node next; public Node(T data) { value = data; } } public static class DoubleEndsQueue { public Node head; public Node tail; public void addFromHead(T value) { Node cur = new Node (value); if (head == null) { head = cur; tail = cur; } else { cur.next = head; head.last = cur; head = cur; } } public void addFromBottom(T value) { Node cur = new Node (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; } Node 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; } Node 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 MyStack { private DoubleEndsQueue queue; public MyStack() { queue = new DoubleEndsQueue (); } public void push(T value) { queue.addFromHead(value); } public T pop() { return queue.popFromHead(); } public boolean isEmpty() { return queue.isEmpty(); } } public static class MyQueue { private DoubleEndsQueue queue; public MyQueue() { queue = new DoubleEndsQueue (); } 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;// end
private int polli;// begin
private 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;
}
}
}
四、栈和队列的常见面试题
1.pop、push、getMin操作的时间复杂度都是 O(1)。
两个栈即可实现。
public static class MyStack2 {
private Stack stackData;
private Stack stackMin;
public MyStack2() {
this.stackData = new Stack();
this.stackMin = new Stack();
}
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();
}
}
2.如何用栈结构实现队列结构
两个栈实现队列
public static class TwoStacksQueue {
public Stack stackPush;
public Stack stackPop;
public TwoStacksQueue() {
stackPush = new Stack();
stackPop = new Stack();
}
// push栈向pop栈倒入数据
private void pushToPop() {
if (stackPop.empty()) {//pop栈必须为空
while (!stackPush.empty()) {//必须将push栈倒完
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();
}
}
3.如何用队列结构实现栈结构
两个队列实现栈
public static class TwoQueueStack五、递归 1.怎么从思想上理解递归{ public Queue queue; public Queue 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(); Queue 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); Queue tmp = queue; queue = help; help = tmp; return ans; } public boolean isEmpty() { return queue.isEmpty(); } }
画个递归的思维脑图
每次调用递归函数，系统进行环境保存压入系统栈中。
3.求数组arr[L…R]中的最大值，怎么用递归方法实现。1）将[L…R]范围分成左右两半。左：[L…Mid] 右[Mid+1…R]
2）左部分求最大值，右部分求最大值
3） [L…R]范围上的最大值，是max{左部分最大值，右部分最大值}
注意：2）是个递归过程，当范围上只有一个数，就可以不用再递归了
// 求arr中的最大值
public static int getMax(int[] arr) {
return process(arr, 0, arr.length - 1);
}
// arr[L..R]范围上求最大值 L ... R N
public static int process(int[] arr, int L, int R) {
// arr[L..R]范围上只有一个数，直接返回，base case
if (L == R) {
return arr[L];
}
// L...R 不只一个数
// mid = (L + R) / 2
int mid = L + ((R - L) >> 1); // 中点 1
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}
六、Master公式
T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数)
的递归函数，可以直接通过Master公式来确定时间复杂度
如果 log(b,a) < d，复杂度为O(N^d)
如果 log(b,a) > d，复杂度为O(N^log(b,a))
如果 log(b,a) == d，复杂度为O(N^d * logN)
1)哈希表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用HashSet结构
3)如果既有key，又有伴随数据value，可以使用HashMap结构
4)有无伴随数据，是HashMap和HashSet唯一的区别，实际结构是一回事
5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为 O(1)，但是常数时间比较大
6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小
7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节
public static class Node {
public int value;
public Node(int v) {
value = v;
}
}
public static class Zuo {
public int value;
public Zuo(int v) {
value = v;
}
}
public static void main(String[] args) {
HashMap test = new HashMap<>();
Integer a = 19000000;
Integer b = 19000000;
System.out.println(a == b);
test.put(a, "我是3");
System.out.println(test.containsKey(b));
Zuo z1 = new Zuo(1);
Zuo z2 = new Zuo(1);
HashMap test2 = new HashMap<>();
test2.put(z1, "我是z1");
System.out.println(test2.containsKey(z2));
// UnSortedMap
HashMap map = new HashMap<>();
map.put(1000000, "我是1000000");
map.put(2, "我是2");
map.put(3, "我是3");
map.put(4, "我是4");
map.put(5, "我是5");
map.put(6, "我是6");
map.put(1000000, "我是1000001");
System.out.println(map.containsKey(1));
System.out.println(map.containsKey(10));
System.out.println(map.get(4));
System.out.println(map.get(10));
map.put(4, "他是4");
System.out.println(map.get(4));
map.remove(4);
System.out.println(map.get(4));
// key
HashSet set = new HashSet<>();
set.add("abc");
set.contains("abc");
set.remove("abc");
// 哈希表，增、删、改、查，在使用时，O（1）！！！！！！！！！！！！！！！！！！！
System.out.println("=====================");
int z = 1000;
int zz = 1000;
System.out.println(z == zz);
Integer c = 100000;
Integer d = 100000;
System.out.println(c.equals(d));
Integer e = 127; // - 128 ~ 127
Integer f = 127;
System.out.println(e == f);
Integer e1 = 1271; // - 128 ~ 127
Integer f1 = 1271;
System.out.println(e1 == f1);
//非基础类型的key按照引用传递。
HashMap map2 = new HashMap<>();
Node node1 = new Node(1);
Node node2 = node1;
map2.put(node1, "我是node1");
map2.put(node2, "我是node1");
System.out.println(map2.size());
System.out.println("======================");
八、有序表
1)有序表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用TreeSet结构
3)如果既有key，又有伴随数据value，可以使用TreeMap结构
4)有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
5)有序表把key按照顺序组织起来，而哈希表完全不组织
// TreeMap 有序表：接口名
// 红黑树、avl、sb树、跳表
// O(logN)
System.out.println("有序表测试开始");
TreeMap treeMap = new TreeMap<>();
treeMap.put(3, "我是3");
// treeMap.put(4, "我是4");
treeMap.put(8, "我是8");
treeMap.put(5, "我是5");
treeMap.put(7, "我是7");
treeMap.put(1, "我是1");
treeMap.put(2, "我是2");
System.out.println(treeMap.containsKey(1));
System.out.println(treeMap.containsKey(10));
System.out.println(treeMap.get(4));
System.out.println(treeMap.get(10));
treeMap.put(4, "他是4");
System.out.println(treeMap.get(4));
// treeMap.remove(4);
System.out.println(treeMap.get(4));
System.out.println("新鲜：");
System.out.println(treeMap.firstKey());
System.out.println(treeMap.lastKey());
// <= 4
System.out.println(treeMap.floorKey(4));
// >= 4
System.out.println(treeMap.ceilingKey(4));
// O(logN)
总结
