web前端算法简介之字典与哈希表

  • 回顾
    • 栈、队列 : 进、出
      • 栈(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]]  = '456'console.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 }

在此例中,obj3b 属性值来自 obj2,从而覆盖了 obj1 中的 b 属性值。

嵌套对象属性

对于嵌套的对象属性,也是同样的原理。如果嵌套的对象结构中有相同的路径,则新的嵌套对象会覆盖原有的对象。

let obj1 = { nested: { a: 1 } };
let obj2 = { nested: { b: 2 } };
let obj3 = { ...obj1, ...obj2 }; // 结果是 { nested: { b: 2 } }

这里,obj3nested 对象完全由 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))的插入、删除和查找操作。

哈希表工作原理:

  1. 哈希函数:首先使用哈希函数将输入的键转换成一个整数值,这个过程被称为“哈希”或“散列”。理想的哈希函数应该满足以下条件:

    • 确定性:对于相同的键总是生成相同的哈希值。
    • 均匀分布:不同的键应尽可能均匀地分布在整个哈希空间内,以减少冲突。
  2. 哈希冲突:由于哈希函数输出范围有限,不同键可能产生相同的哈希值,这种现象称为哈希冲突。为了处理冲突,常见的策略有开放寻址法(如线性探测、二次探测等)、链地址法(每个数组元素指向一个链表,所有哈希值相同的键都在同一个链表中)以及再哈希法等。

  3. 负载因子与扩容:哈希表通常会设定一个最大负载因子(即已存储元素数量与表大小的比例),当负载因子超过某个阈值时,为了保持哈希表的性能,会进行动态扩容并重新哈希所有的元素。

  4. 操作时间复杂度:在理想情况下,哈希表的插入、删除和查找的时间复杂度都是O(1),但在实际应用中,由于哈希冲突的存在,最坏情况下的时间复杂度可能达到O(n)。优秀的哈希函数和合适的冲突解决策略可以尽量降低这种情况发生的概率。

哈希表在编程语言中的常见应用包括字典、映射、关联数组等数据结构,它们广泛应用于数据库索引、缓存系统、唯一性检查等多个场景。

哈希表的工作原理和使用。

假设我们想要创建一个简单的电话簿,其中包含联系人的姓名(键)及其对应的电话号码(值)。

我们将使用哈希表作为数据结构,并且设计一个简单的哈希函数 hash(key) 来计算姓名对应的数组索引。

这里为了简化演示,我们将采用除留余数法的哈希函数,即 H(key) = key % capacity,其中capacity是哈希表数组的大小。

假设有以下联系人:

  1. Alice, 电话:555-1234
  2. Bob, 电话:555-5678
  3. Carol, 电话:555-9012

我们选择哈希表的容量为10。

哈希函数示例:

  • H(“Alice”) = “Alice” % 10 = 0
  • H(“Bob”) = “Bob” % 10 = 2
  • H(“Carol”) = “Carol” % 10 = 2 (注意此处出现了冲突)

为了处理冲突,我们将采用线性探测法,当发现某个位置已经有元素时,就顺序检查下一个位置,直到找到空的位置。

构建哈希表的过程:

  1. 插入 Alice:
  • 哈希地址 = H(“Alice”) = 0,该位置为空,所以将 (“Alice”, 555-1234) 存储在数组下标为0的位置。
  1. 插入 Bob:
  • 哈希地址 = H(“Bob”) = 2,该位置也为空,所以将 (“Bob”, 555-5678) 存储在数组下标为2的位置。
  1. 插入 Carol:
  • 哈希地址 = H(“Carol”) = 2,与 Bob 冲突。
  • 使用线性探测,尝试下一个位置 (2+1)%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;i<key.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^9

js实现方案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的ES6(ECMAScript 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"]); // 只有一个 "apple"

Set 提供了一些方法用于操作其内容:

  • 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] <= 1000

js实现方案

