代码随想录算法训练营Day6 | 242.有效的字母异位词 ●349. 两个数组的交集 ● 202. 快乐数● 1. 两数之和

本文主要是介绍代码随想录算法训练营Day6 | 242.有效的字母异位词 ●349. 两个数组的交集 ● 202. 快乐数● 1. 两数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

基础:

1.哈希表是根据关键值进行直接访问的数据结构,时间复杂度是O(1),也就是通过数组的索引下标,直接访问数组中的元素哈希表的作用就是用来快速判断一个元素是否出现在集合里。

2.常见的哈希结构:

  • 数组
  • set (集合)
  • map (映射)

List, Set, Queue, Map 区别?
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序,存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对(key-value)存储,类似于数学上的函数 y=f(x),“x” 代表 key,“y” 代表 value,key 是无序的、不可重复的,value 是无序的、可重复的,每个键最多映射到一个值。

242.有效的字母异位数

题目:

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

题目链接:242. 有效的字母异位词

卡哥的视频链接:学透哈希表,数组使用有技巧!Leetcode:242.有效的字母异位词

题目思路:创建一个数组,遍历两个字符串,遍历第一个字符串时,把出现的字符串的ASCII码求出来,减去“a”的ASCII码,并得出数值,并在相应的数组位置加一,遍历第二个数组的时候变成减一,如果数组中有不为零的元素,则说明两个字符串不是完全一样的,本题只要求两个字符串所包含的元素相同,顺序无所谓。

代码示例:

代码逻辑详解:

  1. int []record = new int[26];:创建一个长度为26的整数数组 record,用于记录每个字母在字符串 s 中出现的次数。数组的下标表示字母的索引,例如 record[0] 对应字母 a 的出现次数,record[1] 对应字母 b 的出现次数,以此类推。

  2. for (int i = 0; i < s.length(); i++) {...}:遍历字符串 s 中的每个字符,对 record 数组进行更新。具体来说,对于字符串 s 中的每个字符,将该字符转换为相对于字母 a 的偏移量,并将对应的 record 数组中的计数加一。

  3. for (int i = 0; i < t.length(); i++) {...}:同样地,遍历字符串 t 中的每个字符,但这次是将对应的 record 数组中的计数减一。

  4. for(int count:record) {...}:使用增强型 for 循环遍历 record 数组中的每个元素 count。如果存在任何一个元素不等于0,说明字符串 s 中的某些字符在字符串 t 中没有完全匹配,因此返回 false

  5. 如果上述循环结束后,没有返回 false,则说明字符串 s 和字符串 t 是字母异位词,返回 true

这段代码利用了一个技巧,即通过一个数组来记录字符串中每个字母的出现次数。在遍历完两个字符串后,只需检查数组中的元素是否都为0,即可判断两个字符串是否为字母异位词。

leetcode提交记录:

小tips:

charAt(i) 函数 是获取字符串中i位置的字符

s.charAt(i) - 'a'求字母的ascii码之间的差值。

string.charAt(i) - '0'将其转换为整数。

循环条件得出字符串的长度时,length后面记得加括号!!

349. 两个数组的交集

题目:给定两个数组 nums1 和 nums2 ,返回 它们的 

交集

 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

题目链接:349. 两个数组的交集

卡哥的视频链接:学透哈希表,set使用有技巧!Leetcode:349. 两个数组的交集

题目思考:我们只需要找到相同的元素即可,所以重复的可以忽略,所以我们申请两个set集合,因为set集合中的元素不可以重复,申请两个set集合,把第一个数组中包含的元素录入set1,把同时包含在set1和数组2的元素录入set2,最后遍历输出set2集合中的元素即可

代码示例:

代码逻辑详解:

  1. if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; }:首先,检查输入的数组是否为 null 或长度为 0。如果其中任何一个数组为空,则返回一个空数组,因为两个空数组的交集也是空。

  2. Set<Integer> set1 = new HashSet<>();:创建一个 HashSet 集合 set1,用于存储 nums1 数组中的元素。这样做是为了方便快速查找 nums2 数组中的元素是否存在于 nums1 中。

  3. Set<Integer> resSet = new HashSet<>();:创建一个 HashSet 集合 resSet,用于存储两个数组的交集。

  4. for(int i : nums1) { set1.add(i); }:遍历 nums1 数组中的元素,将每个元素添加到 set1 集合中。由于集合中不允许重复元素,这样可以确保 set1 中不会包含重复元素。

  5. for(int i : nums2) { if(set1.contains(i)) { resSet.add(i); } }:遍历 nums2 数组中的元素,对于每个元素,检查是否存在于 set1 集合中。如果存在,则将该元素添加到 resSet 集合中,这样 resSet 集合中存储的就是两个数组的交集。

  6. int[] arr = new int[resSet.size()];:创建一个数组 arr,其长度为 resSet 集合的大小,这样数组的长度就是交集的大小。

  7. int j = 0; for(int i : resSet) { arr[j] = i; j++; }:遍历 resSet 集合中的元素,并将每个元素存储到数组 arr 中。这样,数组 arr 中存储的就是两个数组的交集。

  8. return arr;:返回存储交集元素的数组 arr

leetcode提交记录:

小tips:

得出集合长度是size而不是length

202.快乐数

题目:

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

题目链接:202.快乐数

此题卡哥无视频讲解

快乐数示例:

输入:19
输出:true
解释:

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

题目思考:编写求快乐数的函数,当所要求的数字不是一,也不重复时,就调用函数,计算出是否是快乐数

代码示例:

代码逻辑详解:

  1. Set<Integer> a = new HashSet<>();:创建一个 HashSet 集合 a,用于存储出现过的数字。这样做是为了检测循环,如果在循环中出现了重复的数字,就说明这个数不是快乐数。

  2. while (n != 1 && !a.contains(n)) { ... }:使用 while 循环,循环条件是当 n 不等于 1 且集合 a 中不包含当前数字 n 时执行循环。这个循环会持续直到 n 变为 1(即快乐数)或者出现了重复的数字(即非快乐数)。

  3. a.add(n);:将当前数字 n 加入到集合 a 中,标记为已经访问过。

  4. n = getNextNumber(n);:调用 getNextNumber(n) 方法,根据当前数字 n 计算下一个数字,并将其赋值给 n。

  5. public int getNextNumber(int n) { ... }:定义了一个方法 getNextNumber(int n),用于计算下一个数字。在这个方法中,首先将 n 的各个位上的数字平方后相加,然后返回这个结果。

  6. return n == 1;:如果循环结束后,n 等于 1,则说明这个数是快乐数,返回 true;否则,返回 false。

通过这段代码,可以判断一个整数是否是快乐数。如果一个数是快乐数,那么经过一系列计算后会得到 1;如果不是快乐数,会进入一个循环,最终导致计算出现重复的数字。

leetcode提交记录:​​​​​​​

小tips:注意循环的条件!还有HashSet的写法

1.两数之和

题目:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

题目链接:1. 两数之和

卡哥的视频链接:梦开始的地方,Leetcode:1.两数之和,学透哈希表,map使用有技巧!

题目思考:

这篇关于代码随想录算法训练营Day6 | 242.有效的字母异位词 ●349. 两个数组的交集 ● 202. 快乐数● 1. 两数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “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)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

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

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

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

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

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

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