Javascript算法（滑块窗口、螺旋矩阵）
滑块窗口
JS滑块窗口算法，即滑动窗口算法（Sliding Window），在JavaScript中的应用场景主要集中在处理字符串和数组等数据结构中的子串或子数组问题。这种算法通过维护一个窗口，并移动窗口的两个边界（左右指针）来优化暴力枚举的时间复杂度，从而提高算法的执行效率。以下是一些具体的应用场景及案例：
应用场景
- 字符串匹配问题：在较长的字符串中查找是否存在一个较短的字符串（或模式）。
- 最长子串或子数组问题：查找满足特定条件的最长子串或子数组。
function lengthOfLongestSubstring(s){
let maxLength=0;//做大子串的长度
let currentLength=0;
let charIndexMap={};//字符及其索引的映射
let left=0;//窗口的左边界
for(let right=0;right<s.length;right++){
const char=s[right];
//如果字符已经在窗口中存在，则更新左边界【key1】
if（charIndexMap[char]>=left){
left=charIndexMap[char]+1;
}
//更新字符的索引
charIndexMap[char]=right;
//更新当前窗口的长度
currentLength=right-left+1;
//更新最大长度【key2】
maxLength=Math.max(maxLength,currentLength);
}
return maxLength
}
// 示例用法
const inputString = "abcabcbb";
console.log(`最长的不重复子串的长度是: ${lengthOfLongestSubstring(inputString)}`);- 最小覆盖子串问题（难）：在给定条件下，查找覆盖特定内容的最小子串。
- 字符串排列问题：判断一个字符串是否包含另一个字符串的所有字符（不考虑顺序和数量）。
- 求解字符串或数组的性质：如最大值、最小值、和、平均值等。
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(target, nums) {
let left=0;
let curSum=0;
let minValue=0;
let minLength=nums.length;
for(right=0;right<nums.length;right++){
curSum+=nums[right];
//核心if与while？持续满足条件滑？[key]
while(curSum>=target){
let curLength=right-left+1;
//[key2]
minValue=Math.min(curLength,minLength)
curSum-=nums[left]
left++;
}
}
return minValue;
};水果篮子（Map）
/**
* @param {number[]} fruits
* @return {number}
*/
var totalFruit = function(fruits) {
let maxNumber=0;
let fruitMap=new Map();
let left=0;
for(let right=0;right<fruits.length;right++){
let fruit=fruits[right];
fruitMap.set(fruit,(fruitMap.get(fruit)||0)+1);
while(fruitMap.size>2){
let leftFruit=fruits[left];
fruitMap.set(leftFruit,fruitMap.get(leftFruit)-1);
if(fruitMap.get(leftFruit)===0){
fruitMap.delete(leftFruit);
};
left++;
}
//在循环外，循环只是找出当size>2时候移动左指针调整得到新的滑块
maxNumber=Math.max(maxNumber,right-left+1)
}
return maxNumber;
};螺旋矩阵
螺旋矩阵是指一个呈螺旋状的矩阵，其数字从第一行开始，向右、向下、向左、向上依次变大，如此循环直至填满整个矩阵。以下是对螺旋矩阵的详细解释：
一、定义与特点
- 定义：螺旋矩阵是一个二维数组（或表格），其中的数字按照螺旋式的顺序进行填充。
- 特点：
- 填充顺序：从外圈开始，顺时针或逆时针逐层向中心推进。
- 数字递增：每一层的数字都比前一层的数字大，且在同一层中，数字也是递增的。
二、构造方法
- 确定边界：对于n行m列的螺旋矩阵，首先需要确定其四个边界，即左边界、右边界、上边界和下边界。
- 填充过程：
- 从上边界开始，向右填充数字，直到右边界。
- 然后从右边界开始，向下填充数字，直到下边界。
- 接着从下边界开始，向左填充数字，直到左边界。
- 最后从左边界开始，向上填充数字，直到上边界。
- 完成一层填充后，更新边界，继续下一层的填充，直到填满整个矩阵。
三、应用场景
螺旋矩阵在多个领域有着广泛的应用，包括但不限于：
- 数据可视化：螺旋矩阵能提供独特的视觉效果，便于观察数据的趋势和分布。
- 图像处理：在图像处理中，螺旋矩阵可以用于图像变换、滤波等操作。
- 算法训练：生成和处理螺旋矩阵是对算法逻辑和控制流程的一次良好锻炼。
- 游戏开发：螺旋矩阵可以用于生成迷宫地图等游戏元素。
var generateMatrix = function(n) {
let startX = startY = 0; // 起始位置
let loop = Math.floor(n/2); // 旋转圈数
let mid = Math.floor(n/2); // 中间位置
let offset = 1; // 控制每一层填充元素个数
let count = 1; // 更新填充数字
let res = new Array(n).fill(0).map(() => new Array(n).fill(0));
while (loop--) {
let row = startX, col = startY;
// 上行从左到右（左闭右开）
for (; col < n - offset; col++) {
res[row][col] = count++;
}
// 右列从上到下（左闭右开）
for (; row < n - offset; row++) {
res[row][col] = count++;
}
// 下行从右到左（左闭右开）
for (; col > startY; col--) {
res[row][col] = count++;
}
// 左列做下到上（左闭右开）
for (; row > startX; row--) {
res[row][col] = count++;
}
// 更新起始位置
startX++;
startY++;
// 更新offset
offset += 1;
}
// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值【key1】
if (n % 2 === 1) {
res[mid][mid] = count;
}
return res;
};
mid的计算及填充:
同样的原理，本题的mid计算也存在上述差异;1.如果min(rows,columns)为偶数，则不需要在最后单独
2.考虑矩阵最中间位置的赋值 如果min(rows, columns)为奇数，则矩阵最中间位置不只是[mid][mid],而是会留下来一个特殊的中间行或者中间列，具体是中间行还是中间列，要看rows和columns的大小，如果rows>columns,则是中间列，相反，则是中间行.
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
let startX=0;
let startY=0;
let rowCount=matrix.length;
let columnCount=matrix[0].length;
let loop=Math.floor((Math.min(rowCount,columnCount))/2);
let mid=Math.floor((Math.min(rowCount,columnCount))/2);
let offset=1;
let count=0;
let res=[];
while(loop--){
let row=startX;
let col=startY;
for(;col<columnCount-offset;col++){
res[count]=matrix[row][col];
count++
}
for(;row<rowCount-offset;row++){
res[count]=matrix[row][col];
count++;
}
for(;col>startY;col--){
res[count]=matrix[row][col];
count++;
}
for(;row>startX;row--){
res[count]=matrix[row][col];
count++;
}
startX++;
startY++;
offset++;
}
//核心分析，剩下的，若最小为偶数，则直接可以循环掉
//若为奇数，则可能剩下一行或一列，分情况考虑（比较columCount与rowCount大些）
if((Math.min(rowCount,columnCount))%2){
let row=mid;
let column=mid;
if(rowCount>=columnCount){
for(;row<mid+rowCount-columnCount+1;row++){
res[count++]=matrix[row][column];
}
}else{
for(;column<mid+columnCount-rowCount+1;column++){
res[count++]=matrix[row][column];
}
}
}
return res;
};