2022-11-22

排序-堆排序

完全二叉树是叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。

堆是有如下特点的完全二叉树

根节点的值>=子节点的值，即大顶堆
根节点的值<=子节点的值，即小顶堆

构建大顶堆

从0开始，将每一个数字依次插入，一边插入一边调整堆的结构，使之满足大顶堆的要求
将整个数列试作完全二叉树，自底向上调整树的结构，使之满足大顶堆的要求

建堆与堆化

建堆即构建堆
堆化是从当前位置开始调整数组使之满足堆的特征

堆排序的过程

构建大顶堆
取出堆顶元素
调整剩余数字使之符合大顶堆特点
再次取出堆顶元素
循环往复

完全二叉树的性质(根节点下标为0)

下标i的左子节点下标：2 * i + 1
下表i的右子节点下标：左下标+1
最后一个非叶子节点下标：n/2-1

堆排序的复杂度分析

堆排序的时间复杂度为O(n log n)，堆排序的空间复杂度为 O(1)。

时间复杂度分析由建堆和堆化两个，其中建堆的时间复杂度是O(n)，堆化的时间复杂度是O(n log n)

堆排序代码


public void testHeapSort() {
    int[] arr = new int[]{6, 2, 1, 3, 5, 4};
    buildMaxHeap(arr);

    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        maxHeapify(arr, 0, i);
    }
    
}

/**
 * 构建大顶堆
 * <p>
 * 我要成为亿万富翁
 * 我要财务自由
 */
private void buildMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}

/**
 * 堆化
 * <p>
 * 我要成为亿万富翁
 * 我要财务自由
 *
 * @param arr
 * @param i
 * @param size
 */
private void maxHeapify(int[] arr, int i, int size) {
    int left = 2 * i + 1;
    int right = left + 1;

    int maxValue = i;
    if (left < size && arr[left] > arr[maxValue]) {
        maxValue = left;
    }
    if (right < size && arr[right] > arr[maxValue]) {
        maxValue = right;
    }

    if (maxValue != i) {
        swap(arr, i, maxValue);
        maxHeapify(arr, maxValue, size);
    }
}

/**
 * 交换数组arr 下标 i j  的数据
 * <p>
 * 我要成为亿万富翁
 * 我要财务自由
 *
 * @param arr
 * @param i
 * @param j
 */
private void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[j] ^ arr[i];
    arr[i] = arr[i] ^ arr[j];
}

2022-11-21

数据结构-树的概念

树是由n(n>=0)个有限节点组成一个具有层次关系的集合。常见的树有平衡二叉树、二叉查找树、平衡二叉查找树（AVL树、黄黑树）、完全二叉树、满二叉树等。

常见概念

节点高度，节点到叶子节点的最厂路径
节点深度，根节点到该节点的边的个数
节点层次，深度+1
树的高度，根节点的高度

树的存储方式

链式存储
数组存储(x位于i，则i * 2=左子树，i * 2+1=右子树)

满二叉树

叶子节点在最后一层
叶子节点外，所有节点都有左右子树

完全二叉树

叶子节点在最后2层
最后一层叶子靠左
其他层节点数最大

完全二叉树性质(根节点为0，用数组保存完全二叉树)

下标i的左子节点下标：2 * i + 1
下表i的右子节点下标：左下标+1
最后一个非叶子节点下标：n/2-1

二叉查找树

对于任意节点，左子树的每个节点小于该节点
对于任意节点，右子树的每个节点大于该节点

平衡二叉树

任意节点左右子树高度相差不能大于1

平衡二叉查找树

平衡二叉树的特征
二叉查找树的特征

堆

完全二叉树
每个节点大于等于（或小于等于）子树中每个节点的值

堆的操作

堆化：插入
删除堆顶元素

堆排序

建堆，可以从上往下堆化，或从下往上堆化
排序，取堆顶，与末尾交换然后堆化，继续取堆顶，与末尾交换，再堆化

堆的应用

优先级队列
TOP K 问题
求中位数

2022-11-18

排序-希尔排序

希尔排序也叫缩减增量排序，希尔排序是对插入排序的优化，第一次以间隔一定gap将数组分为多个数组，对子数组做插入排序，然后对gap逐级递减，最后gap等于1，gap等于1时候相当于做全量的插入排序，但是又因为将过多次自排序，已经一定程度有序了，无需2层循坏。

希尔排序对插入排序最重要的优化在于每次移动的时候不只是移动了一个元素。

希尔排序最难点的是增量序列的算法。

希尔排序的空间复杂度是O(1)，时间复杂度是O(n) - O($n^2$)，平均复杂度和增量序列有关。

希尔排序用的比较少，主要是承前启后，给了后面效率比较好的排序一个启发。

2022-11-18

排序-时间复杂度n的2次方汇总

时间复杂度是O($n^2$)的排序算法有冒泡排序、选择排序、插入排序三种。

冒泡排序

两两比较，将大的往后移动即冒泡。

优化方案是如果不再比较，则剩余属于排序完成，则直接跳出循环；进一步的优化方案是每次比较只比较到上次比较的尾部。

选择排序

直接一个一个找最小的放至数组最前面。

优化方案是，每次找最小的和最大的，最小的放至最前面，最大的放至最后面，即二元排序。

插入排序

每次找最合适的位置，然后插入。实现方案包括交换法和移动法。交换即每次将要插入的与每个下标比较，如果小则交换；移动法不交换，将不符合的一个一个后移，直到找到合适的位置后放入。

其中冒泡排序和插入排序是稳定的排序算法，选择排序是不稳定的排序算法。时间复杂度都是O($n^2$)，空间复杂度都是O(1)。

2022-11-18

排序-插入排序

插入排序的思想非常简单，生活中有一个很常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。

插入排序有两种写法：

交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。

// 交换法
public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        // j 记录当前数字下标
        int j = i;
        // 当前数字比前一个数字小，则将当前数字与前一个数字交换
        while (j >= 1 && arr[j] < arr[j - 1]) {
            swap(arr, j, j - 1);
            // 更新当前数字下标
            j--;
        }
    }
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 移动法
public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        int currentNumber = arr[i];
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr[j + 1] = currentNumber;
    }
}

插入排序时间复杂度O($n^2$)，空间复杂度O(1)。

插入排序是稳定的排序算法。

2022-11-17

排序-选择排序

选择排序

最暴力最直接的排序，2层循环，每次都取最小的放在最前面。

选择排序的优化方式是同时记录最小值下标和最大值小标，每次比较的时候选出最小值和最大值，并将最小值放在最前面，最大值放在最后面，优化后的选择排序第一层循环只需要循环一半，该优化方法也叫二元选择排序。

选择排序的时间复杂度是O($n^2$)，空间复杂度是O(1)。

排序算法的稳定性

对于相当的情况，仍然保持原来的顺序，则是稳定的排序算法。

如果相当的情况，顺序有可能变，则不是稳定的排序算法。

2022-11-17

排序-冒泡排序

冒泡排序介绍

冒泡排序，使用2层循环，一边比较，一边把大的移动的下一位，这样每次循环最后一个都是当前最大的。

优化写法，如果循环内没有做一次交换，则没有剩下的就是已经排好序的，无需再继续比较。进一步优化的方法是，如果记录没有交换的下标，下次比较的时候只进行到下标位置。

时间复杂度O($n^{2}$)，空间复杂度O(1)。

private void bubble(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

交换

最常见的交换方法是开辟临时区域交换。

1
2
3

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

还有一种方式，通过先加后减或先减后加的方式，不用新内存即可实现，但这种方式有可能因为int越界导致异常。

// 先加后减
arr[j + 1] = arr[j + 1] + arr[j];
arr[j] = arr[j + 1] - arr[j];
arr[j + 1] = arr[j + 1] - arr[j];

// 先减后加
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j + 1] + arr[j];

最好的交换方式是使用位运算。

1
2
3

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];

2022-11-09

就是玩

“好啊,‘春雨贵如油’,今年要有个好收成了。”淅沥沥的春雨飘在泥泞的小路,飘在路旁一望无际的麦田里。

“好，哈、哈、哈……”一大汉身材魁梧，头发微霜，正行在小路上。看着天空加厚的云层,大汉哈哈大笑。一股春风扑面吹来,凉凉的多挟带了几滴春雨,共落在了大汉脸上,大汉一哆嗦,从腰间拿出一壶酒朝嘴里灌了起来,一阵咕咚声后,大汉依旧把酒壶别在腰里,寻了块石头摸去雨水,坐在上面,看着起伏的麦浪,喃喃说:“该来了吧。”

一阵风过,麦浪的一头正有一骑,朝大汉走来,马上那人头带笠帽,身穿蓑衣,大汉望到,立起身来,“哈哈,来了,哈。”说着从腰间取出酒壶，“咕咚”又喝了一口。

“哒、哒、哒”那骑行到大汉面前,翻身下马躬身下拜道：“拜见大师伯，师傅有要事，不能如约，望大师伯见谅。”“嗯”大汉退了一步，又坐在石块上，缓缓道：“你师傅出事了？”“不错”唇动手动，只见蓑衣人腰间白光一闪，话完时手中已多出了一柄寒光闪闪的亮剑，直指大汉心窝，大汉一惊，眼看剑将刺穿自己的心脏，闪无可闪，挡无可挡。也是他临危不乱，抛出手中酒壶，直向蓑衣人面部。大汉心道：“这一剑即便刺中，他自己也不免被这酒壶伤及面门，岂不回剑自卫。”不料蓑衣人一跃，大吼一声，长剑挥处一道红光闪过。“啪”酒壶也落在蓑衣人右肩，蓑衣人倒飞数尺，蹲坐在地上，口中已喷出数股鲜血。那大汉缓缓一晃，扶住石块，道：“你，你是谁？冒充我师弟门下。姓范的与你有何深仇，要你如此拼命。”蓑衣人并不答话，扶住剑立了起来转身就走。

突然，一道白光闪过，大汉大叫一声，道：“你，卑鄙。”蓑衣人回头看时，大汉胸口已多了两把匕首，刀刃全没入了。“冰封”，大汉最后吐出这两个字，直愣愣再也不动了。

蓑衣人走回去将两把匕首拔出来，从怀中取出三粒丹药放入大汉口中，长揖一下，转身骑上马走了。这“冰封”乃是“三春会”独门毒药,服下之后就如冻住了一般,坚硬无比。而体内却如火烧，巨痛难忍。若三日内服了解药虽说巨痛，七七四十九天后尚可溶冻化火,且可治愈内伤,倘三日内服不得解药,四十九天后,五脏六腑皆被烧烂,巨痛难忍而死。适才蓑衣人给大汉所服即解药。“冰封”原是“范农会”试探人才所用，凡是要入“范农会”者都得先忍过四十九天“冰封”之苦，若能说自己不悔，才可招入“范农会”。所以“范农会”的人人身上都有“冰封”和解药。

丝丝的细雨，麦浪如潮，蓑衣人一骑正行在麦间，骏马飞过，留下一道道月牙儿。行了数里，前面闪出一条大路，路两边各竖一合抱粗的大石柱，石柱上横跨一大石匾，上书大隶书“范农会”，左边石柱上书“侠会范农，共伐天下不平事”，右边书“义举五岳，全保家国忠良人”。蓑衣人纵马驰入路中央，行过匾额，朝石柱冷笑一声，从怀中取出两瓶药，抛上匾额，扭过头，策马飞离了“三春会”。路两旁绿麦幽幽，遥远的尽头灰绿连成一体。细雨依旧，泥湿湿的大路直锸入灰蒙蒙的云际，四周一片空旷。行了一程，雨渐渐停了，蓑衣人也慢了下来。

2022-11-08

哈希表中的算法

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。数组就是一种哈希表。

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

哈希函数

将值映射为数组上的索引的方法。最常用的哈希函数即与数组长度取模。

哈希碰撞

哈希函数将不同的值映射为了相同的索引。

哈希碰撞常用解决方法有拉链法、线性探测法。

Java 中常见哈希结构

HashMap ？7以前，8优化
TreeMap
LinkedHashMap
ConcurrentHashMap ？ 7以前，8优化

2022-11-08

LC题解-环形链表Ⅱ题解笔记

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

题解

快慢指针，快指针一次移动2个，满慢指针一次移动1个，如果不是循环链表，则快指针的next会等于null。

当快指针和慢指针相遇后，慢指针指向头部，快指针在相遇处，快慢指针同时每次移动1个，相遇的节点即为环形节点的入口。

推理

开头至入口的节点数=x，入口到相遇的节点数=y，相遇到入口的节点数=z

（x + y）* 2 = x + y + n * (y + z)

x + y = n * ( y + z)

x = (n - 1)(y + z) + z

根据等式，一个指针从相遇节点快出发，一个指针从头结点出发，在相遇节点出发的指针，一定通过循环(n - 1)圈以及z个节点的情况下，再次与头结点相遇。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;

        while(fast != null && fast.next != null) {
            if(fast == slow) {
                // 第一次相遇
                slow = head;
                while(slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            } else {
                slow = slow.next;
                fast = fast.next.next;
            }
        }

        return null;
    }
}