《알고리즘 노트》 2.체인 테이블, 창고, 대기열, 귀속, 해시 테이블, 순서 테이블
체인 테이블, 창고, 대기열, 귀속, 해시
체인 테이블
단방향 체인 테이블
단방향 체인 테이블의 노드 구조(일반형으로 할 수 있음):
public 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;
}
}
싱글 체인 시계 간단한 연습
package class02;
import java.util.ArrayList;
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;
}
}
// ，
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;
}
// ，
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 static Node testReverseLinkedList(Node head) {
if (head == null) {
return null;
}
ArrayList list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
list.get(0).next = null;
int N = list.size();
for (int i = 1; i < N; i++) {
list.get(i).next = list.get(i - 1);
}
return list.get(N - 1);
}
public static DoubleNode testReverseDoubleList(DoubleNode head) {
if (head == null) {
return null;
}
ArrayList list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
list.get(0).next = null;
DoubleNode pre = list.get(0);
int N = list.size();
for (int i = 1; i < N; i++) {
DoubleNode cur = list.get(i);
cur.last = null;
cur.next = pre;
pre.last = cur;
pre = cur;
}
return list.get(N - 1);
}
public static Node generateRandomLinkedList(int len, int value) {
int size = (int) (Math.random() * (len + 1));
if (size == 0) {
return null;
}
size--;
Node head = new Node((int) (Math.random() * (value + 1)));
Node pre = head;
while (size != 0) {
Node cur = new Node((int) (Math.random() * (value + 1)));
pre.next = cur;
pre = cur;
size--;
}
return head;
}
public static DoubleNode generateRandomDoubleList(int len, int value) {
int size = (int) (Math.random() * (len + 1));
if (size == 0) {
return null;
}
size--;
DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
DoubleNode pre = head;
while (size != 0) {
DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
pre.next = cur;
cur.last = pre;
pre = cur;
size--;
}
return head;
}
// ，
public static boolean checkLinkedListEqual(Node head1, Node head2) {
while (head1 != null && head2 != null) {
if (head1.value != head2.value) {
return false;
}
head1 = head1.next;
head2 = head2.next;
}
return head1 == null && head2 == null;
}
// ，
public static boolean checkDoubleListEqual(DoubleNode head1, DoubleNode head2) {
boolean null1 = head1 == null;
boolean null2 = head2 == null;
if (null1 && null2) {
return true;
}
if (null1 ^ null2) {
return false;
}
if (head1.last != null || head2.last != null) {
return false;
}
DoubleNode end1 = null;
DoubleNode end2 = null;
while (head1 != null && head2 != null) {
if (head1.value != head2.value) {
return false;
}
end1 = head1;
end2 = head2;
head1 = head1.next;
head2 = head2.next;
}
if (head1 != null || head2 != null) {
return false;
}
while (end1 != null && end2 != null) {
if (end1.value != end2.value) {
return false;
}
end1 = end1.last;
end2 = end2.last;
}
return end1 == null && end2 == null;
}
public static void main(String[] args) {
int len = 50;
int value = 100;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
Node node1 = generateRandomLinkedList(len, value);
Node reverse1 = reverseLinkedList(node1);
Node back1 = testReverseLinkedList(reverse1);
if (!checkLinkedListEqual(node1, back1)) {
System.out.println("oops!");
break;
}
DoubleNode node2 = generateRandomDoubleList(len, value);
DoubleNode reverse2 = reverseDoubleList(node2);
DoubleNode back2 = testReverseDoubleList(reverse2);
if (!checkDoubleListEqual(node2, back2)) {
System.out.println("oops!");
break;
}
}
System.out.println("finish!");
}
}
package class02;
public class Code02_DeleteGivenValue {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
// ， ，
public static Node removeValue(Node head, int num) {
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
// head
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;
}
}
Tips: 자바에서도 메모리 유출이 발생할 수 있습니다. CPP와 달리 CPP의 메모리 유출은 우리가 메모리 공간을 열어서 방출을 잊어버릴 수도 있습니다.자바의 메모리 유출은 프로그램의 변수의 생존 주기 때문에 일어날 수 있다. 만약에 이 프로그램이 정시 작업과 비슷한 7*24시간 동안 끊임없이 실행된다면 신청한 변수(데이터 구조)는 제때에 방출되지 않을 수 있다.만약 안에 불필요한 변수를 첨가하는 것을 주의하지 않는다면, 이러한 변수는 메모리 유출이다
스택, 큐
대기열: 데이터 우선 출력, 대기
package class02;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code03_DoubleEndsQueueToStackAndQueue {
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 static boolean isEqual(Integer o1, Integer o2) {
if (o1 == null && o2 != null) {
return false;
}
if (o1 != null && o2 == null) {
return false;
}
if (o1 == null && o2 == null) {
return true;
}
return o1.equals(o2);
}
public static void main(String[] args) {
int oneTestDataNum = 100;
int value = 10000;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
MyStack myStack = new MyStack<>();
MyQueue myQueue = new MyQueue<>();
Stack stack = new Stack<>();
Queue queue = new LinkedList<>();
for (int j = 0; j < oneTestDataNum; j++) {
int nums = (int) (Math.random() * value);
if (stack.isEmpty()) {
myStack.push(nums);
stack.push(nums);
} else {
if (Math.random() < 0.5) {
myStack.push(nums);
stack.push(nums);
} else {
if (!isEqual(myStack.pop(), stack.pop())) {
System.out.println("oops!");
}
}
}
int numq = (int) (Math.random() * value);
if (stack.isEmpty()) {
myQueue.push(numq);
queue.offer(numq);
} else {
if (Math.random() < 0.5) {
myQueue.push(numq);
queue.offer(numq);
} else {
if (!isEqual(myQueue.poll(), queue.poll())) {
System.out.println("oops!");
}
}
}
}
}
System.out.println("finish!");
}
}
수조 실현은 창고에 대해 특히 간단하다. 대열에 대해서는 다음과 같다.
package class02;
public class Code04_RingArray {
public static class MyQueue {
//
private int[] arr;
//
private int pushi;
//
private int polli;
//
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， ， ringbuffer
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
}
창고, 대열 흔히 볼 수 있는 면접 문제
1. 특수한 창고를 실현하고 기본 기능을 바탕으로 창고의 최소 요소를 되돌려주는 기능을 실현한다.
1. pop,push,getMin 작업의 시간 복잡도는 모두 O(1)
2. 디자인된 창고 유형은 기존의 창고 구조를 사용할 수 있다.
사고방식: 두 개의 창고, 한 개의 데이터 창고, 한 개의min 창고를 준비한다.데이터는 데이터 창고를 압축하고 min 창고는 min 창고 꼭대기 요소를 비교한다. 누가 작으면 누구를 추가한다.이렇게 하면 데이터 창고와min 창고는 동시적으로 상승하고 원소의 개수가 똑같이 많으며min 창고의 창고 꼭대기는 데이터 창고의 모든 원소 중 가장 작은 것이다.데이터가 데이터 창고에서 팝업됩니다. 우리는 동시에min창고를 팝업합니다. 개수가 같을 것을 보증합니다. min창고에서 팝업하는 것이 최소값입니다.
package class02;
import java.util.Stack;
public class Code05_GetMinStack {
public static class MyStack1 {
private Stack stackData;
private Stack stackMin;
public MyStack1() {
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);
}
//
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 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.");
}
// ， ， ， data
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 static void main(String[] args) {
MyStack1 stack1 = new MyStack1();
stack1.push(3);
System.out.println(stack1.getmin());
stack1.push(4);
System.out.println(stack1.getmin());
stack1.push(1);
System.out.println(stack1.getmin());
System.out.println(stack1.pop());
System.out.println(stack1.getmin());
System.out.println("=============");
MyStack1 stack2 = new MyStack1();
stack2.push(3);
System.out.println(stack2.getmin());
stack2.push(4);
System.out.println(stack2.getmin());
stack2.push(1);
System.out.println(stack2.getmin());
System.out.println(stack2.pop());
System.out.println(stack2.getmin());
}
}
2. 어떻게 창고 구조로 대열 구조를 실현하고, 어떻게 대열 구조로 창고 구조를 실현하는가
이 두 가지 구조의 응용은 정말 너무 많아서 문제를 풀 때 대량으로 볼 수 있다
/**
*
**/
package class02;
import java.util.Stack;
public class Code06_TwoStacksImplementQueue {
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()) {
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 static void main(String[] args) {
TwoStacksQueue test = new TwoStacksQueue();
test.add(1);
test.add(2);
test.add(3);
System.out.println(test.peek());
System.out.println(test.poll());
System.out.println(test.peek());
System.out.println(test.poll());
System.out.println(test.peek());
System.out.println(test.poll());
}
}
/**
*
**/
package class02;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code07_TwoQueueImplementStack {
public static class TwoQueueStack {
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();
}
}
public static void main(String[] args) {
System.out.println("test begin");
TwoQueueStack myStack = new TwoQueueStack<>();
Stack test = new Stack<>();
int testTime = 1000000;
int max = 1000000;
for (int i = 0; i < testTime; i++) {
if (myStack.isEmpty()) {
if (!test.isEmpty()) {
System.out.println("Oops");
}
int num = (int) (Math.random() * max);
myStack.push(num);
test.push(num);
} else {
if (Math.random() < 0.25) {
int num = (int) (Math.random() * max);
myStack.push(num);
test.push(num);
} else if (Math.random() < 0.5) {
if (!myStack.peek().equals(test.peek())) {
System.out.println("Oops");
}
} else if (Math.random() < 0.75) {
if (!myStack.poll().equals(test.pop())) {
System.out.println("Oops");
}
} else {
if (myStack.isEmpty() != test.isEmpty()) {
System.out.println("Oops");
}
}
}
}
System.out.println("test finish!");
}
}
귀속
1. 사상적 이해의 귀착
2. 실현 차원에서 이해의 귀속
예:
배열arr[L...R]의 최대값을 구하고 귀속 방법으로 어떻게 실현합니까
1. [L...R] 범위를 좌우로 나눈다.왼쪽 [L...Mid], 오른쪽 [mid+1...R] 2, 왼쪽 부분은 최대치, 오른쪽 부분은 최대치 3, [L...R] 범위의 최대치, 바로max{왼쪽 부분은 최대치, 오른쪽 부분은 최대치}
2단계는 귀속 과정으로 범위에서 단지 하나의 수만 있으면 다시 귀속할 필요가 없다
package class02;
public class Code08_GetMax {
// 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) {
if (L == R) { // arr[L..R] ， ，base case
return arr[L];
}
int mid = L + ((R - L) >> 1); //
//
int leftMax = process(arr, L, mid);
//
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}
}
시스템에 귀속되는 것은 어떻게 실현됩니까?귀환은 실제로 시스템 창고를 이용하여 실현된 것이다.현재 호출 현장을 저장하고 하위 문제를 실행하며 하위 문제의 귀환은 현장에 필요한 매개 변수로 채우고 최종적으로 창고 지붕을 복원하는 현장을 구축하여 귀환한다.그래서 귀환 행위는 현학이 아니기 때문에 어떤 귀환도 비귀환 실현으로 바꿀 수 있다. 우리 스스로 창고를 압축하여 교체하는 등 실현하면 된다.
귀속 행위의 시간 복잡도
만족하다
T(N) = aT(N/b) + O(N^d)
그중:a,b,d는 상수
공식에 의하면 하위 문제의 규모는 일치한다. 이 하위 문제는 a회 호출되었고 N/b는 하위 문제의 규모를 대표하며 O(N^d)는 귀속 호출을 제외하고 남은 시간의 복잡도를 제거한다.
예를 들어 상술한 문제의 귀착은 [L...R]에 N개의 수가 있는데 첫 번째 하위 문제의 규모는 N/2이고 두 번째 하위 문제의 규모도 N/2이다.하위 문제가 두 번 호출되었다.액수는 복잡도 O(1)이고 공식은 다음과 같다.
T(N) = 2T(N/2) + O(N^0)
결론: 만약에 우리의 귀환이 이런 공식을 만족시킨다면 귀환의 시간 복잡도(Master 공식)는
logb^a > d => O(N ^ (logb^a))
logb^a < d => O(N^d)
logb^a == d => O(N^d * logN)
그러면 상술한 문제의 a=2,b=2,d=0은 제1조를 만족시키고 귀속 시간의 복잡도는 O(N)이다.
HashMap, HashSet
Hash표의 첨삭 수정은 사용할 때 일률적으로 시간 복잡도는 O(1)이라고 여긴다
Java에서 int double float 기본 형식을 값에 따라 전달합니다.Integer, Double, Float는 인용에 따라 전달된 것으로 포장 유형의 값이 같은지 비교하고 equals 방법을 사용합니다.
주의: 자바 베이스에서 포장류는 범위가 비교적 작으면 베이스는 값 전달을 사용한다. 예를 들어 Integer는 범위가 -128~127사이에 있으면 값에 따라 전달한다.
그러나Hash표에서 포장 유형의 키라도 우리는 일률적으로 값에 따라 전달한다. 예를 들어Hash가put과 같은 키의 값을 가지면 두 개의 값이 같은 키가 생기지 않고 덮어쓰기 작업을 한다.그러나Hash표는 항상 값에 따라 전달되는 것이 아니라 포장 유형에 대한 것이다. 만약에 우리가 정의한 인용 유형이라면 인용에 따라 전달한다
순서표 TreeMap, TreeSet
순서표는 해시표보다 기능이 많지만, 순서표의 많은 조작 시간 복잡도는 O(logN)이다.
질서표의 밑바닥에는 AVL 트리, SB 트리, 빨간색과 검은색 트리, 다이얼 테이블 등 많은 구조가 실현될 수 있다.그 중에서 AVL, SB, 빨간색과 검은색은 모두 각자의 균형성을 갖춘 검색 두 갈래 나무이다
밸런스 두 갈래 나무는 시시각각 자신의 밸런스를 유지하기 때문에 O(logN)로 조작한다.잠시 이해하고, 나중에 따로 정리할게요.
재배열 기능을 충족시켜 밑바닥 트리의 균형을 유지하기 때문에 기초 유형과 포장 유형의 키는 직접 값에 따라 비교한다. 그러나 만약에 우리의 키가 자신이 정의한 유형이라면 우리는 스스로 비교 규칙(비교기)을 제정하여 밑바닥 트리가 비교 후의 균형을 유지하도록 해야 한다.
package class02;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;
public class HashMapAndSortedMap {
public static class Node{
public int value;
public Node(int v) {
value = v;
}
}
public static void main(String[] args) {
// 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 a = 100000;
int b = 100000;
System.out.println(a == b);
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);
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("======================");
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(treeMap.firstKey());
System.out.println(treeMap.lastKey());
// <= 4
System.out.println(treeMap.floorKey(4));
// >= 4
System.out.println(treeMap.ceilingKey(4));
// O(logN)
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
