栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法与数据结构

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法与数据结构

目录

排序

选择排序

冒泡排序

插入排序

常见的时间复杂度排名(由好到差):7种

认识二分法

在一个有序数组中,找某个数是否存在

在一个有序数组中,找>=某个数最左侧的位置

在一个有序数组中,找<=某个数最右侧的位置

局部最小值问题

 认识异或运算

如何不用额外变量交换俩个数

数组中,一个数出现奇数,一个数出现偶数。那么怎么找到这个奇数。

怎么把一个int类型的数,提取出最右侧的1来(二进制)

数组中有俩种数出现了奇数次,其他的数都是偶数次。找到并打印这俩个数。

链表

单链表反转

双链表反转

单链表把给定的值删除

栈和队列

双向链表实现栈和队列

数组实现栈和队列

数组实现栈

数组实现队列

设计一个栈,在基本功能的基础上,增加返回栈中最小元素的功能(使用现成的栈结构)

如何用栈实现队列

如何用队列实现栈

递归

哈希表

有序表

排序

归并排序

数组小和

快速排序

堆结构

大根堆实现

堆排序

系统实现的小根堆

 一个几乎有序的数组,排序之后元素移动的距离一定不超过k

前缀树

固定数组实现方式(26字母)

哈希表实现

桶排序

计数排序

基数排序

排序算法的总结

 链表相关面试题

排序

选择排序

时间复杂度为O(N²)

选择排序过程: 一个arr数组,我从

