工信部网站用户名,现在流行的网站开发工具,wordpress5.0.2版的新功能,企业联系电话回顾 栈、队列 #xff1a; 进、出 栈#xff08;Stack#xff09;#xff1a; 栈的操作主要包括#xff1a; 队列#xff08;Queue#xff09;#xff1a; 队列的操作主要包括#xff1a; 链表、数组 #xff1a; 多个元素存储组成的 简述链表#xff1a;数组 进、出 栈Stack 栈的操作主要包括 队列Queue 队列的操作主要包括 链表、数组 多个元素存储组成的 简述链表数组适用场景 字典与哈希表 字典: 键值对存储的类似于js的对象 一个例子 在JavaScript中对象的覆盖规则遵循合并与替换的原则 字典: map来表示的map的键不会转换类型哈希表 又叫 -- 散列表 在js中没有哈希表哈希表是字典一种实现。 哈希表的工作原理和使用。哈希表与字典区别使用JavaScript实现一个hash表 前端算法题 两数之和存在重复元素 扩展ES6 Set数据类型扩展ES6 中 set和map 的区别 两个数组的交集独一无二的出现次数 引子独一无二的出现次数 无重复字符的最长子串 扩展滑动窗口 例子求给定数组的每个长度为k的连续子数组的最大值 回顾
栈、队列 进、出
栈Stack
栈是一种线性数据结构它遵循“后进先出”Last In, First Out, LIFO原则。在栈中数据元素只能通过一个端点进行插入和删除操作这个端点称为栈顶top。栈的特性是新添加的元素会放在所有已有元素之上而移除元素时总是从栈顶开始移除最近添加的那个元素。
栈的操作主要包括
Push入栈将元素添加到栈顶。Pop出栈移除并返回栈顶元素。Peek/Top读栈顶查看栈顶元素但不移除。IsEmpty判断是否为空检查栈是否包含任何元素。
栈常用于实现函数调用、表达式求值、括号匹配等场景。
队列Queue
队列也是一种线性数据结构但它遵循的是“先进先出”First In, First Out, FIFO原则。在队列中元素可以在一端队尾加入而在另一端队头移除。
队列的操作主要包括
Enqueue入队在队列尾部添加一个元素。Dequeue出队从队列头部移除并返回一个元素。Front读队头查看队头元素但不移除。IsEmpty判断是否为空检查队列是否为空。
队列通常应用于多任务系统中的任务调度、消息传递、广度优先搜索算法等场合。队列可以采用顺序存储结构如循环队列或链式存储结构如链队列来实现。
链表、数组 多个元素存储组成的
简述
区别一
数组下标链表next指针联系在一起
区别二数据插入
数组如果在中间插入新的元素其他元素会重新计算链表不会重新计算说白了是赋值或者替换的一种感觉
区别三查找
数组通过下标进行查找即可链表每次查找都需要从头开始找
链表Linked List和数组Array是两种基本且重要的数据结构它们在内存中的组织方式和操作特性有显著区别。
链表
存储结构链表中的元素不是连续存储的每个元素称为节点包含两部分数据域和指针域。数据域存储实际的数据而指针域存储指向下一个节点的地址。动态分配链表的长度可以在程序运行时动态增长或缩短不需要预先指定大小新添加的元素可以动态地从堆中分配空间。插入/删除在链表中插入或删除一个元素相对容易只需修改相应的指针即可时间复杂度通常为O(1)头插头删至O(n)在中间或尾部插入删除。访问速度访问链表中的特定元素需要从头节点开始遍历直到找到目标位置因此随机访问的时间复杂度通常是O(n)不如数组直接通过下标访问速度快。
数组
存储结构数组是一段连续的内存空间其中每个单元存放一个元素并可以通过索引下标直接访问。静态分配数组在声明时就需要确定其大小一旦初始化后大小就固定不变所有元素占用连续内存空间。插入/删除在数组中插入或删除元素通常比较麻烦因为可能需要移动后续元素以保持连续性时间复杂度通常是O(n)。访问速度数组支持随机访问即通过下标可以直接获取任何位置的元素时间复杂度为O(1)。
适用场景
链表适用于频繁进行插入、删除操作且对访问顺序要求不高的情况例如实现队列、栈等数据结构以及某些动态变化的集合。数组适用于元素数量已知并且需要快速随机访问的情况如实现矩阵运算、查找算法等也常用作缓存或其他固定大小的数据集存储。
更多详细内容请微信搜索“前端爱好者“ 戳我 查看 。
字典与哈希表
字典: 键值对存储的类似于js的对象 字典 : 键值对存储的类似于js的对象键[key]都是字符串类型或者会转换成字符串类型
字典是一种数据结构它在计算机科学中用于存储键-值对key-value pairs其中每个键都是独一无二的且与一个对应的值相关联。
这种数据结构允许通过键快速查找、添加和删除其关联的值。
字典常被比喻为现实生活中的字典就像你通过单词键查找其定义值一样。
Python 中字典的定义和示例
# 定义一个简单的字典
person {name: John Doe,age: 30,city: New York
}# 示例说明
# - 键字符串 name、age 和 city
# - 值对应的值分别为字符串 John Doe、整数 30 和字符串 New York# 访问字典中的值
print(person[name]) # 输出: John Doe# 修改或更新字典中的值
person[age] 31
print(person) # 输出: {name: John Doe, age: 31, city: New York}# 添加新的键值对
person[job] Software Engineer
print(person) # 输出: {name: John Doe, age: 31, city: New York, job: Software Engineer}# 判断键是否存在
if city in person:print(City is:, person[city])在上述例子中person 字典是一个包含个人信息的数据结构通过键如“name”、“age”等可以迅速获取到相应的值如“John Doe”的姓名、30岁的年龄。
一个例子
ar a {}
var b {key:a
}
var c {key:c
}
a[b] 123; // a[[object Object]] 123
a[c] 456; // a[[object Object]] 456console.log( a[b] );结果456而不是123为什么
在JavaScript中对象的覆盖规则遵循合并与替换的原则
当一个对象被赋值给另一个对象或者通过扩展运算符...或Object.assign()方法合并到另一个对象时如果两个对象有相同的属性名键则会发生以下情况
简单类型属性
如果原对象和新对象中存在相同名称的简单类型属性如字符串、数字、布尔值等那么新对象中的该属性值将覆盖原对象的相应属性值。
let obj1 { a: 1, b: hello };
let obj2 { b: world, c: true };
let obj3 { ...obj1, ...obj2 }; // 结果是 { a: 1, b: world, c: true }在此例中obj3 的 b 属性值来自 obj2从而覆盖了 obj1 中的 b 属性值。
嵌套对象属性
对于嵌套的对象属性也是同样的原理。如果嵌套的对象结构中有相同的路径则新的嵌套对象会覆盖原有的对象。
let obj1 { nested: { a: 1 } };
let obj2 { nested: { b: 2 } };
let obj3 { ...obj1, ...obj2 }; // 结果是 { nested: { b: 2 } }这里obj3 的 nested 对象完全由 obj2 中的 nested 值覆盖所以只包含 b: 2。
数组属性
数组作为对象属性时如果源对象和目标对象有同名数组属性不会直接进行合并或替换而是保持原有数组不变。若要合并数组元素需要采用特定的方法比如使用递归合并函数或者是展开操作符结合数组方法来实现数组元素的合并而非覆盖。
let obj1 { array: [1, 2, 3] };
let obj2 { array: [4, 5] };
let obj3 { ...obj1, ...obj2 }; // 结果是 { array: [4, 5] }在这个例子中obj3.array 是 [4, 5] 而不是 [1, 2, 3, 4, 5]因为这不是合并数组而是简单的覆盖。
如果你希望合并数组内容而不是替换可以使用自定义合并函数或者利用 Array.prototype.concat() 或 ES6 的扩展运算符加数组连接的方式来处理
let obj1 { array: [1, 2, 3] };
let obj2 { array: [4, 5] };
let obj3 { ...obj1, array: [...obj1.array, ...obj2.array] }; // 结果是 { array: [1, 2, 3, 4, 5] }字典: map来表示的map的键不会转换类型
字典 -- map来表示的map的键不会转换类型
let map new Map();
map.set(a,1);
map.set(b,2);
console.log( map );
console.log( map.get(b) );
console.log( map.has(x) );map.delete(a);console.log( map );哈希表 又叫 -- 散列表 在js中没有哈希表哈希表是字典一种实现。 哈希表Hash Table是一种高效的数据结构它通过散列函数也称为哈希函数将键Key映射到一个固定范围的索引数组中然后将值Value存储在对应的数组位置上。
这样可以实现近乎常数时间复杂度理想情况下为O(1)的插入、删除和查找操作。
哈希表工作原理 哈希函数首先使用哈希函数将输入的键转换成一个整数值这个过程被称为“哈希”或“散列”。理想的哈希函数应该满足以下条件 确定性对于相同的键总是生成相同的哈希值。均匀分布不同的键应尽可能均匀地分布在整个哈希空间内以减少冲突。 哈希冲突由于哈希函数输出范围有限不同键可能产生相同的哈希值这种现象称为哈希冲突。为了处理冲突常见的策略有开放寻址法如线性探测、二次探测等、链地址法每个数组元素指向一个链表所有哈希值相同的键都在同一个链表中以及再哈希法等。 负载因子与扩容哈希表通常会设定一个最大负载因子即已存储元素数量与表大小的比例当负载因子超过某个阈值时为了保持哈希表的性能会进行动态扩容并重新哈希所有的元素。 操作时间复杂度在理想情况下哈希表的插入、删除和查找的时间复杂度都是O(1)但在实际应用中由于哈希冲突的存在最坏情况下的时间复杂度可能达到O(n)。优秀的哈希函数和合适的冲突解决策略可以尽量降低这种情况发生的概率。
哈希表在编程语言中的常见应用包括字典、映射、关联数组等数据结构它们广泛应用于数据库索引、缓存系统、唯一性检查等多个场景。
哈希表的工作原理和使用。
假设我们想要创建一个简单的电话簿其中包含联系人的姓名键及其对应的电话号码值。
我们将使用哈希表作为数据结构并且设计一个简单的哈希函数 hash(key) 来计算姓名对应的数组索引。
这里为了简化演示我们将采用除留余数法的哈希函数即 H(key) key % capacity其中capacity是哈希表数组的大小。
假设有以下联系人
Alice, 电话555-1234Bob, 电话555-5678Carol, 电话555-9012
我们选择哈希表的容量为10。
哈希函数示例
H(“Alice”) “Alice” % 10 0H(“Bob”) “Bob” % 10 2H(“Carol”) “Carol” % 10 2 注意此处出现了冲突
为了处理冲突我们将采用线性探测法当发现某个位置已经有元素时就顺序检查下一个位置直到找到空的位置。
构建哈希表的过程
插入 Alice
哈希地址 H(“Alice”) 0该位置为空所以将 (“Alice”, 555-1234) 存储在数组下标为0的位置。
插入 Bob
哈希地址 H(“Bob”) 2该位置也为空所以将 (“Bob”, 555-5678) 存储在数组下标为2的位置。
插入 Carol
哈希地址 H(“Carol”) 2与 Bob 冲突。使用线性探测尝试下一个位置 (21)%10 3这个位置也是空的所以将 (“Carol”, 555-9012) 存储在数组下标为3的位置。
最终形成的哈希表可以表示如下用“-”表示空槽位
Index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-------|---|---|---|---|---|---|---|---|---|---|
Value: | Alice | - | Bob | Carol | - | - | - | - | - | - |在这个简化的例子中通过哈希函数和冲突解决策略我们可以快速查找、插入和删除电话簿中的记录。
例如如果要查找Carol的电话号码我们会首先对“Carol”进行哈希运算得到索引2然后由于冲突继续探测到索引3从而找到正确的电话号码。
哈希表与字典区别
区别一如果找key对应的value需要遍历key那么想要省去遍历的过程用哈希表来表示。区别二排列顺序字典是根据添加的顺序进行排列的哈希表Hash Table与字典Dictionary是两种相似但有区别的数据结构它们都是用于存储键值对的数据容器。下面总结了它们在不同编程语言环境中的主要区别
泛型与非泛型
哈希表在某些编程语言中如早期的C#哈希表不是泛型集合这意味着它能够存储任何类型的对象作为键和值但在检索时需要类型转换。字典在很多现代编程语言如C#中字典是泛型集合它允许指定键和值的具体类型从而在编译时提供类型安全并且不需要额外的装箱和拆箱操作提高了效率。
线程安全
哈希表在一些实现中哈希表可能会设计为线程安全的也就是说多个线程可以同时访问而不导致数据不一致或冲突。字典另一方面许多编程语言的标准库中的字典类默认可能不是线程安全的例如C#中的Dictionary类就不是线程安全的若在多线程环境下使用需要程序员自己确保同步机制如使用锁来保证线程安全。
性能与容量
在单线程环境中由于字典通常具有类型安全以及优化过的内部结构因此在查找、插入和删除操作上往往比非泛型哈希表更快空间利用率也更高。
命名空间和实现
C# 中的 HashTable 类位于 System.Collections 命名空间下而 Dictionary 类则位于 System.Collections.Generic 命名空间下后者是.NET Framework 2.0 引入的泛型集合的一部分。
API 设计
不同编程语言中字典和哈希表可能提供了不同的方法集和接口设计字典因为其泛型特性可能拥有更简洁、更易于使用的API。
哈希表和字典的核心功能相同都是基于哈希算法快速存取数据但具体到某个编程语言和库中它们的设计细节和使用场景会有所不同字典倾向于提供更为现代、类型安全和高效的解决方案而哈希表在某些情况下可能是为了向后兼容或是特定线程安全需求而存在的选择。
使用JavaScript实现一个hash表
class HashTable{constructor(){this.table [];}hashCode( key ){let hash 0;for( let i 0;ikey.length;i){hash key.charCodeAt(i);}return hash;} put( key , val ){let hashKey this.hashCode(key);this.table[ hashKey ] val;}get( key ){let hashKey this.hashCode(key);return this.table[hashKey];}
}let hashTable new HashTable();
hashTable.put(person,章三);
console.log( hashTable );
console.log( hashTable.get(person) ); 前端算法题
两数之和
leetcode https://leetcode.cn/problems/two-sum/description/
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]提示
2 nums.length 104
-109 nums[i] 109
-109 target 109
只会存在一个有效答案进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗
js解决方案1
/*** param {number[]} nums* param {number} target* return {number[]}*/
var twoSum function (nums, target) {let map new Map() // 新建Map// 遍历数组for (let i 0; i nums.length; i) {// 定义一个差值let num target - nums[i]// 如果map中包含这个值则返回这个值索引和当前索引if (map.has(num)) {return [map.get(num), i]}// 保存当前值和当前索引map.set(nums[i], i)}
};js解决方案2
/*** param {number[]} nums* param {number} target* return {number[]}*/
var twoSum function (nums, target) {let index1, index2nums.forEach((num, i) {nums.forEach((num1, j) {if (num1 num target i ! j) {index1 i;index2 j}})})return [index1, index2]
};js解决方案3
/*** param {number[]} nums* param {number} target* return {number[]}*/
var twoSum function(nums, target) {let obj {}for(let i 0; i nums.length;i ){let num nums[i]if(num in obj){return [obj[num],i]} else {obj[target-num] i}}};217. 存在重复元素
leetcode地址https://leetcode.cn/problems/contains-duplicate/description/
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 返回 true 如果数组中每个元素互不相同返回 false 。
示例 1
输入nums [1,2,3,1]
输出true示例 2
输入nums [1,2,3,4]
输出false示例 3
输入nums [1,1,1,3,3,4,3,2,4,2]
输出true 提示
1 nums.length 10^5
-10^9 nums[i] 10^9js实现方案1
/*** param {number[]} nums* return {boolean}*/
var containsDuplicate function (nums) {// 新建一个字典let map new Map()// 遍历数组for (const item of nums) {// 如果字典中有当前值则返回trueif (map.has(item)) {return true}// 把当前值保存到字典map.set(item, 1)}return false
};js实现方案2
/*** param {number[]} nums* return {boolean}*/
var containsDuplicate function (nums) { // 新建一个字典let set new Set()// 遍历数组for (const item of nums) {// 如果字典中有当前值则返回trueif (set.has(item)) {return true}// 把当前值保存到字典set.add(item)}return false};扩展ES6 Set数据类型
在JavaScript的ES6ECMAScript 2015中Set 是一种新的数据结构类型它类似于数组但是成员的值都是唯一的不存储重复的值。
这意味着当你向 Set 中添加元素时如果该元素已经存在则不会有任何变化Set的大小也不会增加。
创建 Set 的基本语法是使用 new Set() 构造函数并传入一个可迭代对象如数组或其他 iterable 对象
// 创建一个新的空 Set
const emptySet new Set();// 创建一个包含若干唯一值的 Set
const numbersSet new Set([1, 2, 3, 4, 4, 5]); // 注意尽管有两次 4但只会存储一次
console.log(numbersSet.size); // 输出: 5// 创建一个包含字符串的 Set
const wordsSet new Set([apple, banana, apple]); // 只有一个 appleSet 提供了一些方法用于操作其内容
add(value): 向 Set 添加一个新值如果值已存在则不执行任何操作。delete(value): 从 Set 中删除指定的值。has(value): 检查 Set 是否包含某个值返回布尔结果。clear(): 清除 Set 中的所有元素。size: 属性返回 Set 中元素的数量。
例如
let fruits new Set([apple, banana, cherry]);fruits.add(orange); // 添加一个元素
console.log(fruits.has(banana)); // true检查是否包含 banana
fruits.delete(apple); // 删除 apple
console.log(fruits.size); // 输出当前 fruits Set 的元素数量扩展ES6 中 set和map 的区别
在JavaScript的ES6中Set和Map是两种不同的数据结构类型它们各自有独特的用途和操作方法
Set集合
Set是一个特殊的类型它存储的是唯一不重复的值序列。Set中的元素没有键值对的概念每个元素自身既是键也是值。特点 不允许出现重复值自动去重。集合内的元素是无序的尽管实际实现可能按照某种内部顺序排列但不能通过索引访问。提供了add, delete, has, clear等方法用于操作集合元素。
let set new Set();
set.add(1); // 添加数字1
set.add(apple); // 添加字符串apple
set.has(1); // 返回true判断是否存在
set.delete(apple); // 删除字符串apple
console.log(set.size); // 输出当前集合内元素的数量Map映射
Map是一个键值对的数据结构类似于对象但它允许任何类型的值包括对象作为键并且键值对的顺序是可以被保留的。特点 键值对的形式存储数据键必须是唯一的值可以重复。可以通过键来获取对应的值使用get(key)方法。提供了set(key, value), get(key), delete(key), has(key), clear()等方法以及迭代方法如entries(), keys(), values()。
let map new Map();
map.set(name, Alice); // 添加键值对
map.set({id: 1}, Bob); // 对象也可以作为键
console.log(map.get(name)); // 获取键为name的值Alice
map.delete({id: 1}); // 删除特定键的键值对
console.log(map.has({id: 1})); // 检查是否包含给定键返回布尔值总结起来Set主要用于存储一组唯一的、无需有序的值而Map则用于存储和检索基于任意值关联的数据保持插入时的键值对顺序。
349. 两个数组的交集
leetcode地址https://leetcode.cn/problems/intersection-of-two-arrays/description/
给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1
输入nums1 [1,2,2,1], nums2 [2,2]
输出[2] 示例 2
输入nums1 [4,9,5], nums2 [9,4,9,8,4]
输出[9,4]
解释[4,9] 也是可通过的提示
1 nums1.length, nums2.length 1000
0 nums1[i], nums2[i] 1000js实现方案
/*** param {number[]} nums1* param {number[]} nums2* return {number[]}*/
var intersection function (nums1, nums2) {// 先把数组去重let set1 new Set(nums1)let set2 new Set(nums2)// 然后把第一个去重后的数据转成数组便于使用filter方法let finalNums1 [...set1]// 返回重复数据return finalNums1.filter((item) set2.has(item))
};1207. 独一无二的出现次数
引子
判断一个字符串中出现次数最多的字符并统计次数
例如nums ‘aaabbbbccccccc’
解决方案
function fun( s ){let maxNum 0;let maxStr ;let map new Map();for( let item of s ){map.set( item , (map.get(item) || 0 ) 1 )}for(let [key,value] of map){if( value maxNum ){maxStr key;maxNum value;}}return [maxStr , maxNum];
}console.log( fun(aaabbbbccccccc) );1207. 独一无二的出现次数
leetcode地址https://leetcode.cn/problems/unique-number-of-occurrences/description/
给你一个整数数组 arr请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的就返回 true否则返回 false。
示例 1
输入arr [1,2,2,1,1,3]
输出true
解释在该数组中1 出现了 3 次2 出现了 2 次3 只出现了 1 次。没有两个数的出现次数相同。示例 2
输入arr [1,2]
输出false示例 3
输入arr [-3,0,1,-3,1,1,1,-3,10,0]
输出true提示
1 arr.length 1000
-1000 arr[i] 1000js解决方案
/*** param {number[]} arr* return {boolean}*/
var uniqueOccurrences function (arr) {// 定义一个字典const map new Map()// 遍历数组for (const item of arr) {//判断map中是否有当前项if (map.has(item)) {// 如果有则加一map.set(item, map.get(item) 1)} else {// 如果没有则存储map.set(item, 1)}}// 定义一个setconst set new Set()// 遍历字典根据Set数据的去重性质把数据填充到Set中for (let [key, value] of map) {set.add(value)}// 判断二者长度是否相等return map.size set.size};3. 无重复字符的最长子串
leetcod地址https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示
0 s.length 5 * 10^4
s 由英文字母、数字、符号和空格组成扩展滑动窗口
滑动窗口是一种在计算机科学中广泛使用的抽象概念主要应用于数据流处理、序列算法等领域。
它提供了一种以固定大小的“窗口”查看数据流的方式随着数据流的推进“窗口”会从初始位置开始向前滑动并不断更新窗口内的数据。
具体来说假设我们有一个数据流如一个数组或列表窗口大小为k那么在任意时刻窗口都会包含数据流中最近的k个元素。
当新的元素进入数据流时窗口会向前滑动一位并将最早进入窗口的那个元素移出窗口同时将新元素纳入窗口。
滑动窗口常用于解决诸如求解子数组和、最大/最小值、中位数等问题在网络流量控制、数据平滑、在线统计分析等方面也有广泛应用。
例子求给定数组的每个长度为k的连续子数组的最大值
滑动窗口算法在JavaScript中的应用可以用来解决许多与数组或序列相关的高效问题例如求解连续子数组的最大值、最小值、平均值、中位数等。
以下是一个使用滑动窗口解决“求给定数组的每个长度为k的连续子数组的最大值”的例子
// JavaScript 滑动窗口实现找出所有长度为 k 的连续子数组的最大值
function maxInWindows(nums, k) {const result [];// 初始化一个单调递减栈来保存窗口内的最大值及其索引let stack [];// 右指针遍历数组for (let right 0; right nums.length; right) {// 移除窗口左侧不在范围内的元素对应的索引while (stack.length 0 right - stack[0][1] k) {stack.shift();}// 当栈为空或者当前元素大于栈顶元素时更新栈顶最大值if (stack.length 0 || nums[right] nums[stack[stack.length - 1][1]]) {stack.push([nums[right], right]);}// 如果右指针已经滑动到了窗口内即right k-1那么可以计算并添加结果if (right k - 1) {result.push(stack[0][0]); // 栈顶元素始终是当前窗口的最大值}}return result;
}// 示例用法
const nums [2, 3, 4, 2, 6, 2, 5, 1];
const k 3;
console.log(maxInWindows(nums, k)); // 输出: [4, 6, 6, 5]在这个例子中我们维护了一个单调栈其中存储的是窗口内遇到的最大值及其所在的索引。
随着右指针向右移动不断调整栈中的元素以保持栈顶元素始终为当前窗口的最大值。
当窗口滑动到有效范围时即可从栈顶获取该窗口的最大值并将其添加到结果数组中。
js解决方案1
/*** param {string} s* return {number}*/
var lengthOfLongestSubstring function (s) {// 新建一个hash表const map new Map()//左指针let left 0// 最长字串的结果值let num 0// 遍历字符串for (let i 0; i s.length; i) {// map中是否有当前值if (map.has(s[i]) map.get(s[i]) left) {left map.get(s[i]) 1}num Math.max(num, i - left 1) // i - left 1: 取的是长度所以要 1// 如果map中没有则存储map.set(s[i], i)}return num
};js解决方案2
/*** param {string} s* return {number}*/
var lengthOfLongestSubstring function(s) {// 思路// 1. 先进行右侧指针窗口移动位置后移// 2. 判断是否符合预期。// 2.1 符合进行其他处理比如reurn等// 2.2 不符合左侧指针是否移动位置// 2.2.1 移动或着不移动// 3. 进入下一次循环if(s.length 1){return s.length }//定义指针let left 0let right 1// 定义无重复最长字串let max 0// 定义字串let temp// 当且仅当右侧指针向右侧移动不超过swhile(right s.length){temp s.slice(left,right) // splice(0,1)// 判断当前元素是否包含right所在位置下表元素if(temp.indexOf(s.charAt(right)) -1){left continue} else {right }if(right - left max){max right - left} }return max
};
