Java---刷题02

发布于:2022-11-09 ⋅ 阅读:(8) ⋅ 点赞:(0) ⋅ 评论:(0)

1、数组转字符串

实现一个方法 toString, 把一个整型数组转换成字符串. 例如数组 {1, 2, 3} , 返回的字符串为 "[1, 2, 3]", 注意 逗号 的位置和数量

2、118. 杨辉三角 - 力扣(LeetCode)

3、27. 移除元素 - 力扣(LeetCode)

4、26. 删除有序数组中的重复项 - 力扣(LeetCode)

5、88. 合并两个有序数组 - 力扣(LeetCode)

6、实现 ArrayList 类

public class MyArraylist {
 
    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;
 
    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }
 
    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {
       
    }
 
    // 新增元素,默认在数组最后新增
    public void add(int data) {
       
    }
 
    /**
     * 判断当前的顺序表是不是满的!
     * @return true:满   false代表空
     */
    public boolean isFull() {
       
    }
 
 
    private boolean checkPosInAdd(int pos) {
       
        return true;//合法
    }
 
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        
    }
 
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        
        return -1;
    }
 
    // 获取 pos 位置的元素
    public int get(int pos) {
       
    }
 
    private boolean isEmpty() {
        
    }
    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        
    }
 
    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
       
    }
 
    // 获取顺序表长度
    public int size() {
       
    }
 
    // 清空顺序表
    public void clear() {
        
    }
public class MyArraylist {
 
    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;
 
    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }
 
    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {
        //usedSize==0
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }
 
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //1、判断是否是满的,如果满的,那么进行扩容
        if(isFull()) {
            //扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //2、不满进行插入
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
 
    /**
     * 判断当前的顺序表是不是满的!
     * @return true:满   false代表空
     */
    public boolean isFull() {
        /*if(this.usedSize == this.elem.length) {
            return true;
        }
        return false;*/
        return this.usedSize == this.elem.length;
    }
 
 
    private boolean checkPosInAdd(int pos) {
        if(pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法");
            return false;
        }
        return true;//合法
    }
 
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        //判断下标是否是合法的
        if(!checkPosInAdd(pos)) {
            throw new MyArrayListIndexOutOfException("添加方法的pos不合理!");
        }
        //判断是否是满的
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //挪数据
        for (int i = this.usedSize-1; i >= pos ; i--) {
            this.elem[i+1] = this.elem[i];
        }
        //挪完了数据
        this.elem[pos] = data;
        this.usedSize++;
    }
 
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
 
 
    private boolean checkPosInGet(int pos) {
        if(pos < 0 || pos >= this.usedSize) {
            System.out.println("pos位置不合法");
            return false;
        }
        return true;//合法
    }
 
    // 获取 pos 位置的元素
    public int get(int pos) {
        if(!checkPosInGet(pos)) {
            throw new MyArrayListIndexOutOfException("获取pos下标时,位置不合法");
        }
        //不用写判断空不空 没有问题的
        if(isEmpty()) {
            throw new MyArrayListEmptyException("获取元素的时候,顺序表为空!");
        }
        return this.elem[pos];
    }
 
 
    private boolean isEmpty() {
        return this.usedSize == 0;
    }
 
    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        if(!checkPosInGet(pos)){
            throw new MyArrayListIndexOutOfException("更新pos下标的元素,位置不合法");
        }
        //如果合法 ,那么其实不用判断顺序表为空的状态了
        if(isEmpty()) {
            throw new MyArrayListEmptyException("顺序表为空!");
        }
        //顺序表为满的情况也可以更新
        this.elem[pos] = value;
    }
 
 
    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        if(isEmpty()) {
            throw new MyArrayListEmptyException("顺序表为空,不能删除!");
        }
        int index = indexOf(key);
        if(index == -1) {
            System.out.println("不存在你要删除的数据");
            return;
        }
 
        for (int i = index; i < this.usedSize-1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        //删除完成
        this.usedSize--;
        // this.elem[usedSize] = null; 如果是引用类型 这里需要置为空
    }
 
 
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
 
    // 清空顺序表
    public void clear() {
        /*
        如果是引用数据类型 得一个一个置为空 这样做才是最合适的
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }
        this.usedSize = 0;
        */
 
        this.usedSize = 0;
    }

