• Java---刷题02

    1、数组转字符串

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

    2、118. 杨辉三角 - 力扣（LeetCode）

    3、27. 移除元素 - 力扣（LeetCode）

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

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

    6、实现 ArrayList 类

    1. public class MyArraylist {
    2.  
    3.     public int[] elem;
    4.     public int usedSize;//0
    5.     //默认容量
    6.     private static final int DEFAULT_SIZE = 10;
    7.  
    8.     public MyArraylist() {
    9.         this.elem = new int[DEFAULT_SIZE];
    10.     }
    11.  
    12.     /**
    13.      * 打印顺序表:
    14.      *   根据usedSize判断即可
    15.      */
    16.     public void display() {
    17.        
    18.     }
    19.  
    20.     // 新增元素,默认在数组最后新增
    21.     public void add(int data) {
    22.        
    23.     }
    24.  
    25.     /**
    26.      * 判断当前的顺序表是不是满的！
    27.      * @return true:满   false代表空
    28.      */
    29.     public boolean isFull() {
    30.        
    31.     }
    32.  
    33.  
    34.     private boolean checkPosInAdd(int pos) {
    35.        
    36.         return true;//合法
    37.     }
    38.  
    39.     // 在 pos 位置新增元素
    40.     public void add(int pos, int data) {
    41.         
    42.     }
    43.  
    44.     // 判定是否包含某个元素
    45.     public boolean contains(int toFind) {
    46.         
    47.         return false;
    48.     }
    49.     // 查找某个元素对应的位置
    50.     public int indexOf(int toFind) {
    51.         
    52.         return -1;
    53.     }
    54.  
    55.     // 获取 pos 位置的元素
    56.     public int get(int pos) {
    57.        
    58.     }
    59.  
    60.     private boolean isEmpty() {
    61.         
    62.     }
    63.     // 给 pos 位置的元素设为【更新为】 value
    64.     public void set(int pos, int value) {
    65.         
    66.     }
    67.  
    68.     /**
    69.      * 删除第一次出现的关键字key
    70.      * @param key
    71.      */
    72.     public void remove(int key) {
    73.        
    74.     }
    75.  
    76.     // 获取顺序表长度
    77.     public int size() {
    78.        
    79.     }
    80.  
    81.     // 清空顺序表
    82.     public void clear() {
    83.         
    84.     }
    1. public class MyArraylist {
    2.  
    3.     public int[] elem;
    4.     public int usedSize;//0
    5.     //默认容量
    6.     private static final int DEFAULT_SIZE = 10;
    7.  
    8.     public MyArraylist() {
    9.         this.elem = new int[DEFAULT_SIZE];
    10.     }
    11.  
    12.     /**
    13.      * 打印顺序表:
    14.      *   根据usedSize判断即可
    15.      */
    16.     public void display() {
    17.         //usedSize==0
    18.         for (int i = 0; i < this.usedSize; i++) {
    19.             System.out.print(this.elem[i]+" ");
    20.         }
    21.         System.out.println();
    22.     }
    23.  
    24.     // 新增元素,默认在数组最后新增
    25.     public void add(int data) {
    26.         //1、判断是否是满的，如果满的，那么进行扩容
    27.         if(isFull()) {
    28.             //扩容
    29.             this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    30.         }
    31.         //2、不满进行插入
    32.         this.elem[this.usedSize] = data;
    33.         this.usedSize++;
    34.     }
    35.  
    36.     /**
    37.      * 判断当前的顺序表是不是满的！
    38.      * @return true:满   false代表空
    39.      */
    40.     public boolean isFull() {
    41.         /*if(this.usedSize == this.elem.length) {
    42.             return true;
    43.         }
    44.         return false;*/
    45.         return this.usedSize == this.elem.length;
    46.     }
    47.  
    48.  
    49.     private boolean checkPosInAdd(int pos) {
    50.         if(pos < 0 || pos > this.usedSize) {
    51.             System.out.println("pos位置不合法");
    52.             return false;
    53.         }
    54.         return true;//合法
    55.     }
    56.  
    57.     // 在 pos 位置新增元素
    58.     public void add(int pos, int data) {
    59.         //判断下标是否是合法的
    60.         if(!checkPosInAdd(pos)) {
    61.             throw new MyArrayListIndexOutOfException("添加方法的pos不合理！");
    62.         }
    63.         //判断是否是满的
    64.         if (isFull()) {
    65.             this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    66.         }
    67.         //挪数据
    68.         for (int i = this.usedSize-1; i >= pos ; i--) {
    69.             this.elem[i+1] = this.elem[i];
    70.         }
    71.         //挪完了数据
    72.         this.elem[pos] = data;
    73.         this.usedSize++;
    74.     }
    75.  
    76.     // 判定是否包含某个元素
    77.     public boolean contains(int toFind) {
    78.         for (int i = 0; i < this.usedSize; i++) {
    79.             if(this.elem[i] == toFind) {
    80.                 return true;
    81.             }
    82.         }
    83.         return false;
    84.     }
    85.     // 查找某个元素对应的位置
    86.     public int indexOf(int toFind) {
    87.         for (int i = 0; i < this.usedSize; i++) {
    88.             if(this.elem[i] == toFind) {
    89.                 return i;
    90.             }
    91.         }
    92.         return -1;
    93.     }
    94.  
    95.  
    96.     private boolean checkPosInGet(int pos) {
    97.         if(pos < 0 || pos >= this.usedSize) {
    98.             System.out.println("pos位置不合法");
    99.             return false;
    100.         }
    101.         return true;//合法
    102.     }
    103.  
    104.     // 获取 pos 位置的元素
    105.     public int get(int pos) {
    106.         if(!checkPosInGet(pos)) {
    107.             throw new MyArrayListIndexOutOfException("获取pos下标时，位置不合法");
    108.         }
    109.         //不用写判断空不空 没有问题的
    110.         if(isEmpty()) {
    111.             throw new MyArrayListEmptyException("获取元素的时候，顺序表为空！");
    112.         }
    113.         return this.elem[pos];
    114.     }
    115.  
    116.  
    117.     private boolean isEmpty() {
    118.         return this.usedSize == 0;
    119.     }
    120.  
    121.     // 给 pos 位置的元素设为【更新为】 value
    122.     public void set(int pos, int value) {
    123.         if(!checkPosInGet(pos)){
    124.             throw new MyArrayListIndexOutOfException("更新pos下标的元素，位置不合法");
    125.         }
    126.         //如果合法 ，那么其实不用判断顺序表为空的状态了
    127.         if(isEmpty()) {
    128.             throw new MyArrayListEmptyException("顺序表为空！");
    129.         }
    130.         //顺序表为满的情况也可以更新
    131.         this.elem[pos] = value;
    132.     }
    133.  
    134.  
    135.     /**
    136.      * 删除第一次出现的关键字key
    137.      * @param key
    138.      */
    139.     public void remove(int key) {
    140.         if(isEmpty()) {
    141.             throw new MyArrayListEmptyException("顺序表为空，不能删除！");
    142.         }
    143.         int index = indexOf(key);
    144.         if(index == -1) {
    145.             System.out.println("不存在你要删除的数据");
    146.             return;
    147.         }
    148.  
    149.         for (int i = index; i < this.usedSize-1; i++) {
    150.             this.elem[i] = this.elem[i+1];
    151.         }
    152.         //删除完成
    153.         this.usedSize--;
    154.         // this.elem[usedSize] = null; 如果是引用类型 这里需要置为空
    155.     }
    156.  
    157.  
    158.     // 获取顺序表长度
    159.     public int size() {
    160.         return this.usedSize;
    161.     }
    162.  
    163.     // 清空顺序表
    164.     public void clear() {
    165.         /*
    166.         如果是引用数据类型 得一个一个置为空 这样做才是最合适的
    167.         for (int i = 0; i < this.usedSize; i++) {
    168.             this.elem[i] = null;
    169.         }
    170.         this.usedSize = 0;
    171.         */
    172.  
    173.         this.usedSize = 0;
    174.     }

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

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

    1. public class SingleLinkedList{
    2.  
    3.     static class ListNode {
    4.         public int val;//数值域public ListNode next;//存储下一个节点的地址
    5.  
    6.         public ListNode(int val) {
    7.             this.val = val;
    8.         }
    9.     }
    10.  
    11.     public ListNode head;//代表单链表的头结点的引用
    12.  
    13.     /**
    14.      * 这里只是简单的进行，链表的构造。
    15.      */public void createList() {
    16.         ListNode listNode1 = new ListNode(12);
    17.         ListNode listNode2 = new ListNode(23);
    18.         ListNode listNode3 = new ListNode(34);
    19.         ListNode listNode4 = new ListNode(45);
    20.         ListNode listNode5 = new ListNode(56);
    21.  
    22.         listNode1.next = listNode2;
    23.  
    24.         listNode2.next = listNode3;
    25.         listNode3.next = listNode4;
    26.         listNode4.next = listNode5;
    27.         this.head = listNode1;
    28.     }
    29.  
    30.  
    31.     public void display() {
    32.         ListNode cur = head;
    33.         while (cur != null) {
    34.             System.out.print(cur.val+" ");
    35.             cur = cur.next;
    36.         }
    37.         System.out.println();
    38.     }
    39.  
    40.     /**
    41.      * 从指定的节点开始答应
    42.      * @param newHead
    43.      */public void display(ListNode newHead) {
    44.         ListNode cur = newHead;
    45.         while (cur != null) {
    46.             System.out.print(cur.val+" ");
    47.             cur = cur.next;
    48.         }
    49.         System.out.println();
    50.     }
    51.  
    52.  
    53.     /**
    54.      * 头插法
    55.      * OaddLast
    56.      */public void addFirst(int data){
    57.         ListNode node = new ListNode(data);
    58.         /*if(this.head == null) {
    59.             this.head = node;
    60.         }else {
    61.             node.next = this.head;
    62.             this.head = node;
    63.         }*/
    64.         node.next = this.head;
    65.         this.head = node;
    66.     }
    67.  
    68.     //尾插法 O(n)public void addLast(int data) {
    69.         ListNode node = new ListNode(data);
    70.         if(head == null) {
    71.             head = node;
    72.         }else {
    73.             ListNode cur = head;
    74.             while (cur.next != null) {
    75.                 cur = cur.next;
    76.             }
    77.             //cur.next == null;
    78.             cur.next = node;
    79.         }
    80.     }
    81.  
    82.     /**
    83.      * 任意位置插入,第一个数据节点为0号下标
    84.      * 指定位置插入
    85.      */
    86.  
    87.     public void addIndex(int index,int data) throws MySingleListIndexOutOfException{
    88.         checkIndexAdd(index);
    89.         if(index == 0) {
    90.             addFirst(data);
    91.             return;
    92.         }
    93.         if(index == size()) {
    94.             addLast(data);
    95.             return;
    96.         }
    97.         ListNode node = new ListNode(data);
    98.         ListNode cur = findIndexSubOne(index);
    99.         node.next = cur.next;
    100.         cur.next = node;
    101.     }
    102.  
    103.     /**
    104.      * 找到index-1位置的节点
    105.      * @param index
    106.      * @return 该节点的地址
    107.      */private ListNode findIndexSubOne(int index) {
    108.         ListNode cur = this.head;
    109.         while (index-1 != 0) {
    110.             cur = cur.next;
    111.             index--;
    112.         }
    113.         return cur;
    114.     }
    115.  
    116.     private void checkIndexAdd(int index) {
    117.         if(index < 0 || index > size()) {
    118.             throw new MySingleListIndexOutOfException("任意位置插入的时候，index不合法！");
    119.         }
    120.     }
    121.  
    122.     //查找是否包含关键字key是否在单链表当中  314public boolean contains(int key) {
    123.         //head == null
    124.         ListNode cur = this.head;
    125.         //cur != null 说明 没有遍历完 链表while (cur != null) {
    126.             if(cur.val == key) {
    127.                 return true;
    128.             }
    129.             cur = cur.next;
    130.         }
    131.         return false;
    132.     }
    133.  
    134.     //删除第一次出现关键字为key的节点public void remove(int key){
    135.  
    136.         if(this.head == null) {
    137.             System.out.println("此时链表为空，不能进行删除！");
    138.             return;
    139.         }
    140.  
    141.         if(this.head.val == key) {
    142.             //判断 第一个节点是不是等于我要删除的节点this.head = this.head.next;
    143.             return;
    144.         }
    145.  
    146.         ListNode cur = this.head;
    147.         while (cur.next != null) {
    148.             if(cur.next.val == key) {
    149.                 //进行删除了
    150.                 ListNode del = cur.next;
    151.                 cur.next = del.next;
    152.                 return;
    153.             }
    154.             cur = cur.next;
    155.         }
    156.     }
    157.     //删除所有值为key的节点public void removeAllKey(int key){
    158.         if(this.head == null) {
    159.             return;
    160.         }
    161.  
    162.         ListNode cur = this.head.next;
    163.         ListNode prev = this.head;
    164.  
    165.         while (cur != null) {
    166.             if(cur.val == key) {
    167.                 prev.next = cur.next;
    168.                 cur = cur.next;
    169.             }else {
    170.                 prev = cur;
    171.                 cur = cur.next;
    172.             }
    173.         }
    174.         //单独处理了头节点if(this.head.val == key) {
    175.             head = head.next;
    176.         }
    177.     }
    178.  
    179.     //得到单链表的长度public int size(){
    180.         int count = 0;
    181.         ListNode cur = this.head;
    182.         while (cur != null) {
    183.             count++;
    184.             cur = cur.next;
    185.         }
    186.         return count;
    187.     }
    188.  
    189.     /**
    190.      * 当我们 执行clear这个函数的时候，会将这个链表当中的所有的节点回收
    191.      */public void clear(){
    192.         //this.head = null;//这种做法 比较粗暴！
    193.         ListNode cur = this.head;
    194.         ListNode curNext = null;
    195.         while (cur != null) {
    196.             curNext = cur.next;
    197.             cur.next = null;
    198.             cur = curNext;
    199.         }
    200.         head = null;
    201.     }
    202. }

    8、203. 移除链表元素 - 力扣（LeetCode）

    9、206. 反转链表 - 力扣（LeetCode）

    10、876. 链表的中间结点 - 力扣（LeetCode）

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

    12、模拟实现 LinkedList 类

    1. // 2、无头双向链表实现
    2.  public class LinkedList {
    3.      //头插法
    4.      public void addFirst(int data);
    5.      //尾插法
    6.      public void addLast(int data);
    7.      //任意位置插入,第一个数据节点为0号下标
    8.      public boolean addIndex(int index,int data);
    9.      //查找是否包含关键字key是否在单链表当中
    10.      public boolean contains(int key);
    11.      //删除第一次出现关键字为key的节点
    12.      public void remove(int key);
    13.      //删除所有值为key的节点
    14.      public void removeAllKey(int key);
    15.      //得到单链表的长度
    16.      public int size();
    17.      public void display();
    18.      public void clear();
    19.  }
    1. public class MyLinkedList {
    2.  
    3.  
    4.  
    5.     static class ListNode {
    6.  
    7.         public int val;
    8.  
    9.         public ListNode prev;//前驱
    10.  
    11.         public ListNode next;//后继
    12.  
    13.  
    14.  
    15.         public ListNode(int val) {
    16.  
    17.             this.val = val;
    18.  
    19.         }
    20.  
    21.     }
    22.  
    23.  
    24.  
    25.     public ListNode head;//标记头
    26.  
    27.     public ListNode last;//标记尾巴
    28.  
    29.  
    30.  
    31.     MyLinkedList() {
    32.  
    33.         //last = head = new ListNode(-1);
    34.  
    35.     }
    36.  
    37.  
    38.  
    39.  
    40.  
    41.     public void display(){
    42.  
    43.         ListNode cur = head;
    44.  
    45.         while (cur != null) {
    46.  
    47.             System.out.print(cur.val+" ");
    48.  
    49.             cur = cur.next;
    50.  
    51.         }
    52.  
    53.         System.out.println();
    54.  
    55.     }
    56.  
    57.  
    58.  
    59.     //头插法
    60.  
    61.     public void addFirst(int data){
    62.  
    63.         ListNode node = new ListNode(data);
    64.  
    65.         if(head == null) {
    66.  
    67.             head = node;
    68.  
    69.             last = node;
    70.  
    71.         }else {
    72.  
    73.             node.next = head;
    74.  
    75.             head.prev = node;
    76.  
    77.             head = node;
    78.  
    79.         }
    80.  
    81.     }
    82.  
    83.     //尾插法
    84.  
    85.     public void addLast(int data){
    86.  
    87.         ListNode node = new ListNode(data);
    88.  
    89.         if(head == null) {
    90.  
    91.             head = node;
    92.  
    93.             last = node;
    94.  
    95.         }else {
    96.  
    97.             last.next = node;
    98.  
    99.             node.prev = last;
    100.  
    101.             last = node;
    102.  
    103.         }
    104.  
    105.     }
    106.  
    107.  
    108.  
    109.     //任意位置插入,第一个数据节点为0号下标
    110.  
    111.     public void addIndex(int index,int data){
    112.  
    113.         if(index < 0 || index > size()) {
    114.  
    115.             System.out.println("index不合法！");
    116.  
    117.             return;
    118.  
    119.         }
    120.  
    121.         if(index == 0) {
    122.  
    123.             addFirst(data);
    124.  
    125.             return;
    126.  
    127.         }
    128.  
    129.         if(index == size()) {
    130.  
    131.             addLast(data);
    132.  
    133.             return;
    134.  
    135.         }
    136.  
    137.         //cur拿到了index下标的节点的地址
    138.  
    139.         ListNode cur = searchIndex(index);
    140.  
    141.         ListNode node = new ListNode(data);
    142.  
    143.         node.next = cur;
    144.  
    145.         cur.prev.next = node;
    146.  
    147.         node.prev = cur.prev;
    148.  
    149.         cur.prev = node;
    150.  
    151.     }
    152.  
    153.  
    154.  
    155.  
    156.  
    157.  
    158.  
    159.     private ListNode searchIndex(int index) {
    160.  
    161.         ListNode cur = head;
    162.  
    163.         while (index != 0) {
    164.  
    165.             cur = cur.next;
    166.  
    167.             index--;
    168.  
    169.         }
    170.  
    171.         return cur;
    172.  
    173.     }
    174.  
    175.  
    176.  
    177.     //查找是否包含关键字key是否在单链表当中
    178.  
    179.     public boolean contains(int key){
    180.  
    181.         ListNode cur = head;
    182.  
    183.         while (cur != null) {
    184.  
    185.             if(cur.val == key) {
    186.  
    187.                 return true;
    188.  
    189.             }
    190.  
    191.             cur = cur.next;
    192.  
    193.         }
    194.  
    195.         return false;
    196.  
    197.     }
    198.  
    199.  
    200.  
    201.     //删除第一次出现关键字为key的节点
    202.  
    203.     public void remove(int key){
    204.  
    205.         ListNode cur = head;
    206.  
    207.         while (cur != null) {
    208.  
    209.             if(cur.val == key) {
    210.  
    211.                 //判断当前是不是头节点
    212.  
    213.                 if(cur == head) {
    214.  
    215.                     head = head.next;
    216.  
    217.                     if(head != null) {
    218.  
    219.                         head.prev = null;//这里有问题！！！！ 一个节点！
    220.  
    221.                     }
    222.  
    223.                 }else {
    224.  
    225.                     //中间和尾巴的情况
    226.  
    227.                     cur.prev.next = cur.next;
    228.  
    229.                     if(cur.next != null) {
    230.  
    231.                         cur.next.prev = cur.prev;
    232.  
    233.                     }else {
    234.  
    235.                         last = last.prev;
    236.  
    237.                     }
    238.  
    239.                 }
    240.  
    241.                 return;//删完走人
    242.  
    243.             }else {
    244.  
    245.                 cur = cur.next;
    246.  
    247.             }
    248.  
    249.         }
    250.  
    251.     }
    252.  
    253.  
    254.  
    255.  
    256.  
    257.     //删除所有值为key的节点  之遍历链表一遍
    258.  
    259.     public void removeAllKey(int key){
    260.  
    261.         ListNode cur = head;
    262.  
    263.         while (cur != null) {
    264.  
    265.             if(cur.val == key) {
    266.  
    267.                 //判断当前是不是头节点
    268.  
    269.                 if(cur == head) {
    270.  
    271.                     head = head.next;
    272.  
    273.                     if(head != null) {
    274.  
    275.                         head.prev = null;//这里有问题！！！！ 一个节点！
    276.  
    277.                     }
    278.  
    279.                 }else {
    280.  
    281.                     //中间和尾巴的情况
    282.  
    283.                     cur.prev.next = cur.next;
    284.  
    285.                     if(cur.next != null) {
    286.  
    287.                         cur.next.prev = cur.prev;
    288.  
    289.                     }else {
    290.  
    291.                         last = last.prev;
    292.  
    293.                     }
    294.  
    295.                 } 
    296.                 cur = cur.next;
    297.  
    298.             }else {
    299.  
    300.                 cur = cur.next;
    301.  
    302.             }
    303.  
    304.         }
    305.  
    306.     }
    307.  
    308.     //得到单链表的长度 
    309.     public int size(){
    310.  
    311.         int count = 0;
    312.  
    313.         ListNode cur = head;
    314.  
    315.         while (cur != null) {
    316.             count++;
    317.             cur = cur.next;
    318.         }
    319.         return count;
    320.     } 
    321.     public void clear(){
    322.  
    323.         ListNode cur = head;        
    324.         while (cur != null) {
    325.  
    326.             ListNode curNext = cur.next;
    327.  
    328.             ///cur.val = null;
    329.  
    330.             cur.prev = null;
    331.  
    332.             cur.next = null;
    333.  
    334.             cur = curNext;
    335.         } 
    336.         head = null;
    337.  
    338.         last = null;
    339.  
    340.     } 
    341. }

    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、实现二叉树的基本操作

    1. public class BinaryTree {
    2.  
    3.     static class TreeNode {
    4.         public char val;
    5.         public TreeNode left;//左孩子的引用
    6.         public TreeNode right;//右孩子的引用
    7.  
    8.         public TreeNode(char val) {
    9.             this.val = val;
    10.         }
    11.     }
    12.  
    13.  
    14.     /**
    15.      * 创建一棵二叉树 返回这棵树的根节点
    16.      *
    17.      * @return
    18.      */
    19.     public TreeNode createTree() {
    20.  
    21.     }
    22.  
    23.     // 前序遍历
    24.     public void preOrder(TreeNode root) {
    25.     }
    26.  
    27.     // 中序遍历
    28.     void inOrder(TreeNode root) {
    29.     }
    30.  
    31.     // 后序遍历
    32.     void postOrder(TreeNode root) {
    33.     }
    34.  
    35.     public static int nodeSize;
    36.  
    37.     /**
    38.      * 获取树中节点的个数：遍历思路
    39.      */
    40.     void size(TreeNode root) {
    41.     }
    42.  
    43.     /**
    44.      * 获取节点的个数：子问题的思路
    45.      *
    46.      * @param root
    47.      * @return
    48.      */
    49.     int size2(TreeNode root) {
    50.     }
    51.  
    52.  
    53.     /*
    54.      获取叶子节点的个数：遍历思路
    55.      */
    56.     public static int leafSize = 0;
    57.  
    58.     void getLeafNodeCount1(TreeNode root) {
    59.     }
    60.  
    61.     /*
    62.      获取叶子节点的个数：子问题
    63.      */
    64.     int getLeafNodeCount2(TreeNode root) {
    65.     }
    66.  
    67.     /*
    68.     获取第K层节点的个数
    69.      */
    70.     int getKLevelNodeCount(TreeNode root, int k) {
    71.     }
    72.  
    73.     /*
    74.      获取二叉树的高度
    75.      时间复杂度：O(N)
    76.      */
    77.     int getHeight(TreeNode root) {
    78.        
    79.     }
    80.  
    81.  
    82.     // 检测值为value的元素是否存在
    83.     TreeNode find(TreeNode root, char val) {
    84.         
    85.         return null;
    86.     }
    87.  
    88.     //层序遍历
    89.     void levelOrder(TreeNode root) {
    90.         
    91.     }
    92.  
    93.  
    94.     // 判断一棵树是不是完全二叉树
    95.     boolean isCompleteTree(TreeNode root) {
    96.         return true;
    97.     }
    98. }
    1. public class BinaryTree {
    2.  
    3.     static class TreeNode {
    4.         public char val;
    5.         public TreeNode left;//左孩子的引用
    6.         public TreeNode right;//右孩子的引用
    7.  
    8.         public TreeNode(char val) {
    9.             this.val = val;
    10.         }
    11.     }
    12.  
    13.  
    14.     /**
    15.      * 创建一棵二叉树 返回这棵树的根节点
    16.      * 暂且使用穷举的方式创建二叉树
    17.      * @return
    18.      */
    19.     public TreeNode createTree() {
    20.  
    21.         TreeNode A = new TreeNode('A');
    22.         TreeNode B = new TreeNode('B');
    23.         TreeNode C = new TreeNode('C');
    24.         TreeNode D = new TreeNode('D');
    25.         TreeNode E = new TreeNode('E');
    26.         TreeNode F = new TreeNode('F');
    27.         TreeNode G = new TreeNode('G');
    28.         TreeNode H = new TreeNode('H');
    29.  
    30.         A.left = B;
    31.         A.right = C;
    32.         B.left = D;
    33.         B.right = E;
    34.         C.left = F;
    35.         C.right = G;
    36.         //E.right = H;
    37.         return A;
    38.     }
    39.  
    40.     // 前序遍历
    41.     public void preOrder(TreeNode root) {
    42.         if (root == null) return;
    43.         System.out.print(root.val + " ");
    44.         preOrder(root.left);
    45.         preOrder(root.right);
    46.     }
    47.  
    48.     // 中序遍历
    49.     void inOrder(TreeNode root) {
    50.         if (root == null) return;
    51.         inOrder(root.left);
    52.         System.out.print(root.val + " ");
    53.         inOrder(root.right);
    54.     }
    55.  
    56.     // 后序遍历
    57.     void postOrder(TreeNode root) {
    58.         if (root == null) return;
    59.         postOrder(root.left);
    60.         postOrder(root.right);
    61.         System.out.print(root.val + " ");
    62.     }
    63.  
    64.     public static int nodeSize;
    65.  
    66.     /**
    67.      * 获取树中节点的个数：遍历思路
    68.      */
    69.     void size(TreeNode root) {
    70.         if (root == null) return;
    71.         nodeSize++;
    72.         size(root.left);
    73.         size(root.right);
    74.     }
    75.  
    76.     /**
    77.      * 获取节点的个数：子问题的思路
    78.      *
    79.      * @param root
    80.      * @return
    81.      */int size2(TreeNode root) {
    82.         if (root == null) return 0;
    83.         return size2(root.left)
    84.                 + size2(root.right) + 1;
    85.     }
    86.  
    87.  
    88.     /*
    89.      获取叶子节点的个数：遍历思路
    90.      */
    91.     public static int leafSize = 0;
    92.  
    93.     void getLeafNodeCount1(TreeNode root) {
    94.         if (root == null) return;
    95.         if (root.left == null && root.right == null) {
    96.             leafSize++;
    97.         }
    98.         getLeafNodeCount1(root.left);
    99.         getLeafNodeCount1(root.right);
    100.     }
    101.  
    102.     /*
    103.      获取叶子节点的个数：子问题
    104.      */int getLeafNodeCount2(TreeNode root) {
    105.         if (root == null) return 0;
    106.         if (root.left == null && root.right == null) {
    107.             return 1;
    108.         }
    109.         return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    110.     }
    111.  
    112.     /*
    113.     获取第K层节点的个数
    114.      */int getKLevelNodeCount(TreeNode root, int k) {
    115.         if (root == null) return 0;
    116.         if (k == 1) return 1;
    117.         return getKLevelNodeCount(root.left, k - 1) +
    118.                 getKLevelNodeCount(root.right, k - 1);
    119.     }
    120.  
    121.     /*
    122.      获取二叉树的高度
    123.      时间复杂度：O(N)
    124.      */int getHeight(TreeNode root) {
    125.         if (root == null) return 0;
    126.         int leftH = getHeight(root.left);
    127.         int rightH = getHeight(root.right);
    128.         return leftH > rightH ? leftH + 1 : rightH + 1;
    129.     }
    130.  
    131.  
    132.     // 检测值为value的元素是否存在
    133.     TreeNode find(TreeNode root, char val) {
    134.         if (root == null) return null;
    135.         if (root.val == val) return root;
    136.  
    137.         TreeNode ret = find(root.left, val);
    138.         if (ret != null) {
    139.             return ret;
    140.         }
    141.         ret = find(root.right, val);
    142.         if (ret != null) {
    143.             return ret;
    144.         }
    145.         return null;
    146.     }
    147.  
    148.     //层序遍历
    149.     void levelOrder(TreeNode root) {
    150.         if (root == null) return;
    151.         Queue queue = new LinkedList<>();
    152.         queue.offer(root);
    153.         while (!queue.isEmpty()) {
    154.             TreeNode cur = queue.poll();
    155.             System.out.print(cur.val + " ");
    156.             if (cur.left != null) {
    157.                 queue.offer(cur.left);
    158.             }
    159.             if (cur.right != null) {
    160.                 queue.offer(cur.right);
    161.             }
    162.         }
    163.     }
    164.  
    165.  
    166.     // 判断一棵树是不是完全二叉树
    167.     boolean isCompleteTree(TreeNode root) {
    168.         if (root == null) return false;
    169.         Queue queue = new LinkedList<>();
    170.         queue.offer(root);
    171.         while (!queue.isEmpty()) {
    172.             TreeNode cur = queue.poll();
    173.             if (cur != null) {
    174.                 queue.offer(cur.left);
    175.                 queue.offer(cur.right);
    176.             } else {
    177.                 break;
    178.             }
    179.         }
    180.         //第2次遍历队列 判断队列当中 是否存在非空的元素while (!queue.isEmpty()) {
    181.             TreeNode cur = queue.peek();
    182.             if (cur == null) {
    183.                 queue.poll();
    184.             } else {
    185.                 return false;
    186.             }
    187.         }
    188.         return true;
    189.     }
    190. }

    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、优先级队列(堆)的模拟实现

    1. public class PriorityQueue {
    2.     public int[] elem;
    3.     public int usedSize;
    4.  
    5.     public PriorityQueue() {
    6.     }
    7.  
    8.     /**
    9.      * 建堆的时间复杂度：
    10.      *
    11.      * @param array
    12.      */
    13.     public void createHeap(int[] array) {
    14.     }
    15.  
    16.     /**
    17.      *
    18.      * @param root 是每棵子树的根节点的下标
    19.      * @param len  是每棵子树调整结束的结束条件
    20.      * 向下调整的时间复杂度：O(logn)
    21.      */
    22.     private void shiftDown(int root,int len) {
    23.     }
    24.  
    25.  
    26.     /**
    27.      * 入队：仍然要保持是大根堆
    28.      * @param val
    29.      */
    30.     public void push(int val) {
    31.     }
    32.  
    33.     private void shiftUp(int child) {
    34.     }
    35.  
    36.     public boolean isFull() {
    37.     }
    38.  
    39.     /**
    40.      * 出队【删除】：每次删除的都是优先级高的元素
    41.      * 仍然要保持是大根堆
    42.      */
    43.     public void pollHeap() {
    44.     }
    45.  
    46.     public boolean isEmpty() {
    47.     }
    48.  
    49.     /**
    50.      * 获取堆顶元素
    51.      * @return
    52.      */
    53.     public int peekHeap() {
    54.     }
    55. }
    1. public class PriorityQueue {
    2.     public int[] elem;
    3.     public int usedSize;
    4.  
    5.     public PriorityQueue() {
    6.         this.elem = new int[10];
    7.     }
    8.  
    9.     /**
    10.      * 建堆的时间复杂度：
    11.      *
    12.      * @param array
    13.      */
    14.     public void createHeap(int[] array) {
    15.         //这一步不算是必须的。这里只是我们准备数据，不算做我的建堆时间复杂度当中
    16.         for (int i = 0; i < array.length; i++) {
    17.             elem[i] = array[i];
    18.             usedSize++;
    19.         }
    20.  
    21.         for (int p = (usedSize-1-1)/2; p >= 0 ; p--) {
    22.             shiftDown(p,usedSize);
    23.         }
    24.     }
    25.  
    26.     /**
    27.      *
    28.      * @param root 是每棵子树的根节点的下标
    29.      * @param len  是每棵子树调整结束的结束条件
    30.      * 向下调整的时间复杂度：O(logn)
    31.      */
    32.     private void shiftDown(int root,int len) {
    33.         int parent = root;
    34.         int child = 2*parent+1;
    35.         //进入这个循环，说明一定至少有一个孩子
    36.         while (child < len) {
    37.             //如果有孩子，找到左右孩子的最大值
    38.             if(child+1 < len && elem[child] < elem[child+1]) {
    39.                 child++;
    40.             }
    41.             //child下标一定保存的是左右孩子最大值的下标
    42.             //接下来，孩子的最大值和根节点去比较大小
    43.             if(elem[child] > elem[parent]) {
    44.                 int tmp = elem[child];
    45.                 elem[child] = elem[parent];
    46.                 elem[parent] = tmp;
    47.                 parent = child;//开始更新下标，继续看下面的子树是不是大根堆
    48.                 child = 2*parent+1;
    49.             }else {
    50.                 break;//此时说明已经是大根堆，不需要进行再次调整了
    51.             }
    52.         }
    53.     }
    54.  
    55.  
    56.     /**
    57.      * 入队：仍然要保持是大根堆
    58.      * @param val
    59.      */
    60.     public void push(int val) {
    61.         if(isFull()) {
    62.             elem = Arrays.copyOf(elem,2*elem.length);
    63.         }
    64.         //1、放到最后的位置
    65.         elem[usedSize] = val;
    66.         //2、进行向上调整
    67.         shiftUp(usedSize);
    68.         //3、有效数据+1
    69.         usedSize++;
    70.     }
    71.  
    72.     private void shiftUp(int child) {
    73.         int parent = (child-1) / 2;
    74.         while (child > 0) {
    75.             if(elem[child] > elem[parent]) {
    76.                 int tmp = elem[child];
    77.                 elem[child] = elem[parent];
    78.                 elem[parent] = tmp;
    79.                 child = parent;
    80.                 parent = (child-1)/2;
    81.             }else {
    82.                 break;
    83.             }
    84.         }
    85.     }
    86.  
    87.     public boolean isFull() {
    88.         return usedSize == elem.length;
    89.     }
    90.  
    91.     /**
    92.      * 出队【删除】：每次删除的都是优先级高的元素
    93.      * 仍然要保持是大根堆
    94.      */
    95.     public void pollHeap() {
    96.         if(isEmpty()) {
    97.             System.out.println("优先级队列为空！");
    98.             return;
    99.         }
    100.         int tmp = elem[0];
    101.         elem[0] = elem[usedSize-1];
    102.         elem[usedSize-1] = tmp;
    103.         usedSize--;//9
    104.         shiftDown(0,usedSize);
    105.     }
    106.  
    107.     public boolean isEmpty() {
    108.         return usedSize == 0;
    109.     }
    110.  
    111.     /**
    112.      * 获取堆顶元素
    113.      * @return
    114.      */
    115.     public int peekHeap() {
    116.         if(isEmpty()) {
    117.             System.out.println("优先级队列为空！");
    118.             return -1;
    119.         }
    120.         return elem[0];
    121.     }
    122. }

    41、插入排序和希尔排序

    1. //=====================================================
    2. // 插入排序
    3. public static void insertSort(int[] array){
    4.     // 外层循环目的：取到数组中的每个元素
    5.     for(int i = 1; i < array.length; ++i){
    6.  
    7.         // 将该元素插入到序列中
    8.         // array数组中：[0, i)的元素已经排好了
    9.  
    10.         // i位置的数据是本次要插入的数据---[0,i)
    11.         int key = array[i];
    12.         int end = i-1;
    13.  
    14.         while(end >= 0 && key < array[end]){
    15.             array[end+1] = array[end];
    16.             end--;
    17.         }
    18.  
    19.         array[end+1] = key;
    20.     }
    21. }
    22.  
    23. //===========================================================
    24. // 希尔排序
    25. public static void shellSort(int[] array){
    26.     int gap = array.length;
    27.  
    28.     while(gap > 1){
    29.         gap = gap/3+1;
    30.         for(int i = gap; i < array.length; ++i){
    31.  
    32.             // 将该元素插入到序列中
    33.             // array数组中：[0, i)的元素已经排好了
    34.  
    35.             // i位置的数据是本次要插入的数据---[0,i)
    36.             int key = array[i];
    37.             int end = i-gap;
    38.  
    39.             while(end >= 0 && key < array[end]){
    40.                 array[end+gap] = array[end];
    41.                 end -= gap;
    42.             }
    43.  
    44.             array[end+gap] = key;
    45.         }
    46.     }
    47. }

    42、选择排序和堆排序

    1. //============================================================
    2. // 选择排序
    3. // 时间复杂度：O(N^2)
    4. // 空间复杂度：O(1)
    5. // 稳定性：不稳定
    6. public static void selectSort(int[] array){
    7.     int size = array.length;
    8.     for(int i = 0; i < size-1; ++i){  // 控制具体选择的趟数// 具体选择的方式
    9.        int pos = 0;    
    10.         // 找最大元素的位置
    11.        for(int j = 0; j < size-i; ++j){
    12.             if(array[j] > array[pos]){
    13.                 pos = j;
    14.             }
    15.         }
    16.  
    17.         // 用pos标记的最大元素与区间最后一个位置上的元素交换
    18.         if(pos != size-1-i){
    19.             swap(array, pos, size-i-1);
    20.         }
    21.     }
    22. }
    23.  
    24. public static void selectSortOP(int[] array){
    25.     int begin = 0;
    26.     int end = array.length-1;
    27.     while(begin < end){
    28.  
    29.         // 在[begin, end]区间中找最大和最小元素的位置
    30.        // 最大元素的位置使用maxPos标记
    31.      // 最小元素的位置使用minPos标记    
    32.         int minPos = begin;
    33.         int maxPos = begin;
    34.         int index = begin+1;
    35.         while(index <= end){
    36.             if(array[index] > array[maxPos]){
    37.                 maxPos = index;
    38.             }
    39.  
    40.             if(array[index] < array[minPos]){
    41.                 minPos = index;
    42.             }
    43.  
    44.             index++;
    45.         }
    46.  
    47.         // 在[begin, end]区间中，已经找到了最小与最小元素的位置
    48.        if(maxPos != end){
    49.             swap(array, maxPos, end);
    50.         }
    51.  
    52.         if(minPos == end){
    53.             minPos = maxPos;
    54.         }
    55.  
    56.         if(minPos != begin){
    57.             swap(array, minPos, begin);
    58.         }
    59.  
    60.         begin++;
    61.         end--;
    62.     }
    63. }
    64.  
    65. //================================================================
    66. // 堆排序
    67. public static void shiftDown(int[] array, int size, int parent){
    68.     // child标记parent的左孩子---parent可能有左没有右
    69.     int child = parent*2 + 1;
    70.     while(child < size){   // 如果循环条件成立：parent的左孩子一定是成立的
    71.  
    72.         // 右孩子存在的情况下，找左右孩子中最大的孩子
    73.         if(child+1 < size && array[child+1] > array[child]){
    74.             child += 1;
    75.         }
    76.  
    77.         // 检测parent是否满足堆的特性
    78.         if(array[parent] < array[child]){
    79.             swap(array, parent, child);
    80.             parent = child;
    81.             child = parent*2+1;
    82.         }else{
    83.             return;
    84.         }
    85.     }
    86. }
    87.  
    88. // 时间复杂度：O(NlogN)
    89. // 空间复杂度：O(1)
    90. // 稳定性：不稳定
    91. // 应用场景：需要一个序列中前k个最大||最小 ---- 可能会和其他排序复合起来提高排序的效率
    92. public static void heapSort(int[] array){
    93.     // 1. 建堆
    94.     // a. 找倒数第一个非叶子节点
    95.     int size = array.length;
    96.     int lastLeaf = ((size-2)>>>1);
    97.     for(int root = lastLeaf; root >= 0; root--){
    98.         shiftDown(array, size, root);
    99.     }
    100.  
    101.     // 2. 利用堆删除的思想排序
    102.     int end = size-1;
    103.     while(end > 0){
    104.         // 用堆顶元素与堆中最后一个元素交换
    105.         swap(array, 0, end);
    106.  
    107.         // 将堆中有效元素个数减少一个
    108.  
    109.         // 将堆顶元素向下调整
    110.         shiftDown(array, end,0); // logN
    111.  
    112.         end--;
    113.     }
    114. }

    43、冒泡排序和快速排序

    1. //================================================================
    2. // 冒泡排序
    3. // 时间复杂度：O(N^2)
    4. // 空间复杂度：O(1)
    5. // 稳定性：稳定
    6. // 应用场景：
    7. public static void bubbleSort(int[] array){
    8.     int size = array.length;
    9.     for(int i = 0; i < size; ++i){   // 控制冒泡的趟数
    10.  
    11.         boolean isChange = false;
    12.  
    13.         // 具体冒泡的方式：用相邻的两个元素进行交换// 如果不满足条件则交换for(int j = 1; j < size - i; j++){
    14.             if(array[j-1] > array[j]){
    15.                 swap(array, j-1, j);
    16.                 isChange = true;
    17.             }
    18.         }
    19.  
    20.         if(!isChange){
    21.             return;
    22.         }
    23.     }
    24. }
    25.  
    26. //============================================================
    27. // 快速排序
    28. // 三数取中法：
    29. public static int getIndexOfMiddle(int[] array, int left, int right){
    30.     // left
    31.     // mid: left + ((right-left)>>1)
    32.     // right-1
    33.     int mid = left + ((right-left)>>1);
    34.     if(array[left] < array[right-1]){
    35.         if(array[mid] < array[left]){
    36.             return left;
    37.         }else if(array[mid] > array[right-1]){
    38.             return right-1;
    39.         }else{
    40.             return mid;
    41.         }
    42.     }else{
    43.         if(array[mid] > array[left]){
    44.             return left;
    45.         }else if(array[mid] < array[right-1]){
    46.             return right-1;
    47.         }else{
    48.             return mid;
    49.         }
    50.     }
    51. }
    52.  
    53. // Hoare法时间复杂度：O(N)
    54. public static int partition1(int[] array, int left, int right){
    55.     int index = getIndexOfMiddle(array, left, right);
    56.     if(index != right-1){
    57.         swap(array, index, right-1);
    58.     }
    59.  
    60.     int key = array[right-1];
    61.     int begin = left;
    62.     int end = right-1;
    63.  
    64.     while(begin < end){
    65.         // 让begin从前往后找比key大的元素，找到之后停下来
    66.         while(begin < end && array[begin] <= key){
    67.             begin++;
    68.         }
    69.  
    70.         // 让end从后往前找比key小的元素，找到之后停下来
    71.         while(begin < end && array[end] >= key){
    72.             end--;
    73.         }
    74.  
    75.         if(begin != end){
    76.             swap(array, begin, end);
    77.         }
    78.     }
    79.  
    80.     if(begin != right-1){
    81.         swap(array, begin, right-1);
    82.     }
    83.  
    84.     return begin;
    85. }
    86.  
    87. // 挖坑法----时间复杂度：O(N)
    88. public static int partition2(int[] array, int left, int right){
    89.     int index = getIndexOfMiddle(array, left, right);
    90.     if(index != right-1){
    91.         swap(array, index, right-1);
    92.     }
    93.  
    94.     int key = array[right-1];
    95.     int begin = left;
    96.     int end = right-1;
    97.  
    98.     while(begin < end){
    99.         // 让begin从前往后找比基准值大的元素
    100.         while(begin < end && array[begin] <= key){
    101.             begin++;
    102.         }
    103.  
    104.         if(begin < end){
    105.             // begin位置找到了一个比key大的元素，填end位置的坑
    106.             array[end] = array[begin];
    107.  
    108.             // begin位置就形成一个新的坑位
    109.         }
    110.  
    111.         // 让end从后往前找比基准值小的元素
    112.         while(begin < end && array[end] >= key){
    113.             end--;
    114.         }
    115.  
    116.         if(begin < end){
    117.             // end位置找到了一个比key小的元素，填begin位置的坑
    118.             array[begin] = array[end];
    119.  
    120.             // end位置就形成了一个新的坑位
    121.         }
    122.     }
    123.  
    124.     // begin和end位置是最后的一个坑位
    125.     // 这个坑位使用基准值填充
    126.     array[begin] = key;
    127.     return begin;
    128. }
    129.  
    130. public static int partition(int[] array, int left, int right){
    131.     int cur = left;
    132.     int prev = cur-1;
    133.  
    134.     int index = getIndexOfMiddle(array, left, right);
    135.     if(index != right-1){
    136.         swap(array, index, right-1);
    137.     }
    138.  
    139.     int key = array[right-1];
    140.  
    141.     // 让cur从前往后找比key小的元素
    142.     while(cur < right){
    143.         if(array[cur] < key && ++prev != cur){
    144.             swap(array, cur, prev);
    145.         }
    146.  
    147.         ++cur;
    148.     }
    149.  
    150.     // 将基准值的位置放置好
    151.     if(++prev != right -1){
    152.         swap(array, prev, right-1);
    153.     }
    154.  
    155.     return prev;
    156. }
    157.  
    158. // 时间复杂度：O(NlogN)
    159. // 空间复杂度：O(logN)
    160. // 稳定性：不稳定
    161. // 应用场景：数据越随机越好----越乱越好
    162. public static void insertSortQuick(int[] array, int left, int right){
    163.     // 外层循环目的：取到数组中的每个元素
    164.     for(int i = left+1; i < right; ++i){
    165.  
    166.         // 将该元素插入到序列中
    167.         // array数组中：[0, i)的元素已经排好了
    168.  
    169.         // i位置的数据是本次要插入的数据---[0,i)
    170.         int key = array[i];
    171.         int end = i-1;
    172.  
    173.         while(end >= 0 && key < array[end]){
    174.             array[end+1] = array[end];
    175.             end--;
    176.         }
    177.  
    178.         array[end+1] = key;
    179.     }
    180. }
    181.  
    182. public static void quickSort(int[] array, int left, int right){
    183.     if(right - left < 47) {
    184.         insertSortQuick(array, left, right);
    185.     }else{
    186.         // 假设升序
    187.         // 找一个基准值将[left, right)区间分割成两个部分
    188.         int div = partition(array, left, right);
    189.  
    190.         // 左侧部分比基准值小
    191.         // [left, div)
    192.         quickSort(array, left, div);
    193.  
    194.         // 右侧部分比基准值大
    195.         // [div+1, right)
    196.         quickSort(array, div+1, right);
    197.     }
    198. }
    199.  
    200. public static void quickSort(int[] array){
    201.     Stack s = new Stack<>();
    202.     s.push(array.length);
    203.     s.push(0);
    204.  
    205.     while(!s.empty()){
    206.         int left = s.pop();
    207.         int right = s.pop();
    208.  
    209.         if(right - left < 47){
    210.             insertSortQuick(array, left, right);
    211.         }else{
    212.             int div = partition2(array, left, right);
    213.  
    214.             // 先压入基准值右侧部分
    215.             // [div+1, right);
    216.             s.push(right);
    217.             s.push(div+1);
    218.  
    219.  
    220.             // 后压入基准值左侧部分
    221.             // [left, div)
    222.             s.push(div);
    223.             s.push(left);
    224.         }
    225.     }
    226. }

    44、归并排序和计数排序

    1. //==========================================================
    2. // 归并排序
    3. public static void mergeDate(int[] array, int left, int mid, int right, int[] temp){
    4.     int begin1 = left, end1 = mid;
    5.     int begin2 = mid, end2 = right;
    6.     int index = left;
    7.  
    8.     while(begin1 < end1 && begin2 < end2){
    9.         if(array[begin1] <= array[begin2]){
    10.             temp[index++] = array[begin1++];
    11.         }else{
    12.             temp[index++] = array[begin2++];
    13.         }
    14.     }
    15.  
    16.     while(begin1 < end1){
    17.         temp[index++] = array[begin1++];
    18.     }
    19.  
    20.     while(begin2 < end2){
    21.         temp[index++] = array[begin2++];
    22.     }
    23. }
    24.  
    25. // 时间复杂度：O(NlogN)
    26. // 空间复杂度：O(N)
    27. // 稳定性：稳定
    28. // 应用场景：外部排序
    29. private static void mergeSort(int[] array, int left, int right, int[] temp){
    30.     if(right - left > 1){
    31.         // 先对[left, right)区间中的元素进行均分
    32.         int mid = left + ((right - left)>>1);
    33.  
    34.         // [left, mid)
    35.         mergeSort(array, left, mid, temp);
    36.  
    37.         // [mid, right)
    38.         mergeSort(array, mid, right, temp);
    39.  
    40.         mergeDate(array, left, mid, right, temp);
    41.         System.arraycopy(temp, left, array, left, right-left);
    42.     }
    43. }
    44.  
    45.  
    46. public static void mergeSort(int[] array){
    47.     int[] temp = new int[array.length];
    48.     mergeSort(array, 0, array.length, temp);
    49. }
    50.  
    51. public static void mergeSortNor(int[] array){
    52.     int size = array.length;
    53.     int[] temp = new int[size];
    54.  
    55.     int gap = 1;
    56.  
    57.     while(gap < size){
    58.         for(int i = 0; i < size; i+= 2*gap){
    59.             int left = i;
    60.             int mid = left + gap;
    61.             int right = mid+gap;
    62.             if(mid > size){
    63.                 mid = size;
    64.             }
    65.  
    66.             if(right > size){
    67.                 right = size;
    68.             }
    69.  
    70.             mergeDate(array, left, mid, right, temp);
    71.         }
    72.  
    73.         System.arraycopy(temp, 0, array, 0, size);
    74.  
    75.         gap <<= 1;
    76.     }
    77. }
    78.  
    79. // 计数排序
    80. //==================================================================
    81. // 时间复杂度：O(N)---N表示数组中元素个数
    82. // 空间复杂度：O(M)---M表示范围的大小
    83. // 稳定性：稳定
    84. // 应用场景：数据密集集中在某个范围中
    85. public static void countSort(int[] array){
    86.     // 找数据范围
    87.     int maxValue = array[0];
    88.     int minValue = array[0];
    89.     for(int i = 0; i < array.length; ++i){
    90.         if(array[i] > maxValue){
    91.             maxValue = array[i];
    92.         }
    93.  
    94.         if(array[i] < minValue){
    95.             minValue = array[i];
    96.         }
    97.     }
    98.  
    99.     // 计算计数空间的大小
    100.     int range = maxValue - minValue + 1;
    101.     int[] count = new int[range];
    102.  
    103.     // 1. 统计array中每个数据出现的次数
    104.     for(int i = 0; i < array.length; ++i){
    105.         count[array[i] - minValue]++;
    106.     }
    107.  
    108.     // 2. 根据统计结果回收
    109.     int index = 0;
    110.     for(int i = 0; i < range; ++i){
    111.         while(count[i] > 0){
    112.             array[index++] = i + minValue;
    113.             count[i]--;
    114.         }
    115.     }
    116. }
    117.

    45、912. 排序数组 - 力扣（LeetCode）

    46、实现二叉搜索树代码

    1. public class BinarySearchTree {
    2.  
    3.     static class TreeNode {
    4.         public int key;
    5.         public TreeNode left;
    6.         public TreeNode right;
    7.  
    8.         TreeNode(int key) {
    9.             this.key = key;
    10.         }
    11.     }
    12.  
    13.     public TreeNode root;
    14.  
    15.     /**
    16.      *
    17.      * @param key
    18.      */
    19.     public boolean insert(int key) {
    20.         if(root == null) {
    21.             root = new TreeNode(key);
    22.             return true;
    23.         }
    24.  
    25.         TreeNode cur = root;
    26.         TreeNode parent = null;
    27.  
    28.         while (cur != null) {
    29.             if(cur.key < key) {
    30.                 parent = cur;
    31.                 cur = cur.right;
    32.             }else if(cur.key > key) {
    33.                 parent = cur;
    34.                 cur = cur.left;
    35.             }else {
    36.                 return false;
    37.             }
    38.         }
    39.         TreeNode node = new TreeNode(key);
    40.         //当代码执行到这里之后。cur == null
    41.         if(parent.key < key) {
    42.             parent.right = node;
    43.         }else {
    44.             parent.left = node;
    45.         }
    46.         return true;
    47.     }
    48.  
    49.     public TreeNode search(int key) {
    50.         TreeNode cur = root;
    51.         while (cur != null) {
    52.             if(cur.key == key) {
    53.                 return cur;
    54.             }else if(cur.key < key) {
    55.                 cur = cur.right;
    56.             }else {
    57.                 cur = cur.left;
    58.             }
    59.         }
    60.         return null;
    61.     }
    62.  
    63.     public boolean remove(int key) {
    64.         TreeNode cur = root;
    65.         TreeNode parent = null;
    66.         while (cur != null) {
    67.             if(cur.key < key) {
    68.                 parent = cur;
    69.                 cur = cur.right;
    70.             }else if(cur.key == key) {
    71.                 //这里开始删除！
    72.                 removeNode(parent,cur);
    73.                 return true;
    74.             }else {
    75.                 parent = cur;
    76.                 cur = cur.left;
    77.             }
    78.         }
    79.         return false;
    80.     }
    81.  
    82.     private void removeNode(TreeNode parent,TreeNode cur) {
    83.         if(cur.left == null) {
    84.             if(cur == root) {
    85.                 root = cur.right;
    86.             }else if(cur == parent.left) {
    87.                 parent.left = cur.right;
    88.             }else {
    89.                 parent.right = cur.right;
    90.             }
    91.         }else if(cur.right == null) {
    92.             if(cur == root) {
    93.                 root = cur.left;
    94.             }else if(cur == parent.left) {
    95.                 parent.left = cur.left;
    96.             }else {
    97.                 parent.right = cur.left;
    98.             }
    99.         }else {
    100.             TreeNode targetParent = cur;
    101.             TreeNode target = cur.right;
    102.             while (target.left != null) {
    103.                 targetParent = target;
    104.                 target = target.left;
    105.             }
    106.             cur.key = target.key;
    107.             if(target == targetParent.left) {
    108.                 targetParent.left = target.right;
    109.             }else {
    110.                 targetParent.right = target.right;
    111.             }
    112.         }
    113.     }
    114.  
    115.     //中序遍历即可
    116.     public void inorder(TreeNode root) {
    117.         if(root == null) return;
    118.         inorder(root.left);
    119.         System.out.print(root.key+" ");
    120.         inorder(root.right);
    121.     }
    122. }

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

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

    49、771. 宝石与石头 - 力扣（LeetCode）

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

  • 相关阅读:
    webpack项目 index.html 根据不同的变量引入不同的js
    HAproxy反向代理与负载均衡
    建模干货：关于ZBrush拓扑的必学技能
    【方向盘】Java EE几十种技术，“活着的”还剩几何（Web应用技术篇）
    第60章 ApplicationPart自动集成整体性和独立性插件项
    5G网络身份ID识别---详解5G-GUTI
    Log4cpp 使用DailyRollingFileAppender 设置按天进行日志轮转
    普通人做自媒体怎么赚钱？
    CAIE ALevel物理（9702）易错题分析
    使用node+vite还有axios发出get请求出现此类问题
  • 原文地址：https://blog.csdn.net/weixin_51912875/article/details/126000936