arr[0~N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置上;

arr[1~N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置上;

arr[2~N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置上;

以此类推~~~~

arr[N-2~N-1]范围上,找到最小值所在的位置,然后把最小值交换到N-2位置上;

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;   //记录最小值的位置
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

冒泡排序

时间复杂度是O(N²)

冒泡排序过程:一个arr数组,

arr[0]和arr[0~N-1]范围上进行:arr[0]和arr[1],谁大谁往后移,arr[1]和arr[2]谁大谁往后移~~~以此类推~~~arr[N-2]和arr[N-1],谁大谁往后移到N-1位置上。

arr[0]和arr[0~N-2]范围上进行;

arr[0]和arr[0~N-3]范围上进行;

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

插入排序

时间复杂度是O(N²)

插入排序过程:一个arr数组

arr[0~0]上有序,必然后续;

arr[0~1]上有序,让arr[1]往前看,如果arr[1]

以此类推~~~

想让arr[0~i]上有序,让i往前看,小于就交换,直到左边的数不比自己大。

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

常见的时间复杂度排名(由好到差):7种

O(1)

O(LogN)

O(N)

O(N*LogN)

O(N²)    

O(2^N)

O(N!)

认识二分法

只要能正确构建左右俩侧的淘汰逻辑,你就可以二分

时间复杂度是O(LogN)

在一个有序数组中,找某个数是否存在
    public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        while (L <= R) {
            // >> 1  等价于 除以2
            //  mid = L + ((R - L) >> 1) 等价于 (L+R)/2
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
//        return sortedArr[L] == num;
        return  false;
    }

在一个有序数组中,找>=某个数最左侧的位置
    public static int nearestIndex(int[] arr, int value) {
        int index = -1;
        if (arr == null || arr.length == 0) {
            return index;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) { // 至少一个数的时候
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

在一个有序数组中,找<=某个数最右侧的位置
    public static int nearestIndex(int[] arr, int value) {
        int index = -1;
        if (arr == null || arr.length == 0) {
            return index;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }

局部最小值问题

局部最小值有三种体现如左图所示

    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

 认识异或运算

异或:相同为0,不同为1

也就是可以看成:无进位相加

0 ^ N = N        A ^ B = C

N ^ N = 0        C ^ A = B

如何不用额外变量交换俩个数
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];

数组中,一个数出现奇数,一个数出现偶数。那么怎么找到这个奇数。
    public static void printOddTimesNum1(int[] arr) {
        int eO = 0;
        for (int cur : arr) {
            eO ^= cur;
        }
        System.out.println(eO);
    }

怎么把一个int类型的数,提取出最右侧的1来(二进制)
N & ( ~N + 1 )

数组中有俩种数出现了奇数次,其他的数都是偶数次。找到并打印这俩个数。
    public static void printOddTimesNum2(int[] arr) {
        int eO = 0;
        int eOhasOne = 0;
        for (int curNum : arr) {
            eO ^= curNum;
        }
        int rightOne = eO & (~eO + 1);
        for (int cur : arr) {
            if ((cur & rightOne) != 0) {
                eOhasOne ^= cur;
            }
        }
        System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
    }

链表
    public static class Node {
        public int value;
        public Node next;
        public Node(int data) {
            value = data;
        }
    }
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;
        public DoubleNode(int data) {
            value = data;
        }
    }

单链表反转
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

双链表反转
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

单链表把给定的值删除

删除指定的值,要考虑一个问题。指定的值是head!!!!

    public static Node removeValue(Node head, int num) {
        // head来到第一个不需要删的位置
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }
        // 1 ) head == null   2 ) head != null
        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == num) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

栈和队列

双向链表实现栈和队列
    public static class Node {
        public T value;
        public Node last;
        public Node next;
        public Node(T data) {
            value = data;
        }
    }

    public static class DoubleEndsQueue {
        public Node head;
        public Node tail;
        public void addFromHead(T value) {
            // head == null
            // head != null
            Node cur = new Node(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }
        public void addFromBottom(T value) {
            // tail == null
            // tail != null
            Node cur = new Node(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
        }
        public T popFromHead() {
            // head == null
            // head == tail  也就是一个值
            //
            if (head == null) {
                return null;
            }
            Node cur = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                cur.next = null;    //断开
                head.last = null;
            }
            return cur.value;
        }
        public T popFromBottom() {
            // head == null
            // tail == tail  也就是一个值
            //
            if (head == null) {
                return null;
            }
            Node cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
                cur.last = null; //断开
            }
            return cur.value;
        }
        public boolean isEmpty() {
            return head == null;
        }
    }
    public static class MyStack {
        private DoubleEndsQueue queue;
        public MyStack() {
            queue = new DoubleEndsQueue();
        }
        public void push(T value) {
            queue.addFromHead(value);
        }
        public T pop() {
            return queue.popFromHead();
        }
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }
    public static class MyQueue {
        private DoubleEndsQueue queue;
        public MyQueue() {
            queue = new DoubleEndsQueue();
        }
        public void push(T value) {
            queue.addFromHead(value);
        }
        public T poll() {
            return queue.popFromBottom();
        }
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

数组实现栈和队列

数组实现栈和队列,其实是用一个固定大小的数组去实现。

数组实现栈

其实就是 index++ 和 index --的过程,因为栈是先进后出。

数组实现队列
    public static class MyQueue {
        private int[] arr;
        private int pushi;// end
        private int polli;// begin
        private int size;
        private final int limit;
        public MyQueue(int limit) {
            arr = new int[limit];
            pushi = 0;
            polli = 0;
            size = 0;
            this.limit = limit;
        }
        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("队列满了,不能再加了");
            }
            size++;
            arr[pushi] = value;
            pushi = nextIndex(pushi);
        }
        public int pop() {
            if (size == 0) {
                throw new RuntimeException("队列空了,不能再拿了");
            }
            size--;
            int ans = arr[polli];
            polli = nextIndex(polli);
            return ans;
        }
        public boolean isEmpty() {
            return size == 0;
        }
        private int nextIndex(int i) {
            return i < limit - 1 ? i + 1 : 0;
        }
    }

设计一个栈,在基本功能的基础上,增加返回栈中最小元素的功能(使用现成的栈结构)

第一种方式,只压入最小值

    public static class MyStack1 {
        private Stack stackData;
        private Stack stackMin;
        public MyStack1() {
            this.stackData = new Stack();
            this.stackMin = new Stack();
        }

        public void push(int newNum) {
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum <= this.getmin()) {
                this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
        }

        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            int value = this.stackData.pop();
            if (value == this.getmin()) {
                this.stackMin.pop();
            }
            return value;
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

第二种方式,不管怎样,每次都将最小值压入

public static class MyStack2 {
        private Stack stackData;
        private Stack stackMin;
        public MyStack2() {
            this.stackData = new Stack();
            this.stackMin = new Stack();
        }
        public void push(int newNum) {
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum < this.getmin()) {
                this.stackMin.push(newNum);
            } else {
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }
            this.stackData.push(newNum);
        }
        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }
        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

如何用栈实现队列

要遵循一定的原则

1)pop栈 必须为空   2) push 也要一次性的导完

    public static class TwoStacksQueue {
        public Stack stackPush;
        public Stack stackPop;
        public TwoStacksQueue() {
            stackPush = new Stack();
            stackPop = new Stack();
        }
        private void pushToPop() {
            if (stackPop.empty()) {
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }
        }
        public void add(int pushInt) {
            stackPush.push(pushInt);
            pushToPop();
        }
        public int poll() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            }
            pushToPop();
            return stackPop.pop();
        }
        public int peek() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            }
            pushToPop();
            return stackPop.peek();
        }
    }