7、实现无头单链表的基本操作

 // 1、无头单向非循环链表实现
 public class SingleLinkedList {
     //头插法
     public void addFirst(int data);
     //尾插法
     public void addLast(int data);
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data);
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key);
     //删除第一次出现关键字为key的节点
     public void remove(int key);
     //删除所有值为key的节点
     public void removeAllKey(int key);
     //得到单链表的长度
     public int size();
     public void display();
     public void clear();
 }

public class SingleLinkedList{
 
    static class ListNode {
        public int val;//数值域public ListNode next;//存储下一个节点的地址
 
        public ListNode(int val) {
            this.val = val;
        }
    }
 
    public ListNode head;//代表单链表的头结点的引用
 
    /**
     * 这里只是简单的进行,链表的构造。
     */public void createList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
 
        listNode1.next = listNode2;
 
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }
 
 
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    /**
     * 从指定的节点开始答应
     * @param newHead
     */public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
 
 
    /**
     * 头插法
     * OaddLast
     */public void addFirst(int data){
        ListNode node = new ListNode(data);
        /*if(this.head == null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }*/
        node.next = this.head;
        this.head = node;
    }
 
    //尾插法 O(n)public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
        }else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //cur.next == null;
            cur.next = node;
        }
    }
 
    /**
     * 任意位置插入,第一个数据节点为0号下标
     * 指定位置插入
     */
 
    public void addIndex(int index,int data) throws MySingleListIndexOutOfException{
        checkIndexAdd(index);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndexSubOne(index);
        node.next = cur.next;
        cur.next = node;
    }
 
    /**
     * 找到index-1位置的节点
     * @param index
     * @return 该节点的地址
     */private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
 
    private void checkIndexAdd(int index) {
        if(index < 0 || index > size()) {
            throw new MySingleListIndexOutOfException("任意位置插入的时候,index不合法!");
        }
    }
 
    //查找是否包含关键字key是否在单链表当中  314public boolean contains(int key) {
        //head == null
        ListNode cur = this.head;
        //cur != null 说明 没有遍历完 链表while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
 
    //删除第一次出现关键字为key的节点public void remove(int key){
 
        if(this.head == null) {
            System.out.println("此时链表为空,不能进行删除!");
            return;
        }
 
        if(this.head.val == key) {
            //判断 第一个节点是不是等于我要删除的节点this.head = this.head.next;
            return;
        }
 
        ListNode cur = this.head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                //进行删除了
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }
    //删除所有值为key的节点public void removeAllKey(int key){
        if(this.head == null) {
            return;
        }
 
        ListNode cur = this.head.next;
        ListNode prev = this.head;
 
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //单独处理了头节点if(this.head.val == key) {
            head = head.next;
        }
    }
 
    //得到单链表的长度public int size(){
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
 
    /**
     * 当我们 执行clear这个函数的时候,会将这个链表当中的所有的节点回收
     */public void clear(){
        //this.head = null;//这种做法 比较粗暴!
        ListNode cur = this.head;
        ListNode curNext = null;
        while (cur != null) {
            curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }
}
 

8、203. 移除链表元素 - 力扣(LeetCode)

9、206. 反转链表 - 力扣(LeetCode)

10、876. 链表的中间结点 - 力扣(LeetCode)

11、链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

12、模拟实现 LinkedList 类

// 2、无头双向链表实现
 public class LinkedList {
     //头插法
     public void addFirst(int data);
     //尾插法
     public void addLast(int data);
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data);
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key);
     //删除第一次出现关键字为key的节点
     public void remove(int key);
     //删除所有值为key的节点
     public void removeAllKey(int key);
     //得到单链表的长度
     public int size();
     public void display();
     public void clear();
 }
public class MyLinkedList {
 
 
 
    static class ListNode {
 
        public int val;
 
        public ListNode prev;//前驱
 
        public ListNode next;//后继
 
 
 
        public ListNode(int val) {
 
            this.val = val;
 
        }
 
    }
 
 
 
    public ListNode head;//标记头
 
    public ListNode last;//标记尾巴
 
 
 
