算法跟学

LiSir2024-09-122025-03-05

衡量算法好坏

事前分析法

从最差的执行情况进行一个预估计 - 事前分析法

时间复杂度

利用时间复杂度衡量：一个算法的执行，随数据规模的增大，而增长的时间成本
- 不依赖环境因素

大O表示法

渐进上界：从某个常数n0开始，c * g(n) 总是位于f(n)的上方，那么记作O(g(n))

图示：
表示算法执行的最差情况。
已知f(n)去求g(n)
- 表达式中相乘的常量，可以省略：100 * n^2 中的100。
- 多项式中数量规模更小(低次项)的表达式可以省略：f(n) = n^3 + n 中的 n
- 不同底数的对数，渐进上界可以用一个对数函数log_n 来表示。
- 对数的常数次幂可以省略。

常见的大O表示法

按照时间复杂度从低到高排序：

**常数时间复杂度 O(1)**：
- 不依赖于输入数据规模的固定时间操作。
- 例子：访问数组中的某个元素。
**对数时间复杂度 O(log n)**：
- 当数据规模增加时，执行时间以对数方式增加。
- 例子：二分查找算法。
**线性时间复杂度 O(n)**：
- 执行时间随着输入数据规模线性增长。
- 例子：遍历一个数组或列表。
**线性对数时间复杂度 O(n log n)**：
- 经常出现在高效的排序算法中。
- 例子：归并排序或快速排序。
**平方时间复杂度 O(n^2)**：
- 包含两个嵌套循环的情况。
- 例子：冒泡排序、选择排序或插入排序。
**立方时间复杂度 O(n^3)**：
- 三个嵌套循环的情况。
- 例子：一些矩阵乘法算法。
**指数时间复杂度 O(2^n)**：
- 对于每项都有两种选择的情况。
- 例子：解决旅行商问题（TSP）的简单递归算法。
**阶乘时间复杂度 O(n!))**：
- 需要枚举所有可能的情况。
- 例子：列出所有可能的排列组合。

下面是这些复杂度的一个简单图示表示，展示了随着n的增长，不同复杂度函数的增长速度：

Y Axis (Time)
   |
   |                    O(n!)
   |                  /     
   |               /        
   |            /           
   |         /              
   |      /                 
   |    /                    
   |  /                       
   |/                        
   +----------------------------------------------------> X Axis (Input Size n)
   O(1)  O(log n)  O(n)  O(n log n)  O(n^2)  O(n^3)  O(2^n)

在这个图示中，可以看到随着输入规模n的增加，时间复杂度从O(1)到O(n!)逐渐增加。最理想的情况是时间复杂度为O(1)，即无论输入规模如何，算法的执行时间都是固定的；而最糟糕的情况是时间复杂度为O(n!)，这种情况下算法的执行时间会随着输入规模的增加呈阶乘增长。

大Ω表示法

渐进下界：从某个常数n0开始，c * g(n) 总是位于f(n)的下方，那么记作Ω(g(n))

大Ω符号描述了算法在最好情况下的增长行为，给出了算法运行时间的一个下界估计。
例如，如果一个算法的时间复杂度为Ω(n)，这意味着在最好的情况下，该算法至少需要执行一个常数倍的n次操作。

图示：

Θ表示法

渐进紧界：从某个常数n0开始，f(n)总是位于c1 * g(n) 和c2 * g(n)之间，那么记作Θ(g(n))

Θ符号同时考虑了上界和下界，表示算法的渐近紧致界。它描述了算法在平均情况下的增长行为。
例如，如果一个算法的时间复杂度为Θ(n log n)，这意味着在大多数情况下，算法的运行时间将接近于n log n。

图：

空间复杂度

与时间复杂度类似，一般也使用大O表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本。

排序算法

计数排序

基本思路

计算数组中每个元素的出现次数，并使用这些计数来确定元素在排序结果中的位置。通过这种方式，可以有效地对数据进行排序，避免了传统比较排序所带来的时间复杂度。

计数排序的步骤

