当前位置: 首页 > news >正文

跟着《代码随想录》刷题(三)——哈希表

3.1 哈希表理论基础

哈希表理论基础

3.2 有效的字母异位词

242.有效的字母异位词

在这里插入图片描述
C

bool isAnagram(char * s, char * t){int array[26] = {0};int i = 0;while (s[i]) {// 并不需要记住字符的ASCII码,只需要求出一个相对数值就可以了array[s[i] - 'a']++;i++;}i = 0;while (t[i]) {array[t[i] - 'a']--;i++;}for (i = 0; i < 26; i++) {// 如果数组有元素不为0,说明字符串s和t 一定是谁多了字符或者谁少了字符if (array[i] != 0)return false;}// 数组所有元素都为0,说明字符串s和t是字母异位词return true;
}

cpp

class Solution {
public:bool isAnagram(string s, string t) {int array[26] = {0};for (int i = 0; i < s.size(); i++) {array[s[i] - 'a']++;}for (int j = 0; j < t.size(); j++) {array[t[j] - 'a']--;}for (int k = 0; k < 26; k++) {if (array[k] != 0) {return false;}}return true;}
};

383.赎金信

在这里插入图片描述
在这里插入图片描述

c

bool canConstruct(char * ransomNote, char * magazine){int array[26] = {0};if (strlen(ransomNote) > strlen(magazine)) return false;int i = 0;while (magazine[i]) {array[magazine[i] - 'a']++;i++;}i = 0;while(ransomNote[i]) {array[ransomNote[i] - 'a']--;if (array[ransomNote[i] - 'a'] < 0)return false;i++;}return true;
}

cpp

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.length() > magazine.length()) {return false;}int array[26] = {0};for (int i = 0; i < magazine.length(); i++) {array[magazine[i] - 'a']++;}for (int j = 0; j < ransomNote.length(); j++) {array[ransomNote[j] - 'a']--;if (array[ransomNote[j] - 'a'] < 0) {return false;}}return true;}
};

49. 字母异位词分组

在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> result;unordered_map<string, vector<string>> map;for (string &s : strs) {string key = s;sort(key.begin(), key.end());map[key].emplace_back(s);}for (auto &it : map) result.emplace_back(it.second);return result;}
};

438. 找到字符串中所有字母异位词(滑动窗口+哈希)

在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<int> findAnagrams(string s, string p) {int len_s = s.length();int len_p = p.length();if (len_s < len_p)return vector<int> ();vector<int> count_s(26);vector<int> count_p(26);vector<int> res;for (int i = 0; i < len_p; i++) {count_s[s[i] - 'a']++;count_p[p[i] - 'a']++;}if (count_s == count_p)res.push_back(0);for (int j = 0; j < len_s - len_p; j++) {count_s[s[j] - 'a']--;count_s[s[j + len_p] - 'a']++;if (count_s == count_p)res.push_back(j + 1); // 注意:这里左边已经移动了一位了,所以要加1}return res;}
};

3.3 两个数组的交集

349. 两个数组的交集

在这里插入图片描述
c语言

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;// 用calloc直接全部初始化为0,malloc则是随机值int *res = calloc(lessSize, sizeof(int));int hash[1001] = {0};for (int i = 0; i < nums1Size; i++) {hash[nums1[i]]++;}int count = 0;for (int j = 0; j < nums2Size; j++) {if (hash[nums2[j]] > 0) {res[count++] = nums2[j];}hash[nums2[j]] = 0;}*returnSize = count;return res;
}

cpp
解法一:

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;// 存放结果,之所以用unordered_set,是为了给结果去重unordered_set<int> set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2中的结果在set中出现过if (set.find(num) != set.end()) {result.insert(num);}}return vector<int> (result.begin(), result.end());}
};

解法二:

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;int hash[1001] = {0};for (int n1 : nums1) {hash[n1] = 1;}for (int n2 : nums2) {if (hash[n2] == 1) {result.insert(n2);}}return vector<int>(result.begin(), result.end());}
};