    MyLinkedList() {
 
        //last = head = new ListNode(-1);
 
    }
 
 
 
 
 
    public void display(){
 
        ListNode cur = head;
 
        while (cur != null) {
 
            System.out.print(cur.val+" ");
 
            cur = cur.next;
 
        }
 
        System.out.println();
 
    }
 
 
 
    //头插法
 
    public void addFirst(int data){
 
        ListNode node = new ListNode(data);
 
        if(head == null) {
 
            head = node;
 
            last = node;
 
        }else {
 
            node.next = head;
 
            head.prev = node;
 
            head = node;
 
        }
 
    }
 
    //尾插法
 
    public void addLast(int data){
 
        ListNode node = new ListNode(data);
 
        if(head == null) {
 
            head = node;
 
            last = node;
 
        }else {
 
            last.next = node;
 
            node.prev = last;
 
            last = node;
 
        }
 
    }
 
 
 
    //任意位置插入,第一个数据节点为0号下标
 
    public void addIndex(int index,int data){
 
        if(index < 0 || index > size()) {
 
            System.out.println("index不合法!");
 
            return;
 
        }
 
        if(index == 0) {
 
            addFirst(data);
 
            return;
 
        }
 
        if(index == size()) {
 
            addLast(data);
 
            return;
 
        }
 
        //cur拿到了index下标的节点的地址
 
        ListNode cur = searchIndex(index);
 
        ListNode node = new ListNode(data);
 
        node.next = cur;
 
        cur.prev.next = node;
 
        node.prev = cur.prev;
 
        cur.prev = node;
 
    }
 
 
 
 
 
 
 
    private ListNode searchIndex(int index) {
 
        ListNode cur = head;
 
        while (index != 0) {
 
            cur = cur.next;
 
            index--;
 
        }
 
        return cur;
 
    }
 
 
 
    //查找是否包含关键字key是否在单链表当中
 
    public boolean contains(int key){
 
        ListNode cur = head;
 
        while (cur != null) {
 
            if(cur.val == key) {
 
                return true;
 
            }
 
            cur = cur.next;
 
        }
 
        return false;
 
    }
 
 
 
    //删除第一次出现关键字为key的节点
 
    public void remove(int key){
 
        ListNode cur = head;
 
        while (cur != null) {
 
            if(cur.val == key) {
 
                //判断当前是不是头节点
 
                if(cur == head) {
 
                    head = head.next;
 
                    if(head != null) {
 
                        head.prev = null;//这里有问题!!!! 一个节点!
 
                    }
 
                }else {
 
                    //中间和尾巴的情况
 
                    cur.prev.next = cur.next;
 
                    if(cur.next != null) {
 
                        cur.next.prev = cur.prev;
 
                    }else {
 
                        last = last.prev;
 
                    }
 
                }
 
                return;//删完走人
 
            }else {
 
                cur = cur.next;
 
            }
 
        }
 
    }
 
 
 
 
 
    //删除所有值为key的节点  之遍历链表一遍
 
    public void removeAllKey(int key){
 
        ListNode cur = head;
 
        while (cur != null) {
 
            if(cur.val == key) {
 
                //判断当前是不是头节点
 
                if(cur == head) {
 
                    head = head.next;
 
                    if(head != null) {
 
                        head.prev = null;//这里有问题!!!! 一个节点!
 
                    }
 
                }else {
 
                    //中间和尾巴的情况
 
                    cur.prev.next = cur.next;
 
                    if(cur.next != null) {
 
                        cur.next.prev = cur.prev;
 
                    }else {
 
                        last = last.prev;
 
                    }
 
                } 
                cur = cur.next;
 
            }else {
 
                cur = cur.next;
 
            }
 
        }
 
    }
 
    //得到单链表的长度 
    public int size(){
 
        int count = 0;
 
        ListNode cur = head;
 
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    } 
    public void clear(){
 
        ListNode cur = head;        
        while (cur != null) {
 
            ListNode curNext = cur.next;
 
            ///cur.val = null;
 
            cur.prev = null;
 
            cur.next = null;
 
            cur = curNext;
        } 
        head = null;
 
        last = null;
 
    } 
}

13、141. 环形链表 - 力扣(LeetCode)

14、142. 环形链表 II - 力扣(LeetCode)