确定范围：
- 找到待排序元素的最小值和最大值。这会帮助确定计数数组的大小。
创建计数数组：
- 根据范围创建一个计数数组，数组的长度等于最大值与最小值之间的差值加一。计数数组的每个索引表示待排序数值的每一个可能值。
统计元素出现次数：
- 遍历原始数组，并在计数数组中相应的索引位置上加一。这将统计每个数字在原始数组中出现的次数。
累加计数：
- 对计数数组进行累加，将计数转换为每个元素的最终位置的索引。这一步的作用是将当前元素的出现次数转化为该元素在排序数组中的最终位置。
构建输出数组：
- 创建一个输出数组，按照计数数组中的信息将原始数组中的元素放入正确的位置。
输出结果：
- 将输出数组中的元素一一复制回原始数组（可选，如果存在输出数组）。

总结

优点：
- 时间复杂度是线性的 O(n+k)O(n+k)，相比于 O(nlog⁡n)O(nlogn) 的比较排序，效率更高。
- 稳定性：可以保持相同元素的相对顺序。
缺点：
- 适用范围有限，只适合处理整数或可以转化为离散数字的情况。
- 对于范围大的整数，空间复杂度高，可能导致空间资源浪费。

    public static void CountingSort(int[] n) {
        //算法：计数排序
        //1.确定排序元素的最小值和最大值
        int max = Integer.MIN_VALUE;// 设置最大值为负无穷大
        int min = Integer.MAX_VALUE;// 设置最小值为正无穷大
        for(int num:n){
            if(num>max){
                max = num;
            }
            if(num<min){
                min = num;
            }
        }
        //2.创建计数数组 - 数组的长度等于最大值与最小值之间的差值加一
        int range = max - min + 1;
        int[] count = new int[range];

        //3.统计元素出现的次数
        for (int i = 0; i < n.length; i++) {
            count[n[i]-min]++; //使用偏移量来处理，防止数组中有元素值超出计数数组索引范围
        }
        //4.输出排序后的结果
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            //控制数打印的次数，保证是在count出现的次数 所以这里要小于count[i]
            for (int j = 0; j < count[i]; j++) {
                n[index++] = i + min; //因为上面使用了偏移量，下面就将偏移量在还原回去
            }
        }
        //打印结果
        for(int num : n){
            System.out.print(num+" ");
        }
}

冒泡排序

基本思路

每次比较两个相邻的元素，如果他们的顺序不符合要求，就交换他们的位置。

从小到大：也就是说越大的越在后面。
从大到小：也就是说越小的越在后面。

原理：每进行一趟只能将一个归位，也就是说，n个数进行冒泡排序，需要进行n-1趟排序

冒泡排序的步骤

比较相邻元素：从数组的第一个元素开始，将当前元素与下一个相邻的元素进行比较。
交换位置：如果前一个元素大于后一个元素（在升序排序的情况下），则交换这两个元素的位置。如果是降序排序，则条件相反，即前一个元素小于后一个元素时进行交换。
继续比较：移动到下一组相邻元素，重复步骤1和2。当到达数组的末尾时，称作完成了一轮“冒泡”。此时，最大的元素（对于升序排列）会位于数组的最后一个位置。
重复过程：重复上述过程，但是不包括已经排好序的最后一个元素。每完成一轮冒泡，未排序部分的最大值就会被移动到正确的位置。
检查是否需要继续：当某一轮冒泡过程中没有发生任何交换时，说明数组已经是有序的，可以提前结束排序过程。
结束排序：当所有元素都按照正确的顺序排列后，排序完成。

总结

时间复杂度

最坏情况：O(n^2)，当数组完全逆序时，需要进行最多的比较和交换操作。
最好情况：O(n)，当数组已经是有序的时，只需进行一次遍历来确认所有元素都已经正确排序。
平均情况：O(n^2)，大多数情况下，冒泡排序的时间复杂度接近于最坏情况。

适用场景

小规模数据集：对于小规模的数据集，冒泡排序的性能是可以接受的。
教学和演示：由于其实现简单，冒泡排序常用于教学和算法演示。
部分有序数据：如果数据部分有序，冒泡排序可以在较少的比较和交换操作下完成排序。

