题目清单
1002. 查找常用字符--简单
1090. 受标签影响的最大值--中等
249. 移位字符串分组--中等
first blood ---1002 查找常用字符
这道题是个简单题，题目如下：
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1：
输入：["bella","label","roller"]
输出：["e","l","l"]
示例 2：
输入：["cool","lock","cook"]
输出：["c","o"]
提示：
1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] 是小写字母
题解
1.这道题第一反应，应当采用“集合”的方案进行处理。由于只有26个字母，并且都为小写，所以考虑采用char[26]方式构造，直接数组访问，效率较高。
2.选择每个字母在字符串中出现的次数作为一个统计值，例如示例1，b在字串1中出现1次，字串2中出现1次，字串3中出现0次，则b的出现次数为0.然后字串l在分别在字串1、2、3中都常出现2次，所以l为输出字母，并且需要输出2次。
class Solution {
public:
vector<string> commonChars(vector<string>& A) {
vector<string> res;
int table[26];
//初始化
for(int i=0; i<26; i++)
table[i] = 0xff;
//遍历每个字符串的元素
for(int i=0; i<A.size(); i++)
{
int word[26] = {0};
for (int j=0; j<A[i].size(); j++)
word[(int)A[i][j]-'a']++; //记录每个字符串中某个字母的出现次数
for (int i=0; i<26; i++)
table[i] = min(table[i],word[i]); //更新计数表
}
for (int i=0; i<26 ;i++)
if (table[i])
for (int j = 0;j < table[i]; j++) {
string str;
str.push_back((char)('a'+i));//构造str
res.push_back(str);//放入vector
}
return res;
}
};
double kill--- 1090 受标签影响的最大值
题目如下
我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。
我们从这些项中选出一个子集 S，这样一来：
|S| <= num_wanted ------------|S|表示S的长度
对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。
返回子集 S 的最大可能的 和。
示例 1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。
示例 2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。
示例 3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。
示例 4：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。
提示：
1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length
题解：
该题考虑采用map方式实现。
代码
class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
multimap<int,int> count_map;
multimap<int,int> record_map;
int res = 0;
int count_num = 0;
for(int i = 0; i < values.size(); i++) {
count_map.insert (pair<int,int>(values[i],labels[i]));
}
for (auto it = count_map.crbegin(); it != count_map.crend(); ++it) {
if (record_map.count(it->second) < use_limit) {
record_map.insert (pair<int,int> (it->second,it->first));
count_num++;
res += it->first;
if(count_num >= num_wanted) return res;
}
}
return res;
}
};
知识点总结
1.multimap与map的用法：
map底层实现依然是rb_tree 他的data可以改,但是key不能改,因此map仍然具有自动排序的功能
我们无法使用迭代器改变元素的key(const key),但是可以改变元素的data.
map的key必须独一无二,multimap的key可以重复
https://www.cnblogs.com/LearningTheLoad/p/7466057.html
triple kill--- 249 移位字符串分组
给定一个字符串，对该字符串可以进行 “移位” 的操作，也就是将字符串中每个字母都变为其在字母表中后续的字母，比如："abc" -> "bcd"。这样，我们可以持续进行 “移位” 操作，从而生成如下移位序列：
"abc" -> "bcd" -> ... -> "xyz"
给定一个包含仅小写字母字符串的列表，将该列表中所有满足 “移位” 操作规律的组合进行分组并返回。
示例：
输入: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
输出:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
题解
建立字典的映射关系，以字母之间的距离建立数组作为key。
字符串数组为value 2.str[i+1]-str[i]-26再取模解决回绕问题。
代码
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
vector<vector<string>> ans;
map<vector<int>,vector<string>> mp;
for (auto str : strings) { //value
vector<int> tmp; //key
fo r(int i = 0;i < str.size()-1; ++i) {
tmp.push_back((str[i+1]-str[i]+26)%26);
}
mp[tmp].push_back(str);
}
for (auto &m : mp) {
ans.push_back(m.second);
}
return ans;
}
};
知识点总结
map中key的泛型使用。我一开始是想用两个map，一个存储字符间距，一个存储字符串，并没有想到用一个数组存储字符间距做为key。
主要是考虑map的key必须具备operator < 对元素排序，而vector并不提供 < 操作符。
看了题解之后，才知道，原来还有这种用法，进而确认了一下。但是具体的原因，需要在后续进一步学习STL的时候再研究一下。
https://blog.csdn.net/u013992365/article/details/74838636?utm_source=blogxgwz5
