[数据结构与算法]数据结构终极教程 保姆级别 适合入门

DB

big o notation

describle the performance of an algorithm O(n)

public class BigONotation {
    public static void main(String[] args) {
        //O(n) linearly
        public void log(int []numbers) {
            System.out.println();//O(1)
            for (int number : numbers)
                System.out.println(number);
        }
        //O(n^2) nest loops
        public void log1(int[] numbers) {
            for (int first : numbers)
                for (int second : numbers)
                    System.out.println(first + "," + second);

        }
        //O(logn) binary search ,narrow down half search
        //O(2^n) exponential growth not scalable
    }

Arrays数组

自建数组：

public class Array{
    private int[] items;
    private int count;
    
    public Array(int length){  //构造器初始化数组
        items = new int[length];
    }
    public void insert(int item){
        resizeIfRequired();
        items[count++] = item;
    }
    
    public void insertAt(int item, int index){
        if (index < 0 || index > count)
            throw new IllegalArgumentException();
        for (int i = count-1; i >= index; i--) {//原来的插入项及之后项后移，用倒着的for
            items[i+1] = items[i];
        }
        items[index] = item;
        count++;
    }
    public void reverse(){
        int []newItem = new int[count];
        for (int i = 0; i < count; i++) {
            newItem[i] = items[count-1-i];
        }
        items = newItem;
    }
    
    private void resizeIfRequired(){//封装在类的内部
        if (items.length == count) {
            int[] douItems = new int[count * 2];
            for (int i = 0; i < count; i++) {
                douItems[i] = items[i];
            }
            items = douItems;
        }
    }
    public int max(){
        int max = 0;
        for (int i = 0; i < count; i++) {
            if(items[i] >= max)
                max = items[i];
        }
        return max;
    }
    public void removeAt(int index) {
        if (index < 0 || index >= count)
            throw new IllegalArgumentException();
        for (int i = index; i <count ; i++) {
            items[i] = items[i+1];
        }
        count--;
    }
    
    public Array intersect(Array other){//取两个数组的交集
        var intersecton = new Array(count);
        
        for (int item : items) {
            if (other.indexOf(item) >= 0)
                intersecton.insert(item);
        }
        return intersecton;
    }
    public int indexOf(int item) {
        for (int i = 0; i < count; i++) {
            if (items[i] == item)
                return i;
        }
        return -1;
    }
    public void print() {
        for (int i = 0; i < count; i++) {
            System.out.println(items[i]);
        }
    }
}

Java内置数组

Vector：扩展时大小翻倍，方法都是synchronized同步的，只能由一个线程使用

Arraylist：拓展大小增加50%，方法是异步asynchronous的

他们都是对数组的动态模拟

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add(2, "3");
        list.add("3");
        list.add("4");
        list.add(4, "10");
        list.remove(1);
        System.out.println(list.size());
        System.out.println(list);
        System.out.println(list.contains("1"));//返回一个boolean值

        list.toArray();//将对象转化为原生数组
    }

}

数组总结

链表

自建链表

public class LinkedList {
  private class Node {
    private int value;
    private Node next;

    public Node(int value) {
      this.value = value;
    }
  }

  private Node first;
  private Node last;
  private int size;

  public void addLast(int item) {
    var node = new Node(item);

    if (isEmpty())
      first = last = node;
    else {
      last.next = node;
      last = node;
    }

    size++;
  }

  public void addFirst(int item) {
    var node = new Node(item);

    if (isEmpty())
      first = last = node;
    else {
      node.next = first;
      first = node;
    }

    size++;
  }

  private boolean isEmpty() {
    return first == null;
  }

  public int indexOf(int item) {
    int index = 0;
    var current = first;
    while (current != null) {
      if (current.value == item) return index;
      current = current.next;
      index++;
    }
    return -1;
  }

  public boolean contains(int item) {
    return indexOf(item) != -1;
  }

  public void removeFirst() {
    if (isEmpty())
      throw new NoSuchElementException();

    if (first == last)
      first = last = null;
    else {
      var second = first.next;
      first.next = null;
      first = second;
    }

    size--;
  }

  public void removeLast() {
    if (isEmpty())
      throw new NoSuchElementException();

    if (first == last)
      first = last = null;
    else {
      var previous = getPrevious(last);
      last = previous;
      last.next = null;
    }

    size--;
  }