public class maopaoSort {
    public static void maopaoSort(int[] arr) {
                boolean swapped;
                int n = arr.length;
                do {
                    swapped = false;
                    for (int i = 1; i < n; i++) {
                        if (arr[i - 1] > arr[i]) {
                            // 交换元素
                            int temp = arr[i - 1];
                            arr[i - 1] = arr[i];
                            arr[i] = temp;
                            swapped = true; // 发生了交换
                        }
                    }
                    n--; // 每次循环后，最后的元素已确定，因此减少比较范围
                } while (swapped); // 如果没有发生交换，说明数组已经排序完成

                // 输出排序后的数组
                System.out.println("排序完成后的数组:");
                for (int num : arr) {
                    System.out.print(num + " ");
                }
            }
class Test1 {
    public static void main(String[] args) {
        int[] arr = {3,2,1,6,5,4};
        maopaoSort.maopaoSort(arr);
    }
}

快速排序

基本思路

快速排序是一种分治算法，通过选择一个基准值（pivot），将数组分为两部分：一部分的所有元素都小于或等于基准值，另一部分的所有元素都大于基准值。
递归地对这两部分进行同样的操作，直到整个数组有序。

·快速排序的步骤

**主方法 main**：
- 定义一个待排序的数组 arr。
- 调用 FastSort 方法进行排序。
- 输出排序后的数组。
**快速排序方法 FastSort**：
- 参数：数组 arr，起始索引 low，结束索引 high。
- 终止条件：如果 low 小于 high，继续排序；否则，终止递归。
- 分区：调用 partition 方法获取基准值的位置 pi。
- 递归调用：分别对基准值左侧和右侧的子数组进行递归排序。
**分区方法 partition**：
- 随机选择基准值：生成一个随机索引 RandomIndex，将该索引处的值与数组的最后一个元素交换。
- 设置基准值：将最后一个元素设为基准值 pivot。
- 初始化指针：i 指向比基准值小的最后一个元素的位置，初始值为 low - 1。
- 遍历数组：从 low 到 high - 1 遍历数组，如果当前元素小于或等于基准值，将 i 增加 1 并交换 arr[i] 和 arr[j]。
- 调整基准值位置：将基准值放到正确的位置，即 i + 1，并返回该位置。
**交换方法 swap**：
- 参数：数组 arr，需要交换的两个索引 l 和 r。
- 交换操作：使用临时变量 temp 交换 arr[l] 和 arr[r] 的值

总结

快速排序：通过分治法将数组分为两部分，递归地对这两部分进行排序。
优化方法：随机选择基准值、三数取中法、小数组时使用插入排序、尾递归优化、非递归实现。
时间复杂度：最佳和平均情况为 O(nlog⁡n)O(nlogn)，最坏情况为 O(n2)O(n2)。
空间复杂度：递归实现为 O(log⁡n)O(logn)，非递归实现也为 O(log⁡n)O(logn)。

import java.util.Random;

public class FastSort {
    static Random random = new Random();

    public static void FastSort(int[] arr, int low, int high) {
        if (low < high) {
            // 定基准值位置 - 找基准值索引
            int pi = partition(arr, low, high);
            // 递归调用，分别处理基准值左侧和右侧的剩余数组
            FastSort(arr, low, pi - 1);
            FastSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        //为了提高算法效率，这里选择随机索引来进行优化
        int RandomIndex = low + random.nextInt(high - low + 1);
        //把随机索引处的值，和最后一个元素交换位置
        int temp = arr[high];
        arr[high] = arr[RandomIndex];
        arr[RandomIndex] = temp;

        // 1. 定基准数
        int pivot = arr[high];
        int i = (low - 1); // 指向比基准小的最后一个元素的位置

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于pivot
            if (arr[j] <= pivot) {
                i++;

                // 交换arr[i]和arr[j]
                swap(arr, i, j);
            }
        }
        // 将基准元素放到正确的位置 :分析：
        // 如果没有比基准值小的则不会发生交换，此时基准值就是整个数组中的最小值，按从小到大排序，直接可将基准值定位在第一个元素位置。也就是index = -1 + 1 =0
        temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    //交换函数
    public static void swap(int[] arr, int l, int r) {

        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {5, 2, 3, 1};
        int n = arr.length;

        FastSort(arr, 0, n - 1);

        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

数组

集合、列表、数组

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

数组下标都是从0开始的。
数组内存空间的地址是连续的
正是因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
数组的元素是不能删的，只能覆盖。
针对二维数组：

结论：

C++中二维数组在地址空间上是连续的。

数组的操作

读取：通过索引来访问，一般从0开始。读取的时间复杂度是O(1)
查找：从开始向后遍历查找，最坏的时间复杂度是O(N)
插入：分为在末尾进行插入，和在其他位置进行插入。
删除：当删除某一个元素时，会造成位置空缺，这时需要我们进行填补操作
当数组长度为n时，我们删除第一个元素，共需要1 + (n - 1) = n 步，1是删除操作占一步，而n-1是我们移动所占用的操作次数，时间复杂度是O(N)

数组有关的基础算法题

寻找数组中心索引

详见LeetCode：

https://leetcode.cn/problems/find-the-middle-index-in-array/description/

https://leetcode.cn/problems/find-pivot-index/

解法1

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMiddleIndex = function(nums) {
    if(nums.length === 1){
        return 0
    }
    //计算出数组的总和，和差法计算
    //初始化左侧和
    let leftSum = 0;
  let sum =  nums.reduce((pre,cur)=> pre + cur,0)
    for(let i = 0 ; i< nums.length;i++){
        if(2 * leftSum == sum - nums[i] ){  --> //题中返回i的条件是左边总和等于右边。所以根据这个这个等式可以得出这个条件
            return i;
        }
        //计算左侧和
        leftSum +=nums[i];
    }
    return -1
};

解法2:

左加右减，判断是否相等

var findMiddleIndex = function(nums) {
    //算左侧和，算总和
    let left = 0, right = _.sum(nums)
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i]
        right -= num
        if (left === right) {
            return i
        }
        left += num
    }
    return -1
};

搜索插入位置

解法1

最简单的思路

如果数组中的值大于或者等于target，直接return
如果全部遍历完证明target是最大的数，直接插入末尾

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=target) return i;
        }
        return nums.length;
    }
}

二分查找

算法描述

二分法也被称为折半查找。

题目中如果出现：1.数组为有序数组(升序排列或降序)，2.数组中无重复元素。就可以考虑是不是可以使用二分法了。

因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

二分法第一种写法

（版本一）左闭右闭区间

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid - 1;
            }
        }
        // 未找到目标值
        return -1;
    }
}

二分法第二种写法

（版本一）左闭右开区间

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

在数组：1,2,3,4,7,9,10中查找元素2，如图所示：（注意和方法一的区别）

704.二分查找1

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid;
            }
        }
        // 未找到目标值
        return -1;
    }
}

算法性能

时间复杂度

最坏情况：O(log_n) 该算法的函数:
最好情况：如果目标元素位于数组中央，只需循环1次就能找到O(1)

空间复杂度

需要常数个指针i，j，m，因此额外占用空间是O(1)

移除元素

思路

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素，第二个for循环更新数组。

删除过程如下：

27.移除元素-暴力解法

代码如下：

package 数组算法;

public class RemoveElement {
    //移除数组中某个元素，要知道，数组在内存中是连续存储的，不可以直接进行删除，只能覆盖。
    //解法一：两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
    public static int removeElement(int[] nums, int val) {
        int n = nums.length;
        //遍历数组
        for (int i = 0; i < n; i++) {
            // 发现需要移除的元素，就将数组集体向前移动一位
               if(nums[i]  == val ) {
                   //更新元素
                   for (int j = i + 1; j < n; j++) {
                       nums[j - 1] = nums[j];
                   }
                   n--;
                   i--;//因为下标i以后的都向前移动了一位，所以i也向前移动一位，保证一致
               }

        }
        return n;
    }

    public static void main(String[] args) {
        int nums[] = {0,1,2,3,3,0,4,2};
        System.out.println(removeElement(nums,2));
    }
}

双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

过程如下：

27.移除元素-双指针法

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0, fast = 0; //一对夫妇，原本都是零起点
    while (fast < numsSize) {   //但是有一个跑得快，一个跑得慢
        if (nums[fast] != val) {    //于是跑得快的那个先去寻找共同目标
            nums[slow] = nums[fast];    //如果找到了，就送给跑得慢的那个
            slow++;     //然后跑得慢的那个也就离目标近一点
        }
        fast++; //但是不管是否找得到，跑得快的那方都一直奔跑到生命的尽头
    }
    return slow;    //最终留下跑得慢的一方
}

有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路

暴力排序

最直观的想法，莫过于：每个数平方之后，排个序，代码如下：

class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

双指针法

数组其实是有序的，只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

如动画所示：

代码如下：

