Summary of Data Structure and Algorithm-Part One

Summary of Data Structure and Algorithm-Part One

1. The 10 most commonly used data structures

  1. Array
  2. Linked list
  3. Stack
  4. queue
  5. Hash table
  6. Binary tree
  7. heap
  8. Skip table
  9. Figure
  10. Trie tree

2. The 10 most commonly used algorithms

  1. Recursion
  2. Sort
  3. Binary search
  4. search for
  5. Hash algorithm
  6. how are you
  7. Divide and conquer algorithm
  8. Backtracking algorithm
  9. Dynamic programming
  10. String matching algorithm

3. The relationship between data structure and algorithm

  1. Data structure is how data is organized and serves algorithms.
  2. Algorithms are to perform operations on specific data structures.

4. Common time complexity

  1. O(1)
  2. O(logn)
  3. O(n)
  4. O(nlogn)
  5. O to the k power
  6. Exponential order O (2 to the nth power)
  7. Factorial order O(n!)

5.Time complexity is called progressive time complexity, which represents the relationship between the execution time of the algorithm and the growth of the data scale.

6.Space complexity is called progressive space complexity, which represents the relationship between the storage space of the algorithm and the growth of the data scale.

7. Linear table

  1. The linear table is the structure of the data row like a line.
  2. The data on each linear table can only have forward and backward directions at most.
  3. Arrays, linked lists, queues, and stacks are all linear lists.

8. Nonlinear table

  1. In a non-linear table, the data is not a simple context
  2. Binary trees, heaps, and graphs are all non-linear tables

9. Array

  1. An array is a linear table data structure that uses a set of continuous memory space to store a set of data of the same type.
  2. Contiguous memory space and the same type of data
    • Advantages: Allow the array to be randomly accessed/randomly access the array elements based on the subscript.
    • Disadvantages: Adding and deleting elements in the array requires a large amount of data movement in order to ensure memory continuity.
  3. The search time complexity of the array is not O(1), even if it is a sorted array, it takes O(logn) to find a certain data
  4. Advantages of container/ArrayList and array comparison
    • ArrayList encapsulates many array operations for easy use
    • ArrayList supports dynamic expansion
      • Dynamic expansion still inevitably moves data in memory.If the amount of data can be determined in advance, the data size should be specified when creating an ArrayList.
  5. Disadvantages of container/ArrayList and array comparison
    • ArrayList cannot store basic types. To store basic types, boxing is involved, and unboxing has performance loss
    • The amount of data is known, and the operation of the data is very simple. Most methods of ArrayList are not involved, and arrays can be used.
  6. How to choose container/ArrayList and array
    • For business development, you can use ArrayList directly, which is simple. Lower performance has almost no impact
    • The underlying development compares the network framework, the performance must be optimized to the extreme, and the array must be used.

10. Linked list: A group of scattered memory blocks are connected together through pointers.

  1. Single list
    Node head = node0; Node tail = noden; head.next = node1; ** tail.next = null ; copy the code
  2. Circular linked list
    Node head = node0; Node tail = noden; head.next = node1; ** tail.next = head; Copy code
  3. Doubly linked list
    Node head = node0; Node tail = noden; head.next = node1; head.pre = null ; ** tail.next = null ; tail.pre = noden- 1 ; copy the code
  4. Doubly circular linked list
    Node head = node0; Node tail = noden; head.next = node1; head.pre = tail; ** tail.next = head; tail.pre = noden- 1 ; copy the code

11. Comparison of array and linked list

  1. The time complexity of linked list insertion and deletion is O(1), and the time complexity of random access is O(n).
  2. The time complexity of array insertion and deletion is O(n), and the time complexity of random access is O(1).
  3. The array uses continuous space on the memory, which is friendly to the CPU cache, and the data in the linked list is not continuous in the memory, and it is not friendly to the CPU cache.
  4. The disadvantage of the array is that the size is fixed, and it occupies the full space after declaration.If the array is too large, it will waste memory, and even directly OOM.If it is too small, the expansion of the array will affect performance.
  5. The linked list naturally supports dynamic expansion. However, each element in the linked list must store the next and pre pointers, and a single element takes up more memory.
  6. If the number of data is controllable, the performance of using arrays is better. Avoid storing next and pre pointers to occupy additional space.

12. Several problems with linked lists

1. Single linked list implements LRU