350. 两个数组的交集||

C语言

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;int* ret = calloc(lessSize, sizeof(int));int hash[1001] = {0};int count = 0;int i;for (i = 0; i < nums1Size; i++) {hash[nums1[i]]++;}for (i = 0; i < nums2Size; i++) {if (hash[nums2[i]] > 0) {ret[count++] = nums2[i];hash[nums2[i]]--;}}*returnSize = count;return ret;
}

C++

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> num_map;for (int n1 : nums1) {num_map[n1]++;}vector<int> res;for (int num : nums2) {if (num_map.count(num)) {res.push_back(num);num_map[num]--; if (num_map[num] == 0) {num_map.erase(num);}}}return res;}
};

3.4 快乐数(unordered_set)

202. 快乐数

在这里插入图片描述
在这里插入图片描述

class Solution {
public:int getSum(int n) {int sum = 0;while (n) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {if (1 == n)return true;unordered_set<int> sum_set;int sum = 0;while (1) {sum = getSum(n);if (1 == sum)return true;// 如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return falseif (sum_set.find(sum) != sum_set.end()) {return false;} else {sum_set.insert(sum);n = sum;}}}
};

3.5 两数之和(unorderd_map)

1.两数之和

在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> map;for (int i = 0; i < nums.size(); i++) {int s = target - nums[i];auto iter = map.find(s);// 遍历当前元素,并在map中寻找是否有匹配的keyif (iter != map.end()) {return {iter->second, i};} else {// 如果没找到匹配对,就把访问过的元素和下标加入到map中map.insert(pair<int, int>(nums[i], i));}}return {};}
};

3.6 四数相加||

454. 四数相加||

在这里插入图片描述

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map; //key:a+b的数值,value:a+b数值出现的次数int target = 0;int count = 0;// 统计a+b+c+d = 0 出现的次数// 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中for (int a : nums1) {for (int b : nums2)map[a + b]++;}// 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,//就把map中key对应的value也就是出现次数统计出来。for (int c : nums3) {for (int d : nums4) {target = 0 - (c + d);if (map.find(target) != map.end()) {count += map[target];}}}return count;}
};

3.7 赎金信

383.赎金信

在这里插入图片描述
在这里插入图片描述

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.length() > magazine.length()) return false;int array[26] = {0};for (char s1 : magazine) {array[s1 - 'a']++;}for (char s2 : ransomNote) {array[s2 - 'a']--;if (array[s2 - 'a'] < 0)return false;}return true;}
};

3.8 三数之和

15.三数之和

在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(), nums.end());// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了for (int i = 0; i < nums.size(); i++) {if (nums[i] > 0) return res;// 正确去重a方法if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) right--;else if (sum < 0)left++;else {res.push_back(vector<int>{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重while (left < right && nums[right] == nums[right - 1])right--;while (left < right && nums[left] == nums[left + 1])left++;// 找到答案时,双指针同时收缩right--;left++;}}}return res;}
};

3.9 四数之和

18. 四数之和

在这里插入图片描述

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort(nums.begin(), nums.end());// 一级剪枝for (int k = 0; k < nums.size(); k++) {if (nums[k] > target && nums[k] >=0)break; // 这里使用break,统一通过最后的return返回// 一级去重,对nums[k]去重if (k > 0 && nums[k] == nums[k - 1])continue;for (int i = k + 1; i < nums.size(); i++) {// 二级剪枝if (nums[k] + nums[i] > target && nums[k] + nums[i] >=0)break;// 二级去重,对nums[i]去重if (i > k + 1 && nums[i] == nums[i - 1])continue;int left = i + 1;int right = nums.size() - 1;while (left < right) {// 会溢出long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];if (sum > target)right--;else if (sum < target)left++;else {res.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});// 对nums[left]和nums[right]去重while (left < right && nums[right] == nums[right - 1])right--;while (left < right && nums[left] == nums[left + 1])left++;// 找到答案时,双指针同时收缩right--;left++;}}}}return res;}
};