/*** @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] <= 1000

js解决方案

/*** @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 
};

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

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

相关文章

【Java】IDEA中的JFormDesigner使用教程

目录 1 安装 JFormDesigner 插件2 JFormDesigner 使用教程2.1 新建JFormDesigner Form时的选项2.2 JFormDesigner Form界面布局2.3 JFormDesigner 常用组件 JFormDesigner 是一款用于设计和创建图形用户界面&#xff08;GUI&#xff09;的插件&#xff0c;它允许开发者使用可视…

ZZULIOJ 1112: 进制转换(函数专题)

题目描述 输入一个十进制整数n&#xff0c;输出对应的二进制整数。常用的转换方法为“除2取余&#xff0c;倒序排列”。将一个十进制数除以2&#xff0c;得到余数和商&#xff0c;将得到的商再除以2&#xff0c;依次类推&#xff0c;直到商等于0为止&#xff0c;倒取除得的余数…

ZZULIOJ 1110: 最近共同祖先(函数专题)

题目描述 如上图所示&#xff0c;由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结 点&#xff08;编号是1 的结点&#xff09;都有一条唯一的路径&#xff0c;比如从10 到根结点的路径是(10, 5, 2, 1)&#xff0c; 从4 到根结点的路径是(4, 2, 1)&#xff0…

xtu oj 1340 wave

题目描述 一个n列的网格&#xff0c;从(0,0)网格点出发&#xff0c;波形存在平波(从(x,y)到(x1,y))&#xff0c;上升波(从(x,y)到(x1,y1))&#xff0c;下降波(从(x,y)到(x1,y−1))三种波形&#xff0c;请问从(0,0)出发&#xff0c;最终到达(n,0)的不同波形有多少种&#xff1f…

关于 setData 同步异步的问题

小程序官方文档中的回答解释: 所以大概意思就是: 1.setData在逻辑层的操作是同步&#xff0c;因此this.data中的相关数据会立即更新,比如下面的例子: const a 1 this.setData({b: a ? a : , }) console.log(that.data.b) // 1 2. setData在视图层的操作是异步&#xff0c;…

本地开发环境请求服务器接口跨域的问题(vue的问题)

上面的这个报错大家都不会陌生&#xff0c;报错是说没有访问权限&#xff08;跨域问题&#xff09;。本地开发项目请求服务器接口的时候&#xff0c;因为客户端的同源策略&#xff0c;导致了跨域的问题。下面先演示一个没有配置允许本地跨域的的情况&#xff1a; 可以看到&…

Android可换行的RadioGroup

Android可换行的RadioGroup,有时候需要换行显示的单选列表&#xff0c;当然可以有多种实现方式&#xff0c;比如recycleview或者listview实现&#xff0c;本文采用的是RadioGrouprediobutton方式实现。由于RadioGroup仅支持水平布局与垂直布局&#xff0c;故需要自定义控件实现…

jenkins-cl参数化构建

pipeline片段&#xff08;对应jenkins-cli -p参数的BRANCHdevelop&#xff09; parameters {string(name: BRANCH, defaultValue: master, description: Enter the branch name)}stages {stage(Get Code) {steps {script {def branch params.BRANCHcheckout scmGit(branches: …

2024/1/14周报

文章目录 摘要Abstract文献阅读题目问题与创新方法A.CEMDAN方法B.LSTM网络C. CEEMDAN-LSTM模型 实验过程数据集与数据预处理参数设置评价指标和参数 实验结果 深度学习GRUGRU前向传播GRU的训练过程 总结 摘要 本周阅读了一篇基于CEEMDAN-LSTM的金融时间序列预测模型的文章&…

性能分析与调优: Linux 实现 缺页剖析与火焰图

目录 一、实验 1.环境 2.缺页(RSS增长)剖析与火焰图 一、实验 1.环境 &#xff08;1&#xff09;主机 表1-1 主机 主机架构组件IP备注prometheus 监测 系统 prometheus、node_exporter 192.168.204.18grafana监测GUIgrafana192.168.204.19agent 监测 主机 node_exporter…

redis夯实之路-集群详解

Redis有单机模式和集群模式。 集群是 Redis 提供的分布式数据库方案&#xff0c;集群通过分片( sharding )来实现数据共享&#xff0c;并提供复制和故障转移。集群模式可以有多个 master 。使用集群模式可以进一步提升 Redis 性能&#xff0c;分布式部署实现高可用性&#xff…

【Java 干货教程】Java实现分页的几种方式详解

一、前言 无论是自我学习中&#xff0c;还是在工作中&#xff0c;固然会遇到与前端搭配实现分页的功能&#xff0c;发现有几种方式&#xff0c;特此记录一下。 二、实现方式 2.1、分页功能直接交给前端实现 这种情况也是有的&#xff0c;(根据业务场景且仅仅只能用于数据量…

6、C语言:输入与输出

输入输出 标准输入输出getchar&putchar函数printf函数sprintf函数格式化输入——scanf函数 文件访问文件读写 错误处理&#xff1a;stderr和exit行输入和行输出常用函数字符串操作函数字符类别测试和转换函数存储管理函数数学函数随机数发生器函数其他 标准输入输出 getch…

x-cmd pkg | grex - 用于生成正则表达的命令行工具

目录 简介首次用户生成的正则表达式与 perl 和 rust 兼容支持 Unicode 符号友好的用户体验进一步阅读 简介 grex 是一个旨在简化创作正则表达式的复杂且繁琐任务的库和命令行程序。这个项目最初是 Devon Govett 编写的 JavaScript 工具 regexgen 的 Rust 移植。但 regexgen 在…

红酒和果酒推荐

一、红酒 首先&#xff0c;说一下大家常见的几十元红酒和贵的红酒的区别。 1.品牌价值。 2.工艺要求。 3.主要原料优质与否。几十元的红酒&#xff1a; 工艺要求没有高档红酒要求高&#xff0c;另外用的葡萄是榨的汁&#xff0c;品牌价值低&#xff08;目前市场品牌推广的费…

vue组件通信

1. 概述 组件通信, 就是指 组件与组件 之间的数据传递。 注&#xff1a;组件的数据是独立的&#xff0c;无法直接访问其他组件的数据。所以需要了解组件通信 口诀&#xff1a;谁的数据谁处理 2. 组件关系 不同的组件关系包括&#xff1a; 父子关系&#xff08;包含&#xff…

启英泰伦推出「离线自然说」,离线语音交互随意说,不需记忆词条

离线语音识别是指不需要依赖网络&#xff0c;在本地设备实现语音识别的过程&#xff0c;通常以端侧AI语音芯片作为载体来进行数据的采集、计算和决策。但是语音芯片的存储空间有限&#xff0c;通过传统的语音算法技术&#xff0c;最多也只能存储数百条词条&#xff0c;导致用户…

SOLID 原则

单一功能原则 单一功能原则&#xff08;Single responsibility principle&#xff09;规定每个类都应该有一个单一的功能&#xff0c;并且该功能应该由这个类完全封装起来。所有它的&#xff08;这个类的&#xff09;服务都应该严密的和该功能平行&#xff08;功能平行&#x…

杨中科 EFCORE 第四部分 命令详解56-61

Migrations 深入研究Migrations 1、使用迁移脚本&#xff0c;可以对当前连接的数据库执行编号更高的迁移&#xff0c;这个操作叫做“向上迁移” (Up)&#xff0c;也可以执行把数据库回退到旧的迁移&#xff0c;这个操作叫“向下迁移(Down&#xff09; 2、除非有特殊需要&…