15、160. 相交链表 - 力扣(LeetCode)

16、链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

17、链表分割_牛客题霸_牛客网 (nowcoder.com)

18、21. 合并两个有序链表 - 力扣(LeetCode)

19、20. 有效的括号 - 力扣(LeetCode)

20、栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

21、150. 逆波兰表达式求值 - 力扣(LeetCode)

22、最小栈 - 最小栈 - 力扣(LeetCode)

23、225. 用队列实现栈 题解 - 力扣(LeetCode)

24、232. 用栈实现队列 - 力扣(LeetCode)

25、622. 设计循环队列 - 力扣(LeetCode)

26、实现二叉树的基本操作

public class BinaryTree {
 
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
 
        public TreeNode(char val) {
            this.val = val;
        }
    }
 
 
    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
 
    }
 
    // 前序遍历
    public void preOrder(TreeNode root) {
    }
 
    // 中序遍历
    void inOrder(TreeNode root) {
    }
 
    // 后序遍历
    void postOrder(TreeNode root) {
    }
 
    public static int nodeSize;
 
    /**
     * 获取树中节点的个数:遍历思路
     */
    void size(TreeNode root) {
    }
 
    /**
     * 获取节点的个数:子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
    }
 
 
    /*
     获取叶子节点的个数:遍历思路
     */
    public static int leafSize = 0;
 
    void getLeafNodeCount1(TreeNode root) {
    }
 
    /*
     获取叶子节点的个数:子问题
     */
    int getLeafNodeCount2(TreeNode root) {
    }
 
    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
    }
 
    /*
     获取二叉树的高度
     时间复杂度:O(N)
     */
    int getHeight(TreeNode root) {
       
    }
 
 
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        
        return null;
    }
 
    //层序遍历
    void levelOrder(TreeNode root) {
        
    }
 
 
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        return true;
    }
}
public class BinaryTree {
 
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
 
        public TreeNode(char val) {
            this.val = val;
        }
    }
 
 
    /**
     * 创建一棵二叉树 返回这棵树的根节点
     * 暂且使用穷举的方式创建二叉树
     * @return
     */
    public TreeNode createTree() {
 
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
 
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //E.right = H;
        return A;
    }
 
    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
 
    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
 
    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
 
    public static int nodeSize;
 
    /**
     * 获取树中节点的个数:遍历思路
     */
    void size(TreeNode root) {
        if (root == null) return;
        nodeSize++;
        size(root.left);
        size(root.right);
    }
 
    /**
     * 获取节点的个数:子问题的思路
     *
     * @param root
     * @return
     */int size2(TreeNode root) {
        if (root == null) return 0;
        return size2(root.left)
                + size2(root.right) + 1;
    }
 
 
    /*
     获取叶子节点的个数:遍历思路
     */
    public static int leafSize = 0;
 
    void getLeafNodeCount1(TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }
 
    /*
     获取叶子节点的个数:子问题
     */int getLeafNodeCount2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }
 
    /*
    获取第K层节点的个数
     */int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return getKLevelNodeCount(root.left, k - 1) +
                getKLevelNodeCount(root.right, k - 1);
    }
 
    /*
     获取二叉树的高度
     时间复杂度:O(N)
     */int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }
 
 
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root == null) return null;
        if (root.val == val) return root;
 
        TreeNode ret = find(root.left, val);
        if (ret != null) {
            return ret;
        }
        ret = find(root.right, val);
        if (ret != null) {
            return ret;
        }
        return null;
    }
 
    //层序遍历
    void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
 
 
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        //第2次遍历队列 判断队列当中 是否存在非空的元素while (!queue.isEmpty()) {
            TreeNode cur = queue.peek();
            if (cur == null) {
                queue.poll();
            } else {
                return false;
            }
        }
        return true;
    }
}
 

27、二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

28、110. 平衡二叉树 - 力扣(LeetCode)

29、572. 另一棵树的子树 - 力扣(LeetCode)

30、101. 对称二叉树 - 力扣(LeetCode)

31、100. 相同的树 - 力扣(LeetCode)

32、226. 翻转二叉树 - 力扣(LeetCode)

33、144. 二叉树的前序遍历 - 力扣(LeetCode)

