2021-11-27

一.栈

1.getmin栈

class MyStack{
    public MyStack(Stack<Integer> stackData, Stack<Integer> stackMin) {
        this.stackData = stackData;
        this.stackMin = stackMin;
    }
    private Stack<Integer> stackData; //存所有值的
    private Stack<Integer> stackMin;//始终存存的是最小值
    public void push(int num){
     if(this.stackMin.empty()){
         this.stackMin.push(num);
     }else if (num< this.getMin()){
         this.stackMin.push(num);
     }
     this.stackData.push(num);
    }
    public int pop(){
        if(this.stackData.empty()){
            throw new RuntimeException("empty stack");
        }
        int value=this.stackData.pop();
        if(this.getMin()==value){
            this.stackMin.pop();
        }
        return value;
    }
    public int getMin(){
        if(this.stackMin.empty()){
            throw new RuntimeException("empty stack");
        }
        return  this.stackMin.peek();

    }
}

image.gif

2.猫狗队列

public static class Pet {
        private String type;
        public Pet(String type) {
            this.type = type;
        }

        public String getPetType() {
            return this.type;
        }
    }

    public static class Dog extends Pet {
        public Dog() {
            super("dog");
        }
    }

    public static class Cat extends Pet {
        public Cat() {
            super("cat");
        }
    }

    public static class PetEnterQueue {
        private Pet pet;
        private long count;

        public PetEnterQueue(Pet pet, long count) {
            this.pet = pet;
            this.count = count;
        }

        public Pet getPet() {
            return this.pet;
        }

        public long getCount() {
            return this.count;
        }

        public String getEnterPetType() {
            return this.pet.getPetType();
        }
    }

    public static class DogCatQueue {
        //queue的方法
        //尾部添加
        //boolean add(E e);
        //boolean offer(E e);
        //他们的共同之处是建议实现类禁止添加 null 元素，否则会报空指针 NullPointerException；
        //不同之处在于 add() 方法在添加失败（比如队列已满）时会报 一些运行时错误 错；而 offer() 方法即使在添加失败时也不会奔溃，只会返回 false。
        //删除返回头部
        //E remove();
        //E poll();
        //当队列为空时 remove() 方法会报 NoSuchElementException 错; 而 poll() 不会奔溃，只会返回 null。
        //返回头部
        //E element();
        //E peek();
        //当队列为空时 element() 抛出异常；peek() 不会奔溃，只会返回 null。
        private Queue<PetEnterQueue> dogQ;
        private Queue<PetEnterQueue> catQ;
        private long count;

        //1.add方法将cat类或dog类的实例放入队列中
        //2.pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
        //3.pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
        //4.pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
        //5.isEmpty方法，检查队列中是否还有dog或cat的实例；
        //6.isDogEmpty方法，检查队列中是否有dog类的实例；
        //7.isCatEmpty方法，检查队列中是否有cat类的实例。
        public DogCatQueue() {
            this.dogQ = new LinkedList<PetEnterQueue>();
            this.catQ = new LinkedList<PetEnterQueue>();
            this.count = 0;
        }

        public void add(Pet pet) {
            if (pet.getPetType().equals("dog")) {
                this.dogQ.add(new PetEnterQueue(pet, this.count++));
            } else if (pet.getPetType().equals("cat")) {
                this.catQ.add(new PetEnterQueue(pet, this.count++));
            } else {
                throw new RuntimeException("err, not dog or cat");
            }
        }

        public Pet pollAll() {
            if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
                //总是数量多的那个后入队列的
                if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
                    return this.dogQ.poll().getPet();
                } else {
                    return this.catQ.poll().getPet();
                }
            } else if (!this.dogQ.isEmpty()) {
                return this.dogQ.poll().getPet();
            } else if (!this.catQ.isEmpty()) {
                return this.catQ.poll().getPet();
            } else {
                throw new RuntimeException("err, queue is empty!");
            }
        }

        public Dog pollDog() {
            if (!this.isDogQueueEmpty()) {
                return (Dog) this.dogQ.poll().getPet();
            } else {
                throw new RuntimeException("Dog queue is empty!");
            }
        }

        public Cat pollCat() {
            if (!this.isCatQueueEmpty()) {
                return (Cat) this.catQ.poll().getPet();
            } else
                throw new RuntimeException("Cat queue is empty!");
        }

        public boolean isEmpty() {
            return this.dogQ.isEmpty() && this.catQ.isEmpty();
        }

        public boolean isDogQueueEmpty() {
            return this.dogQ.isEmpty();
        }

        public boolean isCatQueueEmpty() {
            return this.catQ.isEmpty();
        }

    }

