1.2006. 差的绝对值为 K 的数对数目
观察| nums[i] - nums[j] |==target，我们把当前遍历到的数字当作nums[j]然后去查找nums[j]+target和nums[j]-target在数组中存在的次数即可。
class Solution {
public:
unordered_map<int ,int>cnt;
int countKDifference(vector<int>& nums, int k) {
int count=0;
for(auto n:nums)
{
count+=cnt[n+k];
count+=cnt[n-k];
cnt[n]++;
}
return count;
}
};
2.1512. 好数对的数目
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3]
输出：0
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
和上一题类似，不再解释了。
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int hash[101];
memset(hash,0,sizeof(hash));
int ans=0;
for(auto i:nums){
ans+=hash[i];
++hash[i];
}
return ans;
}
};
3.1347. 制造字母异位词的最小步骤数
给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的 任一字符 替换为 另一个字符。
返回使 t 成为 s 的字母异位词的最小步骤数。
字母异位词 指字母相同，但排列不同（也可能相同）的字符串。
示例 1：
输出：s = “bab”, t = “aba”
输出：1
提示：用 ‘b’ 替换 t 中的第一个 ‘a’，t = “bba” 是 s 的一个字母异位词。
示例 2：
输出：s = “leetcode”, t = “practice”
输出：5
提示：用合适的字符替换 t 中的 ‘p’, ‘r’, ‘a’, ‘i’ 和 ‘c’，使 t 变成 s 的字母异位词。
示例 3：
输出：s = “anagram”, t = “mangaar”
输出：0
提示：“anagram” 和 “mangaar” 本身就是一组字母异位词。
示例 4：
输出：s = “xxyyzz”, t = “xxyyzz”
输出：0
示例 5：
输出：s = “friend”, t = “family”
输出：4
提示：
1 <= s.length <= 50000
s.length == t.length
s 和 t 只包含小写英文字母
我们先统计两个字符串中每个字母出现的次数，要使得两个字符串变为字母异位词首先要做的事将两个字符串中的每个字符出现频率相同。
比如s=“aaabde” ,t=“bbbade” 两个字符串频率不同的字母有a,b出现频率相同的我们就不用去管了。那么要如何修改呢？也很简单，向出现频率高的字母借来出现频率的差值个字母即可。对于这个例子，以s为基准，将两个a变为两个b即可。再比如s = “friend”, t = “family”，t相对于s没有出现的有r,e,n,d，将s中的这些字母按任意顺序变为缺失的字母即可。再比如s = “leetcode”, t = “practice”，s相对于t出现频率不同的有l=1,e=3,o=1,d=1，频率差就是l=1,e=2,o=1,d=1,同理将这些频率差变为其他字母即可。
在这里我们在s中改变的字母是s中的字母相对于t出现频率高的那些，首先他已经满足了该字母的出现频率经过改变后可以与t中对应的字母相等。那么多的这些字母就是我们不需要的，也就是说可以对这些字母进行任意操作，所以顺序在这里也是不用考虑的。而那些频率小的字母就是我们要去变为的字母。
class Solution {
public:
int minSteps(string s, string t) {
int ans=0;
int hashs[128],hasht[128];
memset(hashs,0,sizeof(hashs));
memset(hasht,0,sizeof(hasht));
for(int i=0;i<s.size();i++){
++hashs[s[i]];
++hasht[t[i]];
}
for(int i='a';i<='z';i++){
ans+=hashs[i]-hasht[i]>0?hashs[i]-hasht[i]:0;
}
return ans;
}
};
4.面试题 10.02. 变位词组
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
注意：本题相对原题稍作修改
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,“eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
不考虑输出顺序，本题完全是个水题.对于strs中的每个字符串，按照字典序排序之后一定相同，我们就以排序后的字符串为key，原字符串为val，将所有的val插入到key的vector中，之后遍历哈希表即可。
class Solution {
unordered_map<string,vector<string>> map;
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map.clear();
vector<vector<string>> ans;
for(int i=0;i<strs.size();++i){
string tmp=strs[i];
sort(tmp.begin(),tmp.end());
map[tmp].push_back(strs[i]);
}
for(auto & i:map){
ans.push_back(i.second);
}
return ans;
}
};
