以下题目均来自leetcode、poj
最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 ”Aa” 不能当做一个回文字符串。
注意: 假设字符串的长度不会超过 1010。
示例 1:
输入: “abccccdd”
输出: 7
解释: 我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。
class Solution {
public:
int longestPalindrome(string s) {
int charMap[128] = 0;
int maxLength = 0;
int flag = 0;
for (int i = 0; i < s.length(); i++) {
charMap[s[i]]++;
}
for (int i = 0; i < 128; i++) {
if(charMap[i] %2 == 0){
//字符为偶数全部可用
max_length += charMap[i];
}else{
//为奇数 拿一个出来，最后当中心点
max_length += charMap[i] - 1;
flag = 1;
}
}
reutrn max_length + flag;
}
};
单词规律
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = “abba”, str = “dog cat cat dog” 输出: true 示例 2:
输入:pattern = “abba”, str = “dog cat cat fish” 输出: false 示例 3:
输入: pattern = “aaaa”, str = “dog cat cat dog” 输出: false 示例 4:
输入: pattern = “abba”, str = “dog dog dog dog” 输出: false 说明: 你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
class Solution {
public:
bool wordPattern(string pattern, string str) {
std::vector<std::string,char> word_map;
char used[128] = {0};
std::string word;
int pos = 0;
str.push_back(' ');
for (i = 0; i < str.length();i++){
if(str[i] == ' '){
//找到最后都找不到
if(pos == pattern.length()){
reutrn false;
}
if(word_map.find(word) == word_map.end()){
if(used[pattern[pos]]){
return false;
}
word_map[word] = pattern[pos];
used[pattern[pos]] = 1;
}else{
if(word_map[word] != pattern[pos]){
return false;
}
}
word = "";
pos++;
}else{
word += str[i];
}
}
if(pos != pattern.length()){
return false;
}
return true;
}
};
字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], 输出: [ [“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ] 说明：
所有输入均为小写字母。 不考虑答案输出的顺序。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
std::map<std::string,std::vector<std::string>> anagram;
std::vector<std::vector<std::string>> result;
for(int i = 0;i < strs.size();i++){
std::string str = strs[i];
std::sort(str.begin(),str.end());
if(anagram.find(str) == anagram.end()){
std::vector<std::string> item;
anagram[str] = item;
}
anagram[str].push_back(strs[i]);
}
std::map<std::string,std::vector<std::string>> ::iterator it;
for(it = anagram.begin();it != anagram.end();it++){
result.push_back((*it).second);
}
return result;
}
};
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 ”wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int begin = 0;
int result = 0;
std::string word = "";
int char_map[128] = {0};
for(int i = 0;i < s.length();i++){
char_map[s[i]]++;
if(char_map[s[i]] == 1){
word += s[i];
if(result < word.length()){
result = word.length();
}
}else{
//滑动到重复字符的下一个字符，
while(begin < i && char_map[s[i]] > 1){
char_map[s[i]]--;
begin++;
}
word = "";
for(int j = begin;j <= i;j++){
word+=s[j];
}
}
}
return result;
}
};
重复的DNA序列
所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。
示例:
输入: s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出: [“AAAAACCCCC”, “CCCCCAAAAA”]
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
unordered_map<string, int> m;
for (int i = 0; i <= int(s.size() - 10); ++i) {
string str = s.substr(i,10);
if (++m[str] == 2) {
res.push_back(str);
}
}
return res;
}
};
最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = “ADOBECODEBANC”, T = “ABC” 输出: “BANC” 说明：
如果 S 中不存这样的子串，则返回空字符串 ““。 如果 S 中存在这样的子串，我们保证它是唯一的答案。
class Solution {
private:
bool isWindowOk(int maps[],int mapt[],vector<int> &vect){
for(int i= 0;i<vect.size();i++){
if(maps[vect[i]] < mapt[vect[i]]){
return false;
}
}
return true;
}
public:
string minWindow(string s, string t) {
const int MAPSIZE = 128;//char 0-127
int mapt[MAPSIZE] = {0};
int maps[MAPSIZE] = {0};
std::vector<int> vect;
for (int i = 0; i < t.length();i++){
mapt[t[i]]++;
}
for (int i = 0; i < MAPSIZE;i++){
if (m[i] > 0){
vect.push_back(i);
}
}
int windowBegin = 0;
std::string result;
for (int i = 0; i < s.size();i++){
maps[s[i]]++;
while (windowBegin < i){
char begin_ch = s[windowBegin];
if(mapt[begin_ch] == 0){
//窗口头指针字符，不在t中
windowBegin++;
}
else if (maps[begin_ch] > mapt[begin_ch]){
//窗口内有多的字符，移动窗口，减少计数
maps[begin_ch]--;
windowBegin++;
}else{
break;
}
}
if(isWindowOk(maps,mapt,vect)){
int newWindowLen = i - windowBegin + 1;
//更短的才更新
if(result == "" || result.length() < newWindowLen){
result = s.substr(windowBegin,newWindowLen);
}
}
}
return result;
}
};
