门户网站建设哪家好,百度地图轨迹导航,网站数据分析报表,物联网app开发平台第十一章 有效的字母异位词题目理解代码 两数之和题目理解(暴力篇)代码题目理解(哈希篇)代码 有效的字母异位词
力扣链接 给定两个字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的字母异位词
注意#xff1a;若 s 和 t 中每个字符出现的次数都相同#xff0c;… 第十一章 有效的字母异位词题目理解代码 两数之和题目理解(暴力篇)代码题目理解(哈希篇)代码 有效的字母异位词
力扣链接 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词
注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词 示例 1: 输入: s “anagram”, t “nagaram” 输出: true 示例 2: 输入: s “rat”, t “car” 输出: false 提示: 1 s.length, t.length 5 * 104 s 和 t 仅包含小写字母
题目理解
因为题目的要求是:
两个数组 仅仅包含小写字母 ⇒ 一共才26个英语字母两个数组的大小是 1 length 5*10的四次方
⇒ 我们可以采用 哈希的思想 我们可以用一个数组(利用下标)来记录两个数组中每个字母出现的次数 然后通过比较 每个字母出现的次数 和 0 进行比较
️那小写字母如何装换为数组下标? 通过ASCLL码来进行转化 ⇒ 字母 - a
代码
class Solution {
public:bool isAnagram(string s, string t) {int sum[26] {0};// 如果两个数组的大小都不一样, 那就直接返回 falseif(s.size() ! t.size())return false;for(int i 0; i s.size(); i){sum[s[i] - a]; // a数组的此字母对应的下标sum[t[i] - a]--; // b数组的此字母对应的下标--}// 如果两个数组每个字符出现的次数是一样的, 每个下标对应的都是 0for(int i 0; i 26; i){if(sum[i] ! 0)return false;}return true;}
};两数之和
力扣链接 给定一个整数数组 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] 提示 2 nums.length 104 -109 nums[i] 109 -109 target 109 只会存在一个有效答案
题目理解(暴力篇)
这题一看就是 低配版 ⇒ 2 size( ) 10^4, 这个数组的大小就是很巴适 暴力解法就是 两个for循环 ⇒ 最大时间也是 10^8, 不会爆时间的
代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {vectorint sum;for(int i 0; i nums.size(); i){for(int j i 1; j nums.size(); j){if(nums[j] target - nums[i]){sum.push_back(i);sum.push_back(j);break;}}}return sum;}
};题目理解(哈希篇)
我们就会发现, 暴力解法虽然可以, 但是执行时间很长, 那有没有执行时间短的方法呢? 我们的一个思路是: 当我们顺序遍历该数组时, 当我们遍历到一个特定的下标(nums[i])时, 我们需要知道 target - nums[i] 这个数字是否在之前遍历过的数字里面出现过 如果出现 — — 返回 (target - nums[i]) 的下标 和 nums[i]的下标 (i)如果没有出现 — — 不返回, 如果直至数组的结尾, 也没有出现, 那就返回空 当我们查询一个元素是否出现过, 或者一个元素在一个集合中是否存在 — — 那就可以使用哈希
在本题中, 我们不仅需要知道 (target - nums[i])这个数是否遍历过, 也要知道 (target - nums[i]) 的下标 ⇒ 那么我们就不能用数组来进行存储了, 可以采用 map的方式进行存储 (key, value)
⇒ key该存储什么, value又该存储什么呢? 由于本题需要返回的是下标, 所以 key应该存储下标, valu来存储数值
⇒ 那map有三种形式, 我们应该选取哪一种呢? map, unordered_map, multimap
由于unordered_map的查询效率是三个当中最快的, 那么我们就选用 unordered_map
代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {// 选用unordered_map这个数据结构std::unordered_mapint, int map;for(int i 0; i nums.size(); i){// 查询 target - nums[i]是否被遍历过auto cur map.find(target - nums[i]);// 之前有被遍历过, 那就直接返回if(cur ! map.end()){return {cur-second, i};}// 没有遍历过, 那就收入map里面map.insert(pairint, int (nums[i], i));}// 最后在map里面都没有找到, 那就返回空return {}; }
};这个题目要搞懂的四个点:
为什么要选取哈希的算法哈希为啥要用map的数据结构map是用来干什么的map中的key是用来存放什么的, value是用来存放什么的
个人感觉, 搞懂这四个点, 那么此题目就理得条条顺顺喽!!! 人是有惰性属性的动物一旦过多地沉湎于温柔之乡就更削弱了重新投入风暴的勇气和力量. — — 路遥早晨从中午开始
