Java数据结构和算法(代码版)-4

排序算法

package com.lzlg.study.algorithm.new2023.sort;

import java.util.Arrays;

/
 * 冒泡排序
 *
 * @author lzlg
 * 2023/8/4 12:26
 */
public class BubbleSort {
    /
     * 冒泡排序,每轮把最大或最小的放置在合适的位置
     *
     * @param array 数组
     */
    public static void bubbleSort(int[] array) {
        int n = array.length - 1;
        for (int i = 0; i < array.length - 1; i++) {
            int last = 0; // 记录最后交换过的下标
            // 下次循环就从第一个位置到最后交换过的下标
            for (int j = 0; j < n; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    last = j;
                }
            }
            System.out.println("第" + (i + 1) + "轮冒泡:" + Arrays.toString(array));
            n = last;
            // 如果最近交换位置为0,则已经有序,跳出循环
            if (n == 0) {
                break;
            }
        }
    }

    /
     * 进行交换
     *
     * @param array 数组
     * @param i     索引i
     * @param j     索引j
     */
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = {6, 4, 5, 3, 2, 1};
        System.out.println(Arrays.toString(array));
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

package com.lzlg.study.algorithm.new2023.sort; import com.lzlg.study.algorithm.new2023.dynamicarray.DynamicArray; import java.util.Arrays; / * 桶排序 * * @author lzlg * 2023/8/6 11:58 */ public class BucketSort { / * 桶排序,数据都是2位的正整数 * 创建一个有10个桶的数组 * 遍历原数组,取数组元素的高位为下标放入对应下标的桶中 * 然后依次从桶中取出元素 * * @param array 数组 */ public static void bucketSort(int[] array) { // 创建桶数组 DynamicArray[] buckets = new DynamicArray[10]; // 初始化桶 for (int i = 0; i < buckets.length; i++) { buckets[i] = new DynamicArray(); } // 遍历原数组,将元素放入桶中 for (int element : array) { // 下标是高位 buckets[element / 10].addLast(element); } int k = 0; // 然后从桶中取出元素,依次放入原数组中 for (DynamicArray bucket : buckets) { int[] arr = bucket.array(); if (arr.length > 1) { Arrays.sort(arr); } for (int i : arr) { array[k++] = i; } } } / * 桶排序,让每个桶中的数据均匀 * 求原数组中的最大max和最小min,根据max-min+1创建桶数组 * * @param array 数组 */ public static void bucketSortMean(int[] array) { // 找到数组中的最大和最小 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; } } // 创建桶数组 DynamicArray[] buckets = new DynamicArray[max - min + 1]; // 初始化桶 for (int i = 0; i < buckets.length; i++) { buckets[i] = new DynamicArray(); } // 遍历原数组,将元素放入桶中 for (int element : array) { // 下标是桶元素-最小min buckets[element - min].addLast(element); } int k = 0; // 然后从桶中取出元素,依次放入原数组中 for (DynamicArray bucket : buckets) { int[] arr = bucket.array(); if (arr.length > 1) { Arrays.sort(arr); } for (int i : arr) { array[k++] = i; } } } / * 桶排序,让桶中元素的数量不超过指定的范围 * * @param array 数组 * @param range 桶中最大元素的数量 */ public static void bucketSortRange(int[] array, int range) { // 找到数组中的最大和最小 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; } } // 创建桶数组,此时桶长度为(max - min)/range + 1 DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1]; // 初始化桶 for (int i = 0; i < buckets.length; i++) { buckets[i] = new DynamicArray(); } // 遍历原数组,将元素放入桶中 for (int element : array) { // 下标是(桶元素-最小min)除以range buckets[(element - min) / range].addLast(element); } int k = 0; // 然后从桶中取出元素,依次放入原数组中 for (DynamicArray bucket : buckets) { int[] arr = bucket.array(); System.out.println(Arrays.toString(arr)); if (arr.length > 1) { Arrays.sort(arr); } for (int i : arr) { array[k++] = i; } } } public static void main(String[] args) { int[] array = {20, 31, 12, 15, 24, 81, 90, 11, 45, 66}; System.out.println(Arrays.toString(array)); bucketSort(array); System.out.println(Arrays.toString(array)); System.out.println("====================="); array = new int[]{9, 5, 3, 1, 4, 6, 8, 2, 0, 7}; System.out.println(Arrays.toString(array)); bucketSortMean(array); System.out.println(Arrays.toString(array)); System.out.println("====================="); array = new int[]{9, 5, 3, 1, 4, 6, 8, 2, 0, 7}; System.out.println(Arrays.toString(array)); bucketSortRange(array, 3); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 计数排序 * * @author lzlg * 2023/8/6 11:03 */ public class CountingSort { / * 计数排序,适用于数组中的元素都是正整数和0,且最大元素不能超过int的最大值 * 步骤如下: * 1.找到数组中最大元素max * 2.创建计数数组,长度是max+1 * 3.遍历原数组,以数组的元素作为下标,把元素出现的次数作为计数数组的值放入计数数组中 * 4.遍历计数数组,将数组元素(原数组元素出现次数)>0的依次取出放入原数组中 * * @param array 数组 */ public static void countSortPositive(int[] array) { // 找到数组中元素最大的 int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } // 创建新数组,长度是max+1 int[] count = new int[max + 1]; // 遍历原数组,把元素出现的次数放入新数组中 for (int v : array) { count[v]++; } // 原数组下标 int k = 0; // 从计数数组中取出元素 for (int i = 0; i < count.length; i++) { // i表示原数组的元素,count[i]表示元素出现的次数 while (count[i] > 0) { array[k] = i; k++; count[i]--; } } } / * 适用于整数的计数排序 * 步骤如下: * 1.遍历原数组,找到最大值max和最小值min * 2.创建计数数组,数组长度为max-min+1; * 3.遍历原数组,将数组的元素e减去最小值min为下标,出现次数为元素放入计数数组中 * 4.遍历计数数组,把出现次数大于0的下标加上最小值min依次(原数组元素)放入原数组中 * * @param array 数组 */ public static void countSortInteger(int[] array) { // 遍历原数组,找到最大和最小 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; } } // 创建计数数组,数组长度为max-min+1 int[] count = new int[max - min + 1]; // 遍历原数组,将出现次数映射到计数数组中 for (int v : array) { count[v - min]++; } int k = 0; // 从计数数组中取回元素 for (int i = 0; i < count.length; i++) { // count[i]是元素出现的次数 while (count[i] > 0) { // i+min才是原数组中的元素 array[k++] = i + min; count[i]--; } } } public static void main(String[] args) { int[] array = {8, 6, 4, 5, 3, 2, 1, 7, 0}; System.out.println(Arrays.toString(array)); countSortPositive(array); System.out.println(Arrays.toString(array)); System.out.println("====================="); array = new int[]{-1, 6, 4, 5, -3, 2, 1, 7, 0}; System.out.println(Arrays.toString(array)); countSortInteger(array); System.out.println(Arrays.toString(array)); System.out.println("====================="); array = new int[]{-1, -6, -4, -5, -3, -2, -1, -7}; System.out.println(Arrays.toString(array)); countSortInteger(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 堆排序 * * @author lzlg * 2023/8/5 9:59 */ public class HeapSort { / * 堆排序 * * @param array 数组 */ public static void heapSort(int[] array) { // 建堆 buildHeap(array, array.length); // 循环,依次把最大的交换到当前数组的最后 for (int i = array.length - 1; i > 0; i--) { // 建堆后,数组第一个元素是最大的,需要交换到最后 swap(array, 0, i); // 调整堆,以符合堆的特性 loopDown(array, 0, i); } } / * 建堆 * * @param array 数组 * @param size 边界 */ private static void buildHeap(int[] array, int size) { // 只调整父节点,倒数第一个父节点的下标是size/2-1 for (int i = size / 2 - 1; i >= 0; i--) { loopDown(array, i, size); } } / * 下潜 * * @param array 数组 * @param parent 父节点下标 * @param size 边界 */ private static void down(int[] array, int parent, int size) { // 左孩子下标 int left = parent * 2 + 1; // 右孩子下标 int right = left + 1; // 初始最大为父节点下标 int max = parent; // 找到最大的 if (left < size && array[left] > array[max]) { max = left; } if (right < size && array[right] > array[max]) { max = right; } // 如果不是父节点最大,则进行交换,并再次下潜 if (max != parent) { swap(array, max, parent); down(array, max, size); } } / * 循环下潜 * * @param array 数组 * @param parent 父节点下标 * @param size 边界 */ private static void loopDown(int[] array, int parent, int size) { while (true) { // 左孩子下标 int left = parent * 2 + 1; // 右孩子下标 int right = left + 1; // 初始最大为父节点下标 int max = parent; // 找到最大的 if (left < size && array[left] > array[max]) { max = left; } if (right < size && array[right] > array[max]) { max = right; } // 如果父节点已经是最大了,则无需再次循环 if (max == parent) { break; } // 如果不是父节点最大,则进行交换,并再次下潜 swap(array, max, parent); // 将最大的下标赋值给parent,再次循环 parent = max; } } / * 进行交换 * * @param array 数组 * @param i 索引i * @param j 索引j */ private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { int[] array = {6, 4, 5, 3, 2, 1}; System.out.println(Arrays.toString(array)); heapSort(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 插入排序 * * @author lzlg * 2023/8/5 10:17 */ public class InsertionSort { / * 插入排序 * * @param array 数组 */ public static void insertionSort(int[] array) { // 默认数组的第一个元素是有序的 for (int i = 1; i < array.length; i++) { // 保留当前待插入的元素,防止被覆盖 int t = array[i]; // 有序数组的末尾下标 int j = i - 1; // 从后往前依次比较有序数组里的元素 // 如果比当前元素(下标i)的大,则向后移动有序数组的元素 while (j >= 0 && array[j] > t) { array[j + 1] = array[j]; j--; } // 判断有没有移动 if (j != i - 1) { // 找到了插入位置 array[j + 1] = t; } } } public static void main(String[] args) { int[] array = {6, 4, 5, 3, 2, 1}; System.out.println(Arrays.toString(array)); insertionSort(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 归并排序+插入排序 * 归并排序在数据量大时候的性能较好 * 而插入排序在数据量小的时候性能较好 * * @author lzlg * 2023/8/5 11:01 */ public class MergeInsertionSort { / * 归并排序 * * @param array 数组 */ public static void mergeSort(int[] array) { int[] newArray = new int[array.length]; split(array, 0, array.length - 1, newArray); } / * 切分数组的方法,递归是自顶向下的方法(切分是从大变小) * * @param a1 数组 * @param left 左边界(包含)下标 * @param right 右边界(包含)下标 */ public static void split(int[] a1, int left, int right, int[] a2) { // System.out.println(Arrays.toString(Arrays.copyOfRange(a1, left, right + 1))); // 如果数组只有一个元素了,则不再切分 // if (left == right) { // // return; // } // 如果数据量已经切分到小于32时,使用插入排序 if (right - left <= 32) { insertionSort(a1, left, right); return; } int mid = (left + right) >>> 1; split(a1, left, mid, a2); split(a1, mid + 1, right, a2); // 切分后进行合并 merge(a1, left, mid, mid + 1, right, a2); // 合并后的结果在新数组中,因此需要copy回旧数组中 System.arraycopy(a2, left, a1, left, right - left + 1); } / * 插入排序 * * @param array 数组 * @param left 左边界(包含) * @param right 右边界(包含) */ public static void insertionSort(int[] array, int left, int right) { // 默认数组的第一个元素是有序的 for (int i = left; i <= right; i++) { // 保留当前待插入的元素,防止被覆盖 int t = array[i]; // 有序数组的末尾下标 int j = i - 1; // 从后往前依次比较有序数组里的元素 // 如果比当前元素(下标i)的大,则向后移动有序数组的元素 while (j >= left && array[j] > t) { array[j + 1] = array[j]; j--; } // 判断有没有移动 if (j != i - 1) { // 找到了插入位置 array[j + 1] = t; } } } / * 合并两个有序数组到新数组 * * @param a1 数组1 * @param i 数组1的左边界 * @param iEnd 数组1的右边界 * @param j 数组2的左边界 * @param jEnd 数组2的右边界 * @param a2 新数组 */ public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) { // 新数组下标,注意这里的合并的起始下标是i,而不是0 int k = i; // 进行合并,谁小谁先加入 while (i <= iEnd && j <= jEnd) { if (a1[i] < a1[j]) { a2[k] = a1[i]; i++; } else { a2[k] = a1[j]; j++; } k++; } // 防止数组1和数组2还有剩余元素没有加入 // 如果数组1超过右边界,则把数组2剩余的加入新数组中 if (i > iEnd) { System.arraycopy(a1, j, a2, k, jEnd - j + 1); } // 如果数组2超过右边界,则把数组1剩余的加入新数组中 if (j > jEnd) { System.arraycopy(a1, i, a2, k, iEnd - i + 1); } } / * 使用循环,自底向上的方法(切分是从小变大) * 如果数组为8,则第一次宽度为1,则切分的4组两个单数组的左右下标为: * [0,1] [2,3] [4,5] [6,7] * 第二次宽度为2,则切分为2组的两个单数组的左右下标为: * [0,3] [4,7] * 第三次宽度为4,则切分为1组的两个单数组的左右下标为: * [0,7] * * @param array 排序数组 */ public static void loopMergeSort(int[] array) { // 数组长度 int len = array.length; // 临时数组 int[] newArray = new int[len]; // 将数组通过一个逐渐加倍的宽度来划分 // 开始时,宽度为1,如果数组长度为8,则切分为4组两个单数组 // 每组的两个单数组两两合并 for (int width = 1; width < len; width = width * 2) { // 确定每组两个单数组的左边界 for (int left = 0; left < len; left += 2 * width) { // 确定右边界,是下个左边界-1,为不超出数组范围需取最小 int right = Integer.min(left + 2 * width - 1, len - 1); // 确定两个单数组的中间下标值,是left+宽度-1 int mid = left + width - 1; // 进行合并 merge(array, left, mid, mid + 1, right, newArray); } // 循环退出后,将新数组的元素全部copy到旧数组中 System.arraycopy(newArray, 0, array, 0, len); } } public static void main(String[] args) { int[] array = {6, 4, 5, 3, 2, 1, 7, 8}; System.out.println(Arrays.toString(array)); // Arrays.sort(args); mergeSort(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 归并排序 * 先将数组分成只有一个元素的数组(即有序) * 然后将有序数组进行合并 * * @author lzlg * 2023/8/5 11:01 */ public class MergeSort { / * 归并排序 * * @param array 数组 */ public static void mergeSort(int[] array) { int[] newArray = new int[array.length]; split(array, 0, array.length - 1, newArray); } / * 切分数组的方法,递归是自顶向下的方法(切分是从大变小) * * @param a1 数组 * @param left 左边界(包含)下标 * @param right 右边界(包含)下标 */ public static void split(int[] a1, int left, int right, int[] a2) { System.out.println(Arrays.toString(Arrays.copyOfRange(a1, left, right + 1))); // 如果数组只有一个元素了,则不再切分 if (left == right) { return; } int mid = (left + right) >>> 1; split(a1, left, mid, a2); split(a1, mid + 1, right, a2); // 切分后进行合并 merge(a1, left, mid, mid + 1, right, a2); // 合并后的结果在新数组中,因此需要copy回旧数组中 System.arraycopy(a2, left, a1, left, right - left + 1); } / * 合并两个有序数组到新数组 * * @param a1 数组1 * @param i 数组1的左边界 * @param iEnd 数组1的右边界 * @param j 数组2的左边界 * @param jEnd 数组2的右边界 * @param a2 新数组 */ public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) { // 新数组下标,注意这里的合并的起始下标是i,而不是0 int k = i; // 进行合并,谁小谁先加入 while (i <= iEnd && j <= jEnd) { if (a1[i] < a1[j]) { a2[k] = a1[i]; i++; } else { a2[k] = a1[j]; j++; } k++; } // 防止数组1和数组2还有剩余元素没有加入 // 如果数组1超过右边界,则把数组2剩余的加入新数组中 if (i > iEnd) { System.arraycopy(a1, j, a2, k, jEnd - j + 1); } // 如果数组2超过右边界,则把数组1剩余的加入新数组中 if (j > jEnd) { System.arraycopy(a1, i, a2, k, iEnd - i + 1); } } / * 使用循环,自底向上的方法(切分是从小变大) * 如果数组为8,则第一次宽度为1,则切分的4组两个单数组的左右下标为: * [0,1] [2,3] [4,5] [6,7] * 第二次宽度为2,则切分为2组的两个单数组的左右下标为: * [0,3] [4,7] * 第三次宽度为4,则切分为1组的两个单数组的左右下标为: * [0,7] * * @param array 排序数组 */ public static void loopMergeSort(int[] array) { // 数组长度 int len = array.length; // 临时数组 int[] newArray = new int[len]; // 将数组通过一个逐渐加倍的宽度来划分 // 开始时,宽度为1,如果数组长度为8,则切分为4组两个单数组 // 每组的两个单数组两两合并 for (int width = 1; width < len; width = width * 2) { // 确定每组两个单数组的左边界 for (int left = 0; left < len; left += 2 * width) { // 确定右边界,是下个左边界-1,为不超出数组范围需取最小 int right = Integer.min(left + 2 * width - 1, len - 1); // 确定两个单数组的中间下标值,是left+宽度-1 int mid = left + width - 1; // 进行合并 merge(array, left, mid, mid + 1, right, newArray); } // 循环退出后,将新数组的元素全部copy到旧数组中 System.arraycopy(newArray, 0, array, 0, len); } } public static void main(String[] args) { int[] array = {6, 4, 5, 3, 2, 1, 7, 8}; System.out.println(Arrays.toString(array)); Arrays.sort(args); loopMergeSort(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; import java.util.concurrent.ThreadLocalRandom; / * 快速排序 * 找到一个基准点 * 两个指针i,j * 指针i找到比基准点小的 * 指针j找到比基准点大的 * 然后进行交换 * 一轮结束后,就确定了基准点元素所在的下标 * * @author lzlg * 2023/8/6 9:32 */ public class QuickSort { / * 单边快速排序(Lumotu分区) * 找到数组最右边的元素作为基准点 * 两个指针i和j从最左边(索引0)开始进行 * 指针i找到比基准点小的元素下标 * 指针j找到比基准点大的元素下标,然后和指针i交换(前提是i!=j) * 然后继续循环,直到j到达最右边界 * 退出循环后,指针i的下标就是基准点的位置,进行交换 * 然后将数组按照指针i下标分为两组,继续递归进行上述操作 * * @param array 数组 */ public static void singleQuickSort(int[] array) { singleQuickSort(array, 0, array.length - 1); } / * 单边快速排序(递归方法) * * @param array 数组 * @param left 左边界 * @param right 右边界 */ private static void singleQuickSort(int[] array, int left, int right) { // 递归结束条件 if (left >= right) { return; } // 找到下次排序的下标边界 int partition = singlePartition(array, left, right); // 左边数组快排 singleQuickSort(array, left, partition - 1); // 右边数组快排 singleQuickSort(array, partition + 1, right); } / * 进行快速排序分区操作 * * @param array 数组 * @param left 左边界 * @param right 右边界 * @return 下次快速排序的分区下标 */ private static int singlePartition(int[] array, int left, int right) { // 以右边界作为基准点 int pv = array[right]; // 指针i找到比基准点小的 int i = left; // 指针j找到比基准点大的 int j = left; while (i < right) { // 如果使用指针i找到比基准点小的元素,则进行交换 if (array[i] < pv) { if (i != j) { swap(array, i, j); } j++; } // 如果找到比基准点大的元素,则指针j不移动,指向该元素 i++; } // 把基准点元素放入合适的位置,即指针j的下标 swap(array, j, right); return j; } / * 进行交换 * * @param array 数组 * @param i 索引i * @param j 索引j */ private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } / * 双边快速排序 * 选最左边的元素作为基准点 * 开始时指针i指向左边界,指针j指向右边界 * 开始循环,指针j从右向左找比基准点小的元素 * 指针i从左向右找比基准点大的元素 * 找到后进行交换,直到i和j相交 * 退出循环后,指针i的下标就是基准点插入的位置 * * @param array 数组 */ public static void doubleQuickSort(int[] array) { doubleQuickSort(array, 0, array.length - 1); } / * 双边快速排序(递归方法) * * @param array 数组 * @param left 左边界 * @param right 右边界 */ private static void doubleQuickSort(int[] array, int left, int right) { // 递归结束条件 if (left >= right) { return; } // 找到下次排序的下标边界 int partition = doublePartitionWhileRepeat(array, left, right); // 左边数组快排 doubleQuickSort(array, left, partition - 1); // 右边数组快排 doubleQuickSort(array, partition + 1, right); } / * 双边快速排序分区方法 * 问题1:为什么从指针j(从右向左找小的)开始,能先从指针i(从左向右找小的)开始吗? * 不能,因为如果一轮循环结束后,指针i和j就指向的不是基准点插入的位置了 * * 问题2:为何内层循环也要加上i<j的条件? * 因为有极端的情况会导致指针j的小于指针i,从而导致排序错误 * * 问题3:使用随机选择边界可以吗? * 可以,找到该随机位置下标,和左边界进行交换,下面代码和此方法代码一致 * * @param array 数组 * @param left 左边界 * @param right 右边界 * @return 下次快速排序的分区下标 */ private static int doublePartition(int[] array, int left, int right) { // 找到一个随机的元素下标,防止最坏情况的发生 int random = ThreadLocalRandom.current().nextInt(right - left + 1) + left; // 交换到左边界 swap(array, random, left); // 以最左边的为基准点 int pv = array[left]; // 指针i从左向右找到比基准点大的 int i = left; // 指针j从右向左找到比基准点小的 int j = right; while (i < j) { // 先循环指针j,找到比基准点小的 while (i < j && array[j] > pv) { j--; } // 再循环指针i,找到比基准点大的(注意条件是<=) while (i < j && array[i] <= pv) { i++; } // 找到后进行交换 swap(array, i, j); } // 退出循环后,指针i和j的下标就是基准点插入的位置 swap(array, i, left); return i; } / * 上述的双边快速排序如果遇到数组中有大量重复元素时,则性能下降到n的平方 * 此方法的版本是解决重复元素的快速排序方法 * * @param array 数组 * @param left 左边界 * @param right 右边界 * @return 下次快速排序的分区下标 */ private static int doublePartitionWhileRepeat(int[] array, int left, int right) { // 找到一个随机的元素下标,防止最坏情况的发生 int random = ThreadLocalRandom.current().nextInt(right - left + 1) + left; // 交换到左边界 swap(array, random, left); // 以左边为基准点 int pv = array[left]; // 指针i的起始下标是left+1,从左向右找比基准点大的 int i = left + 1; // 指针j,从右向左找比基准点小的 int j = right; // 指针i和指针j如果遇到和基准点重复的元素也会进行交换 // 循环条件改为i <= j,防止因为i<j造成的排序错误 // 如果循环条件是i<j,则如果分区的数组只有两个元素 // 且指针i(left+1)和指针j(right)指向同一个元素 // 但left下标的元素比指针i,j指向的元素小 // 则不会进入循环,直接进行了交换,造成left(元素小)在指针j(元素大)的后面,排序错误 while (i <= j) { // 指针i,从左向右找比基准点大的,大于等于的都会退出循环 while (i <= j && array[i] < pv) { i++; } // 指针j,从右向左找比基准点小的,小于等于的都会退出循环 while (i <= j && array[j] > pv) { j--; } // 需要添加if条件i<=j判断,理由和循环条件的一致 if (i <= j) { swap(array, i, j); // 注意这里要再次进行指针的移动,如果不移动会陷入死循环 i++; j--; } } // 退出循环后,指针j指向的是基准点插入的位置 swap(array, j, left); return j; } public static void main(String[] args) { int[] array = {8, 6, 4, 5, 3, 2, 1, 7}; System.out.println(Arrays.toString(array)); doubleQuickSort(array); System.out.println(Arrays.toString(array)); System.out.println("=========================="); array = new int[]{1, 2, 4, 5, 3, 2, 1, 5}; System.out.println(Arrays.toString(array)); doubleQuickSort(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort.quiz; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; / * 求数组排序后,相邻元素的最大间隔 * 要求时间复杂度O(n) * 数组中元素都是大于等于0的整数 * 如果数组中元素小于2个,返回0 * * @author lzlg * 2023/8/7 9:51 */ public class MaxGap { / * 使用桶排序,这样的实现方法会造成内存超出 * 因为是根据元素的最大和最小值创建桶的 * 如果数组是[1,100_000_000]则会创建很多不必要的桶 * 因此需要修改桶的RANGE范围值 * * @param array 数组 * @return 最大间隔 */ public static int maxGapByBucketSort(int[] array) { // 如果数组中元素小于2个,返回0 if (array.length < 2) { return 0; } // 找到数组中最大和最小 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { max = Integer.max(max, array[i]); min = Integer.min(min, array[i]); } // 根据范围创建桶数量 // 因为桶的数量的表达式是 (max - min) / RANGE + 1 // 期望的桶的个数是数组的长度,因此有 (max - min) / RANGE + 1 = array.length // 通过上式计算出 RANGE = (max - min) / (array.length - 1) final int RANGE = Integer.max(1, (max - min) / (array.length - 1)); // 桶的数量 final int BUCKET_COUNT = (max - min) / RANGE + 1; // 1.创建桶 List<Integer>[] buckets = new List[BUCKET_COUNT]; for (int i = 0; i < BUCKET_COUNT; i++) { buckets[i] = new ArrayList<>(); } // 2.进行排序 // 将元素放入桶中 for (int i : array) { buckets[(i - min) / RANGE].add(i); } int k = 0; // 从桶中依次取出元素 for (List<Integer> bucket : buckets) { // 排序桶 bucket.sort(Comparator.naturalOrder()); for (Integer i : bucket) { array[k++] = i; } } // 3.查找相邻元素的最大间隔 int gap = 0; for (int i = 1; i < array.length; i++) { gap = Integer.max(gap, array[i] - array[i - 1]); } return gap; } / * 使用基数排序 * * @param array 数组 * @return 最大间隔 */ public static int maxGapByRadixSort(int[] array) { // 如果数组中元素小于2个,返回0 if (array.length < 2) { return 0; } // 找到数组中最大元素 int max = array[0]; for (int i = 1; i < array.length; i++) { max = Integer.max(max, array[i]); } // 桶数量 final int BUCKET_COUNT = 10; // 1.创建桶 List<Integer>[] buckets = new List[BUCKET_COUNT]; for (int i = 0; i < BUCKET_COUNT; i++) { buckets[i] = new ArrayList<>(); } // 2.进行排序 int m = 1; // 当m小于数组中的最大时进行循环 while (m <= max) { // 一轮基数排序 for (int i : array) { // 第一次是取个位 buckets[i / m % 10].add(i); } int k = 0; // 放回原数组 for (List<Integer> bucket : buckets) { for (Integer i : bucket) { array[k++] = i; } bucket.clear(); } // 变换取值的位数 m = m * 10; } // 3.查找相邻元素的最大间隔 int gap = 0; for (int i = 1; i < array.length; i++) { gap = Integer.max(gap, array[i] - array[i - 1]); } return gap; } / * 使用桶排序的思想改进版本 * 不再排序桶中的元素,把查找最大间隔和取出桶元素结合起来 * * 1.转换为求相邻桶中后一个桶的最小元素与前一个桶的最大元素的间隙问题 * 2.为保证桶中元素的间隙不大于相邻桶的间隙 * 需要让桶的数量比元素数量多一个,即至少保留一个空桶 * 因为数据是根据RANGE分桶的,如果保留一个空桶,则同一个桶的元素间隙不可能超过RANGE * 因此只能在相邻桶之间找到最大间隙 * * 如上述原因,所以只需要保留每个桶中的最大和最小元素即可 * 数组元素的数据范围是[0,1_000_000_000] * * @param array 数组 * @return 最大间隔 */ public static int fastMaxGap(int[] array) { // 如果数组中元素小于2个,返回0 if (array.length < 2) { return 0; } // 找到数组中最大和最小 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { max = Integer.max(max, array[i]); min = Integer.min(min, array[i]); } // 根据范围创建桶数量 // 因为桶的数量的表达式是 (max - min) / RANGE + 1 // 期望的桶的个数是数组的长度+1(要多一个空桶保证同一个桶中元素间隙不超过RANGE) // 因此有 (max - min) / RANGE + 1 = array.length + 1 // 通过上式计算出 RANGE = (max - min) / array.length - 1 final int RANGE = Integer.max(1, (max - min) / array.length); // 桶的数量 final int BUCKET_COUNT = (max - min) / RANGE + 1; // 创建桶 Bucket[] buckets = new Bucket[BUCKET_COUNT]; // 遍历数组元素,放入桶中 for (int i : array) { int idx = (i - min) / RANGE; // 如果没有相应的桶,则先创建 if (buckets[idx] == null) { buckets[idx] = new Bucket(); } // 添加元素到桶中 buckets[idx].add(i); } // 开始遍历桶,查找出桶之间的最大间隙 int gap = 0; // 记录最新的桶中最大元素 int lastMax = buckets[0].max; for (int i = 1; i < BUCKET_COUNT; i++) { // 桶不为空才进行判断 if (buckets[i] != null) { // 找到桶之间的最大间隙,即后一个桶的最小元素与前一个桶的最大元素的间隙问题 gap = Integer.max(gap, buckets[i].min - lastMax); // 更新最新的桶中最大元素 lastMax = buckets[i].max; } } return gap; } / * 只保留最大和最小元素的桶 * 数组元素的数据范围是[0,1_000_000_000] */ static class Bucket { // 数据范围[0,1_000_000_000] // 因此最大初始为0 int max = 0; // 最小初始为1_000_000_000 int min = 1_000_000_000; / * 添加方法,保证加入桶中元素保持最大和最小 * * @param v 元素 */ void add(int v) { max = Integer.max(max, v); min = Integer.min(min, v); } @Override public String toString() { return "[" + max + ", " + min + ']'; } } public static void main(String[] args) { int[] array = {160275, 21, 12, 28, 343, 342, 22}; System.out.println(maxGapByBucketSort(array)); System.out.println(Arrays.toString(array)); System.out.println("======================"); System.out.println(maxGapByRadixSort(array)); System.out.println(Arrays.toString(array)); System.out.println("======================"); System.out.println(fastMaxGap(array)); } }

package com.lzlg.study.algorithm.new2023.sort.quiz; import java.util.Arrays; / * 按照数组中元素出现的频次排序,相同频次的降序 * 数组中元素值范围是[-100,100] * * @author lzlg * 2023/8/7 9:12 */ public class SortByFrequency { / * 按照数组中元素出现的频次排序,相同频次的降序 * 使用计数排序 * * @param array 数组 * @return 按要求排序好的数组 */ public static int[] sortByFrequency(int[] array) { // 计数数组的长度 final int MAX_COUNT = 201; // 数组中最小元素的值 final int MIN = -100; // 创建计数数组 int[] count = new int[MAX_COUNT]; // 统计数组中元素出现的次数 for (int i : array) { count[i - MIN]++; } // 使用Java流和比较器 // 先比较统计次数,如果统计次数相同,则比较元素值大小 return Arrays.stream(array).boxed() .sorted((i, j) -> { // 频次 int iCount = count[i - MIN]; int jCount = count[j - MIN]; // 比较频次 if (iCount > jCount) { return -1; } else if (jCount > iCount) { return 1; } else {// 如果频次相同,则比较值大小 return j - i; } }).mapToInt(Integer::intValue).toArray(); } public static void main(String[] args) { // 数组 int[] array = {2, 9, 1, 3, 5, 6, 5, 4, 1, 2, 8, 2}; System.out.println(Arrays.toString(array)); System.out.println(Arrays.toString(sortByFrequency(array))); } }

package com.lzlg.study.algorithm.new2023.sort.quiz; import java.util.Arrays; / * 把数组按照给定的序列数组排序 * 如果数组出现了没有在序列数组中出现的,则按照升序排列 * 数组中值的范围是[0,1000],数组长度是[0,1000] * * @author lzlg * 2023/8/7 9:11 */ public class SortBySequenceArray { / * 把数组按照给定的序列数组排序 * 如果数组出现了没有在序列数组中出现的,则按照升序排列 * 使用计数排序 * * @param array 数组,数组中值的范围是[0,1000],数组长度是[0,1000] * @param sequence 序列数组 */ public static void sortBySequence(int[] array, int[] sequence) { final int MAX_COUNT = 1001; // 创建长度为1001的计数数组,因为数组中值的范围是[0,1000] int[] count = new int[MAX_COUNT]; // 统计数组中的出现次数 for (int i : array) { count[i]++; } int k = 0; // 先按照序列数组取出元素,放入到原数组中 for (int i : sequence) { while (count[i] > 0) { array[k++] = i; count[i]--; } } // 然后其余元素按照升序放入到原数组中 for (int i = 0; i < MAX_COUNT; i++) { while (count[i] > 0) { array[k++] = i; count[i]--; } } } public static void main(String[] args) { // 数组 int[] array = {2, 9, 1, 3, 5, 6, 5, 4, 1, 2, 8}; // 序列数组 int[] sequence = {4, 5, 2, 3, 1}; System.out.println(Arrays.toString(array)); sortBySequence(array, sequence); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.ArrayList; import java.util.Arrays; import java.util.List; / * 基数排序 * 准备10个桶 * 给定只有数字的字符串 * 依次从低位到高位把数字作为下标放入相应的桶中 * 放入后,按顺序从桶中取出覆盖原数组 * 直到高位做完桶排序 * * @author lzlg * 2023/8/6 12:35 */ public class RadixSort { / * 基数排序 * * @param strings 字符串数组 * @param length 数组中字符的长度 */ public static void radixSort(String[] strings, int length) { // 创建桶 List<String>[] buckets = new List[10]; for (int i = 0; i < buckets.length; i++) { buckets[i] = new ArrayList<>(); } // 轮次取决于传入的长度 for (int i = length - 1; i >= 0; i--) { // 遍历字符串数组,依次放入桶中 for (String str : strings) { // 将字符映射到桶下标中 buckets[str.charAt(i) - '0'].add(str); } int k = 0; // 依次从桶中取出元素放回原数组中 for (List<String> bucket : buckets) { for (String s : bucket) { strings[k++] = s; } // 每次取出,需清空桶 bucket.clear(); } } } public static void main(String[] args) { String[] numbers = { "123", "234", "111", "890", "999", "666", "754", "233", "520", "521" }; System.out.println(Arrays.toString(numbers)); radixSort(numbers, 3); System.out.println(Arrays.toString(numbers)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 选择排序,用最后一个数组元素,依次和其余数组元素比较 * 如果比之大,则替换下标,一轮完毕后,就找到了最大元素的下标,然后放置到数组的最后 * 再一轮时,取数组倒数第二个元素,然后作上述的描述 * 直到只剩下一个数组元素,排序完毕 * * @author lzlg * 2023/8/4 12:26 */ public class SelectionSort { / * 选择排序 * * @param array 数组 */ public static void selectionSort(int[] array) { // 进行循环遍历 for (int i = array.length - 1; i > 0; i--) { // 一轮开始时默认最大为i int max = i; // 然后找到比max大的元素下标 for (int j = 0; j < i; j++) { if (array[j] > array[max]) { max = j; } } // 如果max不是原来的i了,则进行交换 if (max != i) { swap(array, i, max); } } } / * 进行交换 * * @param array 数组 * @param i 索引i * @param j 索引j */ private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { int[] array = {6, 4, 5, 3, 2, 1}; System.out.println(Arrays.toString(array)); selectionSort(array); System.out.println(Arrays.toString(array)); } }

package com.lzlg.study.algorithm.new2023.sort; import java.util.Arrays; / * 希尔排序 * 通过一个间隙gap将数组分组 * 这些分组的进行插入排序 * 然后缩小gap,再次进行插入排序 * 直到gap为1(为1时还需再次进行插入排序) * * @author lzlg * 2023/8/5 10:39 */ public class ShellSort { / * 希尔排序 * * @param array 数组 */ public static void shellSort(int[] array) { // 间隙是数组长度的一半,每次缩半 for (int gap = array.length >> 1; gap >= 1; gap = gap >> 1) { // 插入排序 for (int i = gap; i < array.length; i++) { // 保留待插入元素 int t = array[i]; // 有序数组的右下标 int j = i - gap; // 找到待插入的位置 while (j >= 0 && array[j] > t) { array[j + gap] = array[j]; // 注意这里要减去gap j -= gap; } if (j != i - gap) { array[j + gap] = t; } } } } public static void main(String[] args) { int[] array = {6, 4, 5, 3, 2, 1}; System.out.println(Arrays.toString(array)); shellSort(array); System.out.println(Arrays.toString(array)); } }

算法设计

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; / * 动态规划-卡特兰数相关问题 * 1.给定一个从1到n的升序数组,如果转换为二叉搜索树,则有多少种树? * 2.数字按1,2,3...n的顺序进栈,问出栈有多少种结果? * 3.给定圆括号的数量,问能组成合法的括号字符串有几种? * (配对的括号中,左括号必须在右括号的前面) * 上面的三个问题都可归结于卡特兰数问题 * 使用动态规划可解决此问题 * * @author lzlg * 2023/8/15 15:18 */ public class CatalanNumber { public static void main(String[] args) { System.out.println(catalan(5)); System.out.println(logCatalanResult(3)); } / * 记录括号问题中的组成结果列表 * 如果n=1即只有一个括号,则返回["()"] * 如果n=2即只有两个括号,则返回["()()", "(())"] * 如果n=3即只有三个括号,则返回["()()()", "()(())", "(())()", "(()())", "((()))"] * * @param n 数组中元素数量 * @return 组成结果列表 */ private static List<String> logCatalanResult(int n) { // 同样使用一个动态数组 List<String>[] dp = new List[n + 1]; // 初始化n为0和1的情况 dp[0] = new ArrayList<>(Collections.singletonList("")); dp[1] = new ArrayList<>(Collections.singletonList("()")); // 记录从2开始的情况 for (int j = 2; j <= n; j++) { // 初始化列表 dp[j] = new ArrayList<>(); // 子情况的数量是当前j值 for (int i = 0; i < j; i++) { // 组合子结果,k1是包含括号的情况,k2是外部括号的情况 for (String k1 : dp[i]) { for (String k2 : dp[j - 1 - i]) { dp[j].add("(" + k1 + ")" + k2); } } } } return dp[n]; } / * 计算卡特兰数的大小 * 可将这里问题拆分为两个子问题,比如 * 数组是[1, 2, 3]时,求二叉搜索树的种类? * 1.考虑到当1作为根节点时,2,3作为子节点的情况(转换为求[2,3]时卡特兰数) * 2.考虑到当2作为根节点时,左右两个子节点的情况(转换为求[1]或[3]时卡特兰数) * 3.考虑到当3作为根节点时,1,2作为子节点的情况(转换为求[1,2]时卡特兰数) * 容易得知当只有一个元素时,卡特兰数为1,当有两个元素时,卡特兰数为2 * 因此可得三个元素时的卡特兰数为: (情况1)2*1 + (情况2)1*1 + (情况3)1*2 = 5 * * 对于出栈结果问题,假如有1,2,3这3个元素 * 需考虑到1最先出战,1第二出栈,1最后出栈的三种子情况 * * 对于括号问题,如果有3对括号 * 需考虑情况1:第一对括号不包含括号,外面两个括号 * 情况2:第一对括号包含一个括号,外面一个括号 * 情况3:第一对括号包含两个括号,外面没有括号 * * @param n 数组中元素数量 * @return 卡特兰数 */ private static int catalan(int n) { // 使用一个一维动态数组记录前面计算过的卡特兰数 int[] dp = new int[n + 1]; // 初始时,当n=0,1时卡特兰数都为1 dp[0] = 1; dp[1] = 1; // 记录从2开始的卡特兰数 for (int j = 2; j <= n; j++) { // 子情况的数量是当前j值 for (int i = 0; i < j; i++) { // 将子情况的数据累加到记录卡特兰数的动态数组中 dp[j] += dp[i] * dp[j - 1 - i]; } System.out.println(Arrays.toString(dp)); } // 返回为n时的卡特兰数 return dp[n]; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 完全背包问题-动态规划 * 完全背包问题中物品是[可以重复放]的,因此和0-1背包问题有一处不同 * 递推公式:比较[前一行同列物品价值]和[当前物品价值+同行列为剩余重量的最大价值] * * @author lzlg * 2023/8/12 12:07 */ public class CompleteKnapsackProblem { / * 物品 */ static class Item { // 编号 int index; // 名称 String name; // 重量 int weight; // 总价值 int value; public Item(int index, String name, int weight, int value) { this.index = index; this.name = name; this.weight = weight; this.value = value; } / * 获取单位价值 * * @return 单位价值 */ int unitValue() { return value / weight; } @Override public String toString() { return "编号:" + index + "\t物品:" + name + "\t重量:" + weight + "\t总价值:" + value; } } public static void main(String[] args) { Item[] items = new Item[]{ new Item(1, "青铜", 2, 3), new Item(2, "白银", 3, 4), new Item(3, "黄金", 4, 7) }; System.out.println(select(items, 6)); System.out.println(selectByArray(items, 6)); } / * 完全背包问题-使用二维动态数组解决 * * @param items 物品数组 * @param total 总重量 * @return 最大价值 */ private static int select(Item[] items, int total) { // 初始化动态数组 int[][] dp = new int[items.length][total + 1]; // 把第一个物品的价值情况算出 Item firstItem = items[0]; for (int j = 0; j <= total; j++) { // 如果放的下,则是第一个物品的价值+剩余重量的该物品的价值 if (j >= firstItem.weight) { dp[0][j] = firstItem.value + dp[0][j - firstItem.weight]; } else {// 放不下,则直接为0 dp[0][j] = 0; } } printDp(dp); // 开始遍历其他物品 for (int i = 1; i < items.length; i++) { // 取出当前物品 Item item = items[i]; for (int j = 1; j <= total; j++) { // 如果放得下 if (j >= item.weight) { // 判断[前一个行同列的价值]和[当前物品价值+同行列为剩余重量的价值]的大小 // 取其最大值 dp[i][j] = Integer.max(dp[i - 1][j], item.value + dp[i][j - item.weight]); } else { // 如果放不下,则还是前一个行同列的价值 dp[i][j] = dp[i - 1][j]; } } printDp(dp); } return dp[items.length - 1][total]; } private static void printDp(int[][] dp) { int column = dp[0].length; for (int i = 0; i < column; i++) { System.out.print("\t" + i); } System.out.println("\n----------------------------------------------"); for (int i = 0; i < dp.length; i++) { System.out.print(i); for (int j = 0; j < dp[i].length; j++) { System.out.print("\t" + dp[i][j]); } System.out.println(); } System.out.println("================================================"); } / * 完全背包问题-使用一维动态数组解决 * * @param items 物品数组 * @param total 总重量 * @return 最大价值 */ private static int selectByArray(Item[] items, int total) { // 初始化动态数组 int[] dp = new int[total + 1]; // 把第一个物品的价值情况算出 // Item firstItem = items[0]; // for (int j = 0; j <= total; j++) { // // 如果放的下,则是第一个物品的价值+剩余重量的该物品的价值 // if (j >= firstItem.weight) { // dp[j] = firstItem.value + dp[j - firstItem.weight]; // } // } // System.out.println(Arrays.toString(dp)); // 可以合并上面的代码 // 开始遍历其他物品 for (int i = 0; i < items.length; i++) { // 取出当前物品 Item item = items[i]; for (int j = 0; j <= total; j++) { // 如果放得下,注意,此时不需要从后往前遍历了 // 因为是完全背包问题,因此需要找到同行的列为剩余重量的最大价值 // 从前往后遍历就会覆盖上一个物品的价值,但不会覆盖当前处理重量的价值 if (j >= item.weight) { // 判断[前一个行同列的价值]和[当前物品价值+同行列为剩余重量的价值]的大小 // 取其最大值 dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]); } } System.out.println(Arrays.toString(dp)); } return dp[total]; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; / * 让两个字符串变为相同需要的删除(可任意删除)操作步数 * 如sea和eat,第一步是sea删除s变为ea,第二步是eat删除t变为ea,总共两步 * 可转换为求最长公共子序列长度l的问题 * 如果有最长公共子序列长度l,则删除的操作步数是(字符串1的长度-长度l)+(字符串2的长度-长度l) * * @author lzlg * 2023/8/14 12:00 */ public class DeleteTwoStringToSubSequence { public static void main(String[] args) { String a = "sea"; String b = "eat"; System.out.println(steps(a, b)); System.out.println(steps("leetcode", "etco")); } / * 让两个字符串变为相同需要的删除(可任意删除)操作步数 * 可转换为求最长公共子序列长度l的问题 * * @param a 字符串a * @param b 字符串b * @return 操作步数 */ private static int steps(String a, String b) { int aLen = a.length(); int bLen = b.length(); // 使用char数组速度更快 char[] aChars = a.toCharArray(); char[] bChars = b.toCharArray(); // 使用二维动态数组,注意这里长度比字符串长度大1,这样可以避免数组下标判断操作 int[][] dp = new int[aLen + 1][bLen + 1]; // 从1开始遍历字符,并填充动态数组结果,i对应字符串a,j对应字符串b for (int i = 1; i <= aLen; i++) { // 可防止在循环j的时候频繁访问 char x = aChars[i - 1]; for (int j = 1; j <= bLen; j++) { char y = bChars[j - 1]; // 如果遇到相同的字符,则从[前一行前一列取最长长度]+1 if (x == y) { dp[i][j] = dp[i - 1][j - 1] + 1; } else {// 如果不同,则则取[前一行同列的最长长度]和[同行前一列的最长长度]中的最大值 dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]); } } } // 只是返回结果不同 return aLen + bLen - 2 * dp[aLen][bLen]; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; import java.util.List; / * 使用动态规划实现贝尔曼福特算法,求一个顶点到其他顶点最短距离的算法 * 初始时,出发顶点的距离值为0,其他顶点的距离值为整数的最大值 * 使用一个一维数组记录出发顶点到各个顶点的最短距离 * 使用如下的递推公式: dist(to) = min(dist(to), dist(from)+edge.weight) * * @author lzlg * 2023/8/12 9:34 */ public class DynamicBellmanFold { / * 边 */ static class Edge { // 起始顶点的下标 int from; // 终止顶点的下标 int to; // 边的权重 int weight; public Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } } public static void main(String[] args) { // 边的集合 List<Edge> edges = Arrays.asList( new Edge(6, 5, 9), new Edge(4, 5, 6), new Edge(1, 6, 14), new Edge(3, 6, 2), new Edge(3, 4, 11), new Edge(2, 4, 15), new Edge(1, 3, 9), new Edge(1, 2, 7) ); // 总共有6个顶点 final int VERTEX_COUNT = 6; // 创建一维数组,记录下标为1的顶点到其他顶点的最短距离 int[] dp = new int[VERTEX_COUNT + 1]; // 初始化dp数组,顶点1到顶点1的距离为0 dp[1] = 0; // 初始时,默认顶点1到其他顶点的距离是无穷(整数最大值) for (int i = 2; i < dp.length; i++) { dp[i] = Integer.MAX_VALUE; } print(dp); // 循环次数是顶点个数-1 for (int i = 0; i < VERTEX_COUNT - 1; i++) { // 便利边的集合,使用递推公式统计出最短距离 for (Edge edge : edges) { if (dp[edge.from] != Integer.MAX_VALUE) { dp[edge.to] = Integer.min(dp[edge.to], dp[edge.from] + edge.weight); } } print(dp); } } private static void print(int[] dp) { StringBuilder sb = new StringBuilder("["); for (int i = 0; i < dp.length; i++) { sb.append(dp[i] == Integer.MAX_VALUE ? "∞" : dp[i]); if (i != dp.length - 1) { sb.append(","); } } sb.append("]"); System.out.println(sb); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 使用动态规划算法解决零钱兑换问题 * 此时的动态数组记录的是当前总金额下和当前硬币值下的最小兑换数 * * @author lzlg * 2023/8/14 9:42 */ public class DynamicCoinChange { public static void main(String[] args) { int[] coins = new int[]{1, 2, 5}; int amount = 5; System.out.println(coinChange(coins, amount)); System.out.println("========="); System.out.println(coinChangeArray(coins, amount)); System.out.println("========="); coins = new int[]{2}; amount = 3; System.out.println(coinChange(coins, amount)); System.out.println("========="); } / * 使用一维动态数组解决零钱兑换问题 * * @param coins 硬币数组 * @param amount 兑换总金额 * @return 最小兑换数 */ private static int coinChangeArray(int[] coins, int amount) { // 注意先将硬币排序 Arrays.sort(coins); // 初始化一维动态数组 int[] dp = new int[amount + 1]; // 将数组初始化,填充所有值为amount+1 Arrays.fill(dp, amount + 1); // 第一个元素还是保持为0 dp[0] = 0; // 把第一个硬币的情况写入动态数组中 // for (int j = 1; j <= amount; j++) { // // 如果当前金额能兑换为硬币,则记录最小硬币数 // if (j >= coins[0]) { // dp[j] = dp[j - coins[0]] + 1; // } else {// 如果不能,则记录为总金额值+1 // // 这里使用一个[总金额值+1],为防止硬币不能兑换该金额的情况 // dp[j] = amount + 1; // } // } System.out.println(Arrays.toString(dp)); // 开始遍历其他的硬币 for (int i = 0; i < coins.length; i++) { // 从金额等于当前硬币面值开始循环 for (int j = coins[i]; j <= amount; j++) { // 在[前一行同列的最小硬币数]和[同行剩余金额列的最小硬币数+1]中选择最小的 dp[j] = Integer.min(dp[j], dp[j - coins[i]] + 1); } System.out.println(Arrays.toString(dp)); } // 在二维数组的最后一个元素记录着结果 int count = dp[amount]; // 需要判断最终硬币数是否小于总金额,如果小于则返回该最小硬币数 // 如果大于等于,则返回-1表示不能兑换 return count < amount ? count : -1; } / * 使用二维动态数组解决零钱兑换问题 * * @param coins 硬币数组 * @param amount 兑换总金额 * @return 最小兑换数 */ private static int coinChange(int[] coins, int amount) { // 注意先将硬币排序 Arrays.sort(coins); // 初始化二维动态数组 int[][] dp = new int[coins.length][amount + 1]; // 把第一个硬币的情况写入动态数组中 for (int j = 1; j <= amount; j++) { // 如果当前金额能兑换为硬币,则记录最小硬币数 if (j >= coins[0]) { dp[0][j] = dp[0][j - coins[0]] + 1; } else {// 如果不能,则记录为总金额值+1 // 这里使用一个[总金额值+1],为防止硬币不能兑换该金额的情况 dp[0][j] = amount + 1; } } printDp(dp); // 开始遍历其他的硬币 for (int i = 1; i < coins.length; i++) { for (int j = 1; j <= amount; j++) { // 如果当前金额大于等于当前硬币面额,则记录最小硬币数 if (j >= coins[i]) { // 在[前一行同列的最小硬币数]和[同行剩余金额列的最小硬币数+1]中选择最小的 dp[i][j] = Integer.min(dp[i - 1][j], dp[i][j - coins[i]] + 1); } else { // 如果小于,则延续前一行同列的最小硬币数 dp[i][j] = dp[i - 1][j]; } } printDp(dp); } // 在二维数组的最后一个元素记录着结果 int count = dp[coins.length - 1][amount]; // 需要判断最终硬币数是否小于总金额,如果小于则返回该最小硬币数 // 如果大于等于,则返回-1表示不能兑换 return count < amount ? count : -1; } private static void printDp(int[][] dp) { for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } System.out.println("======================="); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 动态规划算法-零钱兑换方式有几种? * 递推公式和求最小硬币数的不一样了 * 初始化第一个硬币时的兑换数都为1,因为不能兑换也是一种兑换方式 * 然后遍历其他硬币 * 如果当前金额大于等于当前硬币面额,则 * 当前兑换方式数量=前一行同列的兑换方式数量+同行剩余金额列的兑换方式数量 * 如果小于,则继承前一行同列的兑换方式数量 * * @author lzlg * 2023/8/14 10:14 */ public class DynamicCoinChangeWays { public static void main(String[] args) { int[] coins = new int[]{1, 2, 5}; int amount = 5; System.out.println(coinChangeWays(coins, amount)); System.out.println("========="); System.out.println(coinChangeWaysArray(coins, amount)); System.out.println("========="); } / * 使用一维动态数组解决零钱兑换问题中的兑换方式数量 * * @param coins 硬币数组 * @param amount 总金额 * @return 最大兑换方式数量 */ private static int coinChangeWaysArray(int[] coins, int amount) { // 需要对硬币的面额排序为升序 Arrays.sort(coins); // 使用二维动态数组记录兑换方式数量 int[] dp = new int[amount + 1]; // 当金额为0是,兑换方式为1 dp[0] = 1; // 初始化第一个硬币的情况 for (int j = 1; j <= amount; j++) { if (j >= coins[0]) { dp[j] = dp[j - coins[0]]; } } System.out.println(Arrays.toString(dp)); // 开始处理其他硬币的情况 for (int i = 1; i < coins.length; i++) { for (int j = 1; j <= amount; j++) { // 如果金额大于等于当前硬币面额,则计算兑换方式数量 if (j >= coins[i]) { // 当前硬币兑换方式数量为[前一行同列的兑换方式数量]+[同一行剩余面额为列的兑换方式数量] dp[j] = dp[j] + dp[j - coins[i]]; } } System.out.println(Arrays.toString(dp)); } return dp[amount]; } / * 使用二维动态数组解决零钱兑换问题中的兑换方式数量 * * @param coins 硬币数组 * @param amount 总金额 * @return 最大兑换方式数量 */ private static int coinChangeWays(int[] coins, int amount) { // 需要对硬币的面额排序为升序 Arrays.sort(coins); // 使用二维动态数组记录兑换方式数量 int[][] dp = new int[coins.length][amount + 1]; // 当金额为0是,兑换方式都为1 for (int i = 0; i < coins.length; i++) { dp[i][0] = 1; } // 初始化第一个硬币的情况 for (int j = 1; j <= amount; j++) { if (j >= coins[0]) { dp[0][j] = dp[0][j - coins[0]]; } } printDp(dp); // 开始处理其他硬币的情况 for (int i = 1; i < coins.length; i++) { for (int j = 1; j <= amount; j++) { // 如果金额大于等于当前硬币面额,则计算兑换方式数量 if (j >= coins[i]) { // 当前硬币兑换方式数量为[前一行同列的兑换方式数量]+[同一行剩余面额为列的兑换方式数量] dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]; } else {// 如果小于,则继承前一行同列的兑换方式数量 dp[i][j] = dp[i - 1][j]; } } printDp(dp); } return dp[coins.length - 1][amount]; } private static void printDp(int[][] dp) { for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } System.out.println("======================="); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 动态规划-钢条切割问题,求解钢条切割的最大价值 * * @author lzlg * 2023/8/14 10:46 */ public class DynamicCutSteel { public static void main(String[] args) { int[] values = new int[]{0, 1, 5, 8, 9}; int n = 4; System.out.println(cutSteelMaxValue(values, n)); System.out.println(""); System.out.println(cutSteelMaxValueArray(values, n)); } / * 动态规划-钢条切割问题(使用一维动态数组) * * @param values 价值数组,下标是钢条长度,数组中的值是钢条长度对应的价值 * @param n 当前钢条长度 * @return 最大价值 */ private static int cutSteelMaxValueArray(int[] values, int n) { // 使用一维动态数组记录最大价值 int[] dp = new int[n + 1]; // 开始遍历,因为values数组中存储了钢条长度为0的价值,因此可以不初始钢条长度为0的情况 for (int i = 1; i < values.length; i++) { // 注意此时i是当前钢条长度,j是钢条总长度 for (int j = 1; j <= n; j++) { // 如果钢条总长度大于等于当前钢条长度,则可以切割 if (j >= i) { // 从[前一行同列的最大价值]和[当前长度价值+同行剩余长度为列的最大价值]中取最大值 dp[j] = Integer.max(dp[j], values[i] + dp[j - i]); } } System.out.println(Arrays.toString(dp)); } // 返回最后结果 return dp[n]; } / * 动态规划-钢条切割问题(使用二维动态数组) * 如果当前钢条长度能切割成当前长度(大于等于) * 则从[前一行同列的最大价值]和[当前长度价值+同行剩余长度为列的最大价值]中取最大值 * 如果不能,则继承[前一行同列的最大价值] * * @param values 价值数组,下标是钢条长度,数组中的值是钢条长度对应的价值 * @param n 当前钢条长度 * @return 最大价值 */ private static int cutSteelMaxValue(int[] values, int n) { // 使用二维动态数组记录最大价值 int[][] dp = new int[values.length][n + 1]; // 开始遍历,因为values数组中存储了钢条长度为0的价值,因此可以不初始钢条长度为0的情况 for (int i = 1; i < values.length; i++) { // 注意此时i是当前钢条长度,j是钢条总长度 for (int j = 1; j <= n; j++) { // 如果钢条总长度大于等于当前钢条长度,则可以切割 if (j >= i) { // 从[前一行同列的最大价值]和[当前长度价值+同行剩余长度为列的最大价值]中取最大值 dp[i][j] = Integer.max(dp[i - 1][j], values[i] + dp[i][j - i]); } else {// 否则不可以切割 // 从前一行同列的继承最大价值 dp[i][j] = dp[i - 1][j]; } } printDp(dp); } // 返回最后结果 return dp[values.length - 1][n]; } private static void printDp(int[][] dp) { for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } System.out.println("======================="); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 0-1背包问题-使用动态规划 * 如下所示,要拿走不超过10克的物品 * 每次[不拿或者全拿](注意和分数背包问题的不同) * 问能拿的最高价值是多少? * 编号重量价值 * 0 1 1_000_000 钻戒一枚 * 1 4 1600 黄金一块 * 2 8 2400 红宝石戒指一枚 * 3 5 30 白银一块 * 创建以物品为行,重量为0到最大的列的二维数组(可优化为一维数组) * 开始遍历物品,如果装不下,则直接取前一行的最大价值 * 如果装的下,则应取[前一行的价值],[前一行中列为剩余重量的价值+当前物品价值]中的最大值 * * @author lzlg * 2023/8/12 11:22 */ public class DynamicKnapsack { / * 物品 */ static class Item { // 编号 int index; // 名称 String name; // 重量 int weight; // 总价值 int value; public Item(int index, String name, int weight, int value) { this.index = index; this.name = name; this.weight = weight; this.value = value; } / * 获取单位价值 * * @return 单位价值 */ int unitValue() { return value / weight; } @Override public String toString() { return "编号:" + index + "\t物品:" + name + "\t重量:" + weight + "\t总价值:" + value; } } public static void main(String[] args) { Item[] items = new Item[]{ new Item(0, "黄金一块", 4, 1600), new Item(1, "红宝石戒指一枚", 8, 2400), new Item(2, "白银一块", 5, 30), new Item(3, "钻戒一枚", 1, 1_000_000), }; int maxValue = packSelectArray(items, 10); System.out.println(maxValue); } / * 0-1背包问题,使用二维的动态数组解决 * * @param items 物品数组 * @param total 总重量 * @return 最大价值 */ private static int packSelect(Item[] items, int total) { // 初始化动态数组 int[][] dp = new int[items.length][total + 1]; // 取出第一个物品 Item firstItem = items[0]; // 把只有第一个物品的情况初始化一下 for (int j = 0; j <= total; j++) { // 如果当前的重量装得下第一个物品,则最大价值是该物品的价值 if (j >= firstItem.weight) { dp[0][j] = firstItem.value; } else {// 如果装不下,则价值为0 dp[0][j] = 0; } } printDp(dp); // 开始遍历动态数组,逐渐根据递推公式得出结果 for (int i = 1; i < items.length; i++) { // 从物品数组中得到物品 Item item = items[i]; // 进行重量的遍历 for (int j = 1; j <= total; j++) { // 如果装得下 if (j >= item.weight) { // 比较[前一行同列的价值]和[当前物品价值+前一行列为剩余重量的最大价值] // 取其中较大的 dp[i][j] = Integer.max(dp[i - 1][j], item.value + dp[i - 1][j - item.weight]); } else {// 装不下,则是前一行同列的价值 dp[i][j] = dp[i - 1][j]; } } printDp(dp); } // 二维数组的最后一个值就是要返回的结果 return dp[items.length - 1][total]; } private static void printDp(int[][] dp) { int column = dp[0].length; for (int i = 0; i < column; i++) { System.out.print("\t" + i); } System.out.println("\n----------------------------------------------"); for (int i = 0; i < dp.length; i++) { System.out.print(i); for (int j = 0; j < dp[i].length; j++) { System.out.print("\t" + dp[i][j]); } System.out.println(); } System.out.println("================================================"); } / * 0-1背包问题,使用一维的动态数组解决 * * @param items 物品数组 * @param total 总重量 * @return 最大价值 */ private static int packSelectArray(Item[] items, int total) { // 初始化动态数组 int[] dp = new int[total + 1]; // 取出第一个物品 Item firstItem = items[0]; // 把只有第一个物品的情况初始化一下 for (int j = 0; j <= total; j++) { // 如果当前的重量装得下第一个物品,则最大价值是该物品的价值 if (j >= firstItem.weight) { dp[j] = firstItem.value; } else {// 如果装不下,则价值为0 dp[j] = 0; } } System.out.println(Arrays.toString(dp)); // 开始遍历动态数组,逐渐根据递推公式得出结果 for (int i = 1; i < items.length; i++) { // 从物品数组中得到物品 Item item = items[i]; // 进行重量的遍历,注意使用一维数组,这里是从后往前 // 因为一维数组存储的是前一行物品的价值数组 // 因此从后往前遍历,能不覆盖前一行物品的价值数据信息 for (int j = total; j > 0; j--) { // 如果装得下 if (j >= item.weight) { // 比较[前一行同列的价值]和[当前物品价值+前一行列为剩余重量的最大价值] // 取其中较大的 dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]); } // 装不下,则还是原来的价值 } System.out.println(Arrays.toString(dp)); } // 一维数组的最后一个值就是要返回的结果 return dp[total]; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; / * 动态规划-斐波那契数列 * 动态规划: Dynamic Programming * 分析问题找到递推公式,将当前问题分解成子问题,分阶段进行求解. * 求解过程中缓存子问题的解,避免重复计算. * * @author lzlg * 2023/8/10 11:45 */ public class Fibonacci { public static void main(String[] args) { System.out.println(fibonacciWithArray(7)); System.out.println("========="); System.out.println(fibonacci(7)); } / * 动态规划-使用一维数组实现斐波那契数列 * * @param n 数列的第n项 * @return 数列的第n项的值 */ public static int fibonacciWithArray(int n) { if (n == 0 || n == 1) { return n; } // 要缓存n+1个结果 int[] dp = new int[n + 1]; // 前两项的数列值已经确定 dp[0] = 0; dp[1] = 1; // 进行循环 for (int i = 2; i <= n; i++) { // 根据f(n) = f(n-1) + f(n-2)的递推公式,计算dp[i]的值 dp[i] = dp[i - 1] + dp[i - 2]; } // 最后下标n的值就是所求的解 return dp[n]; } / * 动态规划-使用两个变量记录前两个数列的值 * * @param n 数列的第n项 * @return 数列的第n项的值 */ public static int fibonacci(int n) { if (n == 0 || n == 1) { return n; } // a,b分别记录前两个数列的值 int a = 0; int b = 1; // 进行循环 for (int i = 2; i <= n; i++) { // 计算当前数列的值 int c = b + a; // 更新前两项的值 a = b; b = c; } return b; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; / * 动态规划-打家劫舍问题 * 如果你是一个小偷,如果偷了一个房间 * 再偷相邻的房间会触发警报,那么如何偷才能价值最大化? * 假如有5个房间,价值分别是2, 7, 9, 3, 1 * * @author lzlg * 2023/8/15 16:01 */ public class HouseRobber { public static void main(String[] args) { int[] houses = new int[]{2, 7, 9, 3, 1}; System.out.println(robber(houses)); } / * 动态规划-打家劫舍问题 * 递推公式为: dp[i] = max(dp[i-2] + houses[i], dp[i-1]) * 当前房间的最大价值从[相隔房间的价值+当前房间价值]和[前一个房间价值]中取最大 * * @param houses 房间数组,下标是房号,数组元素是价值 * @return 最大偷窃价值 */ private static int robber(int[] houses) { int len = houses.length; // 如果只有一个房间,则直接打劫 if (len == 1) { return houses[0]; } // 存放当前房间的最大价值的动态数组 int[] dp = new int[len]; // 初始化0号房和1号房的情况 dp[0] = houses[0]; dp[1] = Integer.max(houses[0], houses[1]); // 从2号房开始 for (int i = 2; i < len; i++) { dp[i] = Integer.max(dp[i - 2] + houses[i], dp[i - 1]); } return dp[len - 1]; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 动态规划-求int数组中最长递增子序列长度 * 如[1, 3, 6, 4, 9]的最长递增子序列有[1, 3, 6, 9], [1, 3, 4, 9] 最长长度为4 * * @author lzlg * 2023/8/14 12:21 */ public class MaxLenIncreaseSequence { public static void main(String[] args) { int[] nums = new int[]{1, 3, 6, 4, 9}; System.out.println(maxLenIncreaseSequence(nums)); nums = new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6}; System.out.println(maxLenIncreaseSequence(nums)); } / * 动态规划-求int数组中最长递增子序列长度 * 使用一个一维的动态数组记录此长度,该开始时数组中元素值都为1 * 开始从1遍历int数组,在内循环中从0开始 * 记录到当前数组元素值的最长递增子序列长度 * 如果当前元素的值小于等于内循环中的元素值,则不处理 * 如果大于,则此时最长递增子序列长度=max(当前元素的最长长度,内循环元素的最长长度+1) * * @param nums 数组 * @return 最长递增子序列长度 */ private static int maxLenIncreaseSequence(int[] nums) { // 初始化一维动态数组 int[] dp = new int[nums.length]; Arrays.fill(dp, 1); // 开始遍历数组中其他元素 for (int i = 1; i < nums.length; i++) { // 当前元素i和前面的i-1个元素进行比较 for (int j = 0; j < i; j++) { // 当前元素大于前一个元素时才处理 if (nums[i] > nums[j]) { // 最长递增子序列长度=max(当前元素的最长长度,内循环元素的最长长度+1) dp[i] = Integer.max(dp[i], dp[j] + 1); } } } // 返回动态数组中的最大值 return Arrays.stream(dp).max().getAsInt(); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 动态规划-最长公共子序列长度问题(字符不是连续的,但必须是按照长字符的顺序的) * abcd ae 的最长公共子序列长度是1 * abcd ac 的最长公共子序列长度是2 * * @author lzlg * 2023/8/14 11:22 */ public class MaxLenSubSequence { public static void main(String[] args) { String a = "abcxyz"; String b = "abxyz"; System.out.println(maxLenSubSequence(a, b)); } / * 动态规划-最长公共子序列长度问题(字符不是连续的,但必须是按照长字符的顺序的) * 使用一个动态二维数组来保存,开始遍历字符 * 如果遇到相同的字符,则从[前一行前一列取最长长度]+1 * 如果不同,则取[前一行同列的最长长度]和[同行前一列的最长长度]中的最大值 * * @param a 字符串a * @param b 字符串b * @return 最长公共子序列长度 */ private static int maxLenSubSequence(String a, String b) { int aLen = a.length(); int bLen = b.length(); // 使用二维动态数组,注意这里长度比字符串长度大1,这样可以避免数组下标判断操作 int[][] dp = new int[aLen + 1][bLen + 1]; // 从1开始遍历字符,并填充动态数组结果,i对应字符串a,j对应字符串b for (int i = 1; i <= aLen; i++) { for (int j = 1; j <= bLen; j++) { // 如果遇到相同的字符,则从[前一行前一列取最长长度]+1 if (a.charAt(i - 1) == b.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else {// 如果不同,则则取[前一行同列的最长长度]和[同行前一列的最长长度]中的最大值 dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]); } } } printDp(dp); return dp[aLen][bLen]; } private static void printDp(int[][] dp) { for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } System.out.println("---------------------"); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 动态规划-最长公共子串长度问题(字符是连续的) * abc ab 的最长公共子串长度是2 * abc ac 的最长公共子串长度是1 * * @author lzlg * 2023/8/14 11:22 */ public class MaxLenSubString { public static void main(String[] args) { String a = "itheima"; String b = "thema"; System.out.println(maxLenSubString(a, b)); } / * 动态规划-最长公共子串长度问题(字符是连续的) * 使用一个二维动态数组,开始遍历字符串a和字符串b的每个字符 * 如果遇到的字符相等,则当前最长长度=[前一行前一列中的最长长度]+1 * 如果不等,则直接为0 * * @param a 字符串a * @param b 字符串b * @return 最长公共子串长度 */ private static int maxLenSubString(String a, String b) { int aLen = a.length(); int bLen = b.length(); // 记录最长公共子串长度 int maxLen = 0; // 构建二维动态数组 int[][] dp = new int[aLen][bLen]; // 开始遍历字符,i对应字符串a,j对应字符串b for (int i = 0; i < aLen; i++) { for (int j = 0; j < bLen; j++) { // 如果遇到相等的字符,则当前最长长度=[前一行前一列中的最长长度]+1 if (a.charAt(i) == b.charAt(j)) { // 防止获取字符时数组越界 if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j - 1] + 1; } // 记录当前最长公共子串长度 maxLen = Integer.max(maxLen, dp[i][j]); } else {// 如果不等,则直接为0 dp[i][j] = 0; } } printDp(dp); } // 返回最长公共子串长度 return maxLen; } private static void printDp(int[][] dp) { for (int i = 0; i < dp.length; i++) { System.out.println(Arrays.toString(dp[i])); } System.out.println("---------------------"); } }

package com.lzlg.study.algorithm.new2023.design.dynamic; import java.util.Arrays; / * 动态规范-机器人路径问题 * 1个机器人只能向右或向下走 * 从起点(二维数组的第一个)到终点(二维数组的最后一个)有多少条路径? * 如果是只有一行或一列,则只有1条路径到达终点 * 其他情况,则第i行j列的路径数=第i-1行j列的路径数+第i行j-1列的路径数(递推公式) * * @author lzlg * 2023/8/12 10:06 */ public class RobotRunPath { public static void main(String[] args) { int paths = robotRunPaths(3, 7); System.out.println(paths); paths = robotRunPathsArray(3, 7); System.out.println(paths); System.out.println("========"); paths = robotRunPaths(4, 8); System.out.println(paths); paths = robotRunPathsArray(4, 8); System.out.println(paths); } / * 使用二维数组解决机器人路径问题 * * @param m 行数 * @param n 列数 * @return 路径数量 */ private static int robotRunPaths(int m, int n) { // 动态数组,记录路径数 int[][] dp = new int[m][n]; // 初始化动态数组,第i行0列都是1 for (int i = 0; i < m; i++) { dp[i][0] = 1; } // 初始化动态数组,第0行j列都是1 for (int j = 0; j < n; j++) { dp[0][j] = 1; } // 进行循环,根据递推公式求得路径数 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // 二维数组中的最后一个元素就是结果 return dp[m - 1][n - 1]; } / * 使用一维数组解决机器人路径问题 * * @param m 行数 * @param n 列数 * @return 路径数量 */ private static int robotRunPathsArray(int m, int n) { // 使用一个一维数组记录当前行的路径数 int[] dp = new int[n]; // 初始时,全为0,相当于第0行j列 Arrays.fill(dp, 1); // 开始循环,注意此时递推公式变为dp[j] = dp[j] + dp[j - 1]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; } }

package com.lzlg.study.algorithm.new2023.design.dynamic; / * 动态规划-旅行商问题 * 计算从某个城市出发到剩余城市后再回到出发城市的花费最少? * * @author lzlg * 2023/8/15 17:22 */ public class TravelMerchant { public static void main(String[] args) { // 使用邻接矩阵来表示某城市到另一城市的花费 // 下标是城市编号,元素值是该行下标对应的城市到该列下标对应的城市的花费 int[][] graph = new int[][]{ {0, 1, 2, 3}, {1, 0, 6, 4}, {2, 6, 0, 5}, {3, 4, 5, 0}, }; System.out.println(travelMerchant(graph)); } / * 旅行商问题-动态规划 * 可将问题简化为D(出发城市,剩余城市集合)的子问题 * 假如出发城市下标为0,则问题表述为 * D(0,1|2|3) => g[0][1] + D(1,2|3) 或 g[0][2] + D(2,1|3) 或 g[0][3] + D(3,1|2) * 即该问题等价于[求出发城市0到某城市1(或2或3)的花费]+[从城市1出发到某城市2(或3)的花费]中的最小花费 * 而子问题D(1,2|3)又可以根据上述规则进行拆分为子问题,依次类推,求出问题的解 * * @param graph 邻接矩阵 * @return 最少花费 */ private static int travelMerchant(int[][] graph) { // 使用二维动态数组记录,某城市到剩余其他城市的花费 // 因此行等于城市数m int m = graph.length; // 而列有以下取值[无,城市1,城市2,城市3,城市1|2,城市1|3,城市2|3,城市1|2|3]即2的(m-1)次幂个 // 这里使用3位的二进制数表示列值,000表示无,从后往前分别表示城市1|2|3是否在集合中 // 如101则表示城市3和城市1在集合中 int n = 1 << (m - 1); // 创建二维动态数组,记录D(出发城市,剩余城市集合)值 int[][] dp = new int[m][n]; // 填充第1列(无城市集合-此时是返回到出发城市)的花费值 for (int i = 0; i < m; i++) { dp[i][0] = graph[i][0]; } // 开始遍历填充值,j表示剩余城市集合 for (int j = 1; j < n; j++) { // i表示D(出发城市,剩余城市集合)中的出发城市 for (int i = 0; i < m; i++) { // 使用一个较大值进行初始化 dp[i][j] = Integer.MAX_VALUE >>> 1; // 排除集合j中包含城市i的情况 if (contains(j, i)) { continue; } // 再次遍历所有城市 for (int k = 0; k < m; k++) { // 需要判断该城市在集合j中 if (contains(j, k)) { // 根据算法描述,可得 // 从城市i到剩余城市j集合=[从城市i到城市k+从城市k到排除城市k的集合]中的最小花费 // 因为要从城市0(即i)到城市1(或2或3-即k)d的三条路线中要取最小花费 dp[i][j] = Integer.min(dp[i][j], graph[i][k] + dp[k][exclude(j, k)]); } } } } printDp(dp); // 返回的结果是从城市0到剩余城市然后返回城市0的最小花费 return dp[0][n - 1]; } private static void printDp(int[][] dp) { for (int i = 0; i < dp.length; i++) { StringBuilder sb = new StringBuilder("["); for (int j = 0; j < dp[i].length; j++) { if (dp[i][j] == (Integer.MAX_VALUE >>> 1)) { sb.append("∞"); } else { sb.append(dp[i][j]); } if (j != (dp[i].length - 1)) { sb.append(", "); } } sb.append("]"); System.out.println(sb); } } / * 判断城市city是否在集合中,该位运算还未搞懂 * * @param set 城市集合(二进制对应的十进制数) * @param city 城市city * @return 结果 */ static boolean contains(int set, int city) { return (set >> (city - 1) & 1) == 1; } / * 从集合中排除城市city,该位运算还未搞懂 * * @param set 城市集合(二进制对应的十进制数) * @param city 城市city * @return 排除后结果 */ static int exclude(int set, int city) { return set ^ (1 << (city - 1)); } }

package com.lzlg.study.algorithm.new2023.design.greedy; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; / * 贪心算法-活动选择问题 * 时间: 0 1 2 3 4 5 6 7 8 9 * 活动1: |-------) 选中 * 活动2: |-----------) * 活动3: |-----------) 选中 * 活动4: |-----------) * 活动5: |-----------) 选中 * 如何选择活动,让能进行的活动数量最多? * * @author lzlg * 2023/8/10 10:32 */ public class ActivitySelection { / * 活动类 */ static class Activity { // 活动标识 int index; // 活动开始时间 int start; // 活动结束时间 int end; public Activity(int index, int start, int end) { this.index = index; this.start = start; this.end = end; } / * 获取活动结束时间 * * @return 活动结束时间 */ public int end() { return end; } @Override public String toString() { return "Activity{" + index + "}"; } } public static void main(String[] args) { // 活动总数 Activity[] activities = new Activity[]{ new Activity(5, 5, 8), new Activity(2, 1, 4), new Activity(1, 0, 2), new Activity(4, 3, 6), new Activity(3, 2, 5), }; System.out.println("所有活动======================"); System.out.println(Arrays.toString(activities)); System.out.println("选中的活动======================"); selectActivity(activities); } / * 挑选活动,优先选择最先结束的活动 * 步骤如下: * 1.先根据活动的结束时间进行排序 * 2.排序后的第一个活动一定进行 * 3.开始遍历活动数组,找到活动开始时间>=前一个活动的结束时间的活动 * * @param activities 活动数组 */ private static void selectActivity(Activity[] activities) { // 选中的活动结果列表 List<Activity> result = new ArrayList<>(); // 根据活动结束时间进行排序(升序) Arrays.sort(activities, Comparator.comparingInt(Activity::end)); // 排序后的第一个活动一定进行 Activity prev = activities[0]; result.add(prev); // 遍历排序后的活动数组,从下标1开始 for (int i = 1; i < activities.length; i++) { // 当前活动 Activity current = activities[i]; // 如果当前活动的开始时间>=前一个活动的结束时间,则加入结果中 if (current.start >= prev.end) { result.add(current); // 并把前一个活动的指针指向当前活动,方便下次循环 prev = current; } } // 打印选择结果 for (Activity activity : result) { System.out.println(activity); } } }

package com.lzlg.study.algorithm.new2023.design.greedy; import java.util.Deque; import java.util.LinkedList; import java.util.concurrent.atomic.AtomicInteger; / * 贪心算法示例1-零钱兑换 * 有两个问题,一是有多少种兑换方式?二是最少兑换硬币数? * * @author lzlg * 2023/8/9 11:54 */ public class CoinChange { public static void main(String[] args) { // 硬币数组 int[] coins = new int[]{1, 2, 5}; // 兑换的总金额 int amount = 5; // System.out.println("兑换方式有: " + coinChangeMethodCount(coins, amount) + " 种."); System.out.println("=================="); // 如果硬币数组是升序的,则递归次数太多,如果是降序的则能大大优化 coins = new int[]{5, 2, 1}; coins = new int[]{3}; amount = 2; coins = new int[]{25, 10, 5, 1}; amount = 41; System.out.println("兑换方式有: " + coinChangeMethodCount(coins, amount) + " 种."); System.out.println("=================="); System.out.println("最少兑换硬币数是: " + coinChangeMin(coins, amount) + " 个."); } // 最少兑换硬币数,初始值为-1,表示没有找到解 static int min = -1; / * 零钱兑换-求解最少兑换硬币数 * * @param coins 硬币数组 * @param amount 兑换金额 * @return 最少兑换硬币数 */ public static int coinChangeMin(int[] coins, int amount) { // 使用栈记录兑换方式 Deque<Integer> stack = new LinkedList<>(); coinChangeMin(0, coins, amount, new AtomicInteger(-1), stack, true); return min; } / * 递归计算最少兑换硬币数 * * @param index 当前硬币下标 * @param coins 硬币数组 * @param remainder 剩余兑换金额 * @param count 记录兑换硬币次数 * @param first 排除第一次递归调用入栈的元素 */ private static void coinChangeMin(int index, int[] coins, int remainder, AtomicInteger count, Deque<Integer> stack, boolean first) { // 如果不是第一次调用,则记录当前兑换硬币 if (!first) { // 记录当前兑换硬币 stack.push(coins[index]); } // 增加兑换硬币数的值+1,记录此时的兑换硬币数量 count.incrementAndGet(); // 情况2:如果兑换金额等于0,则返回1,表示有解 if (remainder == 0) { System.out.println("有解: " + stack); // 如果有解,则更新min的值 min = min == -1 ? count.get() : Integer.min(min, count.get()); // 情况3:如果兑换金额大于0,则继续递归并累加 } else if (remainder > 0) { for (int i = index; i < coins.length; i++) { coinChangeMin(i, coins, remainder - coins[i], count, stack, false); } } // 减少兑换硬币数的值-1 // 递归过后,此时需要返回到上层递归步骤中,因此需要减少来时的硬币数 count.decrementAndGet(); // 如果循环结束,则需要从栈中弹出当前元素,以便记录其他的无解或有解的兑换情况 if (!stack.isEmpty()) stack.pop(); } / * 零钱兑换-求解有多少种兑换方式 * * @param coins 硬币数组 * @param amount 兑换金额 * @return 兑换方式数量 */ public static int coinChangeMethodCount(int[] coins, int amount) { // 使用栈记录兑换方式 Deque<Integer> stack = new LinkedList<>(); return coinChangeMethodCount(0, coins, amount, stack, true); } / * 递归计算零钱兑换方式数量 * * @param index 当前硬币下标 * @param coins 硬币数组 * @param remainder 剩余兑换金额 * @param first 排除第一次递归调用入栈的元素 * @return 兑换次数 */ private static int coinChangeMethodCount(int index, int[] coins, int remainder, Deque<Integer> stack, boolean first) { // 如果不是第一次调用,则记录当前兑换硬币 if (!first) { // 记录当前兑换硬币 stack.push(coins[index]); } // 情况1:如果兑换金额小于0,则直接返回0,无解 if (remainder < 0) { System.out.println("无解: " + stack); // 如果无解,则需要从栈中弹出元素,以便记录其他无解的兑换情况 if (!stack.isEmpty()) stack.pop(); return 0; } // 情况2:如果兑换金额等于0,则返回1,表示有解 if (remainder == 0) { System.out.println("有解: " + stack); // 如果有解,则需要从栈中弹出元素,以便记录其他有解的兑换情况 if (!stack.isEmpty()) stack.pop(); return 1; } int count = 0; // 情况3:如果兑换金额大于0,则继续递归并累加 for (int i = index; i < coins.length; i++) { count += coinChangeMethodCount(i, coins, remainder - coins[i], stack, false); } // 如果循环结束,则需要从栈中弹出当前元素,以便记录其他的无解或有解的兑换情况 if (!stack.isEmpty()) stack.pop(); return count; } }

package com.lzlg.study.algorithm.new2023.design.greedy; import java.util.Arrays; import java.util.Comparator; / * 贪心算法-分数背包问题 * 有如下物品,如果要拿走10升的液体 * 每次可以不拿,全拿,或拿一部分,问能拿到的最高价值是多少?(这里的单位价值都是整数) * 编号重量(升) 总价值 * 0 4 24 水 * 1 8 160 牛奶 * 2 2 4000 五粮液 * 3 6 108 可乐 * 4 1 4000 茅台 * * @author lzlg * 2023/8/10 10:57 */ public class FractionalKnapsack { / * 物品 */ static class Item { // 编号 int index; // 名称 String name; // 重量(升) int weight; // 总价值 int value; public Item(int index, String name, int weight, int value) { this.index = index; this.name = name; this.weight = weight; this.value = value; } / * 获取单位价值 * * @return 单位价值 */ int unitValue() { return value / weight; } @Override public String toString() { return "编号:" + index + "\t物品:" + name + "\t重量(升):" + weight + "\t总价值:" + value; } } public static void main(String[] args) { Item[] items = new Item[]{ new Item(0, "水", 4, 24), new Item(1, "牛奶", 8, 160), new Item(2, "五粮液", 2, 4000), new Item(3, "可乐", 6, 108), new Item(4, "茅台", 1, 4000), }; packSelect(items, 10); } / * 选择价值最高的物品,步骤如下 * 1.先根据单位价值进行降序排序 * 2.循环物品数组,如果可选择重量大于等于当前物品的重量,则可以拿取 * 3.拿取后,则需要更新可选择重量,并累加当前的价值到总价值中 * 4.如果可选择重量小于当前物品的重量,则可以拿取一部分 * 5.这一部分的价值=可选择重量*当前物品的单位价值 * 6.同样累加这部分价值到总价值中 * * @param items 物品数组 * @param selectWeight 可挑选的总重量 */ private static void packSelect(Item[] items, int selectWeight) { // 按照单位价值降序排序 Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed()); // 最大价值 int maxValue = 0; for (Item item : items) { System.out.print(item); // 如果可选择重量大于等于当前物品的重量,则可以拿取 if (selectWeight >= item.weight) { // 更新可选择重量=前一个可选择重量-当前物品的重量 selectWeight -= item.weight; // 累加当前的价值到最大价值中 maxValue += item.value; System.out.print("\t拿取重量:" + item.weight + "\n"); } else { // 如果只能拿取一部分 maxValue += selectWeight * item.unitValue(); // 此时退出循环,因为已经拿取部分了,没有剩余的选择余地了 System.out.print("\t拿取重量:" + selectWeight + "\n"); break; } } System.out.println("最大总价值为: " + maxValue); } }

package com.lzlg.study.algorithm.new2023.design.greedy; / * 贪心算法示例1-零钱兑换 * 求解最少兑换硬币数,默认硬币数组是降序的 * * 注意:贪心算法会出现错误的解 * 如 [15, 10, 1] 21 这种情况使用贪心算法得到数量为7(1*15+6*1=21),而实际上最少是3(2*10+1*1=21) * 再如 [15, 10] 20 这种情况使用贪心算法无解 * * @author lzlg * 2023/8/9 12:50 */ public class GreedyCoinChange { public static void main(String[] args) { // 硬币数组 int[] coins = new int[]{5, 2, 1}; // 兑换的总金额 int amount = 18; int count = greedyCoinChange(coins, amount); System.out.println("======="); System.out.println(count); } / * 贪心算法-零钱兑换 * 求解最少兑换硬币数,默认硬币数组是降序的 * * @param coins 硬币数组 * @param amount 兑换金额 * @return 最少兑换硬币数 */ public static int greedyCoinChange(int[] coins, int amount) { // 剩余兑换金额,初始值为当前方法传入的兑换金额 int remainder = amount; // 兑换硬币数 int count = 0; // 遍历硬币数组 for (int coin : coins) { // 如果剩余兑换金额大于硬币金额,则进行兑换 // 注意这里条件没有等于条件,否则退出外层循环比较麻烦 while (remainder > coin) { remainder -= coin; System.out.println(coin); count++; } // 如果剩余兑换金额等于硬币金额,则退出循环 if (remainder == coin) { // 兑换成功,兑换金额为0 remainder = 0; System.out.println(coin); // 兑换硬币数+1 count++; break; } } // 如果还有剩余兑换金额,则返回-1,表示无解 if (remainder > 0) { return -1; } // 返回兑换次数 return count; } }

package com.lzlg.study.algorithm.new2023.design.greedy; import java.util.Arrays; import java.util.Comparator; / * 0-1背包问题 * 如下所示,要拿走不超过10克的物品 * 每次[不拿或者全拿](注意和分数背包问题的不同) * 问能拿的最高价值是多少? * 编号重量价值 * 0 1 1_000_000 钻戒一枚 * 1 4 1600 黄金一块 * 2 8 2400 红宝石戒指一枚 * 3 5 30 白银一块 * * 注意: 使用贪心算法不能解决0-1背包问题 * * @author lzlg * 2023/8/10 11:22 */ public class OneZeroKnapsack { public static void main(String[] args) { Item[] items = new Item[]{ new Item(0, "钻戒一枚", 1, 1_000_000), new Item(1, "黄金一块", 4, 1600), new Item(2, "红宝石戒指一枚", 8, 2400), new Item(3, "白银一块", 5, 30), }; packSelect(items, 10); } / * 0-1背包问题,使用贪心算法不能解决0-1背包问题 * * @param items 物品数组 * @param selectWeight 可选择的重量 */ private static void packSelect(Item[] items, int selectWeight) { // 按照单位价值降序排序 Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed()); // 最大价值 int maxValue = 0; for (Item item : items) { // 如果可选择重量大于等于当前物品的重量,则可以拿取 if (selectWeight >= item.weight) { System.out.print(item); // 更新可选择重量=前一个可选择重量-当前物品的重量 selectWeight -= item.weight; // 累加当前的价值到最大价值中 maxValue += item.value; System.out.print("\t拿取重量:" + item.weight + "\n"); } else { // 0-1背包问题,只能不拿或全拿 } } System.out.println("最大总价值为: " + maxValue); } / * 物品 */ static class Item { // 编号 int index; // 名称 String name; // 重量 int weight; // 总价值 int value; public Item(int index, String name, int weight, int value) { this.index = index; this.name = name; this.weight = weight; this.value = value; } / * 获取单位价值 * * @return 单位价值 */ int unitValue() { return value / weight; } @Override public String toString() { return "编号:" + index + "\t物品:" + name + "\t重量:" + weight + "\t总价值:" + value; } } }

package com.lzlg.study.algorithm.new2023.design; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; / * 霍夫曼树-对字符串的编解码算法 * * @author lzlg * 2023/8/10 9:35 */ public class HuffmanTree { // 要编解码的字符串 String str; // 树的根节点 Node root; // 字符频次Map,key是字符,value是节点 Map<Character, Node> map = new HashMap<>(); / * 构造方法,,步骤如下 * 1.统计字符串中字符出现的频次到map中 * 2.使用优先级队列(小顶堆,已节点字符的频次作为权重)将map中的节点值集合加入 * 3.从优先级队列中出队两个最小频次的节点 * 4.以这两个节点构建一个父节点,父节点的批次是这两个节点的频次之和 * 5.把父节点放回优先级队列中 * 6.循环直到优先级队列中只有一个节点,该节点就是霍夫曼树的根节点 * * @param str 要编解码的字符串 */ public HuffmanTree(String str) { this.str = str; // 统计字符频次 char[] chars = str.toCharArray(); for (char ch : chars) { // 以字符为key,节点为value放入map中 Node node = map.computeIfAbsent(ch, Node::new); // 节点的频次+1 node.freq++; } // 使用优先级队列(小顶堆),以频次作为权重 PriorityQueue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(Node::freq)); // 将所有节点放入队列中 heap.addAll(map.values()); // 开始循环,直到队列中节点数量小于2 while (heap.size() >= 2) { // 弹出两个字符最小频次的节点 Node left = heap.poll(); Node right = heap.poll(); // 计算父节点的频次 int parentFreq = left.freq + right.freq; // 创建父节点,并加入到优先级队列中 heap.offer(new Node(parentFreq, left, right)); } // 循环退出,优先级队列的最后一个节点是根节点 this.root = heap.poll(); // 给有字符的节点编码,并在遍历过程中统计编码后的总bit数 int sum = dfsCode(this.root, new StringBuilder()); // 打印节点信息 for (Node node : map.values()) { System.out.println(node + " 编码" + node.code); } System.out.println("占用的bit数为: " + sum); } / * 给有字符的节点编码 * * @param node 节点 * @param code 编码 */ private int dfsCode(Node node, StringBuilder code) { // 统计字符串经过编码后占用的bit总数 int sum = 0; // 如果是叶子节点,则存储编码 if (node.isLeaf()) { node.code = code.toString(); // 叶子节点的bit数=频次 * 编码长度 sum += node.freq * code.length(); } else {// 如果不是叶子节点,则进行递归 // 向左递归,字符追加0 // 把叶子节点统计好的bit数进行累加 sum += dfsCode(node.left, code.append("0")); // 向右递归,字符追加1 sum += dfsCode(node.right, code.append("1")); } // 当递归结束返回上一层时,需要删除code中的最后一个字符 // 添加判断,防止第一次遍历时code为空的情况 if (code.length() > 0) { code.deleteCharAt(code.length() - 1); } return sum; } / * 编码 * * @return 编码后的字符串(都是0, 1) */ public String encode() { StringBuilder sb = new StringBuilder(); // 遍历字符数组 char[] chars = str.toCharArray(); for (char ch : chars) { // 从map中取出节点的编码 sb.append(map.get(ch).code); } return sb.toString(); } / * 解码,步骤如下 * 1.使用一个指针i遍历已编码的字符数组 * 2.使用一个指针p遍历霍夫曼树,初始时指向根节点 * 3.如果遇到字符是0,则向左走 * 4.如果遇到字符是1,则向右走 * 5.直到到达叶子节点,然后把叶子节点的字符拼接上 * 6.然后把指针p重新指向根节点 * * @param encoded 已编码的字符串 * @return 还原字符串 */ public String decode(String encoded) { // 拼接字符串 StringBuilder sb = new StringBuilder(); // 已编码的字符数组 char[] chars = encoded.toCharArray(); // 遍历字符数组的指针 int i = 0; // 遍历树的指针 Node p = root; // 开始循环 while (i < chars.length) { // 如果p指向的不是叶子节点 if (!p.isLeaf()) { // 如果当前字符是0,则向左走 if (chars[i] == '0') { p = p.left; // 如果当前字符是1,则向右走 } else if (chars[i] == '1') { p = p.right; } // 指针i+1,继续遍历字符数组 i++; } // 这里不用else判断,是因为如果i走到最后,此时如果p不是叶子节点,则i++ // 此时i==字符数组长度,循环退出,导致最后一个字符没有添加上 // 如果遍历到叶子节点了,则拼接字符 if (p.isLeaf()) { sb.append(p.ch); // 将指针p重新指向根节点 p = root; } } return sb.toString(); } / * 树的节点 */ static class Node { // 节点存储的字符(叶子节点才有) Character ch; // 字符出现的频次 int freq; // 字符编码(叶子节点才有) String code; // 左子节点 Node left; // 右子节点 Node right; public Node(Character ch) { this.ch = ch; } public Node(int freq, Node left, Node right) { this.freq = freq; this.left = left; this.right = right; } / * 获取节点字符出现频次 * * @return 频次 */ int freq() { return freq; } / * 判断是否是叶子节点 * 因为霍夫曼树是满二叉树,所以只判断有没有left子节点即可 * * @return 结果 */ boolean isLeaf() { return left == null; } @Override public String toString() { return "Node{" + "ch=" + ch + ", freq=" + freq + '}'; } } public static void main(String[] args) { String str = "abbccccccc"; HuffmanTree tree = new HuffmanTree(str); String encoded = tree.encode(); System.out.println(encoded); System.out.println(tree.decode(encoded)); } }

package com.lzlg.study.algorithm.new2023.design; / * @author lzlg * 2023/8/9 11:17 */ public class Test { public static void main(String[] args) { System.out.println((int) 'A'); } }

回溯算法

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; / * 回溯算法-组合之和 * 从1到9的数字中的指定k个数字(不重复)之和等于目标值的组合集合 * * @author lzlg * 2023/8/16 11:47 */ public class CombineNineNumber { public static void main(String[] args) { // 有解的情况 // List<List<Integer>> list = combineNineNumber(3, 7); // for (List<Integer> combine : list) { // System.out.println(combine); // } // System.out.println(count); // 无解的情况 List<List<Integer>> list = combineNineNumber(2, 18); for (List<Integer> combine : list) { System.out.println(combine); } System.out.println(count); } / * 回溯算法-组合之和 * 从1到9的数字中的指定k个数字(不重复)之和等于目标值的组合集合 * * @param k 数字个数 * @param target 目标值 * @return 组合集合 */ private static List<List<Integer>> combineNineNumber(int k, int target) { List<List<Integer>> result = new ArrayList<>(); dfs(1, k, target, new LinkedList<>(), result); return result; } static int count = 0; / * 回溯算法-组合之和-递归方法 * * @param start 起始数字 * @param k 数字个数 * @param target 目标值 * @param stack 栈 * @param result 组合结果集合 */ private static void dfs(int start, int k, int target, LinkedList<Integer> stack, List<List<Integer>> result) { count++; // 如果栈中的元素数量等于指定的数量k则添加栈元素到组合结果中 // 且目标值等于0的时候 if (target == 0 && stack.size() == k) { result.add(new ArrayList<>(stack)); return; } // 从start数字开始遍历,直到数字9(题目要求是只有1~9的数字) for (int i = start; i <= 9; i++) { // 如果当前数字大于了目标值,则不进行递归 if (i > target) { continue; } // 如果栈中的元素数量已经等于数量k了,下次递归则会超过,因此不再递归 if (stack.size() == k) { continue; } // 记录第一个数字 stack.push(i); // 进行递归,因为不能重复,所以start变为i+1,目标值减少i dfs(i + 1, k, target - i, stack, result); // 回溯 stack.pop(); } } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; / * 回溯算法-数字组合 * 给定一个数字n和组合个数k(n>=k),求组合数(不重复)有多少? * * @author lzlg * 2023/8/16 10:40 */ public class CombineNumber { public static void main(String[] args) { int n = 4; int k = 3; List<List<Integer>> list = combineNumber(n, k); for (List<Integer> combine : list) { System.out.println(combine); } } / * 回溯算法-数字组合 * * @param n 数字 * @param k 组合集合数量 * @return 组合集合列表 */ private static List<List<Integer>> combineNumber(int n, int k) { List<List<Integer>> result = new ArrayList<>(); dfs(1, n, k, new LinkedList<>(), result); return result; } / * 数字组合-递归方法 * * @param start 起始数字 * @param n 最大数字 * @param k 集合数量 * @param stack 栈用于回溯 * @param result 组合结果 */ private static void dfs(int start, int n, int k, LinkedList<Integer> stack, List<List<Integer>> result) { // 如果栈中元素的数量等于k了,则组合完成,添加到结果列表中并返回 if (stack.size() == k) { result.add(new ArrayList<>(stack)); return; } // 从起始数字开始遍历到最大数字n for (int i = start; i <= n; i++) { // 在未入栈前(注意是入栈前)进行判断,需要的数字数量是否小于等于剩余的数字数量 // 需要的数字数量为k - stack.size() // 剩余的数字数量为n - i + 1 // 如果大于,则不进行递归 if (k - stack.size() > n - i + 1) { continue; } // 入栈,固定一个数字 stack.push(i); // 进行递归调用,注意固定的起始数字要加1,再固定另一个数字 dfs(i + 1, n, k, stack, result); // 回溯 stack.pop(); } } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; / * 回溯算法-组合之和 * 给定一个数组和一个目标值 * 求出数组中元素(可重复)加和成目标值的组合集合 * * @author lzlg * 2023/8/16 11:25 */ public class CombineTarget { public static void main(String[] args) { int[] candidates = new int[]{2, 3, 6, 7}; int target = 7; List<List<Integer>> list = combineSum(candidates, target); for (List<Integer> combine : list) { System.out.println(combine); } } / * 回溯算法-组合之和 * * @param candidates 候选元素数组 * @param target 目标值 * @return 组合集合 */ private static List<List<Integer>> combineSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); dfs(0, candidates, target, new LinkedList<>(), result); return result; } / * 组合之和-递归方法 * * @param start 起始候选元素下标 * @param candidates 候选数组 * @param target 目标值 * @param stack 栈 * @param result 组合结果 */ private static void dfs(int start, int[] candidates, int target, LinkedList<Integer> stack, List<List<Integer>> result) { // 目标值在每次递归的时候需要减去候选元素的值 // 如果小于0则没有达到(元素值之和等于目标值)的要求,则直接返回 // 如果下面的循环中有(target < candidate)的判断,则不会有该情况 // if (target < 0) { // return; // } // 如果目标值为0,则达到了(元素值之和等于目标值)的要求 if (target == 0) { // 把栈中的结果添加到组合结果中 result.add(new ArrayList<>(stack)); return; } // 开始遍历候选元素 for (int i = start; i < candidates.length; i++) { // 候选元素 int candidate = candidates[i]; // 如果候选元素已经大于目标值了,则不再进行递归 if (target < candidate) { continue; } // 固定该候选元素 stack.push(candidate); // 进行递归,注意元素是可重复的,所以从i开始递归 // 下次的目标值需要调整为target - candidate dfs(i, candidates, target - candidate, stack, result); // 回溯 stack.pop(); } } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; / * 回溯算法-组合之和 * 给定一个数组和一个目标值 * 求出数组中元素加和成目标值的组合集合(组合情况不能重复,但数组中元素可重复) * * @author lzlg * 2023/8/16 11:25 */ public class CombineTargetNoRepeat { public static void main(String[] args) { int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5}; int target = 8; List<List<Integer>> list = combineSumNoRepeat(candidates, target); for (List<Integer> combine : list) { System.out.println(combine); } } / * 回溯算法-组合之和 * 求出数组中元素加和成目标值的组合集合(组合情况不能重复,但数组中元素可重复) * * @param candidates 候选元素数组 * @param target 目标值 * @return 组合集合 */ private static List<List<Integer>> combineSumNoRepeat(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); // 将候选数组进行排序,让数组中重复的靠近 Arrays.sort(candidates); // 添加判断候选元素是否访问过的boolean数组,进行重复情况的排除 dfs(0, candidates, target, new boolean[candidates.length], new LinkedList<>(), result); return result; } / * 组合之和-递归方法 * * @param start 起始候选元素下标 * @param candidates 候选数组 * @param target 目标值 * @param visited 候选元素是否访问过的记录数组 * @param stack 栈 * @param result 组合结果 */ private static void dfs(int start, int[] candidates, int target, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) { // 目标值在每次递归的时候需要减去候选元素的值 // 如果小于0则没有达到(元素值之和等于目标值)的要求,则直接返回 // 如果下面的循环中有(target < candidate)的判断,则不会有该情况 // if (target < 0) { // return; // } // 如果目标值为0,则达到了(元素值之和等于目标值)的要求 if (target == 0) { // 把栈中的结果添加到组合结果中 result.add(new ArrayList<>(stack)); return; } // 开始遍历候选元素 for (int i = start; i < candidates.length; i++) { // 候选元素 int candidate = candidates[i]; // 如果候选元素已经大于目标值了,则不再进行递归 if (target < candidate) { continue; } // 排除重复元素造成的组合重复情况 // 如果和前一个元素重复,且前一个元素没有访问,则不再进行递归 if (i > 0 && candidate == candidates[i - 1] && !visited[i - 1]) { continue; } // 固定该候选元素 stack.push(candidate); visited[i] = true; // 进行递归,注意元素是可重复的,所以从i开始递归 // 下次的目标值需要调整为target - candidate dfs(i + 1, candidates, target - candidate, visited, stack, result); // 回溯 stack.pop(); visited[i] = false; } } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.Arrays; / * 回溯算法-八皇后问题 * 8x8棋盘中放置8个皇后,和皇后同行同列同对角线(左右对角线)的会有冲突 * 问有多少种放置方法 * * @author lzlg * 2023/8/16 12:28 */ public class EmpressPlace { public static void main(String[] args) { // 4皇后放置问题 // empressPlace(4); System.out.println("==============="); empressPlace(8); } / * 皇后放置问题-回溯算法 * * @param empressCount 皇后数量 */ private static void empressPlace(int empressCount) { // 使用字符二维数组表示皇后放置方式 char[][] places = new char[empressCount][empressCount]; // 使用字符-表示没有放置,使用Q表示放置了皇后 // 初始化该二维数组,刚开始都是- for (char[] place : places) { Arrays.fill(place, '-'); } // 记录冲突的列,不记录行是因为行只能放置一个皇后 boolean[] columnPlace = new boolean[empressCount]; // 左或右对角线的数量:共(2*皇后数量-1)个 int diagonalCount = 2 * empressCount - 1; // 记录冲突的左对角线,共(2*皇后数量-1)个左对角线 // 如果和左对角线的冲突,则(行i-列j)都应该是一样的 // 但这样得到的有负数,需要通过[皇后数量-1-(行i-列j)]进行调整 boolean[] leftDiagonalPlace = new boolean[diagonalCount]; // 记录冲突的右对角线,共(2*皇后数量-1)个左对角线 // 如果和右对角线冲突,则(行i+列j)都应该是一样的 boolean[] rightDiagonalPlace = new boolean[diagonalCount]; // printTable(places); // 开始从下标为0的行进行放置皇后 dfs(0, empressCount, places, columnPlace, leftDiagonalPlace, rightDiagonalPlace); } / * 皇后放置问题-递归方法 * * @param row 要放置的行的下标 * @param empressCount 皇后数量 * @param places 棋盘二维数组 * @param columnPlace 冲突的列数组 * @param leftDiagonalPlace 冲突的左对角线数组 * @param rightDiagonalPlace 冲突的右对角线数组 */ private static void dfs(int row, int empressCount, char[][] places, boolean[] columnPlace, boolean[] leftDiagonalPlace, boolean[] rightDiagonalPlace) { // 如果当前要放置的行等于皇后数量(行数),则找到了解,进行打印结果 if (row == empressCount) { printTable(places); return; } // 开始遍历每一列,放置皇后 for (int col = 0; col < empressCount; col++) { // 判断如果出现冲突,则不进行放置 if (columnPlace[col] || leftDiagonalPlace[empressCount - 1 - (row - col)] || rightDiagonalPlace[row + col]) { continue; } // 放置皇后到该位置 places[row][col] = 'Q'; // 调整冲突数组 columnPlace[col] = true; leftDiagonalPlace[empressCount - 1 - (row - col)] = true; rightDiagonalPlace[row + col] = true; // 进行递归,尝试在新的一行放置下一个皇后 dfs(row + 1, empressCount, places, columnPlace, leftDiagonalPlace, rightDiagonalPlace); // 回溯,即把以前做的修改还原了 places[row][col] = '-'; // 调整冲突数组 columnPlace[col] = false; leftDiagonalPlace[empressCount - 1 - (row - col)] = false; rightDiagonalPlace[row + col] = false; } } private static void printTable(char[][] places) { for (char[] place : places) { System.out.println(new String(place)); } System.out.println("*"); } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; / * 回溯算法-全排列 * 求不重复元素数组的全排列集合 * * @author lzlg * 2023/8/16 10:06 */ public class FullRank { public static void main(String[] args) { int[] nums = {1, 2, 3}; List<List<Integer>> list = fullRank(nums); for (List<Integer> rank : list) { System.out.println(rank); } } / * 回溯算法-全排列,求不重复元素数组的全排列集合 * 使用一个栈和标记是否访问过的boolean数组 * 步骤和人类进行排列的步骤一直,先选定一个元素,再选定一个元素 * * @param nums 数组 * @return 全排列组合集合 */ private static List<List<Integer>> fullRank(int[] nums) { List<List<Integer>> result = new ArrayList<>(); dfs(nums, new boolean[nums.length], new LinkedList<>(), result); return result; } / * 递归方法 * 使用一个栈和标记是否访问过的boolean数组 * * @param nums 数组 * @param visited 标记是否访问过的boolean数组 * @param stack 栈 */ private static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) { // 当栈中元素数量等于数组中元素数量时,递归调用结束 if (stack.size() == nums.length) { // System.out.println(stack); result.add(new ArrayList<>(stack)); return; } // 遍历数组中元素 for (int i = 0; i < nums.length; i++) { // 如果没有访问过元素,才进行访问 if (!visited[i]) { // 当前元素入栈 stack.push(nums[i]); // 标记已访问过 visited[i] = true; // 递归调用,进行下个元素的访问(上面的代码就是选定了一个元素) dfs(nums, visited, stack, result); // 开始回溯,将访问标记和栈中该元素弹出,可重新进行选定 visited[i] = false; stack.pop(); } } } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; / * 回溯算法-全排列 * 求有重复元素数组的全排列集合 * * @author lzlg * 2023/8/16 10:06 */ public class FullRankRepeat { public static void main(String[] args) { // 注意数组中的元素重复了 int[] nums = {1, 1, 3, 3}; List<List<Integer>> list = fullRank(nums); for (List<Integer> rank : list) { System.out.println(rank); } } / * 回溯算法-全排列,求有重复元素数组的全排列集合 * 使用一个栈和标记是否访问过的boolean数组 * 步骤和人类进行排列的步骤一直,先选定一个元素,再选定一个元素 * * @param nums 数组 * @return 全排列组合集合 */ private static List<List<Integer>> fullRank(int[] nums) { // 先排序数组,将重复元素相聚 Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); dfs(nums, new boolean[nums.length], new LinkedList<>(), result); return result; } / * 递归方法 * 使用一个栈和标记是否访问过的boolean数组 * * @param nums 数组 * @param visited 标记是否访问过的boolean数组 * @param stack 栈 */ private static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) { // 当栈中元素数量等于数组中元素数量时,递归调用结束 if (stack.size() == nums.length) { // System.out.println(stack); result.add(new ArrayList<>(stack)); return; } // 遍历数组中元素 for (int i = 0; i < nums.length; i++) { // 如果有重复元素,则规定只能按一种顺序进行访问 // nums[i] == nums[i - 1]是判断当前元素和前一个元素是否重复了 // i > 0防止数组越界 // 查看前一个元素是否访问过,如果前一个元素没有访问过,则进行跳过(这样就能按照先访问前一个重复元素的顺序) if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } // 如果没有访问过元素,才进行访问 if (!visited[i]) { // 当前元素入栈 stack.push(nums[i]); // 标记已访问过 visited[i] = true; // 递归调用,进行下个元素的访问(上面的代码就是选定了一个元素) dfs(nums, visited, stack, result); // 开始回溯,将访问标记和栈中该元素弹出,可重新进行选定 visited[i] = false; stack.pop(); } } } }

package com.lzlg.study.algorithm.new2023.backtrack; import java.util.Arrays; / * 回溯算法-数独问题 * 给一个9x9的且部分已填写1~9数字的数独宫格,求解其余空位的数字 * 同一行的不同有相同数字 * 同一列的不同有相同数字 * 同一个九宫格的不能有相同数字 * * @author lzlg * 2023/8/16 13:17 */ public class SudokuProblem { public static void main(String[] args) { char[][] table = new char[][]{ {'5', '3', '-', '-', '7', '-', '-', '-', '-'}, {'6', '-', '-', '1', '9', '5', '-', '-', '-'}, {'-', '9', '8', '-', '-', '-', '-', '6', '-'}, {'8', '-', '-', '-', '6', '-', '-', '-', '3'}, {'4', '-', '-', '8', '-', '3', '-', '-', '1'}, {'7', '-', '-', '-', '2', '-', '-', '-', '6'}, {'-', '6', '-', '-', '-', '-', '2', '8', '-'}, {'-', '-', '-', '4', '1', '9', '-', '-', '5'}, {'-', '-', '-', '-', '8', '-', '-', '7', '9'} }; printTable(table); solveSudoku(table); System.out.println("==========================="); printTable(table); } private static void printTable(char[][] table) { for (char[] ta : table) { System.out.println(Arrays.toString(ta)); } } / * 解决数独问题,有唯一解 * * @param table 数独宫格 */ private static void solveSudoku(char[][] table) { // 数独九宫格长度 int len = table.length; // 记录行的冲突,这里使用二维boolean数组记录第0(对应第一行)行的与数字(用列下标表示)的冲突 // 字符'1'在列的下标为0,因此可以通过数字字符减去字符'1'的方式找到下标 boolean[][] rowPlace = new boolean[len][len]; // 记录列的冲突,这里使用二维boolean数组记录第0(对应第一列)列的与数字(用行下标表示)的冲突 // 字符'1'在列的下标为0,因此可以通过数字字符减去字符'1'的方式找到下标 boolean[][] colPlace = new boolean[len][len]; // 记录九宫格的冲突 // 列仍然是代表数字字符,行是九宫格的下标,计算方式是 i/3*3 + j/3 boolean[][] squarePlace = new boolean[len][len]; // 根据数独宫格,初始化冲突数组 for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { // 找到字符 char c = table[i][j]; // 不是字符'-'才进行冲突设置 if (c != '-') { // 行冲突 rowPlace[i][c - '1'] = true; // 列冲突 colPlace[j][c - '1'] = true; // 九宫格的冲突 squarePlace[i / 3 * 3 + j / 3][c - '1'] = true; } } } // 开始遍历数独宫格进行依次填写 dfs(0, 0, table, rowPlace, colPlace, squarePlace); } / * 数独问题-递归方法 * * @param row 当前行 * @param col 当前列 * @param table 数独数组 * @param rowPlace 行冲突数组 * @param colPlace 列冲突数组 * @param squarePlace 九宫格冲突数组 * @return 是否已经填写完成 */ private static boolean dfs(int row, int col, char[][] table, boolean[][] rowPlace, boolean[][] colPlace, boolean[][] squarePlace) { int len = table.length; // 找到要填写的空位 while (table[row][col] != '-') { // 如果该行已经全是数字字符,则跳到下一行的第一列 if (++col >= len) { row++; col = 0; } // 如果全部的行遍历完了,也没找到空位,则全部填好了,返回true if (row >= len) { return true; } } // 找个空位后,开始尝试从1到9的数字填写 for (int no = 1; no <= len; no++) { // 如果有冲突,则不能进行填写 if (rowPlace[row][no - 1] || colPlace[col][no - 1] || squarePlace[row / 3 * 3 + col / 3][no - 1]) { continue; } // 填写字符到数独中,这里字符'1'和'0'相差1,因此可以通过no + '0'这种方法填写数字字符 table[row][col] = (char) (no + '0'); // 更新冲突数组 rowPlace[row][no - 1] = true; colPlace[col][no - 1] = true; squarePlace[row / 3 * 3 + col / 3][no - 1] = true; // 进行递归调用,这里还是使用原来的row, col因为上边的循环会帮助找到空位 if (dfs(row, col, table, rowPlace, colPlace, squarePlace)) { // 如果已经找到解了,则直接返回不再继续 return true; } // 如果冲突了,则需要进行回溯 table[row][col] = '-'; rowPlace[row][no - 1] = false; colPlace[col][no - 1] = false; squarePlace[row / 3 * 3 + col / 3][no - 1] = false; } // 如果循环退出后,没有找到合适的数字,则填写失败,返回false return false; } }

分治算法

package com.lzlg.study.algorithm.new2023.divideAndConquer; / * 分治算法-找到字符串中重复次数大于等于k的最长子串 * 题目中的字符串中的字符都是小写英文字母 * * @author lzlg * 2023/8/15 20:24 */ public class FindGtKSubString { public static void main(String[] args) { String str = "aaaccdbbb"; int k = 3; System.out.println(gtKSubStringLen(str, 3)); } / * 分治算法-找到字符串中重复次数大于等于k的最长子串 * 步骤如下: * 1.统计字符的出现次数 * 2.遍历字符数组,如果字符的出现次数小于k,则进行切分字符串,并排除该字符 * 3.然后递归调用此方法,返回子串中最长的 * 递归的终结条件有两种情况: * 1.如果子串的长度小于k,则直接返回0(保持最小) * 2.如果子串的长度大于等于k,则返回子串的长度 * * @param str 字符串 * @param k 重复次数 * @return 重复次数大于等于k的最长子串(字符是连续的) */ private static int gtKSubStringLen(String str, int k) { System.out.println(str); // 如果子串的长度小于k,则直接返回0(保持最小) if (str.length() < k) { return 0; } // 根据题目的要求,字符都是小写英文字母 int[] counts = new int[26]; char[] chars = str.toCharArray(); // 统计字符出现次数 for (char ch : chars) { counts[ch - 'a']++; } // 遍历字符数组,找到切分下标 for (int i = 0; i < chars.length; i++) { // 当前字符的出现次数 int count = counts[chars[i] - 'a']; // 如果当前字符的出现次数大于0且小于k,则进行切分 if (count > 0 && count < k) { // 考虑到该字符可能会有连续多个,因此需要进行循环,找到左右切分边界 // 其中i是切分的左边界,使用j记录切分的右边界 int j = i + 1; // 不超过字符长度,且下标j的字符出现次数也小于k,此时j向右移动 while (j < str.length() && counts[chars[j] - 'a'] < k) { j++; } // 找到了切分的左右边界,则进行切分且返回 // 同时得到切分后子串的最大长度 return Integer.max( gtKSubStringLen(str.substring(0, i), k), gtKSubStringLen(str.substring(j), k) ); } } // 如果循环过后,则该子串达到了要求,故返回子串长度 return str.length(); } }

package com.lzlg.study.algorithm.new2023.divideAndConquer; / * 分治算法-快速幂 * * @author lzlg * 2023/8/15 19:33 */ public class QuickPow { public static void main(String[] args) { System.out.println(myPow(2, 16)); System.out.println(myPow(2, 10)); System.out.println(myPow(2, 0)); System.out.println(myPow(2, -2)); System.out.println(myPow(2, Integer.MIN_VALUE)); System.out.println(myPow(2.1, 3)); } / * 当n是整数时,可正可负 * 快速幂运算,指数n是奇数还是偶数 * * @param x 基数 * @param n 指数 * @return 结果 */ static double myPow(double x, int n) { long p = n; // 如果n是负数,则先转为正数 if (p < 0) { p = -p; } // 使用转为正数的p进行幂运算 double r = myPowPositive(x, p); // 根据n的正负返回结果 return n < 0 ? 1 / r : r; } / * 当n是自然数时 * 快速幂运算,指数n是奇数还是偶数 * * @param x 基数 * @param n 指数 * @return 结果 */ static double myPowPositive(double x, long n) { // 任何数的0次幂都是1 if (n == 0) { return 1.0; } // 任何数的1次幂都是自身 if (n == 1) { return x; } double div = myPowPositive(x, n / 2); // 因为偶数的二进制的最后一位是0,因此与1按位与等于0则是偶数 if ((n & 1) == 0) { return div * div; } else {// 是奇数 return x * div * div; } } }

package com.lzlg.study.algorithm.new2023.divideAndConquer; / * 分治算法-快速选择和快速选择的应用 * * @author lzlg * 2023/8/15 18:32 */ public class QuickSelectApplication { public static void main(String[] args) { int[] array = {6, 5, 1, 2, 4}; System.out.println(quickSelect(array, 0)); System.out.println(quickSelect(array, 1)); System.out.println(quickSelect(array, 2)); System.out.println(quickSelect(array, 3)); System.out.println(quickSelect(array, 4)); System.out.println("========="); System.out.println(findKBigElement(array, 3)); System.out.println("========="); System.out.println(findMedian(array)); array = new int[]{1, 2, 3, 4, 5, 6}; System.out.println(findMedian(array)); } / * 找到数组中的中位数 * 如果数组元素个数是奇数,则直接返回中间的即下标为array.length/2的元素值 * 如果数组元素个数是偶数,则查找中间两个的元素值,相加除以2.0得到中位数 * 这两个元素中后一个的下标是array.length/2,则前一个下标是array.length/2-1 * * @param array 数组 * @return 中位数 */ private static double findMedian(int[] array) { // 如果数组元素个数是奇数 if (array.length % 2 == 1) { // 则快速快速查找排名为array.length / 2的元素 return quickSelect(array, 0, array.length - 1, array.length / 2); } else {// 如果数组元素个数是偶数 // 前一个元素的排名是array.length/2-1 int x = quickSelect(array, 0, array.length - 1, array.length / 2 - 1); // 后一个元素的排名是array.length/2 int y = quickSelect(array, 0, array.length - 1, array.length / 2); return (x + y) / 2.0; } } / * 找到数组中第k大的元素值(从1开始) * 可转换为求数组中排名为(array.length - k)的元素值 * * @param array 数组(未排序) * @param k 指定的k * @return 第k大的元素值 */ private static int findKBigElement(int[] array, int k) { return quickSelect(array, 0, array.length - 1, array.length - k); } / * 从数组中找到排名为k的元素值(从0开始) * * @param array 数组(未排序) * @param k 指定的排名k * @return 排名为k的元素值 */ private static int quickSelect(int[] array, int k) { return quickSelect(array, 0, array.length - 1, k); } / * 从数组中找到排名为k的元素值(从0开始) * 使用分治算法 * 第一次时先找到一个基准点值,然后进行一次分区操作,得到该基准点值所在的下标p * 然后根据下标p和k进行比较,如果相等,则找到了直接返回数组中元素 * 如果k大于p,则需要在右边查找 * 如果k小于p,则需要在左边查找 * * @param array 数组(未排序) * @param left 左边界 * @param right 右边界 * @param k 指定的排名k * @return 排名为k的元素值 */ private static int quickSelect(int[] array, int left, int right, int k) { int p = partition(array, left, right); if (p == k) { return array[p]; } // 如果k大于p,则需要在右边查找 if (k > p) { return quickSelect(array, p + 1, right, k); } // 如果k小于p,则需要在左边查找 return quickSelect(array, 0, p - 1, k); } / * 分区方法,选最右边的作为基准点 * * @param array 数组 * @param left 左边界 * @param right 右边界 * @return 基准点下标 */ private static int partition(int[] array, int left, int right) { // 以右边界作为基准点 int pv = array[right]; // 指针i找到比基准点小的 int i = left; // 指针j找到比基准点大的 int j = left; while (i < right) { // 如果使用指针i找到比基准点小的元素,则进行交换 if (array[i] < pv) { if (i != j) { swap(array, i, j); } j++; } // 如果找到比基准点大的元素,则指针j不移动,指向该元素 i++; } // 把基准点元素放入合适的位置,即指针j的下标 swap(array, j, right); return j; } / * 进行交换 * * @param array 数组 * @param i 下标i * @param j 下标j */ private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } }

package com.lzlg.study.algorithm.new2023.divideAndConquer; / * 分治算法-求一个自然数的平方根的整数部分 * * @author lzlg * 2023/8/15 19:52 */ public class SquareIntegerPart { public static void main(String[] args) { System.out.println(sqrtInt(99)); System.out.println(sqrtInt(1)); System.out.println(sqrtInt(2)); System.out.println(sqrtInt(4)); System.out.println(sqrtInt(5)); System.out.println(sqrtInt(8)); System.out.println(sqrtInt(9)); System.out.println(sqrtInt(2147395599)); System.out.println("==============="); System.out.println(getSqrtInt(99)); System.out.println(getSqrtInt(1)); System.out.println(getSqrtInt(2)); System.out.println(getSqrtInt(4)); System.out.println(getSqrtInt(5)); System.out.println(getSqrtInt(8)); System.out.println(getSqrtInt(9)); System.out.println(getSqrtInt(2147395599)); } / * 求一个自然数的平方根的整数部分,解决因为n太大造成的溢出问题 * * @param n 自然数 * @return 整数部分 */ private static int getSqrtInt(int n) { int l = 1; int r = n; int result = 0; while (l <= r) { // 取中间值 int m = (l + r) >>> 1; // 转换公式,使用除法代替乘法,可防止溢出 if (m <= n / m) { l = m + 1; // 记录最近的小于自然数n的最小整数 result = m; } else {// 如果大于,则需要在左边找 r = m - 1; } } return result; } / * 求一个自然数的平方根的整数部分 * 使用左右边界,左边界初始为1,右边界初始为该自然数 * 找到左右边界的中间值m,计算m的平方 * 如果m的平方小于自然数,则扩大左边界(在右边查找) * 如果m的平方大于自然数,则减少右边界(在左边查找) * 直到左右边界重合,此时记录的上一个m的平方小于自然数的则为返回值 * * @param n 自然数 * @return 整数部分 */ private static int sqrtInt(int n) { int l = 1; int r = n; int result = 0; while (l <= r) { // 取中间值 int m = (l + r) >>> 1; // 计算平方值 int m2 = m * m; if (m2 == n) { return m; // 如果m的平方值小于n,则需要在右边找 } else if (m2 < n) { l = m + 1; // 记录最近的小于自然数n的最小整数 result = m; } else {// 如果大于,则需要在左边找 r = m - 1; } } return result; } }

LeetCode习题

package com.lzlg.study.algorithm.new2023.leetcode; / * 最长公共子串,给定一个字符串数组,找到字符串数组中所有字符串的公共前缀 * * @author lzlg * 2023/8/24 14:59 */ public class LongestCommonPrefix { public static void main(String[] args) { System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"})); System.out.println(longestCommonPrefix(new String[]{"dog", "raceCar", "Car"})); System.out.println(longestCommonPrefix(new String[]{"ab", "a"})); System.out.println(longestCommonPrefix(new String[]{"dog", "dogaa", "dogbb"})); } / * 最长公共子串 * * @param strings 字符串数组 * @return 找到字符串数组中所有字符串的公共前缀 */ private static String longestCommonPrefix(String[] strings) { // 取第一个字符串作为参照 String first = strings[0]; // 开始一个字符字符进行检查 for (int i = 0; i < first.length(); i++) { // 对比其他字符串中的字符 for (int j = 1; j < strings.length; j++) { // 如果当前字符串的长度不够了,则直接返回(字符串切割从0到i-不包括) if (strings[j].length() == i) { return first.substring(0, i); } // 如果遇到不相同的字符了,则直接返回(字符串切割从0到i-不包括) if (strings[j].charAt(i) != first.charAt(i)) { return first.substring(0, i); } } } // 如果循环结束,则是第一个字符串是公共子串的情况,则返回first return first; } }

package com.lzlg.study.algorithm.new2023.leetcode; / * 最长回文子串 * * @author lzlg * 2023/8/24 20:34 */ public class LongestPalindromeSubString { public static void main(String[] args) { String content = "bccbddc"; System.out.println(longestPalindromeSubString(content)); } / * 最长回文子串 * * @param content 字符串 * @return 最长回文子串 */ private static String longestPalindromeSubString(String content) { left = 0; right = 0; // 转换为字符数组 char[] chars = content.toCharArray(); // 开始遍历每个字符,分别从每个字符中心开花 // 为了防止i+1越界,将i的范围减少到chars.length - 1 for (int i = 0; i < chars.length - 1; i++) { // 考虑回文子串是奇数个的情况 extend(chars, i, i); // 考虑回文子串是偶数个的情况 extend(chars, i, i + 1); } // 返回该子串 return new String(chars, left, right - left + 1); } // 记录左边界 static int left = 0; // 记录右边界 static int right = 0; / * 中心开花方法 * * @param chars 字符数组 * @param i 从中心向左移动的指针 * @param j 从中心向右移动的指针 */ private static void extend(char[] chars, int i, int j) { // 在i和j不超过数组范围的情况下,如果i和j对应的字符相等,则分别进行移动 while (i >= 0 && j < chars.length && chars[i] == chars[j]) { i--; j++; } // 退出循环后,此时i和j需要回退一次操作,才能回到原来的回文记录位置 i++; j--; // 更新左边界和右边界,超过原来的才进行更新 if (j - i > right - left) { left = i; right = j; } } }

package com.lzlg.study.algorithm.new2023.leetcode; import cn.hutool.core.lang.Snowflake; import java.util.HashMap; import java.util.Map; / * 长连接转短链接,短链接查找长链接 * * @author lzlg * 2023/9/7 17:04 */ public class LongShortUrl { public static void main(String[] args) { LongShortUrl test = new LongShortUrl(); String longUrl1 = "https://www.lzlgproject.top/11/page/12-hello-world.html"; System.out.println(test.encode(longUrl1)); String longUrl2 = "https://www.lzlgproject.top/11/page/12-activity-python.html"; System.out.println(test.encode(longUrl2)); } // 长连接为key的map private Map<String, String> longToShortMap = new HashMap<>(); // 短链接为key的map private Map<String, String> shortToLongMap = new HashMap<>(); // 短链接前缀 private static final String SHORT_PREFIX = "https://hello.com/"; // 转换为62进制字符串的字符数组 private static final char[] toBase62 = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' }; // 使用雪花算法生成数字 static final Snowflake snowflake = new Snowflake(1, 2); / * 将10进制数转换为62进制字符串 * * @param number 10进制数字 * @return 62进制字符串 */ private static String toBase62(long number) { StringBuilder sb = new StringBuilder(); int len62 = toBase62.length; while (number > 0) { long r = number % len62; sb.append(toBase62[(int) r]); number = number / len62; } return sb.toString(); } / * 长链接转短链接 * 生成id的方式有:1.使用随机数,2.使用hash码,3.使用自增数 * 4.生成62进制的字符串(有数字,大小写字母)(代码演示的是4) * * @param longUrl 长链接 * @return 短链接 */ public String encode(String longUrl) { // 先从Map中获取 String shortUrl = longToShortMap.get(longUrl); if (shortUrl != null) { return shortUrl; } // 生成数字 long number = snowflake.nextId(); // 根据数字生成62进制字符串 String base62 = toBase62(number); // 获取短链接 shortUrl = SHORT_PREFIX + base62; // 放入相应的map中进行缓存 longToShortMap.put(longUrl, shortUrl); shortToLongMap.put(shortUrl, longUrl); // 返回短链接 return shortUrl; } / * 短链接转长链接 * * @param shortUrl 短链接 * @return 长链接 */ public String decode(String shortUrl) { return shortToLongMap.get(shortUrl); } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.HashMap; import java.util.Map; / * 最小覆盖子串,字符都是英文字母 * 给定一个字符串s和字符串t,字符串s包含所有字符串t中的所有字符的最短子串 * * @author lzlg * 2023/8/24 21:10 */ public class MinimalCoverSubString { public static void main(String[] args) { String s = "ADOBECODEBANC"; String t = "ABC"; System.out.println(minimalCoverSubString(s, t)); } / * 最小覆盖子串,使用两个指针i和j * 指针j找到能覆盖的子串的右边界下标 * 指针i找到能覆盖的最短子串的左边界下标 * * @param s 字符串 * @param t 目标串 * @return 最短子串 */ private static String minimalCoverSubString(String s, String t) { // 统计目标串中字符的出现次数 int[] tCount = new int[128]; // 转换为字符数组 char[] tChars = t.toCharArray(); // 统计目标串中字符的出现次数 for (char tCh : tChars) { tCount[tCh]++; } // 统计符合覆盖目标串的条件总数 int passTotal = 0; for (int i : tCount) { if (i > 0) { passTotal++; } } // print(tCount); // 通过覆盖目标串条件数 int passed = 0; SubLen sl = null; // 下标i:左边界 int i = 0; // 下标j:右边界 int j = 0; // 统计从i到j子串的字符出现次数 int[] sCount = new int[128]; // 转换为字符数组 char[] sChars = s.toCharArray(); // 开始循环,找到符合目标的子串 while (j < sChars.length) { // 找到右边界的字符 char right = sChars[j]; // 统计字符出现次数 sCount[right]++; // print(sCount); // 如果当前的字符的出现在sCount的次数==出现在tCount的次数,则通过条件数+1 if (sCount[right] == tCount[right]) { passed++; } // 如果通过的条件数达到符合覆盖目标串的条件总数 while (passed == passTotal && i <= j) { // 此时已经到达了覆盖条件,因此进行记录 if (sl == null) { sl = new SubLen(i, j); } else { // 如果当前子串的比原来的还短,则需要更新 if (j - i < sl.j - sl.i) { sl = new SubLen(i, j); } } // 此时缩小子串的范围,即开始判断覆盖的最短子串的左边界 char left = sChars[i]; // 将对应字符下标的次数减少1 sCount[left]--; // 如果左字符的在sCount的次数<出现在tCount的次数,则通过条件-1 // 如果是没有在目标串中出现的字符,则该字符在sCount的次数会大于tCount的次数 if (sCount[left] < tCount[left]) { passed--; } i++; } j++; } // 如果sl为null,则没有找到覆盖的子串 // 不为null,则记录的是最短子串 return sl == null ? "" : new String(sChars, sl.i, sl.j - sl.i + 1); } / * 记录子串长度的类 */ static class SubLen { // 左边界 int i; // 右边界 int j; public SubLen(int i, int j) { this.i = i; this.j = j; } @Override public String toString() { return "SubLen{" + "i=" + i + ", j=" + j + '}'; } } private static void print(int[] count) { Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < count.length; i++) { if (count[i] > 0) { map.put((char) i, count[i]); } } System.out.println(map); } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.LinkedList; / * 最小值栈,模拟栈,并能在常数时间内返回栈中元素的最小值 * 方法1:使用两个栈 * 方法2:封装新的数据结构(包含最小值) * * @author lzlg * 2023/9/7 16:31 */ public class MinValueStack { / * 方式1:使用两个栈,一个栈记录元素,一个栈记录最小值 */ static class MinTwoStack { private final LinkedList<Integer> stack; private final LinkedList<Integer> min; public MinTwoStack() { this.stack = new LinkedList<>(); this.min = new LinkedList<>(); this.min.push(Integer.MAX_VALUE); } / * 入栈 * * @param value 入栈元素 */ public void push(int value) { stack.push(value); min.push(Integer.min(value, min.peek())); } / * 出栈 * * @return 出栈元素 */ public int pop() { int value = stack.pop(); min.pop(); return value; } / * 查看栈顶元素 * * @return 栈顶元素 */ public int top() { return stack.pop(); } / * 获取栈中最小值 * * @return 最小值 */ public int min() { return min.pop(); } } / * 方式2:使用新的数据结构,该数据结构包含元素和对应最小值 */ static class MinDataStack { private final LinkedList<Data> stack; public MinDataStack() { this.stack = new LinkedList<>(); } / * 入栈 * * @param value 入栈元素 */ public void push(int value) { // 如果栈为空,则直接放入 if (stack.isEmpty()) { stack.push(new Data(value, value)); } else { // 如果不为空,则比较栈顶元素value和当前新元素的value取较小值 stack.push(new Data(value, Integer.min(value, stack.peek().value))); } } / * 出栈 * * @return 出栈元素 */ public int pop() { return stack.pop().value; } / * 查看栈顶元素 * * @return 栈顶元素 */ public int top() { return stack.peek().value; } / * 获取栈中最小值 * * @return 最小值 */ public int min() { return stack.peek().min; } static class Data { int value; int min; public Data(int value, int min) { this.value = value; this.min = min; } } } }

package com.lzlg.study.algorithm.new2023.leetcode; / * 盛最多水的容器 * 给定一个数组,每个数组元素是挡板的高度 * 求该容器最多能盛多少水? * * @author lzlg * 2023/8/24 10:44 */ public class MoreWaterContainer { public static void main(String[] args) { int[] heights = {1, 8, 6, 2, 5, 4, 8, 3, 7}; System.out.println(maxArea(heights)); } / * 盛最多水的容器 * 给定一个数组,每个数组元素是挡板的高度 * 求该容器最多能盛多少水? * 可以观察到如果有两个挡板,则低的挡板决定了高度 * 因此只有改变低的挡板才有可能有最大容量 * * @param heights 挡板高度数组 * @return 最大水容量 */ private static int maxArea(int[] heights) { // 挡板1 int i = 0; // 挡板2 int j = heights.length - 1; // 最大容量 int max = 0; while (i < j) { // 谁挡板低就改变谁 if (heights[i] < heights[j]) { // 计算当前容量,用较低的挡板 int area = heights[i] * (j - i); max = Integer.max(max, area); i++; } else { // 计算当前容量,用较低的挡板 int area = heights[j] * (j - i); max = Integer.max(max, area); j--; } } return max; } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; / * 滑动窗口最大值 * 有一数组: [1, 3, -1, -3, 1, 5, 3, 6, 7] * 滑动窗口的长度k = 3,求滑动窗口的最大值数组 * * @author lzlg * 2023/8/24 12:26 */ public class MovedWindowMaxValue { public static void main(String[] args) { int[] nums = {1, 3, -1, -3, 1, 5, 3, 6, 7}; int k = 3; System.out.println(Arrays.toString(movedWindowMaxValues(nums, k))); } / * 滑动窗口最大值,借助一个单调队列的数据结构 * * @param nums 数组 * @param k 窗口大小 * @return 最大值数组 */ private static int[] movedWindowMaxValues(int[] nums, int k) { // 记录结果的列表 List<Integer> list = new ArrayList<>(); // 创建单调队列 MonotonicQueue queue = new MonotonicQueue(); // 遍历数组元素,依次加入队列中 for (int i = 0; i < nums.length; i++) { // 如果当前队列头部元素是前一个元素,则超过了窗口大小,需要移除 if (i >= k && queue.peek() == nums[i - k]) { queue.poll(); } int num = nums[i]; // 进行入队 queue.offer(num); // 当i移动到达到窗口大小的位置时才记录结果 if (i >= (k - 1)) { list.add(queue.peek()); } } // 列表转换为数组 return list.stream().mapToInt(Integer::intValue).toArray(); } / * 单调队列,始终保持队列中的元素从头向尾是有序的 * 若为[7, 6, 4]且加入元素8时,需要将所有小于8的元素进行移除,再添加元素8入队 */ static class MonotonicQueue { // 使用LinkedList进行模拟 private final LinkedList<Integer> deque = new LinkedList<>(); / * 查看头部元素 * * @return 头部元素 */ public Integer peek() { return deque.peekFirst(); } / * 出队 * * @return 头部元素 */ public Integer poll() { return deque.pollFirst(); } / * 入队 * * @param v 元素v */ public void offer(Integer v) { // 如果队列的尾部小于当前值v,则进行出队 while (!deque.isEmpty() && deque.peekLast() < v) { deque.pollLast(); } // 然后添加元素到尾部 deque.offerLast(v); } } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.HashMap; import java.util.Map; / * 实现简单的lFU(最近使用频率)缓存 * * @author lzlg * 2023/9/7 10:37 */ public class SimpleLFUCache { private final int capacity; // 最小频率 private int minFreq; private final Map<Integer, Node> nodeMap; private final Map<Integer, DoubleLinkedList> freqMap; public SimpleLFUCache(int capacity) { this.capacity = capacity; // 初始时最小频率为1 this.minFreq = 1; this.nodeMap = new HashMap<>(); this.freqMap = new HashMap<>(); } / * 根据key获取value * 需要更新访问频率和最近使用的规则 * * @param key key * @return 值value */ public int get(int key) { if (!nodeMap.containsKey(key)) { return -1; } Node node = nodeMap.get(key); // 找到节点以前的频率链表 DoubleLinkedList list = freqMap.get(node.freq); // 从以前的频率链表中删除该节点 list.remove(node); // 如果以前的频率链表为空且以前的频率等于最小频率,则最小频率增加 if (list.isEmpty() && node.freq == minFreq) { minFreq++; } // 更新节点访问频率 node.freq++; // 放入新的频率链表 freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()) .addFirst(node); return node.value; } / * 放入key和value * * @param key key * @param value value */ public void put(int key, int value) { // 如果key存在,则进行更新 if (nodeMap.containsKey(key)) { // 根据key获取节点 Node node = nodeMap.get(key); // 找到节点以前的频率链表 DoubleLinkedList list = freqMap.get(node.freq); // 从以前的频率链表中删除该节点 list.remove(node); // 如果以前的频率链表为空且以前的频率等于最小频率,则最小频率增加 if (list.isEmpty() && node.freq == minFreq) { minFreq++; } // 更新节点访问频率 node.freq++; // 放入新的频率链表 freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()) .addFirst(node); // 更新节点的value node.value = value; } else {// key不存在,则进行添加 Node node = new Node(key, value); // 放入节点的map中 nodeMap.put(key, node); // 添加新节点到频率为1的链表中 freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()) .addFirst(node); // 判断是否超过容量 if (nodeMap.size() > capacity) { // 如果超过容量,则从最小频率的链表中删除最后一个 Node removed = freqMap.get(minFreq).removeLast(); nodeMap.remove(removed.key); } // 添加新节点,最小频率变为初始值1 minFreq = 1; } } static class DoubleLinkedList { Node head; Node tail; int size; public DoubleLinkedList() { head = tail = new Node(); head.next = tail; tail.prev = head; this.size = 0; } public void addFirst(Node newFirst) { Node oldFirst = head.next; newFirst.prev = head; newFirst.next = oldFirst; head.next = newFirst; oldFirst.prev = newFirst; size++; } public void remove(Node node) { Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; size--; } public Node removeLast() { Node last = tail.prev; remove(last); return last; } public boolean isEmpty() { return size == 0; } } static class Node { Node prev; Node next; int key; int value; // 频率 int freq; public Node() { } public Node(int key, int value) { this.key = key; this.value = value; // 新节点的使用频率初始为1 this.freq = 1; } } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.HashMap; import java.util.Map; / * 实现简单的LRU(最近最少使用)缓存 * * @author lzlg * 2023/9/7 9:53 */ public class SimpleLRUCache { private final int capacity; private final DoubleLinkedList list; private final Map<Integer, Node> map; public SimpleLRUCache(int capacity) { this.capacity = capacity; this.list = new DoubleLinkedList(); this.map = new HashMap<>(); } / * 根据key获取value,注意要符合最近使用的规则 * * @param key key * @return value */ public int get(int key) { if (!map.containsKey(key)) { return -1; } // 从map中获取节点 Node node = map.get(key); // 从链表中删除该节点,并添加到头部 list.remove(node); list.addFirst(node); return node.value; } / * 放入元素,注意超过容量的情况和key存在时符合最近使用的规则 * * @param key key * @param value value */ public void put(int key, int value) { // key存在则更新 if (map.containsKey(key)) { // 取出node进行更新 Node node = map.get(key); node.value = value; // 保证node最近使用 list.remove(node); list.addFirst(node); } else {// key不存在则添加 Node node = new Node(key, value); // 进行添加 map.put(key, node); list.addFirst(node); // 超出容量 if (map.size() > capacity) { // 删除最后一个元素 Node removed = list.removeLast(); map.remove(removed.key); } } } / * 双向链表 */ static class DoubleLinkedList { Node head; Node tail; public DoubleLinkedList() { // 使用哨兵头尾节点 head = tail = new Node(); head.next = tail; tail.prev = head; } / * 添加到头部 * * @param newFirst 新节点 */ public void addFirst(Node newFirst) { // 原第一个节点 Node oldFirst = head.next; // 头节点的下一个节点是新的节点 head.next = newFirst; // 新节点的上一个节点是头节点 newFirst.prev = head; // 新节点的下一个节点是原来的第一个节点 newFirst.next = oldFirst; // 原来的第一个节点的前一个节点是新节点 oldFirst.prev = newFirst; } / * 删除节点 * * @param node 待删除节点 */ public void remove(Node node) { // 节点的前一个节点 Node prev = node.prev; // 节点的后一个节点 Node next = node.next; // 前一个节点的下一个节点是后一个节点 prev.next = next; // 后一个节点的上一个节点是前一个节点 next.prev = prev; } / * 删除最后一个节点 * * @return 节点 */ public Node removeLast() { Node last = tail.prev; remove(last); return last; } } / * 双向链表节点 */ static class Node { Node prev; Node next; int key; int value; public Node() { } public Node(int key, int value) { this.key = key; this.value = value; } } }

package com.lzlg.study.algorithm.new2023.leetcode.stock; import java.util.Arrays; / * 限制交易次数 * 给定一个整数数组,含义是第i(下标)天的股票价格是数组中的值 * 如果允许买卖k次,持有股票时只能卖,且卖出的一天同时可买入,求最大利润 * * @author lzlg * 2023/9/8 15:27 */ public class LimitTradeKCount { public static void main(String[] args) { System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3})); System.out.println(maxProfit(2, new int[]{3, 3, 5, 0, 0, 3, 1, 4})); System.out.println(maxProfit(4, new int[]{1, 2, 0, 1, 0, 3, 1, 4, 5})); } / * 计算股票最大利润 * 有两种情况 * 一.当k的交易次数大于股票价格数组长度的一半时 * 此时交易等于没有上限,则使用maxProfitUnlimited方法 * 二.当不满足一的条件是 * 使用动态规划算法,可得出以下规律: * 第一次买: 要么继承前面第一次买的价格,要么不依赖之前的状态,取当前股票价格的负数 * 第一次卖: 要么继承前面第一次卖的利润,要么计算昨天第一次买的价格 + 当前股票价格 * * 第二次买: 要么继承前面第二次买的价格,要么计算昨天第一次卖的利润 - 当前股票价格 * 第二次卖: 要么继承前面第二次卖的利润,要么计算昨天第二次买的价格 + 当前股票价格 * * 第三次买: 要么继承前面第三次买的价格,要么计算昨天第二次卖的利润 - 当前股票价格 * 第三次卖: 要么继承前面第三次卖的利润,要么计算昨天第三次买的价格 + 当前股票价格 * ... * 第k次买: 要么继承前面第k次买的价格,要么计算昨天第k-1次卖的利润 - 当前股票价格 * 第k次卖: 要么继承前面第k次卖的利润,要么计算昨天第k次买的价格 + 当前股票价格 * * @param k 限制交易次数 * @param prices 股票价格数组 * @return 最大利润 */ private static int maxProfit(int k, int[] prices) { // 股票价格数组长度 int length = prices.length; // 第一种情况,相当于交易无限制 if (k > length / 2) { return maxProfitUnlimited(prices); } // 构建买数组,下标i表示第(i+1)次买 int[] buy = new int[k]; // 进行初始化 Arrays.fill(buy, Integer.MIN_VALUE); // 构建卖数组,下标i表示第(i+1)次卖 int[] sell = new int[k]; // 遍历股票价格,每次都更新买数组和卖数组的值 for (int price : prices) { // 第一次买的情况 buy[0] = Integer.max(buy[0], -price); sell[0] = Integer.max(sell[0], buy[0] + price); // 计算其他购买次数的情况 for (int i = 1; i < k; i++) { // 第(i+1)次买的情况 buy[i] = Integer.max(buy[i], sell[i - 1] - price); // 第(i+1)次卖的情况 sell[i] = Integer.max(sell[i], buy[i] + price); } } return sell[k - 1]; } / * 计算股票最大利润,无交易次数限制 * * @param prices 股票价格数组 * @return 最大利润 */ private static int maxProfitUnlimited(int[] prices) { // i代表股票买入时的天数(下标) int i = 0; // j代表股票卖出时的天数(下标) int j = 1; // 记录最大利润 int maxProfit = 0; while (j < prices.length) { // 如果卖出的价格大于买入的价格,则能产生利润 if (prices[j] > prices[i]) { // 记录最大利润 maxProfit = Integer.max(maxProfit, prices[j] - prices[i]); // j++,判断后续的卖出价格 j++; } else { // 否则没有利润,移动i到j,j++ i = j; j++; } } // 返回最大利润 return maxProfit; } }

package com.lzlg.study.algorithm.new2023.leetcode.stock; / * 给定一个整数数组,含义是第i(下标)天的股票价格是数组中的值 * 如果只能买卖一次,求最大利润 * * @author lzlg * 2023/9/8 12:21 */ public class MaxProfitStock { public static void main(String[] args) { int[] prices = new int[]{7, 1, 5, 3, 6, 4}; System.out.println(maxProfit(prices)); prices = new int[]{9, 3, 12, 1, 2, 3}; System.out.println(maxProfit(prices)); } / * 计算股票最大利润 * * @param prices 股票价格数组 * @return 最大利润 */ private static int maxProfit(int[] prices) { // i代表股票买入时的天数(下标) int i = 0; // j代表股票卖出时的天数(下标) int j = 1; // 记录最大利润 int maxProfit = 0; while (j < prices.length) { // 如果卖出的价格大于买入的价格,则能产生利润 if (prices[j] > prices[i]) { // 记录最大利润 maxProfit = Integer.max(maxProfit, prices[j] - prices[i]); // j++,判断后续的卖出价格 j++; } else { // 否则没有利润,移动i到j,j++ i = j; j++; } } // 返回最大利润 return maxProfit; } }

package com.lzlg.study.algorithm.new2023.leetcode.stock; / * 给定一个整数数组,含义是第i(下标)天的股票价格是数组中的值 * 如果允许买卖多次,持有股票时只能卖,且卖出的一天同时可买入,求最大利润 * * @author lzlg * 2023/9/8 12:21 */ public class MultipleOptMaxProfitStock { public static void main(String[] args) { int[] prices = new int[]{7, 1, 5, 3, 6, 4}; System.out.println(maxProfit(prices)); prices = new int[]{9, 3, 12, 1, 2, 3}; System.out.println(maxProfit(prices)); } / * 计算股票最大利润,使用贪心算法,只在一天时间内计算股票利润 * * @param prices 股票价格数组 * @return 最大利润 */ private static int maxProfit(int[] prices) { // i代表股票买入时的天数(下标) int i = 0; // j代表股票卖出时的天数(下标) int j = 1; // 累计最大利润 int profit = 0; while (j < prices.length) { // 如果卖出的价格大于买入的价格,则能产生利润 if (prices[j] > prices[i]) { // 累计最大利润 profit += prices[j] - prices[i]; } i++; j++; } // 返回最大利润 return profit; } }

package com.lzlg.study.algorithm.new2023.leetcode.stock; / * 卖出股票时有手续费,每次卖出都需要缴纳手续费 * 给定一个整数数组,含义是第i(下标)天的股票价格是数组中的值 * 如果允许买卖多次,持有股票时只能卖,且卖出的一天同时可买入,求最大利润 * * @author lzlg * 2023/9/8 13:05 */ public class StockWithFee { public static void main(String[] args) { System.out.println("===两次交易的情况==="); System.out.println(fastMaxProfit(new int[]{1, 3, 2, 8, 4, 9}, 2)); System.out.println(fastMaxProfit(new int[]{1, 3, 7, 2, 18, 3}, 3)); System.out.println(fastMaxProfit(new int[]{2, 1, 4, 4, 2, 3, 2, 5, 1, 2}, 1)); System.out.println(fastMaxProfit(new int[]{9, 3, 12, 1, 2, 3}, 1)); System.out.println("===一次交易的情况==="); System.out.println(fastMaxProfit(new int[]{1, 3, 7, 5, 10, 3}, 3)); System.out.println(fastMaxProfit(new int[]{1, 3, 7, 5, 10, 11, 3}, 3)); } private static void testNormal() { System.out.println("===两次交易的情况==="); System.out.println(maxProfit(new int[]{1, 3, 2, 8, 4, 9}, 2)); System.out.println(maxProfit(new int[]{1, 3, 7, 2, 18, 3}, 3)); System.out.println(maxProfit(new int[]{2, 1, 4, 4, 2, 3, 2, 5, 1, 2}, 1)); System.out.println(maxProfit(new int[]{9, 3, 12, 1, 2, 3}, 1)); System.out.println("===一次交易的情况==="); System.out.println(maxProfit(new int[]{1, 3, 7, 5, 10, 3}, 3)); System.out.println(maxProfit(new int[]{1, 3, 7, 5, 10, 11, 3}, 3)); } private static void testOptimize() { System.out.println("===两次交易的情况==="); System.out.println(optimizeMaxProfit(new int[]{1, 3, 2, 8, 4, 9}, 2)); System.out.println(optimizeMaxProfit(new int[]{1, 3, 7, 2, 18, 3}, 3)); System.out.println(optimizeMaxProfit(new int[]{2, 1, 4, 4, 2, 3, 2, 5, 1, 2}, 1)); System.out.println(optimizeMaxProfit(new int[]{9, 3, 12, 1, 2, 3}, 1)); System.out.println("===一次交易的情况==="); System.out.println(optimizeMaxProfit(new int[]{1, 3, 7, 5, 10, 3}, 3)); System.out.println(optimizeMaxProfit(new int[]{1, 3, 7, 5, 10, 11, 3}, 3)); } / * 计算股票买卖最大利润,有手续费的情况 * 使用动态规划算法,定义一个买的数组和卖的数组 * * @param prices 股票价格数组 * @param fee 手续费 * @return 最大利润 */ public static int maxProfit(int[] prices, int fee) { // 股票价格数组长度 int length = prices.length; // 创建买数组 int[] buy = new int[length]; // 创建卖数组 int[] sell = new int[length]; // 初始化第一天交易情况 buy[0] = -prices[0]; sell[0] = 0; // 开始遍历 for (int i = 1; i < length; i++) { // 计算买的情况 // 比较[前一天买的利润]和[{前一天如果<卖>的话}减去当前股票价格的利润]中取最大 buy[i] = Integer.max(buy[i - 1], sell[i - 1] - prices[i]); // 计算卖的情况 // 比较[前一天卖的利润]和[{前一天如果<买>的话}加上当前股票价格减去手续费的利润]中取最大 sell[i] = Integer.max(sell[i - 1], buy[i - 1] + prices[i] - fee); } // 返回最大利润 return sell[length - 1]; } / * 计算股票买卖最大利润,有手续费的情况 * 使用动态规划算法,降维和优化 * * @param prices 股票价格数组 * @param fee 手续费 * @return 最大利润 */ public static int optimizeMaxProfit(int[] prices, int fee) { // 初始化前一天交易情况 int prevBuy = -prices[0]; int prevSell = 0; // 开始遍历 for (int i = 1; i < prices.length; i++) { // 计算买的情况 // 比较[前一天买的利润]和[{前一天如果<卖>的话}减去当前股票价格的利润]中取最大 int buy = Integer.max(prevBuy, prevSell - prices[i]); // 计算卖的情况 // 比较[前一天卖的利润]和[{前一天如果<买>的话}加上当前股票价格减去手续费的利润]中取最大 int sell = Integer.max(prevSell, prevBuy + prices[i] - fee); // 计算后,下次循环时更新前一天的交易情况 prevBuy = buy; prevSell = sell; } // 返回最大利润 return prevSell; } / * 计算股票买卖最大利润,有手续费的情况 * 使用动态规划算法,降维和优化 * * @param prices 股票价格数组 * @param fee 手续费 * @return 最大利润 */ public static int fastMaxProfit(int[] prices, int fee) { // 初始化前一天交易情况 int prevBuy = Integer.MIN_VALUE; int prevSell = 0; // 开始遍历 for (int price : prices) { // 计算买的情况 // 比较[前一天买的利润]和[{前一天如果<卖>的话}减去当前股票价格的利润]中取最大 prevBuy = Integer.max(prevBuy, prevSell - price); // 计算卖的情况 // 比较[前一天卖的利润]和[{前一天如果<买>的话}加上当前股票价格减去手续费的利润]中取最大 prevSell = Integer.max(prevSell, prevBuy + price - fee); // 计算后,下次循环时更新前一天的交易情况 } // 返回最大利润 return prevSell; } }

package com.lzlg.study.algorithm.new2023.leetcode.stock; / * 有冷冻期,当天卖股票,只能隔一天再买 * 给定一个整数数组,含义是第i(下标)天的股票价格是数组中的值 * 如果允许买卖多次,持有股票时只能卖,求最大利润 * * @author lzlg * 2023/9/8 14:46 */ public class StockWithFreeze { public static void main(String[] args) { int[] prices = new int[]{1, 2, 3, 0, 2}; System.out.println(maxProfit(prices)); } / * 计算股票最大利润,冷冻期一天 * 使用动态规划算法,不过卖出的时候查看的是前两天的卖出情况 * * @param prices 股票价格数组 * @return 最大利润 */ private static int maxProfit(int[] prices) { int length = prices.length; // 如果只有一天的股票价格,则没有利润 if (length == 1) { return 0; } // 创建买情况数组 int[] buy = new int[length]; // 创建卖情况数组 int[] sell = new int[length]; // 初始化第一天的数据 buy[0] = -prices[0]; sell[0] = 0; // 初始化第二天买的数据,第二天买的情况是要么第一天买,要么第二天买 buy[1] = Integer.max(-prices[0], -prices[1]); // 初始化第二天卖的数据,第二天卖的情况是要么第一天不卖,要么第一天买第二天卖 sell[1] = Integer.max(sell[0], buy[0] + prices[1]); for (int i = 2; i < length; i++) { // 买的情况,要么继承前一天的情况,要么<前两天>卖的利润-当前股票价格 buy[i] = Integer.max(buy[i - 1], sell[i - 2] - prices[i]); // 卖的情况,要么继承前一天的情况,要么<前一天>买的价格+当前股票价格 sell[i] = Integer.max(sell[i - 1], buy[i - 1] + prices[i]); } // 返回最大利润 return sell[length - 1]; } }

package com.lzlg.study.algorithm.new2023.leetcode; / * 字符串匹配(暴力破解和KMP算法) * * @author lzlg * 2023/8/24 13:52 */ public class StringMatch { public static void main(String[] args) { String str = "aaacaaab"; String pattern = "aaab"; System.out.println(index(str, pattern)); System.out.println(kmp(str, pattern)); } / * 字符串匹配,暴力匹配 * * @param str 字符串 * @param pattern 模式串 * @return 模式串在字符串中首次出现的下标 */ private static int index(String str, String pattern) { // 转换为字符数组 char[] strChars = str.toCharArray(); char[] patternChars = pattern.toCharArray(); // i遍历字符串数组 int i = 0; // j遍历模式串数组 int j = 0; // 开始循环 while (i <= strChars.length - patternChars.length) { // 循环模式串 for (j = 0; j < patternChars.length; j++) { // 如果遇到不同的,则直接跳出循环 if (strChars[i + j] != patternChars[j]) { break; } } // 如果j走到了模式串的尾部,则证明匹配成功,返回下标i if (j == patternChars.length) { return i; } i++; } // 循环结束,没有匹配成功,返回-1 return -1; } / * 字符串匹配,KMP算法 * * @param str 字符串 * @param pattern 模式串 * @return 模式串在字符串中首次出现的下标 */ private static int kmp(String str, String pattern) { // 找到匹配公共串数组,其中下标代表的是(i+1)个字符时的匹配公共串长度(数组元素) int[] lsp = lsp(pattern); // 转换为字符数组 char[] strChars = str.toCharArray(); char[] patternChars = pattern.toCharArray(); // i遍历字符串数组 int i = 1; // j遍历模式串数组 int j = 0; // 开始遍历,整个遍历过程中只有j回退,i一直向前 // 循环条件变为模式串的剩余长度小于等于字符串的剩余长度时(此时才能匹配到,如果超出了,则一定匹配不上) while (patternChars.length - j <= strChars.length - i) { // 如果遇到相同字符,则i和j都前进 if (strChars[i] == patternChars[j]) { i++; j++; // 如果遇到不同的字符,且下标j是模式串的头部 } else if (j == 0) { // 此时i前进 i++; } else {// 如果遇到不同的字符,且下标j不是模式串的头部 // 需要根据lsp数组来确定j下次回退的位置(前面字符的匹配公共串长度) j = lsp[j - 1]; } // 找到了匹配位置 if (j == patternChars.length) { // 此时下标为i-模式串长度(也是j) return i - j; } } // 没有找到,则返回-1 return -1; } / * 求模式串的匹配公共串数组 * * @param pattern 模式串 * @return 匹配公共串数组 */ private static int[] lsp(String pattern) { // 转换为字符数组 char[] patternChars = pattern.toCharArray(); // 创建匹配公共串数组,其中下标代表的是(i+1)个字符时的匹配公共串长度(数组元素) int[] lsp = new int[patternChars.length]; // 使用和kmp同样的方式计算匹配公共串长度(数组元素) // 当只有一个字符时,此时前后缀匹配长度为0 lsp[0] = 0; // 下标i代表后缀元素的下标 int i = 1; // 下标j代表前缀元素的下标 int j = 0; while (i < patternChars.length) { // 如果找到相同的字符时,下标即使当前i下标,记录匹配的公共串长度为j+1 if (patternChars[i] == patternChars[j]) { lsp[i] = j + 1; j++; i++; // 如果遇到不同的字符,且j是头部,此时没有共同部分 } else if (j == 0) { lsp[i] = 0; i++; } else {// 如果遇到不同的字符,且j不是头部,此时有共同部分 // 同样的j需要回退到lsp数组中已经在前(j-1)个字符中找到的匹配公共串长度位置 j = lsp[j - 1]; } } return lsp; } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; / * 三数之和,给定一个数组,目标值是0 * 要求找到等于目标值的三个数,并且结果不能重复 * * @author lzlg * 2023/8/24 10:06 */ public class ThreeNumberSum { public static void main(String[] args) { int[] nums = {-4, -1, -1, 0, 0, 1, 1, 2}; List<List<Integer>> result = threeSum(nums); System.out.println(result); } / * 三数之和,思路是先固定一个数字,然后使用两数之和查找和此数字相加等于0的 * * @param nums 数组 * @return 结果列表 */ private static List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); // 将n=3改为4,则是求四数之和 dfs(3, 0, nums.length - 1, 0, nums, new LinkedList<>(), result); return result; } / * 递归方法 * * @param n 数量 * @param i 下标i,指向较小的 * @param j 下标j,指向较大的 * @param target 目标值,固定为0 * @param nums 数组 * @param stack 栈,保存一次结果 * @param result 结果列表 */ private static void dfs(int n, int i, int j, int target, int[] nums, LinkedList<Integer> stack, List<List<Integer>> result) { if (n == 2) { // 求两数之和 twoSum(i, j, nums, target, stack, result); return; } // 只需要留足够查找剩余数的数量就可以了,因此k的范围可以优化 // 如果是三数之和,需要最后留两个,如果是四数之和,需要最后留三个 for (int k = i; k < j - (n - 2); k++) { // 如果前面有相同的数字已经找过了,则不再查找 if (k > i && nums[k] == nums[k - 1]) { continue; } // 固定第一个数 stack.push(nums[k]); // 进行递归调用,数量-1,从k+1开始到j结束找到目标值为(target-nums[k])的两个数 dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result); // 如果递归结束,不满足条件,则弹出栈元素,进行固定下一个数 stack.pop(); } } / * 两数之和方法 * * @param i 下标i * @param j 下标j * @param nums 数组 * @param target 目标值 * @param stack 栈,记录一次结果 * @param result 结果列表 */ private static void twoSum(int i, int j, int[] nums, int target, LinkedList<Integer> stack, List<List<Integer>> result) { while (i < j) { int sum = nums[i] + nums[j]; if (sum > target) { j--; } else if (sum < target) { i++; } else { // 找到了,加入结果中,注意栈中已经添加了固定的一个数 List<Integer> list = new ArrayList<>(stack); list.add(nums[i]); list.add(nums[j]); // 添加到结果集合中 result.add(list); // 移动指针,继续查找下一个 i++; j--; // 未防止重复,则需要判断i和j对应的是否有重复的 // 如果i和之前的重复,则跳过 while (i < j && nums[i] == nums[i - 1]) { i++; } // 如果j和之前(因为是从后向前,因此之前是指j+1)的重复,也跳过 while (i < j && nums[j] == nums[j + 1]) { j--; } } } } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.LinkedList; / * 接雨水问题 * 给定一个数组,其中元素都是大于等于0的,元素的含义是柱子的高度 * 这样的数组能存放多少的雨水? * * @author lzlg * 2023/8/24 12:59 */ public class TrappingRainWater { public static void main(String[] args) { int[] heights = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; System.out.println(trappingRainWater(heights)); heights = new int[]{4, 2, 0, 3, 2, 5}; System.out.println(trappingRainWater(heights)); } / * 接雨水问题,使用一个单调栈(栈顶最小,栈底最大)来解决 * 如果遇到要弹出元素了,则此时需要计算雨水的容量 * * @param heights 柱子高度数组 * @return 雨水容量 */ private static int trappingRainWater(int[] heights) { int volume = 0; // 使用一个栈 LinkedList<Pillar> stack = new LinkedList<>(); // 遍历数组元素 for (int i = 0; i < heights.length; i++) { // 将入栈的柱子是右柱子 Pillar right = new Pillar(heights[i], i); // 入栈前,检查是否有高度小于当前柱子的,如果有则进行弹出 while (!stack.isEmpty() && stack.peek().height < heights[i]) { // 要弹出栈的柱子(中间低洼的) Pillar pop = stack.pop(); // 左边的柱子 Pillar left = stack.peek(); // 左边的柱子有可能没有,故需要判断 // 开始计算雨水容量 if (left != null) { // 宽度=右柱子下标-左柱子下标-1 int width = right.i - left.i - 1; // 高度=左右柱子最低的-中间柱子高度 int height = Integer.min(right.height, left.height) - pop.height; // 计算容量并累加 volume += width * height; } } // 柱子入栈 stack.push(right); } return volume; } / * 柱子 */ static class Pillar { // 柱子高度 int height; // 柱子下标 int i; public Pillar(int height, int i) { this.height = height; this.i = i; } @Override public String toString() { return "Pillar{" + "height=" + height + ", i=" + i + '}'; } } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.*; / * 模拟推特,有三个类:推特类,用户类,推文类 * 推特中有多个用户,用户之间可相互关注,用户可发推文 * * @author lzlg * 2023/9/8 9:07 */ public class Twitter { / * 存储用户数据的map集合 */ final Map<Long, User> userMap = new HashMap<>(); / * 用户发布推文 * * @param userId 用户id * @param tweetId 推文id */ public void postTweet(long userId, long tweetId) { // 如果用户存在,则返回map中用户,否则进行创建 User user = userMap.computeIfAbsent(userId, User::new); // 将推文添加到用户的推文链表中 user.head.next = new Tweet(tweetId, user.head.next); } / * 用户添加关注 * * @param userId 用户id * @param followeeId 关注用户id */ public void follow(long userId, long followeeId) { // 如果用户存在,则返回map中用户,否则进行创建 User user = userMap.computeIfAbsent(userId, User::new); // 创建关注用户 User followee = userMap.computeIfAbsent(followeeId, User::new); // 用户关注集合添加关注用户id user.followeeSet.add(followee.id); } / * 用户取消关注 * * @param userId 用户id * @param followeeId 被取消关注用户id */ public void unfollow(long userId, long followeeId) { // 用户存在,才从关注列表中删除用户 User user = userMap.get(userId); if (user != null) { user.followeeSet.remove(followeeId); } } / * 获取用户和该用户关注的用户的最近10篇推文 * * @param userId 用户id * @return 推文id列表 */ public List<Long> getLastTenTweets(long userId) { // 用户不存在时,返回空列表 User user = userMap.get(userId); if (user == null) { return Collections.emptyList(); } // 使用优先级队列进行推文的排序,根据时间戳从大到小排序 PriorityQueue<Tweet> maxHeap = new PriorityQueue<>( Comparator.comparing(Tweet::getTimestamp).reversed()); if (user.head.next != null) { maxHeap.offer(user.head.next); } for (Long followeeId : user.followeeSet) { Tweet head = userMap.get(followeeId).head; if (head.next != null) { maxHeap.offer(head.next); } } // 推文id列表 List<Long> tweetIds = new ArrayList<>(10); // 计数 int count = 0; // 取10条最近的推文 while (!maxHeap.isEmpty() && count < 10) { Tweet poll = maxHeap.poll(); tweetIds.add(poll.id); // 将下一条推文加入堆中 if (poll.next != null) { maxHeap.offer(poll.next); } count++; } return tweetIds; } / * 用户类,只保留id和关注的用户列表和推文列表,其他属性略 */ static class User { // 用户id long id; // 关注其他用户的id集合 Set<Long> followeeSet = new HashSet<>(); // 推文链表头节点,按照时间戳从大到小排序,即最新的在头部 Tweet head = new Tweet(-1, null); public User(long id) { this.id = id; } } / * 推文类,是单链表节点类,只保留id,其他属性略 */ static class Tweet { // 推文id long id; // 时间戳 long timestamp; // 下个推文 Tweet next; public Tweet(long id) { this.id = id; this.timestamp = System.currentTimeMillis(); } public Tweet(long id, Tweet next) { this.id = id; this.timestamp = System.currentTimeMillis(); this.next = next; } public long getId() { return id; } public long getTimestamp() { return timestamp; } } }

package com.lzlg.study.algorithm.new2023.leetcode; import java.util.Arrays; / * 两数之和,给定一个升序的数组和目标值,返回两个数相加等于目标值的索引 * 要求在内存空间是常量级别的 * * @author lzlg * 2023/8/24 9:38 */ public class TwoDigitSum { public static void main(String[] args) { int[] nums = {1, 2, 3, 4, 5, 6, 7}; int target = 8; System.out.println(Arrays.toString(twoSum(nums, target))); } / * 两数之和,给定一个升序的数组和目标值,返回两个数相加等于目标值的索引 * 要求在内存空间是常量级别的 * 使用两个指针i和j分别指向最小和最大(第一个和最后一个) * 然后遍历数组,将i和j对应的数相加和目标值进行判断 * 如果大于目标值,则j进行减少 * 如果小于目标值,则i进行增加 * 如果等于目标值,则找到了,退出循环并返回结果 * * @param nums 数组 * @param target 目标值 * @return 索引数组 */ private static int[] twoSum(int[] nums, int target) { int i = 0; int j = nums.length - 1; while (i < j) { int sum = nums[i] + nums[j]; // 如果两数之和大于目标值,则减少j if (sum > target) { j--; // 如果小于,则增加i } else if (sum < target) { i++; } else { break; } } return new int[]{i, j}; } }

数据结构

算法

程序员内功

支付宝

微信