【12.30】转行小白历险记-刷算法06

2023-12-31 06:28

本文主要是介绍【12.30】转行小白历险记-刷算法06,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

01补充一下:哈希表的基础知识

1. 创建哈希表

在 JavaScript 中,您可以使用对象或 Map 来创建一个哈希表。

  • 使用对象:
let hashTable = {};
  • 使用 Map 对象:
let hashMap = new Map();

2. 插入键值对(Add / Set)

向哈希表中添加键值对。

  • 使用对象:
hashTable[key] = value;
  • 使用 Map 对象:
hashMap.set(key, value);

3. 搜索键值(Get)

根据键获取哈希表中的值。

  • 使用对象:
let value = hashTable[key];
  • 使用 Map 对象:
let value = hashMap.get(key);

4. 检查键是否存在(Check for Key)

检查哈希表中是否存在某个键。

  • 使用对象:
let exists = key in hashTable;
  • 使用 Map 对象:
let exists = hashMap.has(key);

5. 删除键值对(Delete)

从哈希表中删除一个键值对。

  • 使用对象:
delete hashTable[key];
  • 使用 Map 对象:
hashMap.delete(key);

6. 遍历哈希表(Iterate)

遍历哈希表中的所有键值对。

  • 使用对象:
for (let key in hashTable) {if (hashTable.hasOwnProperty(key)) {console.log(key, hashTable[key]);}
}
  • 使用 Map 对象
hashMap.forEach((value, key) => {console.log(key, value);
});

7. 获取哈希表大小(Size)

获取哈希表中的键值对数量。

  • 使用对象:需要手动计算。
let size = Object.keys(hashTable).length;
  • 使用 Map 对象:
let size = hashMap.size;

02JS常见数据结构

在 JavaScript 中,数组(Array)、集合(Set)和映射(Map)都是用于存储数据的常见数据结构,但它们各自有不同的特性和用途:

数组(Array)

  1. 有序集合:数组是元素的有序集合,其中每个元素都有一个数字索引。

  2. 重复元素:数组可以包含重复的元素。

  3. 元素类型:数组中的元素可以是任意类型,包括不同类型的混合。

  4. 使用场景:适用于需要顺序访问或快速访问特定索引元素的场景。

  5. 基本操作:添加、删除、访问元素等,以及一系列数组特有的方法(如 mapfilterreduce 等)。

集合(Set)

  1. 无序集合:Set 是无序的集合,不保证元素的顺序。

  2. 唯一元素:Set 中的元素是唯一的,不允许重复。

  3. 元素类型:Set 中的元素可以是任意类型。

  4. 使用场景:适用于需要存储不重复元素、快速检查元素是否存在的场景。

  5. 基本操作:添加、删除元素,以及检查元素是否存在。

映射(Map)

  1. 键值对:Map 存储键值对集合,其中键和值可以是任意类型。

  2. 有序集合:Map 保持键值对的插入顺序。

  3. 唯一键:Map 中的键是唯一的。

  4. 使用场景:适用于需要快速访问、更新或删除键值对的场景。

  5. 基本操作:添加、删除键值对,访问或更新值,以及遍历键值对。

总结

  • 数组(Array):有序集合,可包含重复元素,通过数字索引访问元素。
  • 集合(Set):无序集合,元素唯一,不包含重复元素,常用于去重和快速查找。
  • 映射(Map):键值对集合,保持插入顺序,键唯一,适用于存储和处理相关联的数据。

 03Leetcode:350. 两个数组的交集

下面的代码逻辑是用set实现的,set创建的数据结构是没有重复元素的,所以一旦数组中有重复的元素,会导致输出的结果只有一个比如

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

这个和题意不太符合

在选择数据结构的时候可以选择Map

函数逻辑,适合349的题号

  1. 数组交换(如果需要)

    • 首先,代码检查两个数组的长度。如果 nums1 的长度小于 nums2 的长度,则交换这两个数组。这样做的目的是优化性能,减少后续在较大的数组上进行的查找操作。
  2. 创建 Set 对象

    • nums1Set 是使用 nums1 创建的 Set 对象。由于 Set 中的元素是唯一的,这样可以快速检查一个元素是否存在于 nums1 中。
    • resSet 是一个用来存储最终交集结果的空 Set 对象。
  3. 查找交集

    • 遍历 nums2 中的每个元素。对于 nums2 中的每个元素,检查它是否存在于 nums1Set 中(即是否也是 nums1 的元素)。
    • 如果存在,则将该元素添加到结果集 resSet 中。由于 Set 自动处理重复值,因此即使 nums2 中有重复元素,结果集中也不会有重复
  4. 返回结果

    • 使用 Array.from(resSet) 将结果集 resSet 转换为数组形式,并返回。这是因为 Set 对象不是数组,而题目要求返回数组形式的结果。

示例

假设调用 intersection([1, 2, 2, 1], [2, 2]),函数将执行如下:

  • 由于 [1, 2, 2, 1] 的长度不小于 [2, 2] 的长度,因此不交换数组。
  • 创建 nums1Set{1, 2}
  • 遍历数组 [2, 2],并检查每个元素是否在 nums1Set 中。
  • 2nums1Set 中,因此被添加到 resSet 中。
  • 返回 [2] 作为交集结果。

 正确解法用

用map和数组相结合

04 快乐数

示例 1:检测 19 是否是快乐数

  1. 初始化

    • n = 19
    • seen 集合为空。
  2. 第一次循环

    • 19 不等于 1,且 19 不在 seen 集合中,因此继续执行。
    • 19 添加到 seen 集合中。
    • 计算 19 的各位数的平方和:1*1 + 9*9 = 1 + 81 = 82
    • 更新 n = 82
  3. 第二次循环

    • 82 不等于 1,且 82 不在 seen 集合中。
    • 82 添加到 seen 集合中。
    • 计算 82 的各位数的平方和:8*8 + 2*2 = 64 + 4 = 68
    • 更新 n = 68
  4. 后续几次循环

    • 类似地,计算 68 的各位数平方和得到 100,然后计算 100 的各位数平方和得到 1
    • 更新 n = 1
  5. 结束循环

    • n 等于 1,跳出循环。
  6. 返回结果

    • n === 1true,因此函数返回 true,表示 19 是快乐数。

示例 2:检测 2 是否是快乐数

  1. 初始化

    • n = 2
    • seen 集合为空。
  2. 循环

    • 重复计算 n 的各位数的平方和,并更新 n
    • 每次迭代后检查 n 是否变为 1 或 n 是否已存在于 seen 中。
    • 在计算的过程中,您会发现 n 开始循环(例如,变为之前已经出现过的数字),但永远不会变为 1。
  3. 结束循环

    • 检测到循环,因为 n 的值已经在 seen 集合中出现过。
  4. 返回结果

    • 因为 n 不等于 1,所以函数返回 false,表示 2 不是快乐数。

这篇关于【12.30】转行小白历险记-刷算法06的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/555224

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯: