前缀和算法篇:解决子数组累加和问题

在这里插入图片描述

1.前缀和原理

那么在介绍前缀和的原理之前,那么我们先来说下前缀和最基本的一个应用场景,那么就是如我们标题所说的子数组累加和问题,那么假设我们现在有一个区间为[L,R]的数组,那么我们要求的其中子数组比如[L,i]或者[i,m] (L<=i<=m<=R)的累加和,那么我们最暴力的方法就是遍历一遍数组的子区间累加得到该子数组的累加和,那么我们每次求出一个累加和那么也就意味着要遍历一次数组,那么我们能否以一个较小的代价就能够得到子数组的累加和,那么这就是我们前缀和所应用的一个最基本的场景。

假设我们有了左边界L(或者说数组下标为0的位置)到这个数组中任意位置i的一个累加和,那么我们计算其中的子数组比如[i,m] (i<m)的累加和,那么我们只需要L到i的累加和sum1,以及L到m的累加和sum2,那么我们用sum2-sum1则是我们子数组[i.m]的累加和,那么这就是我们前缀和得到子数组累加和的一个原理

那么我们根据这个原理,如果我们加载一个前缀和数组sum,该数组的每一个的位置表示从左区间L到该位置的累加和,那么有了这个数组之后,我们可以计算区间[L,R]中任意一个子数组[i,m] (i<=m)的累加和假设其累加和为ant,那么公式则是ant=sum[m]-sum[i-1]。

所以现在的关键就是我们怎么得到前缀和数组,那么我们可以采取一个递推的思路加载我们的前缀和数组sum,那么最开始我们肯定只有左区间L到L的前缀和,它的前缀和就是数组下标为0的值,然后我们要扩展L到1的前缀和,那么我们就通过前面计算好的L到L的前缀和加上arr[1]的值就是L到1,那么计算L到2,那么我们手上有计算好的L到1的前缀和,那么我们在这个L到1的前缀和的基础上加上arr[2],那么同理现在要计算L到i位置,那么就用sum[i-1]+arr[i]即可,所以我们的代码实现可以采取一个循环的方式来得到我们的前缀和数组中的每一个位置的值。
在这里插入图片描述

但是这里我们知道我们计算[i,m] (i<=m),我们公式是sum[m]-sum[i-1],那么我们知道在数组中我们的左边界L就是为0,那么我们如果要计算[L,i]的累加和的话,那么公式就是sum[i]-sum[L-1],而这里L是0,那么L-1就是-1,可是对于数组来说,访问不到下标为-1的前缀和数组,所以这里为了处理边界,我们会将区间[L,R]整体往右平移一个单位[L+1,R+1],也就是说在加载我们的前缀和数组的时候,我们理解为我们的原数组内容的开头的左侧多出了一个0,然后再加载我们的前缀和数组,这样[L,i]的累加和就是sum[i+1]-sum[L]

代码模版:

#include<iostream>
#include<vector>
using namespace std;
#define N 8
int main()
{vector<int> arr={0,1,2,3,4,5,6};vector<int> sum(N,0);for(int i=1;i<sum.size();i++){sum[i]=sum[i-1]+arr[i-1];}return 0;
}

2.前缀和应用

题目一:求子数组累加和 难度:EZ

题目:现在给你一个数组,数组中的元素有正有负,让你求其中区间为[L,R]的子数组的累加和。

题目思路:那么这个题就是我们上文所说的前缀和最基本的应用场景,纯纯模版题,那么就套我们的模版来做即可

代码实现:

class solution
{int count(vector<int>& arr,int l,int r){vector<int> sum(arr.size()+1,0);for(int i=1;i<sum.size();i++){sum[i]=sum[i-1]+arr[i-1];}return sum[r+1]-sum[l];}
}

题目二:求累加和为aim的最长子数组 难度:MID

题目:现在给一个数组,数组中的元素有正有负,那么我们要求这个数组中累加和为aim,并且最长的子数组,返回这个最长子数组的长度。

题目思路:那么这里我们要求累加和为aim且长度最长的子数组,那么这里我们看到有关于子数组问题的,那么一定就要敏感,因为子数组意味着连续区间,那么它可以应用我们的滑动窗口或者前缀和,但是具体题目得具体分析。

那么这里我们可以这样想,假设我们这个数组的整体的区间为[L,R],那么我们就求这个区间上每一个位置i,求以该位置作为子数组结尾往左延伸的并且累加和为aim的子数组的最长长度,那么我们有了每一个位置以该位置结尾的子数组的最长长度,那么我们在综合每一个位置的长度得到最长的,那么这个最长的长度就是我们整个区间[L,R]所能够得到的累加和为aim的最长子数组长度。

那么现在问题就变为了我们怎么求每个位置的以该位置结尾的累加和为aim的最长子数组呢?那么我们可以首先加载一个该数组的前缀和数组,那么我们对于每一个L到i位置区间的前缀和,我们可以以该视角去理解该区间的前缀和

我们假设我们L到i位置区间的前缀和为sum,那么我们这里的sum前缀和可以由两部分得到,假设我们在这个L到i位置区间任取一个点位m,那么我们这里L到i区间的前缀和可以等价于L到m位置的前缀和加上我们的m到i位置累加和得到,那么我们按照这个理解的话,那么求以这个数组中任意以i位置结尾往左延伸的累加和为aim的子数组,我们可以看成我们L到i区间的前缀和sum是由以该i位置结尾往左延伸到m位置的累加和aim加上L到m的前缀和sum-aim得到,那么我们要往左延伸的更长,那么意味着我们的前缀和sum-aim的长度就得更短,那么所谓更短就是我们这个前缀和sum-aim出现的位置更靠前,那么我们就可以从左往右加载我们的前缀和数组的时候同时通过一个哈希表其中key是前缀和,value值是该前缀和第一次出现从左侧第一次出现的位置,那么这个位置就是我们sum-aim最靠前的位置

那么由于我们是在加载我们前缀和的同时,计算好我们当前i位置的前缀和后如果是以第一次出现的话立马会添加进哈希表当中计算好i位置的前缀和,那么我由于我们是从左往右加载我们的前缀和同事将计算好的前缀和添加到哈希表中,那么也就意味着我们此时在哈希表中记录的第一次出现的前缀和的位置一定是在i位置的左侧而不是右侧,因为我们还未计算i位置右侧的前缀和,所以我们计算好i位置的前缀和,然后立马查询哈希表计算出该位置往左延伸累加和为aim的最长子数组,然后在每个位置综合得到整个区间累加和为aim的最长子数组。
在这里插入图片描述

代码实现:

class Solution
{
public:// 计算数组中累加和为aim的最长子数组的长度int count(vector<int>& arr, int aim){vector<int> sum(arr.size() + 1, 0); // 前缀和数组,大小比原数组多1int ans = 0; // 存储最长子数组的长度unordered_map<int, int> value; // 哈希表,存储前缀和及其首次出现的索引value[0] = 0; // 初始化哈希表,前缀和为0时的索引为0for (int i = 1; i < sum.size(); i++){sum[i] = sum[i - 1] + arr[i - 1]; // 计算前缀和// 如果当前前缀和已经存在于哈希表中,更新其索引为最新位置// 但实际上,我们不需要更新,因为我们只关心第一次出现的位置// 检查是否存在前缀和为sum[i] - aim的索引if (value.find(sum[i] - aim) != value.end()){// 如果存在,计算当前子数组的长度,并更新最长长度ans = max(ans, i - value[sum[i] - aim]);}// 如果当前前缀和不在哈希表中,则添加进去if (value.find(sum[i]) == value.end()){value[sum[i]] = i;}}return ans;}
};

题目三:求子数组累加和为aim的个数 难度:MID

题目:现在我们有一个数组,那么我们要求这个数组中子数组累加和为aim的个数。

题目思路:那么在上一个题目,我们就说了,我们一个区间为[L,R]的一个数组的累加和假设为sum,那么它的累加和可以看做我们前缀和L到i位置的累加和加上i到R位置的累加和,那么这里我们的思路就是求这个数组中每个位置结尾往左延伸累加和为aim的数量,然后累加每个位置得到以该位置结尾的累加和为aim的数量就是我们整个数组累加和为aim的子数组的数量。

那么我们求每个位置i以该位置结尾的累加和为aim的数量,那么我们知道L到i区间的前缀和sum可以看做由L到m位置的前缀和加上m到R位置的前缀和,那么我们这里统计我们在L到i位置处的前缀和为sum-aim的数量有多少个,那么就可以得到以i位置为结尾的累加和为aim的子数组有多少个

那么我们实现则是在加载前缀和的同时记录我们的哈希表,我们哈希表则记录前缀和出现的次数,那么我们在从左往右加载我们前缀和数组的同时,然后计算该位置处的累加和为aim的子数组的数量,因为我们是从左往右遍历数组,然后更新我们的哈希表,那么此时记录在哈希白中的各种前缀和出现的次数一定都是在i位置之前的,因为i位置之后的前缀和我们还未被记录到哈希表当中去,所以我们边加载我们的前缀和数组,边查询我们的哈希表得到每个位置以该位置结尾的累加和为aim的子数组的数量

代码实现:

class Solution
{
public:// 计算数组中子数组累加和为aim的个数int count(vector<int>& arr, int aim){vector<int> sum(arr.size() + 1, 0); // 前缀和数组,大小比原数组多1int ans = 0; // 存储满足条件的子数组个数unordered_map<int, int> value; // 哈希表,存储前缀和及其出现次数value[0]++; // 初始化哈希表,前缀和为0的初始出现次数为1for (int i = 1; i < sum.size(); i++){sum[i] = sum[i - 1] + arr[i - 1]; // 计算当前位置的前缀和// 在更新哈希表之前,先查询是否存在前缀和为sum[i] - aim// 如果存在,说明从某个位置到当前i位置的子数组累加和为aimans += value[sum[i] - aim];// 更新哈希表中当前前缀和的出现次数value[sum[i]]++;}return ans;}
};

题目四:求正负数相等的子数组的最大长度 难度:MID

题目:我们现在会有一个数组,那么这个数组的元素包含正负数以及零,那么我们要求求出满足正数的数量与负数的数量相等的子数组的最长长度。(注:这里只关心正数与负数是否相等,不算数值0哦)

例:[12,-1,-6,0,3,6]

其中最长子数组是区间为[0,4]的子数组[12,-1,-6,0,3]以及区间[1,5]的子数组[-1,-6,0,3,6],长度都为5

题目思路:那么这里我们分析题意,那么这里我们只要寻找正数以及负数数量相等的子数组,那么这道题的关键就是我们不关心这个数组中各个数的数值而只关心该数的一个状态是正数还是负数还是0,所以我们就得将我们的原数组首先给预处理一下,我们原数组的各个数值的正数比如12或者6,那么在这道题中无论他的数值在大或者在小,那么他们都是同一类数,也就是正数,所以我们预处理得到的数组只有这个数的状态信息没有数值信息,所以我们这里将我们的正数转换为1,负数转换为-1,0就是0,比如原数组为[12,-1,-6,0,3,6],那么经过预处理之后得到数组是[1,-1,-1,0,1,1],那么我们接着对预处理数组加载一个前缀和数组

那么该对于区间[L,R]的数组来说,如果该位置i的前缀和为0,那么说明该区间的正负数的数量相等,整个区间就记录答案,,若位置i的前缀和不为0,那么说明这个区间[L,i]中的数的分布是负数是不等于正数的,那么也就是说我们该区间中还有可能有正负数的数量相等的区间存在,因为我们知道一个区间[L,R]的前缀和可以由区间[L,m]的前缀和加上[m,R]的前缀和,所以我们这里的思路就是求每个位置以该位置为结尾往左延伸满足正数的数量等于负数的数量的最长子数组,那么最后我们求得每个位置满足要求的最长长度,那么综合就得到整个区间满足要求的最长子数组长度

所以这里如果我们的i位置的前缀和不为0,假设i位置的前缀和为sum,那么我们找在i位置之前的前缀和为sum出现的最靠前的位置,因为sum+0=sum,那么找到i位置之前最靠前的sum位置m,那么m到i的累加和就是0,那么就是以i位置结尾往左延伸的正负数数量相等的最长子数组

所以我们在加载我们的前缀和数组的时候同时将每个前缀和第一次出现的位置记录在我们的哈希表,那么我们在加载计算出我们该i位置的前缀和的同时,那么我们查询我们的哈希表,那么此时哈希白记录的是前缀和第一次出现的位置,由于我们是从左往右加载前缀和数组的同时查询我们的哈希表,那么我们这里i位置右侧位置的前缀和都还未被计算添加哈希表中,所以意味着我们在哈希表当中记录的第一次出现的前缀和都是在i位置的左侧的,所以我们就可以查询得到我们以i位置结尾的满足要求的最长子数组,综合每个位置得到答案,那么该题经过预处理之后就和第二题是一样的了。

代码实现:

class Solution
{
public:int count(vector<int>& arr){// 预处理数组,将正数转为1,负数转为-1,零保持为0for (int i = 0; i < arr.size(); i++){if (arr[i] > 0){arr[i] = 1;}else if (arr[i] < 0){arr[i] = -1;}// 零保持为0,不需要显式处理}vector<int> sum(arr.size() + 1, 0); // 前缀和数组,大小比原数组多1int ans = 0; // 存储最长子数组长度unordered_map<int, int> value; // 哈希表,存储前缀和及其首次出现的位置value[0] = 0; // 初始化,前缀和为0的初始位置为0for (int i = 1; i < sum.size(); i++){sum[i] = sum[i - 1] + arr[i - 1]; // 计算当前位置的前缀和// 如果当前前缀和已经在哈希表中,则更新最长子数组长度// 如果 sum[i] 已经存在,则不更新 value[sum[i]],以保持最左边的位置if (value.find(sum[i]) == value.end()){value[sum[i]] = i; // 记录前缀和首次出现的位置}// 检查是否存在前缀和为 -sum[i],即 sum[i] + (-sum[i]) = 0// 这意味着从 value[-sum[i]] 到 i 的子数组满足条件if (value.find(-sum[i]) != value.end()){ans = max(ans, i - value[-sum[i]]);}}return ans;}
};

题目五:求表现良好的最长时间段 难度:MID

题目:那么这里我们会给一个数组,数组的每一个元素代表着员工当天工作一个时间,数值都是非负数,那么如果当天工作时间大于8小时的话就是疲劳的一天,如果小于等于8就是精神良好的一天,那么良好的时间段就是在该时间段内精神良好的一天的数量大于疲劳的一天的数量,求良好时间段的最长长度是多少。(注:时间段必须是连续的)

例:[10,10,10,9,1,1]

表现良好的最长时间段是[9,1,1],长度是3

题目思路:那么这道题的话,还是跟上一道题一样,那么这里我们不同数值的数中共就可以分为两个状态,分别是疲劳以及精神良好,那么我们还是得预处理我们的数组,将大于8的数转换为-1,小于等于8的数转换为1

那么对于任意位置i来说,如果该位置的前缀和大于等于1,那么说明在L到i这个区间中数的分布是正数大于负数,那么整个区间就到达标,那么如果说我们的前缀和是小于等于0的,那么说明负数的数量是大于等于我们的正数的,那么这个区间是有正数的数量大于负数的数量的可能的,那么这里假设i位置的前缀和为sum,那么找到sum-1出现的最早位置即可

那么假设i位置的前缀和是-3,那么我们要在的则是-4出现的最早位置,那么这里就会产生一个疑问为什么不找我们-5以及-6前缀和出现的最早位置呢,那么这里就是本题目的一个难点,**我们知道我们经过预处理之后的数组的数值只有1和-1两种,所以一个前缀和只能一点一点的增加和减少,所以要得到我们的前缀和-5,那么它一定是在它之前有一个右侧前缀和为-4在其右侧加了一个累加和为-1的区间才能达到前缀为-5,那么同理要得到前缀和为-6,那么得到-6之前也得有一个前缀和为-5在其右侧要加一个累加和为-1的区间,那么也就意味这我们我们最早出现前缀和为-5的区间一定是在最早出现前缀和为-4的区间的右侧,同理最早出现前缀和为-6的区间一定出现在最早出现的前缀和为-5的区间的右侧,**那么我们现在只需要以i位置为结尾往左延伸的正数数量大于负数数量的最长子数组,那么该最长子数组的累加和一定是大于等于1,那么我们就只需要找到sum-1的前缀和出现的最早位置,在我们刚才的例子中,i位置的前缀和为-3,那么我们找前缀和为-4出现的最早位置,那么至于这么找前面的题我们已经说了用我们的哈希表,那么这里我就不再赘述了,直到把刚才加粗的内容想通,那么这个题的难点就被解决了。

代码实现:

class Solution {
public:int longestGoodPeriod(vector<int>& hours) {// 预处理数组,将大于8小时的工作时间转换为-1,小于等于8小时的工作时间转换为1vector<int> transformed(hours.size());for (int i = 0; i < hours.size(); ++i) {transformed[i] = (hours[i] > 8) ? -1 : 1;}// 前缀和数组vector<int> prefixSum(transformed.size() + 1, 0);for (int i = 1; i <= transformed.size(); ++i) {prefixSum[i] = prefixSum[i - 1] + transformed[i - 1];}// 哈希表,存储每个前缀和首次出现的位置unordered_map<int, int> prefixSumIndex;prefixSumIndex[0] = 0; // 初始化,前缀和为0的初始位置为0int maxLength = 0;// 遍历前缀和数组,寻找满足条件的最长子数组for (int i = 1; i <= transformed.size(); ++i) {int currentSum = prefixSum[i];// 如果当前前缀和减1存在于哈希表中,则计算子数组长度if (prefixSumIndex.find(currentSum - 1) != prefixSumIndex.end()) {int startIndex = prefixSumIndex[currentSum - 1];maxLength = max(maxLength, i - startIndex);}// 如果当前前缀和还未出现在哈希表中,则记录其首次出现的位置if (prefixSumIndex.find(currentSum) == prefixSumIndex.end()) {prefixSumIndex[currentSum] = i;}}return maxLength;}
};

3.结语

那么这就是本篇文章关于前缀和的所有内容,那么讲了前缀和的原理以及代码实现,还有具体的应用,那么我们知道与子数组有关的问题,那么我们可以先往前缀和方向上思考,看能不能应用。

那么如果这篇文章让你有所收获的话,那么就三连关注支持一下博主,那么我们会持续更新,请大家多多关注与支持!
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/17327.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Notepad++ 中删除所有以 “pdf“ 结尾的行

Notepad 中删除所有以 “pdf” 结尾的行 操作步骤 1.打开文件&#xff1a; 在 Notepad 中打开你需要处理的文本文件。 2.打开查找和替换对话框&#xff1a; 按快捷键 Ctrl F&#xff0c;打开“查找和替换”对话框。 3.启用正则表达式模式&#xff1a; 在对话框的底部&#xf…

知识管理成功:关键指标和策略,研究信息的投资回报率

信息过载会影响生产力。没有人工智能的帮助&#xff0c;信息过载会影响生产力。大量的可用信息&#xff0c;知识工作者不仅仅是超负荷工作&#xff1b;他们感到不知所措&#xff0c;他们倾向于浪费时间&#xff08;和脑细胞&#xff09;来应付他们被大量的数据抛向他们&#xf…

Golang 进阶训练营

一、Golang 的 slice、map、channel 1.1 slice vs array a : make([]int, 100) //切片 b : [100]int{} //数组array需指明长度&#xff0c;长度为常量且不可改变 array长度为其类型中的组成部分&#xff08;给参数为长度100的数组的方法传长度为101的会报错&#xff09; array在…

Oracle临时表空间(基础操作)

临时表空间 临时表空间&#xff1a;用来存放用户的临时数据&#xff0c;临时数据在需要时被覆盖&#xff0c;关闭数据库后自动删除&#xff0c;其中不能存放永久性数据。 用户进程和服务器进程是一对一的叫做专用连接。 任何一个用户连到oracle数据库&#xff0c;oracle都会…

AI时代的前端开发:对抗压力的利器

在飞速发展的AI时代&#xff0c;前端开发工程师们面临着前所未有的挑战。项目周期不断缩短&#xff0c;需求变化日新月异&#xff0c;交付压力更是与日俱增&#xff0c;这使得开发人员承受着巨大的压力。如何提升对抗压能力&#xff0c;成为摆在每一位前端工程师面前的重要课题…

如何使用DHTMLX Scheduler的拖放功能,在 JS 日程安排日历中创建一组相同的事件

DHTMLX Scheduler 是一个全面的调度解决方案&#xff0c;涵盖了与规划事件相关的广泛需求。假设您在我们的 Scheduler 文档中找不到任何功能&#xff0c;并且希望在我们的 Scheduler 文档中看到您的项目。在这种情况下&#xff0c;很可能可以使用自定义解决方案来实现此类功能。…

计算机网络-八股-学习摘要

一&#xff1a;HTTP的基本概念 全称&#xff1a; 超文本传输协议 从三个方面介绍HTTP协议 1&#xff0c;超文本&#xff1a;我们先来理解「文本」&#xff0c;在互联网早期的时候只是简单的字符文字&#xff0c;但现在「文本」的涵义已经可以扩展为图片、视频、压缩包等&am…

【pytorch】weight_norm和spectral_norm

apply_parametrization_norm 和spectral_norm是 PyTorch 中用于对模型参数进行规范化的方法&#xff0c;但它们在实现和使用上有显著的区别。以下是它们的主要区别和对比&#xff1a; 实现方式 weight_norm&#xff1a; weight_norm 是一种参数重参数化技术&#xff0c;将权…

回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核极限学习机多变量回归预测

回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核极限学习机多变量回归预测 目录 回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核极限学习机多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核…

多媒体软件安全与授权新范例,用 CodeMeter 实现安全、高效的软件许可管理

背景概述 Reason Studios 成立于 1994 年&#xff0c;总部位于瑞典斯德哥尔摩&#xff0c;是全球领先的音乐制作软件开发商。凭借创新的软件产品和行业标准技术&#xff0c;如 ReWire 和 REX 文件格式&#xff0c;Reason Studios 为全球专业音乐人和业余爱好者提供了一系列高质…

C++,STL容器适配器,stack:栈深入解析

文章目录 一、容器概览与核心特性核心特性速览二、底层实现原理1. 容器适配器设计2. 默认容器对比三、核心操作详解1. 容器初始化2. 元素操作接口3. 自定义栈实现四、实战应用场景1. 括号匹配校验2. 浏览器历史记录管理五、性能优化策略1. 底层容器选择基准2. 内存预分配技巧六…

互联网大厂中面试的高频计算机网络问题及详解

前言 哈喽各位小伙伴们,本期小梁给大家带来了互联网大厂中计算机网络部分的高频面试题,本文会以通俗易懂的语言以及图解形式描述,希望能给大家的面试带来一点帮助,祝大家offer拿到手软!!! 话不多说,我们立刻进入本期正题! 一、计算机网络基础部分 1 …

「软件设计模式」工厂方法模式 vs 抽象工厂模式

前言 在软件工程领域&#xff0c;设计模式是解决常见问题的经典方案。本文将深入探讨两种创建型模式&#xff1a;工厂方法模式和抽象工厂模式&#xff0c;通过理论解析与实战代码示例&#xff0c;帮助开发者掌握这两种模式的精髓。 一、工厂方法模式&#xff08;Factory Metho…

Docker部署Alist网盘聚合管理工具完整教程

Docker部署Alist网盘聚合管理工具完整教程 部署alist初始化修改密码添加存储&#xff01;联通网盘阿里云盘百度网盘 部署alist 本文以Linux Docker部署&#xff0c;假设你已经安装好Docker docker run -d --restartalways \-v /your/data:/opt/alist/data \-p 5244:5244 \-e …

Excel常用操作

Excel常用操作 学习资源 37_电子表格处理考点精讲_设置数据格式_哔哩哔哩_bilibili 快速输入数据与编辑数据 一个工作簿可以包含多个工作表 特殊数据的添加格式 输入负数, 例如-3、-5 常规输入, 直接输入-3、-5;使用(), 例如在单元格中输入(3)回车即可变为-3;上述括号不区分中…

SpringMVC环境搭建

文章目录 1.模块创建1.创建一个webapp的maven项目2.目录结构 2.代码1.HomeController.java2.home.jsp3.applicationContext.xml Spring配置文件4.spring-mvc.xml SpringMVC配置文件5.web.xml 配置中央控制器以及Spring和SpringMVC配置文件的路径6.index.jsp 3.配置Tomcat1.配置…

常见的排序算法:插入排序、选择排序、冒泡排序、快速排序

1、插入排序 步骤&#xff1a; 1.从第一个元素开始&#xff0c;该元素可以认为已经被排序 2.取下一个元素tem&#xff0c;从已排序的元素序列从后往前扫描 3.如果该元素大于tem&#xff0c;则将该元素移到下一位 4.重复步骤3&#xff0c;直到找到已排序元素中小于等于tem的元素…

Golang的容器化部署流程

# Golang的容器化部署流程 什么是容器化部署 容器化部署是将应用程序、运行环境及其依赖项打包在一起&#xff0c;以便可以在任何环境中快速、一致地运行的技术。它提供了更高效的资源利用、更便捷的部署和更稳定的环境。 的容器化支持 天生支持跨平台编译&#xff0c;使得将Go…

前缀树算法篇:前缀信息的巧妙获取

前缀树算法篇&#xff1a;前缀信息的巧妙获取 那么前缀树算法是一个非常常用的算法&#xff0c;那么在介绍我们前缀树具体的原理以及实现上&#xff0c;我们先来说一下我们前缀树所应用的一个场景&#xff0c;那么在一个字符串的数据集合当中&#xff0c;那么我们查询我们某个字…

tomcat html乱码

web tomcat html中文乱码 将html文件改成jsp <% page language"java" contentType"text/html; charsetUTF-8" pageEncoding"UTF-8"%>添加 <meta charset"UTF-8">