242. 有效的字母异位词
题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
思路分析
方法一:hash表
由于字符串中的都是小写字母,所以我们可以用数组来作为Hash表.
将s中的字母出现的种类个数保存到数组arr中.
将数组arr减掉t中字母出现的种类个数
判断数组arr是否都为0,如果都为0,则说明 s和t是字母异位词.
方法二
直接sort排序,然后判断两个字符串是否相等.
参考代码
#include<bits/stdc++.h> using namespace std; //Hash表的使用 bool isAnagram(string s, string t) { int arr[30] = {0}; for(char ch : s){//统计s中的字母以及个数 arr[ch-'a']++; } for(char ch : t) {//用t中的字母和s中的进行抵消.. arr[ch-'a']--; } for(int i = 0;i < 30;i++) { if(arr[i]!=0){ return false;//s和t中有字符不一样. } } return true; }
- 时间复杂度:O(n)
- 空间复杂度:O(1)
49. 字母异位词分组
题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""] 输出: [[""]]
示例 3:
输入: strs = ["a"] 输出: [["a"]]
思路分析
字母异位词其实就是两个串所使用的的字母以及个数都相同,只是顺序不同.所以如果两个串是字母异位词,则这两个串排序后是相等的.
我们可以使用map来存储解决,因为不要求有序和可重复性,所以我们可以使用 unordered_map
我们依次对字符串数组进行遍历,如果当前字符串排序后在map中出现过,则将其存入该key对应的val数组中.如果没有出现过则创建以该串为键的键值对.
最终遍历Map将结果存放到vector数组中.
参考代码
#include<bits/stdc++.h> using namespace std; vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string>> M; vector<vector<string>> res; string s; for(int i = 0; i < strs.size(); i++) { // s = strs[i]; sort(s.begin(),s.end()); M[s].push_back(strs[i]); } //遍历输出 for(unordered_map<string,vector<string>>::iterator it = M.begin(); it!=M.end(); it++) { res.push_back(it->second); } return res; }
438. 找到字符串中所有字母异位词
题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
思路分析
方法一:滑动窗口法+hash表
由于字符串中的都是小写字母,所以我们可以用数组的下标进行映射.即选择数组类型的hash表; 由于求的是子串的异位词,可以使用一个滑动窗口法:窗口大小固定,从前往后移动,寻找符合的子串.
初始化滑动窗口.也就是对arrS和arrP初始化. arrS中至少含有arrP中的所有元素.
判断初始化后的窗口是否相等,如果相同则将其实下标0加入结果集.
S滑动窗口向后移动寻找满足的子串满足是P的异位词,并将满足的起始下标加入结果集.
返回结果集
参考代码
bool judgeArr(int arr1[],int arr2[]) { //判断两个数组是否相等 for(int i = 0; i < 30; i++) { if(arr1[i]!=arr2[i]) { return false; } } return true; } //滑动窗口法+hash表 vector<int> findAnagrams(string s, string p) { int m = s.size(); int n = p.size(); vector<int> res; int arrS[30] = {0}; int arrP[30] = {0}; if(s.size() <p.size()) {//长度s < p,则s中不可能存在子串 和p是异位词 return {}; } //初始化滑动窗口 s的窗口至少含有p中的所有元素 for(int i = 0; i < n; i++) { arrS[s[i]-'a']++; arrP[p[i]-'a']++; } if(judgeArr(arrS,arrP)) {//判断初始化后的窗口是否相等 res.push_back(0); } //s滑动窗口移动寻找子串满足是p的异位词 注意:s的窗口大小和p相等 for(int i = n; i<m; i++) { arrS[s[i]-'a']++; arrS[s[i-n]-'a']--; if(judgeArr(arrS,arrP)) { res.push_back(i-n+1); } } return res; }
383. 赎金信
题目描述
为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
如果可以构成，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true
思路分析
方法一:hash表
因为是字符,所以可以采用数组的hash表(也可以使用unordered_map的hash表,因为考虑到效率而且还不需要排序)
**注:**使用数组还是使用set/map类型的hash表,要认真考虑.如果元素用数组可以很好的表示并且范围很小,那就考虑数组.比如元素字符… 本题使用数组较为简单
方法二:双指针
先对两个串排序.
i指向ransomNote串,j指向magazine串.然后从前往后遍历俩串,如果相同就都++,如果j对应的字符大于了i对应的字符,说明不满足了. 如果j对应的字符小于i对应的字符,说明magazine中的该字符是满足的而且还多余.
如果i能遍历完ransomNote,则说明能找到符合题意的串.
参考代码
方法一:hash表(数组)
//直接LeetCode242进行改造... 数组做hash表 bool canConstruct(string s, string t) { int arr[30] = {0}; for(char ch : s){//统计s中的字母以及个数 arr[ch-'a']++; } for(char ch : t) {//用t中的字母和s中的进行抵消.. arr[ch-'a']--; } for(int i = 0;i < 30;i++) { if(arr[i]>0){ return false;//s和t中有字符不一样. } } return true; } //使用map作为哈希表 bool canConstruct(string s1, string s2) { if(s1.size()>s2.size()) { return false; } unordered_map<char,int> sMap; for(char c : s2) { if(sMap.find(c)==sMap.end()) { sMap[c] = 1; } else { sMap[c]++; } } for(char c : s1) { if(sMap.find(c)!=sMap.end()) { sMap[c]--; if(sMap[c]<0){ return false; } }else{ return false; } } return true; }
- 时间复杂度 O(n)
- 空间复杂度O(n)
方法二:双指针
bool canConstruct(string ransomNote, string magazine) { if(ransomNote.size()>magazine.size()) { return false; } sort(ransomNote.begin(),ransomNote.end()); sort(magazine.begin(),magazine.end()); //cout<<ransomNote<<"--"<<magazine<<endl; int i,j; for(i = 0,j = 0; i < ransomNote.size(); i++,j++) { if(j>=magazine.size()) { return false; } if(ransomNote[i]==magazine[j]) { continue; } else if(ransomNote[i]>magazine[j]) { i--; } else { return false; } } return true; }
349. 两个数组的交集
题目描述
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4]
思路分析
方法一:hash表
由样例可知,最后的结果是要去重的. 我们选择unordered_set类型的hash表:输出结果中的每个元素一定是唯一的， 同时可以不考虑输出结果的顺序
**注:**由于数组中数的返回比较大,所以不建议使用数组来作为hash表.
方法二:暴力法(此法代码省略)
先给nums1和nums2排序.
然后双层循环判断nums1的元素是否出现在了nums2中.
判断过程中要进行去重:nums1中循环的元素和前一个相等则不处理,不相等再去nums2中判断是否存在
将nums1和nums2都存在的元素加入结果集
参考代码
方法一:hash表
#include<bits/stdc++.h> using namespace std; //方法一: 先给nums1和nums2排序.然后双层循环判断nums1的元素是否出现在了nums2中.遍历时,如果元素和前一个相等则不处理,不相等再去nums2中判断是否存在. //方法二:先去重使用nums1_set 然后遍历nums2,判断元素在nums1_set中是否出现,如果出现则加入结果集合..O(N) unordered_set的查找效率是O(1) //另外通过这个题,也要学到vector初始化set,set初始化vector的知识点 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result_set;//结果集 unordered_set<int> nums1_set(nums1.begin(),nums1.end()) ; for(int i = 0; i < nums2.size(); i++) { //如果发现 nums2的元素 ,在nums1_set中出现过 if(nums1_set.find(nums2[i])!=nums1_set.end()) { result_set.insert(nums2[i]) ; } } return vector<int>(result_set.begin(),result_set.end()); }