参考:《代码随想录》哈希表

相关文章:

跟着《代码随想录》刷题(三)——哈希表

3.1 哈希表理论基础 哈希表理论基础 3.2 有效的字母异位词 242.有效的字母异位词 C bool isAnagram(char * s, char * t){int array[26] {0};int i 0;while (s[i]) {// 并不需要记住字符的ASCII码&#xff0c;只需要求出一个相对数值就可以了array[s[i] - a];i;}i 0;whi…...

HTML - 扫盲

文章目录1. 前言2. HTML2.1 下载 vscode3 HTML 常见标签3.1 注释标签3.2 标题标签3.3 段落标签3.4 换行标签3.5 格式化标签1. 加粗2. 倾斜3. 下划线3.6 图片标签3.7 超链接标签3.8 表格标签3.9 列表标签4. 表单标签4.1 from 标签4.2 input 标签4.3 select 标签4.4 textarea标签…...

【系统分析师之路】2022上案例分析历年真题

【系统分析师之路】2022上案例分析历年真题 【系统分析师之路】2022上案例分析历年真题【系统分析师之路】2022上案例分析历年真题2022上案例分析历年真题第一题&#xff08;25分&#xff09;2022上案例分析历年真题第二题&#xff08;25分&#xff09;2022上案例分析历年真题第…...

Python编程规范

Python编程规范 当今Python编程社区有许多关于编程规范的约定和惯例。以下是一些常见的Python编程规范&#xff1a; 1.使用有意义的命名 使用有意义的命名可以使代码更加清晰、易读、易维护。变量、函数、类和模块的命名应该能够明确传达其用途&#xff0c;而不是使用无意义…...

【Java】Spring Boot项目的创建和使用

文章目录SpringBoot的创建和使用1. 什么是Spring Boot&#xff1f;为什么要学Spring Boot&#xff1f;2. Spring Boot项目的优点3. Spring Boot 项目的创建3.1 使用idea创建3.2 接下来创建Spring Boot项目4. 项目目录介绍和运行4.1 运行项目4.2 输出内容5. 总结SpringBoot的创建…...

Malware Dev 00 - Rust vs C++ 初探

写在最前 如果你是信息安全爱好者&#xff0c;如果你想考一些证书来提升自己的能力&#xff0c;那么欢迎大家来我的 Discord 频道 Northern Bay。邀请链接在这里&#xff1a; https://discord.gg/9XvvuFq9Wb我会提供备考过程中尽可能多的帮助&#xff0c;并分享学习和实践过程…...

JavaScript HTML DOM 事件

文章目录JavaScript HTML DOM 事件对事件做出反应HTML 事件属性使用 HTML DOM 来分配事件onload 和 onunload 事件onchange 事件onmouseover 和 onmouseout 事件onmousedown、onmouseup 以及 onclick 事件JavaScript HTML DOM 事件 HTML DOM 使 JavaScript 有能力对 HTML 事件做…...

推荐算法——NCF知识总结代码实现

NCF知识总结代码实现1. NeuralCF 模型的结构1.1 回顾CF和MF1.2 NCF 模型结构1.3 NeuralCF 模型的扩展---双塔模型2. NCF代码实现2.1 tensorflow2.2 pytorchNeuralCF&#xff1a;如何用深度学习改造协同过滤&#xff1f; 随着技术的发展&#xff0c;协同过滤相比深度学习模型的…...

redis(4)String字符串

前言 Redis中有5大数据类型&#xff0c;分别是字符串String、列表List、集合Set、哈希Hash、有序集合Zset&#xff0c;本篇介绍Redis的字符串String Redis字符串 String是Redis最基本的类型&#xff0c;你可以理解成与Memcached一模一样的类型&#xff0c;一个key对应一个value…...

session一致性问题

在http访问请求中&#xff0c;web服务器会自动为同一个浏览器的访问用户自动创建唯一的session&#xff0c;提供数据存储功能。最常见的&#xff0c;会把用户的登录信息、用户信息存储在session中&#xff0c;以保持登录状态。只要用户不重启浏览器&#xff0c;每次http短连接请…...

上岸16K,薪资翻倍,在华为外包做测试是一种什么样的体验····

现在回过头看当初的决定&#xff0c;还是正确的&#xff0c;自己转行成功&#xff0c;现在进入了华为外包测试岗&#xff0c;脱离了工厂生活&#xff0c;薪资也翻了一倍不止。 我17年毕业于一个普通二本学校&#xff0c;电子信息工程学院&#xff0c;是一个很不出名的小本科。…...

django项目中如何添加自定义的django command

项目目录 1.我们自己建立的application叫做app&#xff0c;首先在这个app目录下&#xff0c;我们需要新建management目录&#xff0c;这个目录里应该包括&#xff1a;__ init__.py&#xff08;内容为空&#xff0c;用于打包&#xff09;和commands目录&#xff0c;然后在comma…...

【算法基础】哈希表⭐⭐⭐

一、哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意…...

基于SpringMVC、Spring、MyBatis开发的校园点餐系统

文章目录 项目介绍主要功能截图:后台登录用户管理商品管理评论管理订单管理角色管理咨询管理前台前台首页我的订单商品详情支付方式选择支付成功页面部分代码展示设计总结项目获取方式🍅 作者主页:Java韩立 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题…...

LeetCode 热题 C++ 148. 排序链表 152. 乘积最大子数组 160. 相交链表

力扣148 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4]示例 2&#xff1a; 输入&#xff1a;head [-1,5,3,4,0] 输出&#xff1a;[-1,0,3,4,5]示例 3&#x…...

JavaScript 基础【快速掌握知识点】

目录 为什么要学JavaScript? 什么是JavaScript 特点&#xff1a; 组成&#xff1a; JavaScript的基本结构 基本结构 内部引用 外部引用 console对象进行输出 JavaScript核心语法 1、变量声明 2、数据类型 3、运算符 4、条件语句 5、循环语句 6、数组 7…...

基于Frenet优化轨迹的⾃动驾驶动作规划⽅法

动作规划&#xff08;Motion Control&#xff09;在⾃动驾驶汽⻋规划模块的最底层&#xff0c;它负责根据当前配置和⽬标配置⽣成⼀序列的动作&#xff0c;本⽂介绍⼀种基于Frenet坐标系的优化轨迹动作规划⽅法&#xff0c;该⽅法在⾼速情况下的ACC辅助驾驶和⽆⼈驾驶都具有较强…...

Spring(入门)

1. 什么是spring&#xff0c;它能够做什么?2. 什么是控制反转(或依赖注入)3. AOP的关键概念4. 示例 4.1 创建工程4.2 pom文件4.3 spring配置文件4.4 示例代码 4.4.1 示例14.4.2 示例2 &#xff08;abstract&#xff0c;parent示例&#xff09;4.4.3 使用有参数构造方法创建jav…...

2023-02-25力扣每日一题

链接&#xff1a; https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/ 题意&#xff1a; 给定字符串s1,s2&#xff0c;仅由x,y组成 每次可以在两边各挑一个字符交换 求让s1等于s2的最小步骤 解&#xff1a; 1000啊1000&#xff0c;双指针贪一下就过了 …...

如何外网登录管理云通信短信网关平台?——快解析映射方案

云通信&#xff08;Cloud Communications &#xff09;是基于云计算商业模式应用的通信平台服务&#xff0c;简单易用,满足企业一键群发场景,支持多种语言SDK和API 接入。各个通信平台软件都集中在云端&#xff0c;且互通兼容&#xff0c;用户只要登录云通信平台&#xff0c;不…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...