1、数组转字符串
实现一个方法 toString, 把一个整型数组转换成字符串. 例如数组 {1, 2, 3} , 返回的字符串为 "[1, 2, 3]", 注意 逗号 的位置和数量
4、26. 删除有序数组中的重复项 - 力扣（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;
}
}
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;
}
}14、142. 环形链表 II - 力扣（LeetCode）
16、链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
17、链表分割_牛客题霸_牛客网 (nowcoder.com)
18、21. 合并两个有序链表 - 力扣（LeetCode）
20、栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
21、150. 逆波兰表达式求值 - 力扣（LeetCode）
23、225. 用队列实现栈 题解 - 力扣（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)
29、572. 另一棵树的子树 - 力扣（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]--;
}
}
}
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)
本文含有隐藏内容，请 开通VIP 后查看