如何用队列实现栈
    public static class TwoQueueStack {
        public Queue queue;
        public Queue help;
        public TwoQueueStack() {
            queue = new LinkedList<>();
            help = new LinkedList<>();
        }
        public void push(T value) {
            queue.offer(value);
        }
        public T poll() {
            while (queue.size() > 1) {
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            Queue tmp = queue;
            queue = help;
            help = tmp;
            return ans;
        }
        public T peek() {
            while (queue.size() > 1) {
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            help.offer(ans);
            Queue tmp = queue;
            queue = help;
            help = tmp;
            return ans;
        }
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

递归

举例:数组arr[L...R]中的最大值,怎么用递归方法实现。

1)将[L...R]范围分成左右俩半。 左:[L..Mid] 右:[Mid+1...R]

2)左部分求最大值,右部分求最大值

3)[L...R]范围上的最大值,是max{左部分最大值,右部分最大值}

注意:2)是个递归的过程,当范围上只有一个数,就可以不用再递归了。

    public static int getMax(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }
    public static int process(int[] arr, int L, int R) {
        // arr[L..R]范围上只有一个数,直接返回,base case
        if (L == R) {
            return arr[L];
        }
        // L...R 不只一个数
        // mid = (L + R) / 2
        int mid = L + ((R - L) >> 1); // 中点   	1
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

怎么实质上去理解这个递归,我们可以看如下图去加深记忆

哈希表

有序表

TreeMap   O(LogN)

排序

归并排序

1)整体是递归,左边排好序 + 右边排好序 + merge让整体有序

2)让其整体有序的过程里用了排外序方法

3)利用master公式来求解时间复杂度

4)当然可以用非递归实现

归并排序时间复杂度是O(N*LogN)

归并排序的实质是把比较行为变成了有序信息并传递

递归方式

    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }
    // O(N * logN)
    public static void process(int[] arr, int L, int R) {
        if (L == R) { // base case
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 要么p1越界了,要么p2越界了
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

非递归方式

    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 步长
        int mergeSize = 1;   // 当前有序的,左组长度
        while (mergeSize < N) { // log N
            // 当前左组的,第一个位置
            int L = 0;
            while (L < N) {
                int M = L +mergeSize - 1;
                if (M >= N) {
                    break;
                }
                int R = Math.min(M+mergeSize, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            // 防止溢出
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1;
        }
    }

当我们要计算某一个数左边有几个数比它小,都可以用MergeSort。以此类推

数组小和

 左 比 右 小  产生小和     小和去help            只有这里会产生小和

             相等     先拷贝     右组的数

             大于     先拷贝     右组的数

        产生 小和的个数 就是右组的个数

    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    // arr[L..R]既要排好序,也要求小和返回
    // 所有merge时,产生的小和,累加
    // 左 排序   merge
    // 右 排序  merge
    // merge
    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        // l < r
        int mid = l + ((r - l) >> 1);
        return
                process(arr, l, mid)
                        +
                        process(arr, mid + 1, r)
                        +
                        merge(arr, l, mid, r);
    }

    public static int merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }

快速排序

快速排序的时间复杂度O(N*LogN)

快速排序其实就是一个partition的过程。

给定一个数组arr,和一个整数num。把小于等于num的数放在数组的左边,大于num的数放在数组的右边。

1) 当[i]<=num,此时当前数和<=区下一个交换,<=区右移,i++

