代码随想录算法训练营第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

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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

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