public class LRULinkedList < T > { class Node < T > { public T data; public Node next; public Node (T data, Node next) { super (); this .data = data; this .next = next; } } private static int DEFAULT_CAPACITY = 6 ; private int capacity = DEFAULT_CAPACITY; private int count = 0 ; private Node head = null ; public LRULinkedList ( int capacity) { this .capacity = capacity; } public boolean isFull () { return count == capacity; } public Node createNode (T data) { Node node = new Node(data, null ); return node; } public void access (T data) { if (data == null ){ throw new IllegalArgumentException( "The accessed element cannot be empty!" ); } if (head == null ){ head = createNode(data); count++; return ; } if (head.data.equals(data)){ //The head node is the data to be accessed return ; } Node curr = head; while (curr.next != null && !curr.next.data.equals(data)){ curr = curr.next; } if (curr.next != null && curr.next.data.equals(data)){ //The element to be accessed already exists Node target = curr.next; curr.next = target.next; target.next = head; head = target; } else { //The element to be accessed does not exist if (isFull()){ //The linked list is full //Delete the current end node //There is a problem with this writing, print the result: //The current data is: -> 10 -> 8 -> 6 -> 4 -> 2 -> 9 -> 7 -> 5 -> 3 -> 1 //Node c = head; //while(c != null && c.next != null) { //c = c.next; //} //c = null; Node c = head; while (c != null && c.next != null && c.next.next != null ) { c = c.next; } c.next = null ; addHead(data); } else { //The linked list is not full //Add the head node directly addHead(data); count++; } } } private void addHead (T data) { Node target = createNode(data); target.next = head; head = target; } private void printAll () { System.out.print( "The current data is: "); Node curr = head; while (curr != null ) { System.out.print( "->" + curr.data); curr = curr.next; } } public static void main (String[] args) { LRULinkedList<Integer> list = new LRULinkedList<>( 6 ); list.access( 1 ); list.access( 3 ); list.access( 5 ); list.access( 7 ); list.access( 9 ); list.access( 2 ); list.access( 4 ); list.access( 6 ); list.access( 8 ); list.access( 10 ); list.printAll(); Person a = new Person(); a.name = "a" ; Person b = new Person(); b.name = "b" ; Person c = new Person(); c.name = "c" ; a.friend = b; b.friend = c; //There is a problem with writing like this: friend of b: name:c //try { //c = null; //System.out.println("friend of b:" + b.friend); //} catch (Exception e) { //} //try { //b.friend = null; //System.out.println("b's friend:" + b.friend); //} catch (Exception e) { //} } public static class Person { public String name; public Person friend; @Override public String toString () { return "name:" + name; } } } Copy code

2. The above example leads to a misunderstanding

//A.attr and C both point to the same object B A.attr = B; BInstance C = B; Blanking//C C = null ; //null case A.attr not duplicated code
  • A.attr -> B
  • C -> B
  • C = null, it just breaks the link between the variable name of C and the instance of B, but B is still linked by A.attr. B itself will not be made blank.

3. Joseph issue an Ali T questions: How do I use a line of code to solve the problem of Josephus

3.1. Using arrays to solve
/** * Joseph's problem: use an array to solve */ public class JosephusArray { public static void main (String[] args) { JosephusArray t = new JosephusArray(); int [] arr = new int [ 11 ]; for ( int i = 0 ; i <arr.length; i++) { arr[i] = i + 1 ; } System.out.println( "The value of the array:" ); Arrays.stream(arr).forEach(System.out::println); int result = t.findLastItemData(arr, 3 ); System.out.println( "Final remaining Item value:" + result); } public int findLastItemData ( int [] arr, int k) { if (arr == null || arr.length <= 0 ) { return - 1 ; } if (arr.length == 1 ) { return 0 ; } int length = arr.length; int count = arr.length; int index = 0 ; int step = 0 ; int tagIndex = -1 ; while (count> 1 ) { while (step <k) { if (arr[index] !=- 1 ) { step++; tagIndex = index; } if (index == length- 1 ) { index = 0 ; } else { index++; } } arr[tagIndex] = -1 ; step = 0 ; count--; } while (arr[index] ==- 1 ) { if (index == length- 1 ) { index = 0 ; } else { index++; } } return arr[index]; } } //Print the result: The value of the array: . 1 2 . 3 . 4 . 5 . 6 7 . 8 . 9 10 . 11 final residual value of Item: 7 copy the code
3.2. Use a circular list to solve
public class JosephusLinkedList < T > { public static class Node < T > { public T data; public Node<T> next; public Node (T data) { super (); this .data = data; } } private Node<T> head; private Node<T> tail; public void add (Node<T> node) { if (head == null ) { head = tail = node; head.next = head; } else { tail.next = node; node.next = head; tail = node; } } public void remove (Node<T> node) { if (head == null || node == null ) { return ; } Node curr = head; while (curr.next != node) { curr = curr.next; } if (head.next == head) { head.next = null ; head = tail = null ; return ; } Node next = node.next; curr.next = next; if (node == head) { head = next; } node.next = null ; } public int findLastItemData ( int k) { if (head == null ) { return - 1 ; } Node curr = head; Node pre = null ; int step = 0 ; while (head.next != head) { while (step <k) { pre = curr; curr = curr.next; step++; } remove(pre); step = 0 ; } return ( int ) head.data; } public static void main (String[] args) { JosephusLinkedList<Integer> t = new JosephusLinkedList<Integer>(); for ( int i = 1 ;i<= 11 ;i++) { t.add( new Node<Integer>(i)); } int result = t.findLastItemData( 5 ); System.out.println( "The value of the last remaining item:" + result); } } //print the results: the value of the last remaining items: 8 copy the code

4. Array implements LRU

public class LRUBasedArray < T > { public static int DEFAULT_CAPACITY = 6 ; private int capacity = DEFAULT_CAPACITY; private T[] data; private int count; private Map<T, Integer> positionHolder; public LRUBasedArray ( int capacity) { this .count = 0 ; this .capacity = capacity; this .data = (T[]) new Object[capacity]; this .positionHolder = new HashMap<>(capacity); } public void clear () { positionHolder.clear(); data = (T[]) new Object[capacity]; count = 0 ; } public boolean isFull () { return count == capacity; } public boolean contains (T item) { return positionHolder.containsKey(item); } public void access (T item) { //First determine whether the item already exists boolean contains = contains(item); if (contains) { //Get the index of the item int index = positionHolder.get(item); if (index == 0 ) { data//current to be accessed, is already in the array of the head return ; } else { //The current data to be accessed is not at the head of the array. You need to move the data to the head and move other array elements to the right transferToRight(index); setHead(item); } } else { //Judging whether the array is full boolean isFull = isFull(); if (isFull) { //The array is full //Empty the tail element removeTail(); //Move the element to the right transferToRight(capacity- 1 ); //Insert the head element setHead(item); } else { //The array is not full //Move the element to the right transferToRight(count); //Insert header element setHead(item); //count plus one count++; } } } public void setHead (T item) { data[ 0 ] = item; positionHolder.put(item, 0 ); } public void removeTail () { positionHolder.remove(data[capacity- 1 ]); data[capacity- 1 ] = null ; } public void transferToRight ( int toIndex) { for ( int i = toIndex- 1 ; i >= 0 ; i--) { data[i + 1 ] = data[i]; positionHolder.put(data[i + 1 ], i+ 1 ); } } public void printAll () { for ( int i = 0 ; i <count; i++) { System.out.println( "item" +i+ ":" + data[i]); } } public static void main (String[] args) { LRUBasedArray<Integer> lruBasedArray = new LRUBasedArray<>( 6 ); lruBasedArray.access( 1 ); lruBasedArray.access( 2 ); lruBasedArray.access( 3 ); lruBasedArray.access( 4 ); lruBasedArray.access( 5 ); lruBasedArray.access( 6 ); lruBasedArray.access( 7 ); lruBasedArray.access( 3 ); lruBasedArray.access( 3 ); lruBasedArray.access( 3 ); lruBasedArray.access( 8 ); lruBasedArray.access( 9 ); lruBasedArray.access( 10 ); lruBasedArray.printAll(); } } //Run Results item0: 10 ITEM1: . 9 ITEM2: . 8 Item3: . 3 ITEM4: . 7 ITEM5: . 6 copy the code

5. Custom singly linked list, check whether the character is a palindrome string

public class PalindromeSinglyList < T > { public class Node < T > { public T data; public Node<T> next; public Node (T data, Node<T> next) { super (); this .data = data; this . next = next; } @Override public String toString () { return "Node [data=" + data + "]" ; } } public Node<T> head; public void add (T item) { if (head == null ) { head = new Node<T>(item, null ); return ; } Node<T> tail = head; while (tail.next != null ) { tail = tail.next; } tail.next = new Node<T>(item, null ); } public Node inverseList (Node tail) { Node curr = head; Node next = null ; while (curr.next != tail) { next = curr.next.next; curr.next.next = head; head = curr.next; curr.next = next; } tail.next = head; curr.next = null ; head = tail; return tail; } public boolean compareTwoList (Node leftHead, Node rightHead) { if (leftHead == null || rightHead == null ) { return false ; } while (leftHead != null && rightHead != null && leftHead.data.equals(rightHead.data)) { leftHead = leftHead.next; rightHead = rightHead.next; } return leftHead == null && rightHead == null ; } private void printNode (Node node) { while (node != null ) { System.out.println(node); node = node.next; } } public boolean isPalindrome () { if (head == null ) { //empty list return false ; } if (head.next == null ) { //Only the head element return true ; } if (head.next.next == null ) { //There are only 2 elements return head.data.equals(head.next.data); } //There are >=3 elements //First determine whether the number of elements is odd or even Node slow = head; Node fast = head; while (slow.next != null && fast.next != null && fast.next.next != null ) { slow = slow.next; fast = fast.next.next; } Node leftHead,rightHead; if (fast.next != null ) { //even elements rightHead = slow.next; leftHead = inverseList(slow); } else { //odd number of elements rightHead = slow; leftHead = inverseList(slow); } //Print two Nodes and subsequent Nodes System.out.println( "List elements on the left half:" ); printNode(leftHead); System.out.println( "List elements on the right half:" ); printNode(rightHead); boolean result = compareTwoList(leftHead, rightHead); System.out.println( "Whether the palindrome string:" + result); return result; } public static void main (String[] args) { int [] d1 = new int [] { 1 , 2 , 3 , 4 , 3 , 2 , 1 }; int [] d2 = new int [] { 1 , 2 , 3 , 2 , 1 }; int [] d3 = new int [] { 1 , 2 , 2 , 1 }; int[] d4 = new int [] { 1 , 0 , 1 , 0 }; PalindromeSinglyList list1 = new PalindromeSinglyList(); for ( int item:d1) { list1.add(item); } PalindromeSinglyList list2 = new PalindromeSinglyList(); for ( int item:d2) { list2.add(item); } PalindromeSinglyList list3 = new PalindromeSinglyList(); for ( int item:d3) { list3.add(item); } PalindromeSinglyList list4 = new PalindromeSinglyList(); for ( int item:d4) { list4.add(item); } list1.isPalindrome(); System.out.println( "===============" ); list2.isPalindrome(); System.out.println( "===============" ); list3.isPalindrome(); System.out.println( "===============" ); list4.isPalindrome(); } } //operation result List elements on the left half: Node [data= 4 ] Node [data= 3 ] Node [data= 2 ] Node [data= 1 ] List elements on the right half: Node [data= 4 ] Node [data= 3 ] Node [data= 2 ] Node [data= 1 ] Whether palindrome string: true =============== List elements on the left half: Node [data= 3 ] Node [data= 2 ] Node [data= 1 ] List elements on the right half: Node [data= 3 ] Node [data= 2 ] Node [data= 1 ] Whether palindrome string: true =============== List elements on the left half: Node [data= 2 ] Node [data= 1 ] List elements on the right half: Node [data= 2 ] Node [data= 1 ] Whether palindrome string: true =============== List elements on the left half: Node [data= 0 ] Node [data= 1 ] List elements on the right half: Node [data= 1 ] Node [data= 0 ] Whether palindrome string: false Copy code

6. Single linked list reversal

public class LinkedListTest { public class Node < T > { public T data; public Node<T> next; public Node (T data) { this .data = data; } } public Node reverse (Node list) { if (list == null ) { throw new IllegalArgumentException( "The head node of the linked list cannot be empty!" ); } if (list.next == null ) { return list; } Node curr = list; Node next = null ; while (curr.next != null ) { next = curr.next.next; curr.next.next = list; list = curr.next; curr.next = next; } return list; } private void testReverse () { Node list = new Node<Integer>( 3 ); Node n1 = new Node<Integer>( 2 ); Node n2 = new Node<Integer>( 4 ); Node n3 = new Node<Integer>( 6 ); Node n4 = new Node<Integer>( 8 ); list.next = n1; n1.next = n2; n2.next = n3; n3.next = n4; Node result = reverse(list); while (result != null ) { System.out.println( "Current value:" + result.data); result = result.next; } } public static void main (String[] args) { LinkedListTest t = new LinkedListTest(); t.testReverse(); } } //Run Results: Current value: 8 Current Value: 6 Current Value: 4 Current Value: 2 Current Value: 3 copy the code
  1. Detection of rings in singly linked lists
public boolean checkCircle (Node list) { if (list == null || list.next == null || list.next.next == null ) { return false ; } Node slow = list; Node fast = list; while (slow.next != null && fast.next != null && fast.next.next != null ) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true ; } } return false ; } private void testCheckCircle () { Node list = new Node<Integer>( 3 ); Node n1 = new Node<Integer>( 2 ); Node n2 = new Node<Integer>( 4 ); Node n3 = new Node<Integer>( 6 ); Node n4 = new Node<Integer>( 8 ); list.next = n1; n1.next = n2; n2.next = n3; n3.next = n1; //n3.next = n4; boolean result = checkCircle(list); System.out.println( "The current singly linked list has a ring:" + result); } public static void main (String[] args) { LinkedListTest t = new LinkedListTest(); t.testCheckCircle(); } //The result: the current single-chain looped: to true copy the code

7. The merger of two ordered singly linked lists

public Node mergeTwoSortedList (Node l1, Node l2) { if (l1 == null || l2 == null ) { throw new IllegalArgumentException( "Parameter cannot be empty!" ); } Node soldier = new Node( null ); Node curr = soldier; while (l1 != null && l2 != null ) { if (l1.data.hashCode() <l2.data.hashCode()) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } if (l1 != null ) { curr.next = l1; } if (l2 != null ) { curr.next = l2; } return soldier.next; } public void testMergeTwoSortedList () { Node<Integer> l1 = new Node<Integer>( 1 ); Node<Integer> l11 = new Node<Integer>( 3 ); Node<Integer> l12 = new Node<Integer>( 9 ); Node<Integer> l13 = new Node<Integer>( 19 ); l1.next = l11; l11.next = l12; l12.next = l13; Node<Integer> l2 = new Node<Integer>( 2 ); Node<Integer> l21 = new Node<Integer>( 4 ); Node<Integer> l22 = new Node<Integer>( 6 ); Node<Integer> l23 = new Node<Integer>( 12 ); l2.next = l21; l21.next = l22; l22.next = l23; Node result = mergeTwoSortedList(l1, l2); while (result != null ) { System.out.println( "Current item value:" + result.data); result = result.next; } } public static void main (String[] args) { LinkedListTest t = new LinkedListTest(); t.testMergeTwoSortedList(); } //Run Results: Current Item Value: 1 Current Item Value: 2 Current Item Value: 3 Current key: 4 Current Item Value: 6 Current key: 9 Current Item Value: 12 Current Item Value: 19 copy the code

8. Delete the Kth last node of the singly linked list

public Node deleteLastK (Node list, int k) { if (list == null || k < 1 ) { throw new IllegalArgumentException( "The parameter is wrong!" ); } Node fast = list; int count = 0 ; while (fast.next != null && count <k- 1 ) { fast = fast.next; count++; } if (count <k- 1 ) { throw new IllegalArgumentException( "The length of the list is not enough!" ); } if (fast.next == null ) { //There are only k nodes in the linked list, and only the head node can be deleted Node curr = list; list = list.next; curr.next = null ; return curr; } Node slow = list; fast = fast.next; while (slow.next != null && fast.next != null ) { slow = slow.next; fast = fast.next; } Node next = slow.next.next; slow.next.next = null ; slow.next = next; return list; } public void testDeleteLastK () { Node list = new Node<Integer>( 3 ); Node n1 = new Node<Integer>( 2 ); Node n2 = new Node<Integer>( 4 ); Node n3 = new Node<Integer>( 6 ); Node n4 = new Node<Integer>( 8 ); Node n5 = new Node<Integer>( 10 ); Node n6 = new Node<Integer>( 12 ); list.next = n1; n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n6; Node result = deleteLastK(list, 4 ); while (result != null ) { System.out.println( "Current item value:" + result.data); result = result.next; } } public static void main (String[] args) { LinkedListTest t = new LinkedListTest(); t.testDeleteLastK(); } //Run Results: Current Item Value: 3 Current Item Value: 2 Current key: 4 Current key: 8 Current Item Value: 10 Current Item Value: 12 copy the code

9. Find the middle node of the singly linked list

public Node findMiddleNode (Node list) { if (list == null ) { throw new IllegalArgumentException( "Parameter cannot be empty!" ); } if (list.next == null || list.next.next == null ) { //Only 1 node, or only 2 nodes. Take the head node as the intermediate node return list; } Node slow = list; Node fast = list; while (slow.next != null && fast.next != null && fast.next.next != null ) { slow = slow.next; fast = fast.next.next; } return slow; } public void testFindMiddleNode () { Node list = new Node<Integer>( 3 ); Node n1 = new Node<Integer>( 2 ); Node n2 = new Node<Integer>( 4 ); Node n3 = new Node<Integer>( 6 ); Node n4 = new Node<Integer>( 8 ); Node n5 = new Node<Integer>( 10 ); Node n6 = new Node<Integer>( 12 ); list.next = n1; n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n6; Node middle = findMiddleNode(list); System.out.println( "The value of the middle node:" + middle.data); } public static void main (String[] args) { LinkedListTest t = new LinkedListTest(); t.testFindMiddleNode(); } //Run Results: The value of the intermediate node: 6 copy the code

13.Stack: A linear table structure with restricted operations that only supports unidirectional stacking and popping.

1. Use 2 stacks to realize the browser's forward and backward

2. Use a linked list to implement the stack

public class StackBasedOnLinkedList { public class Node { public int data; public Node next; public Node ( int data, Node next) { super (); this .data = data; this .next = next; } public int getData () { return data; } } private Node top; public void push ( int data) { Node node = new Node(data, null ); if (top == null ) { top = node; } else { node.next = top; top = node; } } public int pop () { if (top == null ) { return - 1 ; } int value = top.data; top = top.next; return value; } public void printAll () { while (top!= null ) { System.out.println( "Current value:" + top.data); top = top.next; } } public static void main (String[] args) { StackBasedOnLinkedList t = new StackBasedOnLinkedList(); t.push( 1 ); t.push( 2 ); t.push( 3 ); t.push( 4 ); t.push( 5 ); t.printAll(); } } //Run Results: Current value: 5 Current value: 4 Current Value: 3 current value: 2 Current Value: 1 copy the code

3. Use 2 stacks to realize the browser's open, forward and backward functions

public class SimpleBrowser { public class Node { public String data; public Node next; public Node (String data, Node next) { super (); this .data = data; this .next = next; } public String getData () { return data; } } public class StackBasedOnLinkedList { public Node top; public void push (Node node) { if (top == null ) { top = node; } else { node.next = top; top = node; } } public String pop () { if (top == null ) { return "The current stack is empty!" ; } String result = top.data; top = top.next; return result; } public void clear () { while (top != null ) { pop(); } } public boolean hasElements () { return top != null ; } public void printAll () { Node curr = top; while (curr != null ) { System.out.println( "Current element value:" + curr.data); curr = curr.next; } } } public String currentPage; public StackBasedOnLinkedList backStack; public StackBasedOnLinkedList forwardStack; public SimpleBrowser () { this .backStack = new StackBasedOnLinkedList(); this .forwardStack = new StackBasedOnLinkedList(); } public boolean canGoBack () { return this .backStack.hasElements(); } public boolean canGoForward () { return this .forwardStack.hasElements(); } public String goBack () { if (canGoBack()) { String url = this .backStack.pop(); this .forwardStack.push( new Node(url, null )); this .currentPage = this .backStack.top == null ? Null : this .backStack.top.data; return url; } return null ; } public String goForward () { if (canGoForward()) { String url = this .forwardStack.pop(); this .backStack.push( new Node(url, null )); this .currentPage = url; return url; } return null ; } public String open (String url) { this .forwardStack.clear(); this .backStack.push( new Node(url, null )); this .currentPage = url; return url; } public static void main (String[] args) { SimpleBrowser t = new SimpleBrowser(); t.open( "url1" ); t.open( "url2" ); t.open( "url3" ); t.open( "url4" ); t.open( "url5" ); t.open( "url6" ); t.open( "url7" ); t.open( "url8" ); t.goBack(); t.goBack(); t.goBack(); t.goBack(); System.out.println( "Current Page:" + t.currentPage); t.goBack(); t.goForward(); t.goForward(); System.out.println( "Current Page:" + t.currentPage); t.open( "urlX" ); System.out.println( "Current page:" + t.currentPage); } } //operation result Current page: url4 Current page: url5 Current page: urlX Copy code

14. Queue: A linear table with limited operations, first in, first out, is a typical queue.

1. Enqueue: Add 1 element to the end of the queue

2. Dequeue: Take 1 element from the head of the queue

3. Build an array-based queue

/** * Queue constructed as an array. */ public class QueueBasedOnArray { public String[] items; public int head, tail; public int size; public QueueBasedOnArray ( int capacity) { this .size = capacity; this .items = new String[size]; head = tail = 0 ; } /** * Determine whether the queue is empty * * @return */ public boolean isEmpty () { return head == tail; } /** * Determine whether the queue is full * * @return */ public boolean isFull () { return tail == size; } /** * Join the team * * @param item * @return */ public boolean enqueue (String item) { //As long as the queue is full before, you cannot continue to add elements, even if you delete elements if (isFull()) { //The current queue is full return false ; } items[tail] = item; tail++; return true ; } /** * Departure * * @return */ public String dequeue () { if (isEmpty()) { return null ; } String result = items[head]; head++; return result; } /** * Print all elements in the current queue */ public void printAll () { if (isEmpty()) { return ; } System.out.println( "All elements of the queue:" ); for ( int i = head; i <tail; i++) { System.out.println( "Current element value:" + items[i]); } } public static void main (String[] args) { QueueBasedOnArray t = new QueueBasedOnArray( 6 ); t.enqueue( "1" ); t.enqueue( "2" ); t.enqueue( "3" ); t.enqueue( "4" ); t.enqueue( "5" ); t.enqueue( "6" ); t.enqueue( "7" ); t.printAll(); t.dequeue(); t.dequeue(); t.dequeue(); t.dequeue(); t.enqueue( "X" ); t.printAll(); } } //operation result: All elements of the queue: Current element value: 1 Current element value: 2 Current element value: 3 Current element value: 4 Current element value: 5 Current element value: 6 All elements of the queue: Current element value: 5 current element value: 6 copy the code

4. Build an array-based queue, as long as the array has free space, you can continue to add elements

public class DynamicQueueBasedOnArray { public String[] items; public int head, tail; public int size; public DynamicQueueBasedOnArray ( int capacity) { size = capacity; items = new String[size]; head = tail = 0 ; } public boolean isEmpty () { return head == tail; } public String dequeue () { if (isEmpty()) { return null ; } String result = items[head]; head++; return result; } /** * Join the team * When entering the queue, if the tail of the queue has reached the threshold, see if the head is at the position of 0 and not at the position of 0, indicating that the elements of the queue from the position of 0->head-1 have been taken out, and the queue still has space. * The element should be moved, and then the new element should be added to the end of the queue. * @param item * @return */ public boolean enqueue (String item) { if (tail == size) { if (head == 0 ) { //The queue is full return false ; } else { //The queue is not full //The positions from 0 to head-1 are empty for ( int i = head; i <tail; i++) { items[i-head] = items[i]; } tail = tail-head; head = 0 ; } } items[tail] = item; tail++; return true ; } public void printAll () { if (isEmpty()) { return ; } System.out.println( "All elements in the current queue:" ); for ( int i = head; i <tail; i++) { System.out.println( "Current element value:" + items[i]); } } public static void main (String[] args) { DynamicQueueBasedOnArray t = new DynamicQueueBasedOnArray( 6 ); t.enqueue( "1" ); t.enqueue( "2" ); t.enqueue( "3" ); t.enqueue( "4" ); t.enqueue( "5" ); t.enqueue( "6" ); t.enqueue( "7" ); t.enqueue( "8" ); t.printAll(); t.dequeue(); t.dequeue(); t.dequeue(); t.dequeue(); t.enqueue( "X" ); t.printAll(); } } //operation result: All elements of the current queue: Current element value: 1 Current element value: 2 Current element value: 3 Current element value: 4 Current element value: 5 Current element value: 6 All elements of the current queue: Current element value: 5 Current element value: 6 Current element value: X Copy code

5. Construct an unbounded queue based on a linked list

/** * Build a queue based on a linked list * The linked list itself is unbounded, so the number of elements in the queue is not limited */ public class QueueBasedOnLinkedList { public class Node { public String data; public Node next; public Node (String data, Node next) { this .data = data; this .next = next; } public Node (String data) { this .data = data; } } public Node head; public Node tail; public void enqueue (String data) { if (head == null ) { head = tail = new Node(data); } else { tail.next = new Node(data); tail = tail.next; } } public String dequeue () { if (head == null ) { return null ; } String data = head.data; head = head.next; if (head == null ) { tail = null ; } return data; } public void printAll () { Node curr = head; System.out.println( "All elements in the current queue:" ); while (curr != null ) { System.out.println( "Current element value:" + curr.data); curr = curr.next; } } public static void main (String[] args) { QueueBasedOnLinkedList t = new QueueBasedOnLinkedList(); t.enqueue( "1" ); t.enqueue( "2" ); t.enqueue( "3" ); t.enqueue( "4" ); t.dequeue(); t.printAll(); } } //operation result: All elements of the current queue: Current element value: 2 current element value: 3 current element value: 4 copy the code

6. Build an array-based circular queue

  1. Tail points to an index of an element that has not yet been stored. This is convenient for judging whether the queue is empty. Tail points to the'next', so when head==tail, the queue is empty.
  2. If tail points to the last element in the queue, to determine whether the queue is empty, it is necessary to determine whether the element at the head position or the tail position is empty. In order to ensure that it is empty, the array at the corresponding position must be set every time the queue is left The element is left blank, and then it can be'head+1'.
    1 and 2 are more visible, and tail points to the'next' to simplify the code.
  3. In a circular queue built on the basis of an array, there must be 1 position to be wasted.
    • Because tail points to the'next', it is the position where there is no element currently stored.
    • The circular queue is circular, and this position can only be an index value on the ring.
    • Unlike the acyclic pairs constructed by arrays, tail can be up to n, and n is not in the range of the array index value.
public class CircleQueueBasedOnArray { public String[] items; public int head, tail; public int size; public CircleQueueBasedOnArray ( int capacity) { head = tail = 0 ; size = capacity; items = new String[size]; } public boolean isEmpty () { return head == tail; } public boolean isFull () { return (tail + 1 )% size == head; } public boolean enqueue (String item) { if (isFull()) { return false ; } items[tail] = item; tail = (tail + 1 )% size; return true ; } public String dequeue () { if (isEmpty()) { return null ; } String result = items[head]; head = (head + 1 )% size; return result; } public void printAll () { if (isEmpty()) { return ; } System.out.println( "All elements in the current queue:" ); for ( int i = head; i != tail; i = (i + 1 )% size) { System.out.println( "Current element value:" + items[i]); } } public static void main (String[] args) { CircleQueueBasedOnArray t = new CircleQueueBasedOnArray( 6 ); t.enqueue( "1" ); t.enqueue( "2" ); t.enqueue( "3" ); t.enqueue( "4" ); t.enqueue( "5" ); t.enqueue( "6" ); t.printAll(); t.dequeue(); t.dequeue(); t.dequeue(); t.printAll(); t.enqueue( "11" ); t.enqueue( "12" ); t.enqueue( "13" ); t.enqueue( "14" ); t.enqueue( "15" ); t.printAll(); } } //Current running results: //It can be seen from the printing results: In the circular queue built on the basis of arrays, 1 position will be wasted, in order for the tail to point to the'next'. All elements of the current queue: Current element value: 1 Current element value: 2 Current element value: 3 Current element value: 4 Current element value: 5 All elements of the current queue: Current element value: 4 Current element value: 5 All elements of the current queue: Current element value: 4 current element value: 5 current element value: 11 current element value: 12 current element value: 13 copy the code

15. Recursion

1. Conditions that can be solved by recursion

  1. The solution of a problem can be decomposed into solutions of several sub-problems.
  2. The original problem and the sub-problem are completely the same except for the different data scales.
  3. The problem is decomposed into sub-problems and cannot be decomposed indefinitely.It must have a termination condition, that is, a recursive termination condition.

2. Disadvantages of recursion

  1. If the recursion level is too deep, it will cause a stack overflow.
    • Taking JVM as an example, the depth of each thread stack is limited. If the number of recursion is too large, stack frames are constantly pushed onto the function call stack, and Stack Overfllow is triggered if the limit is exceeded.
  2. Recursion may have double counting problems
    • For example, f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3), f(n-2) is repeated Calculated 2 times
    • As an example to avoid repeated calculations, the results of the previously specified parameters should be stored in a hash table
  3. Each time the recursion is called, a stack frame is created and pushed onto the stack. The stack frame contains temporary variables. Multiple calls will increase the space complexity of the algorithm.
    • Compared with the while loop, we can declare 1 variable and use it repeatedly in the while loop, with low space complexity
  4. Recursion is'synchronous' and needs to wait for the result of the previous call.If the number of calls is too large, it will accumulate to a high time cost.

3. Several recursive problems

3.1. For n-stairs, you can go up 1 or 2 steps each time, how many ways are there in total?
private Map<Integer,Integer> results = new HashMap<Integer,Integer>(); public int goStairs ( int n) { if (n <= 1 ){ return 1 ; } if (n == 2 ){ return 2 ; } if (results.containsKey(n)){ return results.get(n); } return goStairs(n- 1 ) + goStairs(n- 2 ); } Copy code

16. How to evaluate a sorting algorithm: It is measured from three aspects: the execution efficiency of the sorting algorithm, the space complexity of the sorting algorithm, and the stability of the sorting algorithm.

1. The execution efficiency of the sorting algorithm

  1. Best case, worst case, average case time complexity.
    • Some of the data to be sorted are close to order, and some are completely disordered. The different degree of order affects the execution time of sorting, and it is necessary to know the performance of the algorithm under different degree of order data.
  2. Time complexity coefficient, constant, low order.
    • Time complexity reflects the increasing trend of execution time when n is large, and coefficients, constants, and low-levels are ignored when expressed.
    • However, in actual sorting scenarios, you may only encounter a small data size of less than 1000. Therefore, for different algorithms with the same order of time complexity, their coefficients, constants, and low-level must be considered.
  3. The number of comparisons and the number of exchanges (movements).
    • The sorting algorithm based on comparison will definitely involve comparison between elements and position exchange (or movement). Therefore, the number of comparison and exchange (or movement) should also be taken into consideration.

2. Memory consumption of sorting algorithm

  1. Like other algorithms, its memory consumption is measured by space complexity.
  2. In-place sorting: specifically refers to a sorting algorithm whose space complexity is O(1).

3. The stability of the sorting algorithm

  1. Stability refers to: If there are elements with equal values in the sequence to be sorted, after sorting, the original order of elements with equal values remains unchanged.
  2. After sorting, the original order between elements of equal value remains unchanged, which is called a stable sorting algorithm.
  3. After sorting, the original order between elements of equal value changes, which is called an unstable sorting algorithm.
  4. For example, a set of data should be sorted according to the attribute value of attr1 from large to small. When the attribute value of attr1 is equal, it is sorted according to the attribute value of attr2 from small to large.
    • First sort by attr2 attribute value from smallest to largest
    • Then use the stable sorting algorithm to sort from large to small according to attr1.

17. Bubble Sort

1. Bubble sort will only operate on two adjacent data.

2. If the size relationship between two adjacent elements does not meet the requirements, they are exchanged.

3. One bubbling will move at least one element to the correct position. Repeat n times to complete the sorting of n data.

public class BubbleSort { public void bubbleSort ( int [] arr) { if (arr == null || arr.length <= 1 ) { return ; } int length = arr.length; //moved is used to mark whether element interaction occurs for each bubbling. If no interaction occurs, it means that the current data has been sorted and the comparison can be aborted. boolean moved = false ; int temp; for ( int i = 0 ; i <length; i++) { moved = false ; for ( int j = 0 ; j <length- 1 -i; j++) { if (arr[j]> arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; moved = true ; } } if (!moved) { System.out.println( "Bubbling times:" + (i + 1 )); break ; } } } public static void main (String[] args) { BubbleSort t = new BubbleSort(); int [] arr = { 12 , 54 , 32 , 8 , 6 , 3 , 111 , 45 }; t.bubbleSort(arr); Arrays.stream(arr).forEach(System.out::println); } } //Run Results: bubbling times: . 6 . 3 . 6 . 8 12 is 32 45 54 is 111 copy the code

4. Time complexity, space complexity, and stability of bubble sort

  1. Best-case time complexity: O(n)
    • All elements are in order.
    • After bubbling once and finding that there is no element exchange, the sorting is terminated.
  2. Worst case time complexity: O(n^2)
    • All elements are completely in reverse order
    • bubbling n times.
  3. Average case time complexity: O(n^2)
    • Order: the number of correctly sorted pairs of elements in the original array
    • Full order: The original array is completely ordered, and its order is called full order
    • Reverse order: the number of wrongly sorted element pairs in the original array
      • Reverse order degree = full order degree-order degree
      • The degree of reversal is the number of times the original array needs to perform element swaps
      • Full order degree = n*(n-1)/2, the average reverse order degree is full order degree/2 = n*(n-1)/4
      • The number of comparison exchanges must be greater than the number of exchanges, and the worst time complexity is O(n^2). So the average time complexity of bubble sorting is O(n^2)
  4. The space complexity is O(1), which is a stable sort.

18. Insertion sort

1. Insertion sort divides the entire array into a sorted interval and an unsorted interval. The initial sorted interval has only 1 element, which is the first element of the array.

2. Every time you take the element at the head of the unsorted interval, find a suitable position in the sorted interval and insert it, and ensure that the sorted interval is always in order.

3. Repeat the whole process until the unsorted interval elements are empty.

public class InsertSort { public void insertSort ( int [] a) { if (a == null || a.length <= 1 ) { return ; } int value; int j; for ( int i = 1 ; i <a.length; i++) { value = a[i]; j = i- 1 ; for (; i >= 0 ; j--) { if (a[j]> value) { a[j + 1 ] = a[j]; } else { break ; } } a[j + 1 ] = value; } } public static void main (String[] args) { InsertSort t = new InsertSort(); int [] a = { 1 , 2 , 31 , 32 , 19 , 18 , 17 , 16 , 61 , 58 , 54 }; t.insertSort(a); System.out.println( "Run result:\n" ); Arrays.stream(a).forEach(System.out::println); } } operation result: 1 2 16 17 18 19 31 32 54 58 61 is duplicated code

4. The best case time complexity of insertion sort is O(n), the worst case time complexity is O(n^2), and the average time complexity is O(n^2). The space complexity is O(1 ), which belongs to stable sorting.

19. Select Sort

1.Selection sorting is similar to insertion sorting, and also divides the entire array into sorted and unsorted intervals.

2. Every time the smallest element is found in the unsorted interval, it is placed at the end of the sorted interval.

public class SelectSort { public void selectSort ( int [] a) { if (a == null || a.length <= 1 ) { return ; } int minIndex; int temp; for ( int i = 0 ; i <a.length- 1 ; i++) { minIndex = i; for ( int j = i + 1 ; j <a.length; j++) { if (a[j] <a[minIndex]) { minIndex = j; } } temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } public static void main (String[] args) { SelectSort t = new SelectSort(); int [] a = { 3 , 5 , 7 , 2 , 4 , 6 , 89 , 40 }; t.selectSort(a); System.out.println( "Select the sorted array:" ); Arrays.stream(a).forEach(System.out::println); } } Select the sorted array: 2 . 3 . 4 . 5 . 6 . 7 40 89 duplicated code

3. Choose the best and worst for sorting, and the average time complexity is O(n^2), because each time you have to compare them completely, there is no chance of exiting halfway.

4. The space complexity of selection sort is O(1).

5. Selective sorting is not a stable sorting, because the min element needs to be exchanged with the end element of the sorted interval, which may cause the order to be disrupted. Above:

20. The time complexity of bubble sort and insertion sort is the same, both are O(n^2). Why is insertion sort more common?

1.Although the time complexity of the two is the same as O(n^2), the element exchange operation, insertion sort is simpler than bubble sort, and the number of code lines is lower, so the performance of insertion sort is better.

2. Comparison of element exchange between the two

//Bubble sort if (a[j]> a[j + 1 ]){ temp = a[j]; a[j] = a[j + 1 ]; a[j + 1 ] = temp; moved = true ; } //Insert sort if (a[j]> value){ a[j + 1 ] = a[j]; } else { break ; } Copy code

21. Merge Sort

1. Divide the original array into 2 parts, after the 2 parts are sorted, merge the 2 parts

2. Each part can continue to be divided into 2 parts, recursively executed

3. Pseudo code

public void sort ( int [] arr) { splitSort(arr, 0 , arr.length- 1 ); } public int [] splitSort( int [] arr, int startIndex, int endIndex) { if (startIndex >= endIndex) { return new int [] {arr[startIndex] }; } int midIndex = (startIndex + endIndex)/2 ; int [] a1 = splitSort(arr, startIndex, midIndex); int [] a2 = splitSort(arr, midIndex + 1 , endIndex); int [] result = merge(a1, a2); return result; } public int [] merge( int [] a1, int [] a2) { int [] result = new int [a1.length + a2.length]; int i1 = 0 ; int i2 = 0 ; for ( int i = 0 ; i <result.length; i++) { if (a1[i1]> a2[i2]) { result[i] = a2[i2]; i2++; } else { result[i] = a1[i1]; i1++; } } return result; } Copy code

4. The time complexity of merge sort is O(nlogn), which is very stable

5. The space complexity of merge sort is O(n), because merging arrays requires creating new arrays, so they are not sorted in place.

6. Merge sort is a stable sort. For example, if the elements in a1 and a2 have the same value, the elements of a1 are first added to the merged array according to the convention.

22. Quick Sort

1.Quick sorting is to take one element in the array as the partition value each time.The value of the element in the array is placed on the left side of the array, and the value greater than the value is placed on the right side.

2. Then sort the left and right sides separately and execute recursively.

3. Pseudo code

public void sort ( int [] arr) { quickSort(arr, 0 , arr.length- 1 ); } public void quickSort ( int [] arr, int startIndex, int endIndex) { if (arr == null || startIndex >= endIndex){ return ; } int pivot = partition(arr, startIndex, endIndex); quickSort(arr, startIndex, pivot- 1 ); quickSort(arr, pivot + 1 , endIndex); } public int partition ( int [] arr, int startIndex, int endIndex) { int value = arr[endIndex]; int pivot = endIndex; for ( int i = startIndex; i<endIndex- 1 ; i++){ if (a[i ] <value){ if (pivot == endIndex){ if (i != startIndex){ swap(i, startIndex); } pivot = startIndex; } else { swap(pivot + 1 , i); pivot++; } } } if (pivot != endIndex){ pivot = pivot + 1 ; swap(endIndex, pivot); } return pivot; } Copy code

4. The time complexity of quicksort is O(nlogn), and the worst time complexity is O(n^2).

5.Quick sort is in-situ sorting, because it does not involve creating a new array and sorts the array elements directly.

6. Fast sorting is not a stable sorting. It is designed to exchange array elements. There are two situations that will cause the order of elements with the same value to change.