2) [i]>num,i++

1)[i] = num,i++

2)[i] < num,[i]与<区右一个交换,<区右移,i++

3)[i] > num,[i]与>区左一个交换,>区左移,此时i不变

i 和 大于区域,相遇的时候停止。

    public static void quickSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process3(arr, 0, arr.length - 1);
    }

    public static void process3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // 随机找一个值和R交换
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag(arr, L, R);
        process3(arr, L, equalArea[0] - 1);
        process3(arr, equalArea[1] + 1, R);
    }
    public static int[] netherlandsFlag(int[] arr, int L, int R) {
        if (L > R) { // L...R L>R
            return new int[] { -1, -1 };
        }
        if (L == R) {
            return new int[] { L, R };
        }
        int less = L - 1; // < 区 右边界
        int more = R; // > 区 左边界
        int index = L;
        while (index < more) { // 当前位置,不能和 >区的左边界撞上
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                swap(arr, index++, ++less);
            } else { // >
                swap(arr, index, --more);
            }
        }
        swap(arr, more, R); // <[R]   =[R]   >[R]
        return new int[] { less + 1, more };
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

堆结构

1)堆结构就是用数组实现的完全二叉树结构

2)完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3)完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4)堆结构的heaplnsert与heapify操作

5)堆结构的增大和减少

6)优先级队列结构,就是堆结构
完全二叉树就是层级满的,最下一层是从左向右,有满的趋势。

用一个数组其实就可以实现完全二叉树:

第一种方式数组下标从0开始(也是本文所使用的方式)

左孩子 2 * i + 1        右孩子 2 * i + 2           父亲  ( i - 1 )/ 2         

满足这三条规律,就是一个完全二叉树(向下取整)

第二种方式数组下标从1开始

左孩子 2 * i         右孩子 2 * i + 1           父亲  i / 2

这种实现方式是因为可以用位运算去代替公式,因为位运算会很快

大根堆实现

加入一个数的实现思路:当插入第二个数的时候,会找自己的父,如果小于等于那么就不动,就是一个完全二叉树,并且是一个大根堆;如果大于就进行交换,交换完之后继续比较直到自己为父。

删除最大值的实现思路:需要数组中第一个值和最后一个值交换,然后heapsize--,然后用父节点去找左孩子右孩子,在跟最大的去交换,直到越界(越界heapsize可知)。

    public static class MyMaxHeap {
        private int[] heap;
        private final int limit;
        private int heapSize;  //即表示我收集了多少个数,也表示我下一个来的数放在哪里

        public MyMaxHeap(int limit) {
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public boolean isFull() {
            return heapSize == limit;
        }

        public void push(int value) {
            if (heapSize == limit) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            // value heapSize
            heapInsert(heap, heapSize++);
        }

        public int pop() {
            int ans = heap[0];
            swap(heap, 0, --heapSize);
            heapify(heap, 0, heapSize);
            return ans;
        }

        private void heapInsert(int[] arr, int index) {
            // [index] [index-1]/2
            // index == 0
            // index 不比 index父大
            //
            while (arr[index] > arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int[] arr, int index, int heapSize) {
            int left = index * 2 + 1;
            while (left < heapSize) { // 如果有左孩子,有没有右孩子,可能有可能没有!
                // 把较大孩子的下标,给largest
                int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                largest = arr[largest] > arr[index] ? largest : index;
                if (largest == index) {
                    break;
                }
                // index和较大孩子,要互换
                swap(arr, largest, index);
                index = largest;  //把大的给index  下一个跟index比较
                left = index * 2 + 1;
            }
        }

        private void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

堆排序

时间复杂度是O(N*LogN)

一个无序数组,看成一个一个的 数来,并且生成大根堆。用第一个数与N-1的位置交换,之后heapify。

把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆,一直周而复始。

public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // O(N*logN)
		for (int i = 0; i < arr.length; i++) { // O(N)
			heapInsert(arr, i); // O(logN)
		}

        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        // O(N*logN)
        while (heapSize > 0) { // O(N)
            heapify(arr, 0, heapSize); // O(logN)
            swap(arr, 0, --heapSize); // O(1)
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) { // 下方还有孩子的时候

            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

系统实现的小根堆

 一个几乎有序的数组,排序之后元素移动的距离一定不超过k

已知一个几乎有序的数组。几乎有序是指,如果把数组排好序的话,每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的。那么请选择一个合适的排序策略,对这个数组进行排序。

实现思路:先把 K+1放进小根堆 然后弹出最小值放进0的位置上,然后放值 在弹出最小值放在1的位置上~~~以此类推。

    public static void sortedArrDistanceLessK(int[] arr, int k) {
        if (k == 0) {
            return;
        }
        // 默认小根堆
        PriorityQueue heap = new PriorityQueue<>();
        int index = 0;
        // 0...K
        for (; index <= Math.min(arr.length - 1, k); index++) {
            heap.add(arr[index]);
        }

        int i = 0;
        for (; index < arr.length; i++, index++) {
            arr[i] = heap.poll();
            heap.add(arr[index]);
        }
        //依次弹出
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }

前缀树

1)单个字符串中,字符从前到后的加到一颗多叉树上

2)字符放在路上,节点上有专属的数据项(常见的是pass和end值)

3)所有样本都这样添加,如果没有路就新建,如有路就复用

4)沿途节点的pass值增加1,每个字符串结束时来到的节点end值增加1       

