代码随想录算法训练营第33期第三章 哈希表part01

2024-03-14 06:12

本文主要是介绍代码随想录算法训练营第33期第三章 哈希表part01,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

242. 有效的字母异位词 04分 21

给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的字母异位词。注意:st 中每个字符出现的次数都相同,则称 st 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"

输出: true

示例 2:

输入: s = "rat", t = "car"

输出: false


直接上代码


bool isAnagram(string s, string t) {map<char, int> hash;for (int i = 0; i < s.size(); i++) {			// 记录 s[i] 的出现次数if (hash.count(s[i])) hash[s[i]]++;   else hash[s[i]] = 1;}for (int i = 0; i < t.size(); i++) {			// 利用 t[i] 消除记录的 s[i] 出现次数if (hash.count(t[i])) hash[t[i]]--;else return false;}for (const auto& entry : hash) {if (entry.second != 0) return false;		// t 中有不能与 s 抵消的}return true;
}

349. 两个数组的交集 08 分 59

给定两个数组 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] 也是可通过的


直接上代码


vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {map<int, int> hash;for (int item : nums1) {if (hash.count(item)) hash[item]++;else hash[item] = 1;}vector<int> res;for (int item : nums2) {if (hash.count(item)) hash[item] = -10000;   // 标记,表示该元素在两数组的交集}for (auto item : hash) {if (item.second == -10000) res.push_back(item.first);}return res;
}

说明:一开始没有正确理解题意,以为只要 nums2 在 hash 中出现就行,没有考虑 nums2 的重复个数,所以导致得出的结果包含重复的元素。


202. 快乐数 

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

「快乐数」 定义为:

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

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19

输出:true

解释:

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

示例 2:

输入:n = 2

输出:false


解题思路


        和卡哥的解题方式不同,用的双指针,根据题目的规则,发现不是快乐数的计算一圈之后会回到原来的数,然后就形成死循环,而是快乐数的会因为变成 1 退出循环,所以又是一道双指针判断环的,最近接触了好多双指针。

int getSum(int n) {  						// 获取每个位数的平方和int sum = 0;while (n > 0) {int i = n % 10;sum += i * i;n /= 10;}return sum;
}bool isHappy(int n) {int fast = n, slow = n;do {  									// 模拟快指针走两步,慢指针走一步slow = getSum(slow);fast = getSum(fast);fast = getSum(fast);} while (fast != slow);return slow == 1;
}

1. 两数之和 04 分 59

给定一个整数数组 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]


双指针-快慢指针


        又是一道双指针的题,初始时,slow = 0,fast = 1, 不过这次循环的判断条件不是以 fast 为准,而是 slow,slow 一开始固定,然后 fast 不断向右移,如果到 nums.size() - 1 还没得到目标值,slow++, fast 重置为 slow + 1; 重复以上步骤,直到找到目标值。

vector<int> twoSum(vector<int>& nums, int target) {int slow = 0, fast = 1;while (slow < nums.size() - 1) {if (target - nums[slow] == nums[fast]) break;if (fast == nums.size() - 1) {  // fast 走到 数组末端 slow 移动,fast 指向 slow 前一个slow++; fast = slow + 1;}else ++fast;}return { slow, fast };
}

题外话,今天补前天的,前天收到一个面试,后面就完全准备面试了,没来得及写博客。

这篇关于代码随想录算法训练营第33期第三章 哈希表part01的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时