34、106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

35、105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)

36、236. 二叉树的最近公共祖先 - 力扣(LeetCode)

37、107. 二叉树的层序遍历 II - 力扣(LeetCode)

38、102. 二叉树的层序遍历 - 力扣(LeetCode)

39、面试题 17.14. 最小K个数 - 力扣(LeetCode)

40、优先级队列(堆)的模拟实现

public class PriorityQueue {
    public int[] elem;
    public int usedSize;
 
    public PriorityQueue() {
    }
 
    /**
     * 建堆的时间复杂度:
     *
     * @param array
     */
    public void createHeap(int[] array) {
    }
 
    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度:O(logn)
     */
    private void shiftDown(int root,int len) {
    }
 
 
    /**
     * 入队:仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
    }
 
    private void shiftUp(int child) {
    }
 
    public boolean isFull() {
    }
 
    /**
     * 出队【删除】:每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
    }
 
    public boolean isEmpty() {
    }
 
    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
    }
}
public class PriorityQueue {
    public int[] elem;
    public int usedSize;
 
    public PriorityQueue() {
        this.elem = new int[10];
    }
 
    /**
     * 建堆的时间复杂度:
     *
     * @param array
     */
    public void createHeap(int[] array) {
        //这一步不算是必须的。这里只是我们准备数据,不算做我的建堆时间复杂度当中
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
 
        for (int p = (usedSize-1-1)/2; p >= 0 ; p--) {
            shiftDown(p,usedSize);
        }
    }
 
    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度:O(logn)
     */
    private void shiftDown(int root,int len) {
        int parent = root;
        int child = 2*parent+1;
        //进入这个循环,说明一定至少有一个孩子
        while (child < len) {
            //如果有孩子,找到左右孩子的最大值
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            //child下标一定保存的是左右孩子最大值的下标
            //接下来,孩子的最大值和根节点去比较大小
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;//开始更新下标,继续看下面的子树是不是大根堆
                child = 2*parent+1;
            }else {
                break;//此时说明已经是大根堆,不需要进行再次调整了
            }
        }
    }
 
 
    /**
     * 入队:仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //1、放到最后的位置
        elem[usedSize] = val;
        //2、进行向上调整
        shiftUp(usedSize);
        //3、有效数据+1
        usedSize++;
    }
 
    private void shiftUp(int child) {
        int parent = (child-1) / 2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
 
    public boolean isFull() {
        return usedSize == elem.length;
    }
 
    /**
     * 出队【删除】:每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
        if(isEmpty()) {
            System.out.println("优先级队列为空!");
            return;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;//9
        shiftDown(0,usedSize);
    }
 
    public boolean isEmpty() {
        return usedSize == 0;
    }
 
    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        if(isEmpty()) {
            System.out.println("优先级队列为空!");
            return -1;
        }
        return elem[0];
    }
}
 

41、插入排序和希尔排序

//=====================================================
// 插入排序
public static void insertSort(int[] array){
    // 外层循环目的:取到数组中的每个元素
    for(int i = 1; i < array.length; ++i){
 
        // 将该元素插入到序列中
        // array数组中:[0, i)的元素已经排好了
 
        // i位置的数据是本次要插入的数据---[0,i)
        int key = array[i];
        int end = i-1;
 
        while(end >= 0 && key < array[end]){
            array[end+1] = array[end];
            end--;
        }
 
        array[end+1] = key;
    }
}
 
//===========================================================
// 希尔排序
public static void shellSort(int[] array){
    int gap = array.length;
 
    while(gap > 1){
        gap = gap/3+1;
        for(int i = gap; i < array.length; ++i){
 
            // 将该元素插入到序列中
            // array数组中:[0, i)的元素已经排好了
 
            // i位置的数据是本次要插入的数据---[0,i)
            int key = array[i];
            int end = i-gap;
 
            while(end >= 0 && key < array[end]){
                array[end+gap] = array[end];
                end -= gap;
            }
 
            array[end+gap] = key;
        }
    }
}

42、选择排序和堆排序

//============================================================
// 选择排序
// 时间复杂度:O(N^2)
// 空间复杂度:O(1)
// 稳定性:不稳定
public static void selectSort(int[] array){
    int size = array.length;
    for(int i = 0; i < size-1; ++i){  // 控制具体选择的趟数// 具体选择的方式
       int pos = 0;    
        // 找最大元素的位置
       for(int j = 0; j < size-i; ++j){
            if(array[j] > array[pos]){
                pos = j;
            }
        }
 
        // 用pos标记的最大元素与区间最后一个位置上的元素交换
        if(pos != size-1-i){
            swap(array, pos, size-i-1);
        }
    }
}
 
public static void selectSortOP(int[] array){
    int begin = 0;
    int end = array.length-1;
    while(begin < end){
 
        // 在[begin, end]区间中找最大和最小元素的位置
       // 最大元素的位置使用maxPos标记
     // 最小元素的位置使用minPos标记    
        int minPos = begin;
        int maxPos = begin;
        int index = begin+1;
        while(index <= end){
            if(array[index] > array[maxPos]){
                maxPos = index;
            }
 
            if(array[index] < array[minPos]){
                minPos = index;
            }
 
            index++;
        }
 
        // 在[begin, end]区间中,已经找到了最小与最小元素的位置
       if(maxPos != end){
            swap(array, maxPos, end);
        }
 
        if(minPos == end){
            minPos = maxPos;
        }
 
        if(minPos != begin){
            swap(array, minPos, begin);
        }
 
        begin++;
        end--;
    }
}
 
//================================================================
// 堆排序
public static void shiftDown(int[] array, int size, int parent){
    // child标记parent的左孩子---parent可能有左没有右
    int child = parent*2 + 1;
    while(child < size){   // 如果循环条件成立:parent的左孩子一定是成立的
 
        // 右孩子存在的情况下,找左右孩子中最大的孩子
        if(child+1 < size && array[child+1] > array[child]){
            child += 1;
        }
 
        // 检测parent是否满足堆的特性
        if(array[parent] < array[child]){
            swap(array, parent, child);
            parent = child;
            child = parent*2+1;
        }else{
            return;
        }
    }
}
 
// 时间复杂度:O(NlogN)
// 空间复杂度:O(1)
// 稳定性:不稳定
// 应用场景:需要一个序列中前k个最大||最小 ---- 可能会和其他排序复合起来提高排序的效率
public static void heapSort(int[] array){
    // 1. 建堆
    // a. 找倒数第一个非叶子节点
    int size = array.length;
    int lastLeaf = ((size-2)>>>1);
    for(int root = lastLeaf; root >= 0; root--){
        shiftDown(array, size, root);
    }
 
    // 2. 利用堆删除的思想排序
    int end = size-1;
    while(end > 0){
        // 用堆顶元素与堆中最后一个元素交换
        swap(array, 0, end);
 
        // 将堆中有效元素个数减少一个
 
        // 将堆顶元素向下调整
        shiftDown(array, end,0); // logN
 
        end--;
    }
}

43、冒泡排序和快速排序

//================================================================
// 冒泡排序
// 时间复杂度:O(N^2)
// 空间复杂度:O(1)
// 稳定性:稳定
// 应用场景:
public static void bubbleSort(int[] array){
    int size = array.length;
    for(int i = 0; i < size; ++i){   // 控制冒泡的趟数
 
        boolean isChange = false;
 
        // 具体冒泡的方式:用相邻的两个元素进行交换// 如果不满足条件则交换for(int j = 1; j < size - i; j++){
            if(array[j-1] > array[j]){
                swap(array, j-1, j);
                isChange = true;
            }
        }
 
        if(!isChange){
            return;
        }
    }
}
 
//============================================================
// 快速排序
// 三数取中法:
public static int getIndexOfMiddle(int[] array, int left, int right){
    // left
    // mid: left + ((right-left)>>1)
    // right-1
    int mid = left + ((right-left)>>1);
    if(array[left] < array[right-1]){
        if(array[mid] < array[left]){
            return left;
        }else if(array[mid] > array[right-1]){
            return right-1;
        }else{
            return mid;
        }
    }else{
        if(array[mid] > array[left]){
            return left;
        }else if(array[mid] < array[right-1]){
            return right-1;
        }else{
            return mid;
        }
    }
}
 
// Hoare法时间复杂度:O(N)
public static int partition1(int[] array, int left, int right){
    int index = getIndexOfMiddle(array, left, right);
    if(index != right-1){
        swap(array, index, right-1);
    }
 
    int key = array[right-1];
    int begin = left;
    int end = right-1;
 
    while(begin < end){
        // 让begin从前往后找比key大的元素,找到之后停下来
        while(begin < end && array[begin] <= key){
            begin++;
        }
 
        // 让end从后往前找比key小的元素,找到之后停下来
        while(begin < end && array[end] >= key){
            end--;
        }
 
        if(begin != end){
            swap(array, begin, end);
        }
    }
 
    if(begin != right-1){
        swap(array, begin, right-1);
    }
 
    return begin;
}
 
// 挖坑法----时间复杂度:O(N)
public static int partition2(int[] array, int left, int right){
    int index = getIndexOfMiddle(array, left, right);
    if(index != right-1){
        swap(array, index, right-1);
    }
 
    int key = array[right-1];
    int begin = left;
    int end = right-1;
 
    while(begin < end){
        // 让begin从前往后找比基准值大的元素
        while(begin < end && array[begin] <= key){
            begin++;
        }
 
        if(begin < end){
            // begin位置找到了一个比key大的元素,填end位置的坑
            array[end] = array[begin];
 
            // begin位置就形成一个新的坑位
        }
 
        // 让end从后往前找比基准值小的元素
        while(begin < end && array[end] >= key){
            end--;
        }
 
        if(begin < end){
            // end位置找到了一个比key小的元素,填begin位置的坑
            array[begin] = array[end];
 
            // end位置就形成了一个新的坑位
        }
    }
 
    // begin和end位置是最后的一个坑位
    // 这个坑位使用基准值填充
    array[begin] = key;
    return begin;
}
 
public static int partition(int[] array, int left, int right){
    int cur = left;
    int prev = cur-1;
 
    int index = getIndexOfMiddle(array, left, right);
    if(index != right-1){
        swap(array, index, right-1);
    }
 
    int key = array[right-1];
 
    // 让cur从前往后找比key小的元素
    while(cur < right){
        if(array[cur] < key && ++prev != cur){
            swap(array, cur, prev);
        }
 
        ++cur;
    }
 
    // 将基准值的位置放置好
    if(++prev != right -1){
        swap(array, prev, right-1);
    }
 
    return prev;
}
 
// 时间复杂度:O(NlogN)
// 空间复杂度:O(logN)
// 稳定性:不稳定
// 应用场景:数据越随机越好----越乱越好
public static void insertSortQuick(int[] array, int left, int right){
    // 外层循环目的:取到数组中的每个元素
    for(int i = left+1; i < right; ++i){
 
        // 将该元素插入到序列中
        // array数组中:[0, i)的元素已经排好了
 
        // i位置的数据是本次要插入的数据---[0,i)
        int key = array[i];
        int end = i-1;
 
        while(end >= 0 && key < array[end]){
            array[end+1] = array[end];
            end--;
        }
 
        array[end+1] = key;
    }
}
 
public static void quickSort(int[] array, int left, int right){
    if(right - left < 47) {
        insertSortQuick(array, left, right);
    }else{
        // 假设升序
        // 找一个基准值将[left, right)区间分割成两个部分
        int div = partition(array, left, right);
 
        // 左侧部分比基准值小
        // [left, div)
        quickSort(array, left, div);
 
        // 右侧部分比基准值大
        // [div+1, right)
        quickSort(array, div+1, right);
    }
}
 
public static void quickSort(int[] array){
    Stack<Integer> s = new Stack<>();
    s.push(array.length);
    s.push(0);
 
    while(!s.empty()){
        int left = s.pop();
        int right = s.pop();
 
        if(right - left < 47){
            insertSortQuick(array, left, right);
        }else{
            int div = partition2(array, left, right);
 
            // 先压入基准值右侧部分
            // [div+1, right);
            s.push(right);
            s.push(div+1);
 
 
            // 后压入基准值左侧部分
            // [left, div)
            s.push(div);
            s.push(left);
        }
    }
}
 

44、归并排序和计数排序

//==========================================================
// 归并排序
public static void mergeDate(int[] array, int left, int mid, int right, int[] temp){
    int begin1 = left, end1 = mid;
    int begin2 = mid, end2 = right;
    int index = left;
 
    while(begin1 < end1 && begin2 < end2){
        if(array[begin1] <= array[begin2]){
            temp[index++] = array[begin1++];
        }else{
            temp[index++] = array[begin2++];
        }
    }
 
    while(begin1 < end1){
        temp[index++] = array[begin1++];
    }
 
    while(begin2 < end2){
        temp[index++] = array[begin2++];
    }
}
 
// 时间复杂度:O(NlogN)
// 空间复杂度:O(N)
// 稳定性:稳定
// 应用场景:外部排序
private static void mergeSort(int[] array, int left, int right, int[] temp){
    if(right - left > 1){
        // 先对[left, right)区间中的元素进行均分
        int mid = left + ((right - left)>>1);
 
        // [left, mid)
        mergeSort(array, left, mid, temp);
 
        // [mid, right)
        mergeSort(array, mid, right, temp);
 
        mergeDate(array, left, mid, right, temp);
        System.arraycopy(temp, left, array, left, right-left);
    }
}
 
 
public static void mergeSort(int[] array){
    int[] temp = new int[array.length];
    mergeSort(array, 0, array.length, temp);
}
 
public static void mergeSortNor(int[] array){
    int size = array.length;
    int[] temp = new int[size];
 
    int gap = 1;
 
    while(gap < size){
        for(int i = 0; i < size; i+= 2*gap){
            int left = i;
            int mid = left + gap;
            int right = mid+gap;
            if(mid > size){
                mid = size;
            }
 
            if(right > size){
                right = size;
            }
 
            mergeDate(array, left, mid, right, temp);
        }
 
        System.arraycopy(temp, 0, array, 0, size);
 
        gap <<= 1;
    }
}
 
// 计数排序
//==================================================================
// 时间复杂度:O(N)---N表示数组中元素个数
// 空间复杂度:O(M)---M表示范围的大小
// 稳定性:稳定
// 应用场景:数据密集集中在某个范围中
public static void countSort(int[] array){
    // 找数据范围
    int maxValue = array[0];
    int minValue = array[0];
    for(int i = 0; i < array.length; ++i){
        if(array[i] > maxValue){
            maxValue = array[i];
        }
 
        if(array[i] < minValue){
            minValue = array[i];
        }
    }
 
    // 计算计数空间的大小
    int range = maxValue - minValue + 1;
    int[] count = new int[range];
 
    // 1. 统计array中每个数据出现的次数
    for(int i = 0; i < array.length; ++i){
        count[array[i] - minValue]++;
    }
 
    // 2. 根据统计结果回收
    int index = 0;
    for(int i = 0; i < range; ++i){
        while(count[i] > 0){
            array[index++] = i + minValue;
            count[i]--;
        }
    }
}
  
 

45、912. 排序数组 - 力扣(LeetCode)

46、实现二叉搜索树代码

public class BinarySearchTree {
 
    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;
 
        TreeNode(int key) {
            this.key = key;
        }
    }
 
    public TreeNode root;
 
    /**
     *
     * @param key
     */
    public boolean insert(int key) {
        if(root == null) {
            root = new TreeNode(key);
            return true;
        }
 
        TreeNode cur = root;
        TreeNode parent = null;
 
        while (cur != null) {
            if(cur.key < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.key > key) {
                parent = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }
        TreeNode node = new TreeNode(key);
        //当代码执行到这里之后。cur == null
        if(parent.key < key) {
            parent.right = node;
        }else {
            parent.left = node;
        }
        return true;
    }
 
    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.key == key) {
                return cur;
            }else if(cur.key < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;
    }
 
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.key < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.key == key) {
                //这里开始删除!
                removeNode(parent,cur);
                return true;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        return false;
    }
 
    private void removeNode(TreeNode parent,TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }
 
    //中序遍历即可
    public void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.key+" ");
        inorder(root.right);
    }
}

47、二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

48、136. 只出现一次的数字 - 力扣(LeetCode)

49、771. 宝石与石头 - 力扣(LeetCode)

50、旧键盘 (20)__牛客网 (nowcoder.com)