可以完成前缀相关的查询

字符串加入几次看  end

以某一个字符为前缀看 pass

固定数组实现方式(26字母)
    public static class Node1 {
        public int pass;
        public int end;
        public Node1[] nexts;

        // char tmp = 'b'  (tmp - 'a')
        public Node1() {
            pass = 0;
            end = 0;
            // 0    a
            // 1    b
            // 2    c
            // ..   ..
            // 25   z
            // nexts[i] == null   i方向的路不存在
            // nexts[i] != null   i方向的路存在
            nexts = new Node1[26];
        }
    }

    public static class Trie1 {
        private Node1 root;

        public Trie1() {
            root = new Node1();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] str = word.toCharArray();   //toCharArray  将字符串转换为字符数组
            Node1 node = root;
            node.pass++;
            int path = 0;
            for (int i = 0; i < str.length; i++) { // 从左往右遍历字符
                path = str[i] - 'a'; // 由字符,对应成走向哪条路
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node1();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word) {
            if (search(word) != 0) {
                char[] chs = word.toCharArray();
                Node1 node = root;
                node.pass--;
                int path = 0;
                for (int i = 0; i < chs.length; i++) {
                    path = chs[i] - 'a';
                    if (--node.nexts[path].pass == 0) {
                        node.nexts[path] = null;
                        return;
                    }
                    node = node.nexts[path];
                }
                node.end--;
            }
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node1 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        // 所有加入的字符串中,有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node1 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }

哈希表实现
    public static class Trie2 {
        private Node2 root;

        public Trie2() {
            root = new Node2();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            node.pass++;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if (!node.nexts.containsKey(index)) {
                    node.nexts.put(index, new Node2());
                }
                node = node.nexts.get(index);
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word) {
            if (search(word) != 0) {
                char[] chs = word.toCharArray();
                Node2 node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chs.length; i++) {
                    index = (int) chs[i];
                    if (--node.nexts.get(index).pass == 0) {
                        node.nexts.remove(index);
                        return;
                    }
                    node = node.nexts.get(index);
                }
                node.end--;
            }
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.end;
        }

        // 所有加入的字符串中,有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.pass;
        }
    }

桶排序

桶排序思想下的排序:计数排序 & 基数排序

1)桶排序思想下的排序都是不基于比较的排序

2)时间复杂度为O(N)

3)应用范围有限,需要样本的数据状况满足桶的划分

计数排序

必须知道样本的数量  并且数量很小  它是一个强相关的

    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 数中的最大值创建一个bucket数组
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        //然后从左到右写回去
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }

基数排序

排序算法的总结

 链表相关面试题

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/943330.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号