231217 刷题日报

1. LRU

2.LFU

3. 十字链表，加法，乘法

public class Main {
    public static void main(String[] args) {
        CrossLinkedList list = new CrossLinkedList(3, 3);
        list.insert(0, 0, 1);
        list.insert(1, 0, 5);
        list.insert(2, 2, 3);

        list.display();
        System.out.println("----------");


        CrossLinkedList listB = new CrossLinkedList(3, 3);
        listB.insert(0, 0, 1);
        // listB.insert(1, 0, 5);
        listB.insert(2, 2, 3);

        listB.display();
        System.out.println("----------");
/*
        list.add(listB);
        list.display();

        System.out.println("----------");*/

        list.mutiply(listB);
        list.display();

    }
}

class CrossLinkedList {
    Node[] rheads, cheads;
    int rows, cols;

    CrossLinkedList(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        rheads = new Node[rows];
        cheads = new Node[cols];
    }

    public void insert(int row, int col, int value) {
        Node newNode = new Node(row, col, value);
        Node currNode = rheads[row];
        if (null == currNode || currNode.col > newNode.col) {
            newNode.right = currNode;
            rheads[row] = newNode;
        } else {
            while(currNode.right != null && currNode.right.col < newNode.col) {
                currNode = currNode.right;
            }
            newNode.right = currNode.right;
            currNode.right = newNode;
        }
        currNode = cheads[col];
        if (null == currNode || currNode.row > newNode.row) {
            newNode.down = currNode;
            cheads[col] = newNode;
        } else {
            while(currNode.down != null && currNode.down.row < newNode.row) {
                currNode = currNode.down;
            }
            newNode.down = currNode.down;
            currNode.down = newNode;
        }
    }

    public void display() {
        for(int i=0; i<rows; i++) {
            Node currNode = rheads[i];
            if (null == currNode) {
                for(int j=0; j<cols; j++) {
                    System.out.printf("0 ");
                }
            } else {
                int j=0;
                while (j < cols) {
                    if (null == currNode || j < currNode.col) {
                        System.out.printf("0 ");
                    } else {
                        System.out.printf("%d ", currNode.value);
                        currNode = currNode.right;
                    }
                    j++;
                }
            }
            System.out.println();
        }
    }


    public void add(CrossLinkedList N) {
        Node pa, pb; // 新增两个用于便利两个矩阵的节点
        Node[] hl = new Node[this.cols];
        Node pre = null;
        // 对hl数组初始化，指向每一列的第一个非0元素
        for(int j=0; j<this.cols; j++) {
            hl[j] = this.cheads[j];
        }

        // 按照行进行遍历
        for(int i=0; i<this.rows; i++) {
            pa = rheads[i];
            pb = N.rheads[i];
            // pb=null说明矩阵N当前行的非零元素已经遍历完
            while (pb != null) {
                Node p = new Node(pb);
                // 第1种情况: pa为空，或者pa.col > pb.col，此时将 pb 结点插入到矩阵 A 中。
                if (null == pa || pa.col > pb.col) {
                    // 如果pre=null，说明这行没有非0元素
                    if (pre == null) {
                        rheads[p.row] = p;
                    } else {
                        pre.right = p;
                    }
                    p.right = pa;
                    pre = p;
                    // 在链接好行链表后，链接到对应列的列链表种的相应位置
                    if (this.cheads[p.col] == null || this.cheads[p.col].row > p.row) {
                        p.down = this.cheads[p.col];
                        this.cheads[p.col] = p;
                    } else {
                        p.down = hl[p.col].down;
                        hl[p.col].down = p;
                    }
                    // 更新hl中的数据
                    hl[p.col] = p;
                } else {
                    // 第2种情况，pa.col < pb.col，只需移动pa的位置，继续判断pa和pb的位置
                    if (pa.col < pb.col) {
                        pre = pa;
                        pa = pa.right;
                        continue;
                    }
                    // 第3，4种情况，当行标和列标都相等的情况下，需要讨论两者相加的值的问题
                    if (pa.col == pb.col) {
                        pa.value += pb.value;
                        if (pa.value == 0) {
                            if (pre == null) {
                                this.rheads[pa.row] = pa.right;
                            } else {
                                pre.right = pa.right;
                            }
                            p = pa;
                            pa = pa.right;
                            if (this.cheads[p.col] == p) {
                                this.cheads[p.col] = hl[p.col] = p.down;
                            } else {
                                hl[p.col].down = p.down;
                            }
                        }

                    }
                }
                pb = pb.right;
            }
        }
    }

    public void mutiply(CrossLinkedList list) {
        Node prev = null;
        for(int row=0; row < rows; row++) {
            Node pa = rheads[row];
            Node pb = list.rheads[row];

            while(pa != null) {
                if (pb == null) {
                    // remove pa
                    remove(prev, pa);
                    break;
                }
                if (pa.col < pb.col) {
                    remove(prev, pa);
                    pa = pa.right;
                } else if (pa.col > pb.col) {
                    pb = pb.right;
                } else {
                    // pb不为null，相乘
                    pa.value *= pb.value;
                    pa = pa.right;
                    pb = pb.right;
                }
                prev = pa;
            }


        }
    }

    public void remove(Node prev, Node node) {
        if (prev == null) {
            rheads[node.row] = node.right;
            return;
        }
        prev.right = node.right;
    }
}

class Node {
    int row, col, value;
    Node right, down;
    Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }

    Node(Node node) {
        this.row = node.row;
        this.col = node.col;
        this.value = node.value;
    }

}

4. 225. 用队列实现栈

class MyStack {
    Queue<Integer> queueOut = new LinkedList<>();
    Queue<Integer> queueIn = new LinkedList<>();

    public void push(int x) {
        queueIn.offer(x);
    }

    public int pop() {
        if (queueOut.isEmpty()) {
            queueOut = queueIn;
            queueIn = new LinkedList<>();
        }
        while (queueOut.size() > 1) {
            queueIn.offer(queueOut.poll());
        }
        return queueOut.poll();
    }

    public int top() {
        int value = pop();
        queueIn.offer(value); // 注意，入队ququeIn
        return value;
    }

    public boolean empty() {
        return queueIn.isEmpty() && queueOut.isEmpty();
    }

}

5.?232. 用栈实现队列

class MyQueue {
    Stack<Integer> stackIn, stackOut;
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        while(stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }
    
    public int peek() {
        int value = pop();
        stackOut.push(value); // 注意，压栈stackOut
        return value;
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

第4题和第5题统一写法，都是实现pop方法，但是要注意，peek和top，