怎么自己做网站游戏,网站ui外包,域名如何申请,营销网络电话软件文章目录 #x1f914;0.哈希表#x1f33c;1. 两数之和#x1f33b;1. 题目#x1f337;2. 算法原理#x1f33a;3. 代码实现 #x1f348;面试题 01.02. 判定是否互为字符重排#x1f34c;1. 题目#x1f34f;2. 算法原理#x1f353;3. 代码实现 #x1f914;0.哈… 文章目录 0.哈希表1. 两数之和1. 题目2. 算法原理3. 代码实现 面试题 01.02. 判定是否互为字符重排1. 题目2. 算法原理3. 代码实现 0.哈希表
哈希表用于“快速”查找某个元素在刷题的时候如果数据范围不大我们可以用数组来模拟一个建议的哈希表C里面的哈希表是unordered_map关于哈希表的内容可以查看此篇文章哈希(hash)——【C实现】
1. 两数之和
1. 题目 题目链接1. 两数之和 给定一个整数数组 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只会存在一个有效答案
**进阶**你可以想出一个时间复杂度小于 O(n2) 的算法吗
2. 算法原理
解法一暴力枚举
这里固定一个元素然后遍历后面的元素看看有没有和为target的两层for循环时间复杂度为O(N2)
解法二哈希表
我们找个一个元素之后只需要看数组里面是否有target-nums[i]的值要快速确定一个值采用哈希表。
这里因为要返回元素的下标所以我们哈希表里面的映射为nums[i], i。 不要一次性将元素全部丢进哈希表例如target 4数组为[2,3,4,5]如果先全部丢进去那么到2的时候哈希表里面有hash[nums[i]] target - nums[i]的但是这个情况明显不符合 3. 代码实现
class Solution {
public:vectorint twoSum(vectorint nums, int target){unordered_mapint, int hash;for(int i 0; i nums.size(); i){int x target - nums[i];if(hash.count(x)) return {i,hash[x]};hash[nums[i]] i;}return {-1,-1};}
};运行结果 面试题 01.02. 判定是否互为字符重排
1. 题目 题目链接面试题 01.02. 判定是否互为字符重排 给定两个由小写字母组成的字符串 s1 和 s2请编写一个程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。
示例 1
输入: s1 abc, s2 bca
输出: true 示例 2
输入: s1 abc, s2 bad
输出: false说明
0 len(s1) 100 0 len(s2) 100
2. 算法原理
解法一排序比较
这里可以直接用sort将这2个字符串排序然后直接比较这两个字符串是否相等即可排序sort的时间复杂度为O(2N*logN)
解法一哈希表
这里也能直接统计字符出现的个数如果这两个字符串字符都相同且出现的个数一样即代表互为重排列。 这里要创建1个哈希表但是只有26个英文字母所以直接用数组模拟哈希表即可。 时间复杂度为O(2N)
3. 代码实现
排序比较 class Solution {
public:bool CheckPermutation(string s1, string s2){if(s1.size() ! s2.size()) return false;sort(s1.begin(),s1.end());sort(s2.begin(),s2.end());return s1 s2;}
};哈希表
class Solution {
public:bool CheckPermutation(string s1, string s2){if(s1.size() ! s2.size()) return false;int hash[26] { 0 };for(auto ch1 : s1)hash[ch1 - a];for(auto ch2 : s2){hash[ch2 - a]--;if(hash[ch2- a] 0) return false;}return true;}
};运行结果