3.一个栈实现另外栈的排序

public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<Integer>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && help.peek() < cur) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

二.链表

1.print 2个有序链表的公共部分

class Node{
    public int value;
    public Node next;
    public Node(int data){
        this.value=data;
    }
}
public class NodeTest {
    public void printCommonPart(Node head1,Node head2){
        while(head1!=null&&head2!=null){
            if (head1.value<head2.value){
                head1=head1.next;
            }else if (head1.value>head2.value){
                head2=head2.next;
            }else{
                System.out.println(head1.value);
                head1=head1.next;
                head2=head2.next;
            }
        }
    }
}

2.单双链表删除倒数第k个节点

//单
//类似差值    
public static Node removeLastKthNode(Node head, int lastKth) {
        if (head == null || lastKth < 1) {
            return head;
        }
        Node cur = head;
        while (cur != null) {
            lastKth--;
            cur = cur.next;
        }
        if (lastKth == 0) {
            head = head.next;
        }
        if (lastKth < 0) {
            cur = head;
            while (++lastKth != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return cur;
    }
//栈
//双指针
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        // 让快指针先走k步，和慢指针相差k个距离
        for (int i = k; i > 0; i--) {
            fast = fast.next;
        }

        // 此时让慢指针和快指针同时走，知道快指针到达链表末尾为null时，慢指针就在倒数第k个位置上了
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 直接返回慢指针即为答案
        return slow;
    }
}

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        // 让快指针先走k步，和慢指针相差k个距离
        for (int i = k; i > 0; i--) {
            fast = fast.next;
        }

        // 此时让慢指针和快指针同时走，知道快指针到达链表末尾为null时，慢指针就在倒数第k个位置上了
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 直接返回慢指针即为答案
        return slow;
    }
}

//作者：linzeliang1222
//链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/jian-zhi-offer-22-lian-biao-zhong-dao-sh-ixsa/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            this.value = data;
        }
    }

    public static DoubleNode removeLastKthNode(DoubleNode head, int lastKth) {
        if (head == null || lastKth < 1) {
            return head;
        }
        DoubleNode cur = head;
        while (cur != null) {
            lastKth--;
            cur = cur.next;
        }
        if (lastKth == 0) {
            head = head.next;
            head.last = null;
        }
        if (lastKth < 0) {
            cur = head;
            while (++lastKth != 0) {
                cur = cur.next;
            }
            DoubleNode newNext = cur.next.next;
            cur.next = newNext;
            if (newNext != null) {
                newNext.last = cur;
            }
        }
        return head;
    }

3.删除链表的中间节点和a/b处的节点
4.反转单向和双向链表
5.反转部分单向链表
6.环形单链表约瑟夫
7.判断一个表是否是回文结构
8.两个单链表组成相加链表
9.删除无序单链表中重复出现的节点
10.单链表删除指定节点
11.单链表的选择排序
12.一种怪异的节点删除方式
13.有序环形单链表中插入新节点
14.合并两个有序单链表
15.按照左右半区的方式重新组合单链表

三.二叉树

1.二叉树的序列化和反序列化
2.判断t1树是否包含t2树的全部拓扑结构
3.判断二叉树是否为平衡二叉树
4.根据后续数组重建搜索二叉树
5.判断一颗二叉树是否为搜索二叉树和完全二叉树
6.通过有序数组生成平衡搜索二叉树
7.通过先序和中序生成后序列数组