数据结构考前速览

数据结构考试前的一些复习整理，包括可能会考的作业代码

易记混算法细节

计数排序最后一步

for (j = input.length - 1; j >= 0; j--) {
    output[--T[input[j]]] = input[j];
}

寻找最小值递归

return n == 1 ? a[0] : Math.min(FindMin(a, n - 1), a[n - 1]);

BST中用到的递归

//Insert
if(T.key<key){
    T.right=Insert(T.right,key);
}

//Height
return Math.max(Height(T.left),Height(T.right))+1;

Dijkstra

//对优先队列比较器的override， o1 - o2 为升序
PriorityQueue<Vertex> PQ = new PriorityQueue<Vertex>(new Comparator<Vertex>() {
    @Override
    public int compare(Vertex o1, Vertex o2) {
        return o1.getDistance() - o2.getDistance();
    }
});

动态规划问题

爬楼梯

• 第 1 ~ k 阶 每一阶的数量等于前面所有的和

• 第 k+1 ~ n 阶 第s阶的数量等于s-1到s-k的和

Combination/Permutation

组合先建表再循环，每次去掉一个传到递归

排列循环里面建表，表里只删除他本身的数

public int combination(ArrayList<Integer> a, int[] k, int Pos) {
    if (Pos == k.length) {
        System.out.println(Arrays.toString(k));
        return 1;
    }
   //区别1
    ArrayList<Integer> b = new ArrayList<>();
    
    int sum = 0;
    while(!a.isEmpty()) {
        k[Pos] = a.get(0);
        //区别2
        a.remove(0);
        b.addAll(a);
        sum += combination(b, k, Pos + 1);
    }
    return sum;
}

public int Permutation(ArrayList<Integer> a, int[] k, int Pos) {
    if (Pos == k.length) {
        System.out.println(Arrays.toString(k));
        return 1;
    }
    int sum = 0;
    for (int i = 0; i < a.size(); i++) {
        k[Pos] = a.get(i);
        ArrayList<Integer> b = new ArrayList<Integer>();
        b.addAll(a);
        b.remove(i);
        sum += Permutation(b, k, Pos + 1);
    }
    return sum;
}

英语单词拼写

PrioroityQueue

Comparator

adjacent

Dijkstra

iterative

recursive

Combination

Permutation

Partition

sentinel

HW1

插入排序

void insertionSort(int[] a) {
    int i, j, k;
    for (i = 1; i < a.length; i++) {
        k = a[i];
        j = i - 1;
        while (j >= 0 && a[j] > k) {
            a[j + 1] = a[j];
            j--;
        }
        a[j+1] = k;
    }
}

归并排序

此处为刘汝佳的《算法竞赛入门经典》中的写法，与《算法导论》略不同

void mergeSort(int[] a, int x, int r, int[] T) {
    if (r - x > 1) {
        int m = (x + r) / 2;
        int i = x, q = m, p = x;

        mergeSort(a, x, m, T);
        mergeSort(a, m, r, T);
        while (p < m || q < r) {
            if (q >= r || (p < m && a[p] <= a[q]))
                T[i++] = a[p++];
            else
                T[i++] = a[q++];
        }
        
        for (i = x; i < r; i++) {
            a[i] = T[i];
        }
    }
}

HW2

寻找最小值

int FindMin(int[] a, int n) {
    return n == 1 ? a[0] : Math.min(FindMin(a, n - 1), a[n - 1]);
}
//FindMin(a, a.length));

求和取平均

int Sum(int[] a, int n) {
    return n == 1 ? a[0] : Sum(a, n - 1) + a[n - 1];
}
//Sum(a, a.length) / a.length

HW3

堆排序

void HeapSort(int[] array) {
    int HeapSize = array.length;

    buildMinHeap(array);
    for (int i = 0; i < array.length; i++) {
        swap(array, 0, HeapSize - 1);
        MinHeapify(array, 0, --HeapSize);
    }

}