  private Node getPrevious(Node node) {
    var current = first;
    while (current != null) {
      if (current.next == node) return current;
      current = current.next;
    }
    return null;
  }

  public int size() {
    return size;
  }

  public int[] toArray() {
    int[] array = new int[size];
    var current = first;
    var index = 0;
    while (current != null) {
      array[index++] = current.value;
      current = current.next;
    }

    return array;
  }

  public void reverse() {
    if (isEmpty()) return;

    var previous = first;
    var current = first.next;
    while (current != null) {
      var next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }

    last = first;
    last.next = null;
    first = previous;
  }

  public int getKthFromTheEnd(int k) {
    if (isEmpty())
      throw new IllegalStateException();

    var a = first;
    var b = first;
    for (int i = 0; i < k - 1; i++) {
      b = b.next;
      if (b == null)
        throw new IllegalArgumentException();
    }
    while (b != last) {
      a = a.next;
      b = b.next;
    }
    return a.value;
  }

  public void printMiddle() {
    if (isEmpty())
      throw new IllegalStateException();

    var a = first;
    var b = first;
    while (b != last && b.next != last) {
      b = b.next.next;
      a = a.next;
    }

    if (b == last)
      System.out.println(a.value);
    else
      System.out.println(a.value + ", " + a.next.value);
  }

  public boolean hasLoop() {
    var slow = first;
    var fast = first;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;

      if (slow == fast)
        return true;
    }

    return false;
  }

  public static LinkedList createWithLoop() {
    var list = new LinkedList();
    list.addLast(10);
    list.addLast(20);
    list.addLast(30);

    // Get a reference to 30
    var node = list.last;

    list.addLast(40);
    list.addLast(50);

    // Create the loop
    list.last.next = node;

    return list;
  }
}

Java内置链表

是双向的

public class Main {
    public static void main(String[] args) {
        var list = new LinkedList();
        list.addLast(5);
        list.addLast(10);
        list.addLast(15);
        list.addLast(20);
        list.addFirst(0);
        list.removeFirst();
        System.out.println(list.contains(10));
        System.out.println(list.indexOf(10));
        System.out.println(list.size());
        var array = list.toArray();//转换为原生数组
        System.out.println(list);
        System.out.println(Arrays.toString(array));//输出原生数组
    }

}

链表总结

栈

applications

implement the undo features

build compilers(eg synax checking)

evaluate expressions

build navigation(eg forword/back)

机制：LIFO last in first out

基本操作：

push(item)

pop()

peek()

isEmpty()

Java内置stack

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek());
        var top = stack.pop();
        System.out.println(top);
        System.out.println(stack);
    }

}

stack的应用 : 反转字符串

public class StringReverser {
    public String reverse(String input){
        if (input == null)
            throw new IllegalArgumentException();
        Stack<Character> stack = new Stack<>();
        //for (int i = 0; i < input.length(); i++) {
        //    stack.push(input.charAt(i));
        //} //
        for (char ch : input.toCharArray())
            //Java不可以对string进行foreach迭代，要将其转换为字符串数组，更简洁
            stack.push(ch);
        /*字符串拼接的方法
        String reversed = "";
        while ( !stack.empty()) {
            reversed += stack.pop();//每进行一次拼接，就要创建新的字符串对象空间，
            因为string在Java中是不可变的，对字符串进行编辑是，内存会重新分配空间
        }
        */
        StringBuffer reversed = new StringBuffer();
        //处理大量字符串时，用stringbuffer类替换字符串拼接
        while (!stack.empty()) {
            reversed.append(stack.pop());
        }
        return reversed.toString();//最后要将其转换为字符串输出
    }
}


public class Main {
    public static void main(String[] args) {
        String str = "apple";
        StringReverser reverser = new StringReverser();
        var array = reverser.reverse(str);
        System.out.println(array);
    }

}

匹配字符串