package 数组算法;
//算法：有序数组的平方。
public class ArrSqrt {
    //最基本想法：直接暴力排序，循环平方后再排序
    public static int[] arrsqrt(int nums[]) {
        int n = nums.length;
        //定义一个接受结果的数组
        int result[] = new int[n];
        //定义三个指针
        int i = 0;
        int j = n - 1;
        int k = n - 1;
        //遍历原数组
        while (i <= j) {
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                result[k--] = nums[j] * nums[j];
                j--;
            } else {
                result[k--] = nums[i] * nums[i];
                i++;
            }
        }
            return result;
    }
    public static void main(String[] args) {
        int nums[] = {-7,-3,2,3,11};
        int[] arrsqrt = arrsqrt(nums);
        for(int num:arrsqrt){
            System.out.print(num + " ");
        }
    }
}

二维数组

旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

LeetCode：https://leetcode.cn/leetbook/read/array-and-string/clpgd/

https://leetcode.cn/problems/rotate-image/description/

解法1

先沿着对角线进行变换，在水平进行每一行进行反转

var rotate = function(matrix) {
    let n = matrix.length;
    
    // Step 1: 转置矩阵（即沿着主对角线交换元素）
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    // Step 2: 反转每一行以完成旋转
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n / 2; j++) {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
};

字符串

字符串是由零个或多个字符组成的有限序列。一般记为 s = a1a2…an。它是编程语言中表示文本的数据类型。

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

leetCode地址：https://leetcode.cn/leetbook/read/array-and-string/ceda1/

横向扫描法

主代码部分：

首先选择字符串数组中的第一个元素作为开始比较的起始字符串，接着循环更新前缀字符串，如果前缀字符串为0则直接返回空字符串即可。

函数部分：

接着编写字符串比较函数，接收两个字符串作为参数

比较逻辑是：以长度最小的字符串的长度作为遍历条件，并设置一个记录索引，该索引(index)表示 从字符串起点到该索引位置的字符都相同 初始化为0

依次判断两个字符串当前索引位置是否相同，如果不同则跳出当前循环，index++

最终返回其中一个字符串从0 到 index 截取出来的子字符串作为前缀字符串

var longestCommonPrefix = function(strs) {
    // 遍历数组，更新最长前缀
    let prefix = strs[0];
    for(let i = 1; i < strs.length; i++){
        prefix = findCommonPrefix(prefix, strs[i]);
        if(prefix.length == 0){
            return "";
        }
    }
    return prefix;
};

// 编写比较函数
function findCommonPrefix(str1, str2) {
    // 找出字符串1和字符串2中长度最小的那个, 作为遍历的条件
    let len1 = str1.length;
    let len2 = str2.length;
    let minLen = Math.min(len1, len2);
    // 使用index来记录最终它们公共的位置索引
    let index = 0;
    
    while(index < minLen && str1.charAt(index) === str2.charAt(index)) {
        index++;
    }

    return str1.substring(0, index);
}

最长回文子串

中心回文

给你一个字符串 s，找到 s 中最长的回文子串。

LeetCode:https://leetcode.cn/leetbook/read/array-and-string/conm7/

//使用中心回文
var longestPalindrome = function(s){
    if(s.length <= 1){
        return s;
    }

    let start = 0;
    let end = 0;
    for(let i=0;i<s.length;i++){
    //处理当我们的s是奇数个时，找中心
    let len_js = centerFunction(s,i,i);
    //当s是偶数个时，我们用中间两个作为中间数处理
    let len_os = centerFunction(s,i,i + 1);
    //找到我们最大的那个回文串的长度
    let Max_hw = Math.max(len_js,len_os);
    //计算起始点
    //比较当前回文串长度 和之前的长度 --- 因为我们要最大的回文串，所以这里以大于作为条件
    if(Max_hw > end - start){
        //下面计算从中心向两边移动的距离
        start = i - Math.floor((Max_hw - 1) / 2);
        end = i + Math.floor(Max_hw / 2);
    }
    }
        return s.substring(start,end + 1)
}

//中心回文处理函数
function centerFunction(s,left,right){
    //原理就是，我们从中心拓展，逐渐向两边寻找,left是左边，right是右边
    //回文回文，最重要的一点就是，中心左边和右边需要一样的字符
    while(left >= 0 && right < s.length && s[left] === s[right]){
        //满足这个条件就继续下一个，记住中心向两边，所以
        left--;
        right++;
    }
    //最终返回中心回文的长度，题目中要求我们找到最大的中心回文字符串
    //这一步计算满足条件的回文串长度
    return right - left -1
}

解析:

为什么第二个函数返回right - left -1？
- left 和 right 的移动：
  - 在 while 循环中，left 向左移动，right 向右移动，直到 s[left] 和 s[right] 不相等，或者 left 和 right 超出字符串的边界。
  - 当循环结束时，left 和 right 分别指向回文子串的左右边界之外的位置。
- 回文子串的长度：
  - 回文子串的实际长度应该是 right - left - 1，因为 left 和 right 已经移动到了回文子串的边界之外。
  - 例如，如果 left 最终停在 i - 1，right 最终停在 i + 1，那么回文子串的长度应该是 (i + 1) - (i - 1) - 1 = 1。
为什么if条件内要写成那样子？
- 为什么是 (len - 1) / 2？
  1. 奇数长度回文子串：
  - 对于一个奇数长度的回文子串，中心位置 i 是一个具体的字符。
  - 回文子串的长度是 len，那么从中心位置向左和向右扩展的步数是相同的，即 (len - 1) / 2。
  - 例如，如果 len = 5，那么向左和向右各扩展 (5 - 1) / 2 = 2 步。
  2. 偶数长度回文子串：
  - 对于一个偶数长度的回文子串，中心位置 i 实际上是一个“虚拟中心”，位于两个字符之间。
  - 回文子串的长度是 len，那么从中心位置向左和向右扩展的步数仍然是 (len - 1) / 2。
  - 例如，如果 len = 4，那么向左和向右各扩展 (4 - 1) / 2 = 1.5 步。由于步数必须是整数，Math.floor 会将其向下取整为 1 步。
  3. 统一公式：
  - 无论是奇数长度还是偶数长度，(len - 1) / 2 都可以统一表示从中心位置向左扩展的步数。
  - Math.floor 的作用是确保步数是整数，避免偶数长度时出现小数。
  为什么是 len / 2？
  1. 奇数长度回文子串：
  - 对于奇数长度的回文子串，从中心位置向右扩展的步数也是 (len - 1) / 2。
  - 但由于 len / 2 和 (len - 1) / 2 在奇数情况下是等价的（因为 len 是奇数，len / 2 会自动向下取整），所以可以直接用 len / 2。
  2. 偶数长度回文子串：
  - 对于偶数长度的回文子串，从中心位置向右扩展的步数是 len / 2。
  - 例如，如果 len = 4，那么向右扩展 4 / 2 = 2 步。
  3. 统一公式：
  - len / 2 可以直接表示从中心位置向右扩展的步数，无论是奇数长度还是偶数长度。
  为什么 (len - 1) / 2 和 len / 2 不同？
  - (len - 1) / 2 用于计算向左扩展的步数，因为它需要处理偶数长度时中心位置是“虚拟”的情况。
  - len / 2 用于计算向右扩展的步数，因为它可以直接表示步数，不需要额外减 1。
  - (len - 1) / 2 是为了统一处理奇数长度和偶数长度的情况，确保向左扩展的步数正确。
  - len / 2 是向右扩展的步数，直接使用即可。
  - 这种设计是为了让代码能够同时处理奇数长度和偶数长度的回文子串，而不需要分别写逻辑。

衡量算法好坏

事前分析法

时间复杂度

大O表示法

常见的大O表示法

大Ω表示法

Θ表示法

空间复杂度

排序算法

计数排序

基本思路

计数排序的步骤

总结

冒泡排序

基本思路

冒泡排序的步骤

总结

快速排序

基本思路

·快速排序的步骤

总结

数组

集合、列表、数组

数组理论基础

数组的操作

数组有关的基础算法题

寻找数组中心索引

解法1

解法2:

搜索插入位置

解法1

二分查找

算法描述

二分法第一种写法

二分法第二种写法

算法性能

移除元素

思路

暴力解法

双指针法

有序数组的平方

思路

暴力排序

双指针法

二维数组

旋转矩阵

解法1

字符串

最长公共前缀

横向扫描法

最长回文子串

中心回文

为什么是 (len - 1) / 2？

1. 奇数长度回文子串：

2. 偶数长度回文子串：

3. 统一公式：

为什么是 len / 2？

1. 奇数长度回文子串：

2. 偶数长度回文子串：

3. 统一公式：

为什么 (len - 1) / 2 和 len / 2 不同？

为什么是 `(len - 1) / 2`？

为什么是 `len / 2`？

为什么 `(len - 1) / 2` 和 `len / 2` 不同？