void MinHeapify(int[] array, int i, int HeapSize) {
    int min, l, r;
    l = left(i);
    r = right(i);
    if (l < HeapSize && array[i] >= array[l]) {
        min = l;
    } else {
        min = i;
    }
    if (r < HeapSize && array[min] >= array[r]) {
        min = r;
    }
    if (min != i) {
        swap(array, min, i);
        MinHeapify(array, min, HeapSize);
    }

}

void swap(int[] array, int x, int y) {
    int t = array[x];
    array[x] = array[y];
    array[y] = t;
}

void buildMinHeap(int[] array) {
    for (int i = (array.length - 1) / 2; i >= 0; i--) {
        MinHeapify(array, i, array.length);
    }

}

int left(int x) {
    return 2 * x + 1;
}

int right(int x) {
    return 2 * x + 2;
}

int father(int x) {
    return (x - 1) / 2;
}

HW4

快排

//QuickSort(a, 0, size - 1);
static void QuickSort(int[] a, int p, int r) {
    if (p < r) {
        int q = Partition(a, p, r);
        QuickSort(a, p, q - 1);
        QuickSort(a, q + 1, r);
    }
}

static int Partition(int[] a, int p, int r) {
    int x = a[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (a[j] <= x) {
            i++;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, r);
    return i + 1;
}

static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

计数排序

//CountingSort(a, b, size);
static void CountingSort(int[] input, int[] output, int k) {
    int[] T = new int[k];
    int i, j;
    for (i = 0; i < T.length; i++) {
        T[i] = 0;
    }
    for (j = 0; j < input.length; j++) {
        T[input[j]]++;
    }
    for (i = 1; i < k; i++) {
        T[i] = T[i] + T[i - 1];
    }
    for (j = input.length - 1; j >= 0; j--) {
        output[--T[input[j]]] = input[j];

    }
}

HW5

栈

class Stack {
    int[] data;
    int top;

    public Stack(int N) {
        this.data = new int[N];
        this.top = -1;
    }

    void Push(int x) throws Exception {
        if (top == data.length - 1) {
            throw new Exception("StackOverFlow");
        } else {
            this.data[++top] = x;
        }
    }

    int Pop() throws Exception {
        if (top==-1) {
            throw new Exception("StackUnderFlow");
        } else {
            return this.data[top--];
        }
    }
    boolean IsEmpty() {
        if(top==-1) {
            return false;
        }else {
            return true;
        }
    }
}
//Test

try {
    S.Push(1);
    S.Push(2);
    S.Push(3);
} catch (Exception e) {
    e.printStackTrace();
}

队列

class Queue {
    int data[];
    int front;
    int rear;

    public Queue(int N) {
        this.data = new int[N];
        this.front = this.rear = -1;
    }

    void Enqueue(int x) throws Exception {
        if (rear == data.length - 1) {
            throw new Exception("QueueOverFlow");
        } else {
            this.data[++rear] = x;
        }
    }

    int Dequeue() throws Exception {
        if (front >= rear) {
            throw new Exception("QueueUnderFlow");
        } else {
            return this.data[++front];
        }
    }

    boolean IsEmpty() {
        if (front >= rear) {
            return false;
        } else {
            return true;
        }
    }
}
//Test
try {
    Q.Enqueue(1);
    Q.Enqueue(2);
    Q.Enqueue(3);
} catch (Exception e) {
    e.printStackTrace();
}

HW6

链表

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList L = new LinkedList();
        // Insert a new Node x at the beginning of the list
        Node x = new Node(1);
        L.Insert(x);
        // Insert a node with key equal to x at the beginning of the list
        L.Insert(new Node(2));
        // Insert a node x after node cur
        if (L.Insert(new Node(3), x)) {
            System.out.println("successfully insert a node x after node cur");
        } else {
            System.out.println("did not found node cur");
        }
        // Delete a node x
        L.Delete(x);
        // Delete a node with key of x
        if (L.Delete(2)) {
            System.out.println("successfully delete a node with key of x");
        } else {
            System.out.println("did not found node with the very key");
        }
        // Search the node with key equal to x
        Node s = L.Search(3);
        // Print out the list from the beginning
        L.print();
    }
}
class Node {
    int v;
    Node pre;
    Node next;