//version 1.0
public class Expression {
    public boolean isBalanced(String input){
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (ch == '(' ||ch == '<' || ch == '{' ||ch == '[')
                stack.push(ch);
            if (ch == ')' || ch== '>' ||ch =='}' ||ch == ']') {
                var top = stack.pop();

                if (    (ch == ')' && top!= '(' ) ||
                        (ch == '>' && top!= '<' ) ||
                        (ch == ']' && top!= '[' ) ||
                        (ch == '}' && top!= '{' )
                )
                    return false;
            }
        }
        return stack.empty();
    }
}


public class Main {
    public static void main(String[] args) {
        String str = "{(a+b)}";
        Expression exp = new Expression();
        var result = exp.isBalanced(str);
        System.out.println(result);
    }

}

//version 2.0
public class Expression {
    public boolean isBalanced(String input){
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (isLeftBracket(ch))
                stack.push(ch);
            if (isRightBracket(ch)) {
                var top = stack.pop();

                if (bracketMatch(ch,top))
                    return false;
            }
        }
        return stack.empty();
    }
    private boolean isLeftBracket (char ch){
        return ch == '(' ||ch == '<' || ch == '{' ||ch == '[';
    }
    private boolean isRightBracket(char ch) {
        return ch == ')' || ch== '>' ||ch =='}' ||ch == ']';
    }
    private boolean bracketMatch(char left,char right){
        return  (left == ')' && right!= '(' ) ||
                (left == '>' && right!= '<' ) ||
                (left == ']' && right!= '[' ) ||
                (left == '}' && right!= '{' );
    }
}

//version 3.0
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Expression {
// 不应该在私有方法中声名数组
    private final List<Character> rightBrackets = Arrays.asList(')',']','}','>');
    private final List<Character> leftBrackets =  Arrays.asList('(','[','{','<');

    public boolean isBalanced(String input){
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (isLeftBracket(ch))
                stack.push(ch);
            if (isRightBracket(ch)) {
                if(stack.empty())   return false;

                var top = stack.pop();
                if (!bracketMatch(ch,top))
                    return false;
            }
        }
        return stack.empty();
    }
    private boolean isLeftBracket (char ch){

        return leftBrackets.contains(ch);
    }
    private boolean isRightBracket(char ch) {
        return rightBrackets.contains(ch);
    }
    private boolean bracketMatch(char left,char right){
        return  leftBrackets.indexOf(left) == rightBrackets.indexOf(right);
    }
}

自建stack

import java.util.Arrays;


public class Stack {
    private int []items = new int[5];
    private int count;

    public void push(int item){
        if (count == items.length)
            throw new StackOverflowError();
        items[count++] = item;
    }
    public int pop(){

        return items[--count];

    }
    public int peek(){
        return items[count-1];
    }
    public boolean isEmpty(){
        return count == 0;
    }
    @Override
    public String toString() {
        int[] result = Arrays.copyOfRange(items, 0, count);


        return Arrays.toString(result);
    }

}

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(5);
        stack.push(20);
        var top = stack.pop();
        System.out.println(top);
        System.out.println(stack);
    }

}

总结

Queues

FIFO first in first out

applications

Printers

os

web servers

live support systems

常用方法

enqueue

dequeue

peek

isEmpty

isFull

Java自带queue

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        var front = queue.remove();
        System.out.println(front);
        System.out.println(queue);
    }

}

//反转queue

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        var front = queue.remove();
        System.out.println(front);
        System.out.println(queue);
        reverse(queue);

        System.out.println(queue);
    }
    public static void reverse(Queue<Integer> queue){
        Stack<Integer> stack = new Stack<>();

        while (! queue.isEmpty()) {
            stack.push(queue.remove());
        }
        while (!stack.isEmpty()) {
            queue.add(stack.pop());
        }
    }
    
}

用数组构建queue

import java.util.Arrays;


public class ArrayQueue {
    private int[] items ;
    private int count;
    private int front;
    private int rear;

    public ArrayQueue(int capacity) {
        items = new int[capacity];
    }
    public void enqueue(int item) {
        if (count == items.length)
            throw new IllegalArgumentException();

        items[rear] = item;
        rear = ( rear + 1) % items.length;

        count++;
    }
    public int dequeue() {
        var item = items[front];
        items[front] = 0;
        front = (front + 1) % items.length;
        count--;
        return item;

    }
    @Override
    public String toString() {
        return Arrays.toString(items);
    }

}