    public Node(int x) {
        this.v = x;
        pre = null;
        next = null;
    }
}

class LinkedList {
    Node sential = new Node(-1);

    public LinkedList() {
        this.sential.pre = this.sential;
        this.sential.next = this.sential;
    }

    public void Insert(Node N) {
        N.next = this.sential.next;
        this.sential.next.pre = N;
        this.sential.next = N;
        N.pre = this.sential;
    }

    public boolean Insert(Node N, Node M) {
        Node cur = sential.next;
        while (cur != sential) {
            if (cur == M) {
                N.next = cur.next;
                cur.next.pre = N;
                N.pre = cur;
                cur.next = N;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void Delete(Node x) {
        x.next.pre = x.pre;
        x.pre.next = x.next;
    }

    public boolean Delete(int x) {
        Node cur = sential.next;
        while (cur != sential) {
            if (cur.v == x) {
                cur.next.pre = cur.pre;
                cur.pre.next = cur.next;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public Node Search(int x) {
        Node cur = sential.next;
        while (cur != sential) {
            if (cur.v == x) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    public void print() {
        Node cur = sential.next;
        while (cur != sential) {
            System.out.println(cur.v);
            cur = cur.next;
        }
    }
}

HW7

BST

public class BST_Test {
    public static void main(String[] args) {
        BST Tree =new BST(5);
        for(int i=0;i<10;i++) {
            Tree.Insert(Tree.PtrR,(int)(Math.random()*10));
        }
        System.out.println("Height:");
        System.out.println(Tree.Height(Tree.PtrR));
        System.out.println("PreOrder:");
        Tree.PreOrder(Tree.PtrR);
        System.out.println("InOrder:");
        Tree.InOrder(Tree.PtrR);
        System.out.println("PostOrder:");
        Tree.PostOrder(Tree.PtrR);
        System.out.println("Minimum:");
        System.out.println(Tree.Tree_MinimumRecursive(Tree.PtrR).key);
        System.out.println("Maximum:");
        System.out.println(Tree.Tree_MaximumIterative(Tree.PtrR).key);
        System.out.println("Search:");
        System.out.println(Tree.Tree_SearchRecursive(Tree.PtrR,5).key);
        System.out.println("Successor:");
        System.out.println(Tree.Tree_Successor(Tree.PtrR).key);
        
    }

}

class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;
    TreeNode parent;

    public TreeNode(int key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

class BST {
    public TreeNode PtrR;

    public BST(int key) {
        TreeNode Root = new TreeNode(key);
        PtrR = Root;
    }

    public TreeNode Insert(TreeNode T, int key) {
        if (T == null) {
            return new TreeNode(key);
        }
        if (T.key < key) {
            T.right = Insert(T.right, key);
            T.right.parent = T;
        } else if (T.key >= key) {
            T.left = Insert(T.left, key);
            T.left.parent = T;
        }
        return T;
    }

    public int Height(TreeNode T) {
        if (T == null) {
            return 0;
        } else {
            return Math.max(Height(T.left), Height(T.right)) + 1;
        }
    }

    public void PreOrder(TreeNode T) {
        if (T == null) {
            return;
        }
        System.out.println(T.key);
        PreOrder(T.left);
        PreOrder(T.right);
    }

    public void InOrder(TreeNode T) {
        if (T == null) {
            return;
        }

        InOrder(T.left);
        System.out.println(T.key);
        InOrder(T.right);
    }

    public void PostOrder(TreeNode T) {
        if (T == null) {
            return;
        }
        PostOrder(T.left);
        PostOrder(T.right);
        System.out.println(T.key);
    }

    public TreeNode Tree_MinimumRecursive(TreeNode T) {
        if (T.left == null) {
            return T;
        }
        return Tree_MinimumRecursive(T.left);
    }

    public TreeNode Tree_MaximumIterative(TreeNode T) {
        while (T.right != null) {
            T = T.right;
        }
        return T;
    }

    public TreeNode Tree_SearchRecursive(TreeNode T, int key) {
        if (T.key == key) {
            return T;
        } else {
            if (key >= T.key) {
                return Tree_SearchRecursive(T.right, key);
            }
            if (key < T.key) {
                return Tree_SearchRecursive(T.left, key);
            }
        }
        return null;
    }

    public TreeNode Tree_Successor(TreeNode T) {
        if (T.right != null) {
            return Tree_MinimumRecursive(T.right);
        }

        while (T.parent != null && T.parent.right == T) {
            T = T.parent;
        }
        return T.parent;
    }

}

HW8

class Vertex

class Vertex {
    String name;
    String color;

    public Vertex(String name) {
        this.name = name;
        this.color = "White";
    }

    public String toString() {
        return this.name;
    }

    public String getColor() {
        return color;
    }

    public void setColor(String color) {
        this.color = color;
    }
}

BFS

void BFS(Map<Vertex, List<Vertex>> G, Vertex V) {
    Queue<Vertex> Q = new LinkedList<>();
    Q.add(V);
    V.setColor("Grey");
    while (!Q.isEmpty()) {
        Vertex current = Q.poll();
        System.out.println(current.toString());
        current.setColor("Black");
        List<Vertex> adjacent = G.get(current);
        for (Vertex n : adjacent) {
            if (n.getColor().equals("White")) {
                Q.add(n);
                n.setColor("Grey");
            }
        }
    }
}

DFS

//非递归写法
void DFS(Map<Vertex, List<Vertex>> G, Vertex V) {
    Stack<Vertex> S = new Stack<>();
    S.push(V);
    V.setColor("Grey");
    System.out.println(V.toString());
    while (!S.isEmpty()) {
        Vertex current = S.peek();
        boolean isFinished = true;
        List<Vertex> adjacent = G.get(current);
        for (Vertex n : adjacent) {
            if (n.getColor().equals("White")) {
                S.push(n);
                System.out.println(n.toString());
                isFinished = false;
                n.setColor("Grey");
                break;
            }
        }
        if (isFinished) {
            S.pop().setColor("Black");
        }
    }
}

HW9

class Vertex

class Vertex {
    private String name;
    private Vertex p;
    private int distance;
    private boolean isCollected;

    public Vertex(String name) {
        this.name = name;
        this.p = null;
        this.distance = Integer.MAX_VALUE;
        this.isCollected = false;
    }

    @Override
    public String toString() {
        return this.name;
    }

    public String getName() {
        return name;
    }

    public boolean isCollected() {
        return isCollected;
    }

    public void setCollected(boolean isCollected) {
        this.isCollected = isCollected;
    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }
    //p for previous
    public Vertex getP() {
        return p;
    }

    public void setP(Vertex p) {
        this.p = p;
    }

}

Dijkstra

void Dijkstra(Graph G) {
    PriorityQueue<Vertex> PQ = new PriorityQueue<Vertex>(new Comparator<Vertex>() {
        @Override
        public int compare(Vertex o1, Vertex o2) {
            return o1.getDistance() - o2.getDistance();
        }
    });
    G.vS.setDistance(0);
    PQ.add(G.vS);
    PQ.add(G.vT);
    PQ.add(G.vY);
    PQ.add(G.vX);
    PQ.add(G.vZ);
    while (!PQ.isEmpty()) {
        Vertex current = PQ.poll();
        current.setCollected(true);
        for (Vertex V : G.Map.get(current).keySet()) {
            if (!V.isCollected()) {
                if (V.getDistance() > current.getDistance() + G.Map.get(current).get(V)) {
                    V.setDistance(current.getDistance() + G.Map.get(current).get(V));
                    V.setP(current);
                    PQ.remove(V);
                    PQ.add(V);
                }
            }
        }
    }
}

HW10

Climb Stairs

两个参数 n, k

n 阶梯总数

k 一步能上的最大阶梯数

climbstairs_iterative

public int climbstairs_iterative(int n, int k) {
    int[] dp = new int[n + 1];
    if (n > k) {
        for (int i = 1; i <= k; i++) {
            dp[i] = 0;
            for (int j = 1; j < i; j++) {
                dp[i] += dp[i - j];
            }
            dp[i]++;
        }
        for (int i = k + 1; i < dp.length; i++) {
            dp[i] = 0;
            for (int j = 1; j <= k; j++) {
                dp[i] += dp[i - j];
            }
        }
        return dp[n];
    } else {
        for (int i = 1; i <= n; i++) {
            dp[i] = 0;
            for (int j = 1; j < i; j++) {
                dp[i] += dp[i - j];
            }
            dp[i]++;
        }
        return dp[n];
    }
}

climbstairs_recursive

public int climbstairs_recursive(int n, int k) {
    if (n == 1) {
        return 1;
    } else if (n <= k) {
        int a = 0;
        for (int i = 1; i < n; i++) {
            a += climbstairs_recursive(i, k);
        }
        return a + 1;
    } else if (n > k) {
        int a = 0;
        for (int i = 1; i <= k; i++) {
            a += climbstairs_recursive(n - i, k);
        }
        return a;
    }
    return 0;
}

Combination

//Test case 
//combination(a, k, 0);
public int combination(ArrayList<Integer> a, int[] k, int Pos) {
    if (Pos == k.length) {
        System.out.println(Arrays.toString(k));
        return 1;
    }
    ArrayList<Integer> b = new ArrayList<>();
    int sum = 0;
    while(!a.isEmpty()) {
        k[Pos] = a.get(0);
        a.remove(0);
        b.addAll(a);
        sum += combination(b, k, Pos + 1);
    }
    return sum;
}

HW11

Permutation

public void PermutationTest() {
    // Test case: n=5, k=3
    int n = 5;
    int k = 2;
    int Pos = 0;
    int[] p = new int[k];
    ArrayList<Integer> a = new ArrayList<Integer>();
    for (int i = 1; i <= n; i++) {
        a.add(i);
    }
    System.out.println(String.format("P(%d,%d):", k, n));
    System.out.println("Sum is " + Permutation(a, p, Pos));
}

public int Permutation(ArrayList<Integer> a, int[] k, int Pos) {
    if (Pos == k.length) {
        System.out.println(Arrays.toString(k));
        return 1;
    }
    int sum = 0;
    for (int i = 0; i < a.size(); i++) {
        k[Pos] = a.get(i);
        ArrayList<Integer> b = new ArrayList<Integer>();
        b.addAll(a);
        b.remove(i);
        sum += Permutation(b, k, Pos + 1);
    }
    return sum;
}

Rod Cut

public void CutTest() {
    // Test case: n = 9
    int n = 9;
    ArrayList<Integer> solution = new ArrayList<Integer>();
    int[] price = new int[] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
    System.out.println("Solution: ");
    System.out.println("The best price is: " + RodCut(solution, price, n));
}

public int RodCut(ArrayList<Integer> solution, int[] price, int n) {
    if (n == 0) {
        System.out.println(solution.toString());
        return 0;
    } else {
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (i < price.length) {
                if (solution.isEmpty() || (!solution.isEmpty() && solution.get(solution.size() - 1) <= i)) {
                    solution.add(i);
                    q = Math.max(q, price[i] + RodCut(solution, price, n - i));
                    solution.remove(solution.size() - 1);
                }
            }
        }
        return q;
    }
}