public class Main {
    public static void main(String[] args) {

        ArrayQueue queue = new ArrayQueue(5);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(13);
        queue.dequeue();
        queue.enqueue(14);
        queue.enqueue(15);
        queue.enqueue(16);
        System.out.println(queue);
    }
}

用栈构建数组

import java.util.Stack;
public class QueueWithTwoStacks {
    private Stack<Integer> stack1 = new Stack<>();  //enqueue
    private Stack<Integer> stack2 = new Stack<>();  //dequeue

    public void enqueue(int item) { //O(1)
        stack1.push(item);
    }

    public int  dequeue() { //O(n)
        if(stack1.isEmpty() && stack2.isEmpty())
            throw new IllegalStateException();
        if (stack2.isEmpty()) { //作用域只在这个代码块
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}
//refacting
public class QueueWithTwoStacks {
    private Stack<Integer> stack1 = new Stack<>();  //enqueue
    private Stack<Integer> stack2 = new Stack<>();  //dequeue

    public void enqueue(int item) { //O(1)
        stack1.push(item);
    }

    public int  dequeue() { //O(n)
        if(stack1.isEmpty() && stack2.isEmpty())
            throw new IllegalStateException();
        moveStack1ToStack2();
        return stack2.pop();
    }

    private void moveStack1ToStack2() {
        if (stack2.isEmpty()) { //作用域只在这个代码块
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    }

    public int  peek() {
        if(stack1.isEmpty() && stack2.isEmpty())
            throw new IllegalStateException();
        moveStack1ToStack2();
        return stack2.peek();
    }
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

priorityqueues:

可用数组和堆实现，本例用数组

import java.util.Arrays;

public class PriorityQueue {
  private int[] items = new int[5];
  private int count;

  // O(n)
  public void add(int item) {
    if (isFull())
      throw new IllegalStateException();

    var i = shiftItemsToInsert(item);
    items[i] = item;
    count++;
  }

  public boolean isFull() {
    return count == items.length;
  }

  private int shiftItemsToInsert(int item) {
    int i;
    for (i = count - 1; i >= 0; i--) {
      if (items[i] > item)
        items[i + 1] = items[i];
      else
        break;
    }
    return i + 1;
  }

  // O(1)
  public int remove() {
    if (isEmpty())
      throw new IllegalStateException();

    return items[--count];
  }

  public boolean isEmpty() {
    return count == 0;
  }

  @Override
  public String toString() {
    return Arrays.toString(items);
  }
}

public class Main {
    public static void main(String[] args) {

        PriorityQueue queue = new PriorityQueue();
        queue.add(12);
        queue.add(13);
        queue.add(15);
        queue.add(17);
        queue.add(14);
        var result = queue.remove();
        System.out.println(result);
        System.out.println(queue);

    }
}

Java自带的priorityqueue

public class Main {
    public static void main(String[] args) {

        PriorityQueue queue = new PriorityQueue();
        queue.add(5);
        queue.add(4);
        queue.add(2);
        queue.add(1);
        queue.add(3);
        System.out.println(queue);
        while (! queue.isEmpty())
            System.out.println(queue.remove());
    }
}

summary

Hash Tables

differnt names about hash

applications

spell checkers

dictionaries

compilers

code editor

deterministic 确定的

give same input return same value

通常通过HashMap实现Map接口，hashtable已经淘汰，concurrenthashmap用于多线程

java内置hash

import java.util.HashMap;
import java.util.Map;
public class Main {
    public static void main(String[] args) {

        Map<Integer,String> map = new HashMap<>();
        map.put(1, "cp");
        map.put(2, "tr");
        map.put(3, "wbj");
        map.put(3, "sjh");//hashmap中不允许有重复项，后者会覆盖前者
        map.put(null, null);//key,value 均可以为null值
        System.out.println(map.get(3));//通过key得到value
        map.remove(null);//通过key移除该项
        System.out.println(map.containsKey(1));
        System.out.println(map.containsValue("sjh")); //O(n)
        System.out.println(map);
        for (var item : map.keySet()) {//打印key
            System.out.println(item);
        }
        for (var item : map.entrySet()) {//打印键值对
            System.out.println(item);
        }
        for (var item : map.entrySet()) {//打印key
            System.out.println(item.getKey());
        }
        for (var item : map.entrySet()) {
            System.out.println(item.setValue("1"));
        }
        System.out.println(map);
    }
}

寻找第一个（不）重复的字符

First Non-repeated Character And firstRepeated Character

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class CharacterFinder {
    public char findFirstNonRepeated(String str){
        Map<Character, Integer> map = new HashMap<>();

        var chars = str.toCharArray();
        for (char ch : chars) {
//            if (map.containsKey(ch))   {
//                var count = map.get(ch);
//                map.put(ch, count);
//            }
//            else
//                map.put(ch, 1);
            var count = map.containsKey(ch) ? map.get(ch) : 0;
            map.put(ch , count + 1);
        }
        for (char ch : chars) {
            if (map.get(ch) == 1)
                return ch;

        }
        return Character.MIN_VALUE;
    }
    public char findFirstRepeatedChar(String str) {
        Set<Character> set = new HashSet<>();
        for (var ch : str.toCharArray() ) {
            if (set.contains(ch))
                return ch;
            set.add(ch);
        }
        return Character.MIN_VALUE;
        }
    }

set 接口主要由hashset类实现

hash函数

public class Main {
    public static void main(String[] args) {
        String str =  "chen peng";
        System.out.println(hashCode(str));
    }
    public static int hashCode(String str) {
        var chars = str.toCharArray();
        int hash = 0;
        for (var ch : chars) {
            hash += ch;
        }
        hash = hash % 100;
        return hash;
    }
}

collisons

处理collision的方法

chainings and open addressing

自建hashtable

import java.util.LinkedList;

/**
 * @Author: CP
 * @Date: 2021/8/24 -08 -24 -21:06
 * @Description: myself
 * @version: 1.0
 */
public class HashTable {
    private class Entry {
        private int key;
        private  String value;

        public Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    private LinkedList<Entry>[] entries= new LinkedList[5];
    public void put(int key, String value) {
        var index = hash(key);
        if (entries[index] == null)
            entries[index] = new LinkedList<>();
        for (var entry : entries[index]) {
            if (entry.key == key){
                entry.value = value;
                return;
            }
        }
        entries[index].addLast(new Entry(key, value));
    }
    public String get(int key) {
        var index = hash(key);
        if (entries[index] != null) {
            for (var entry :entries[index])
                if (entry.key == key)
                    return entry.value;
        }
        return null;
    }
    public void remove (int key) {
        var index = hash(key);
        if (entries[index] == null) {
            throw new IllegalStateException();
        }
        for (var entry  : entries[index]) {
            if (entry.key == key) {
                entries[index].remove(entry);
                return;
            }
        }
        throw new IllegalStateException();
    }
    private int hash(int key) {
        return key % entries.length;
    }
}

进行重构

import java.util.LinkedList;

public class HashTable {
  private class Entry {
    private int key;
    private String value;

    public Entry(int key, String value) {
      this.key = key;
      this.value = value;
    }
  }

  private LinkedList<Entry>[] entries = new LinkedList[5];

  public void put(int key, String value) {
    var entry = getEntry(key);
    if (entry != null) {
      entry.value = value;
      return;
    }

    getOrCreateBucket(key).add(new Entry(key, value));
  }

  public String get(int key) {
    var entry = getEntry(key);

    return (entry == null) ? null : entry.value;
  }

  public void remove(int key) {
    var entry = getEntry(key);
    if (entry == null)
      throw new IllegalStateException();
    getBucket(key).remove(entry);
  }

  private LinkedList<Entry> getBucket(int key) {
    return entries[hash(key)];
  }

  private LinkedList<Entry> getOrCreateBucket(int key) {
    var index = hash(key);
    var bucket = entries[index];
    if (bucket == null)
      entries[index] = new LinkedList<>();

    return bucket;
  }

  private Entry getEntry(int key) {
    var bucket = getBucket(key);
    if (bucket != null) {
      for (var entry : bucket) {
        if (entry.key == key)
          return entry;
      }
    }
    return null;
  }

  private int hash(int key) {
    return key % entries.length;
  }
}

总结

linear 会造成簇的问题easy to form cluster 插入和检索时降低性能

quadratic 使得寻址进行更大的跳跃，可以避免成簇，但可能会造成无限循环