专题7：字符串匹配
题目459:重复的子字符串（NO）
-
解题思路：这里用到了substr获取子串，然后直接堆成相同大小的主串，然后进行比较。
这题主要没做出的原因是时间复杂度一直优化不下去 -
myself
class Solution {
public:bool repeatedSubstringPattern(string s) {//直接暴力枚举每个每个子串，看是否能全部都匹配string child="";for(int i=0;i<s.size()/2;i++)//自己不能算子串{child+=s[i];//子串每次都增加一个单位std::cout<<child<<std::endl;//判断是否可以全部匹配string temp=child;string add=child;//直接先用子串堆出完整的字符串在进行判断if(s.size()%child.size()!=0){//不可能重复构成主串，继续判断下一个continue;}while(temp.size()!=s.size()){temp+=add;//如果不是子串也跳出if(s.find(temp)==string::npos){break;}}//构成主串了，进行判断if(temp==s){return true;}}return false;}
};
- 较好的答案
class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();for (int len = 1; len <= n / 2; len++) {if (n % len == 0) {string sub = s.substr(0, len);//获取子串string pattern;//组合成新得主串for (int i = 0; i < n / len; i++) {pattern += sub;}//比较if (pattern == s) {return true;}}}return false;
}
};
- substr用法介绍
string::substr 是 C++ 中 std::string 类的一个成员函数，用于提取字符串中的子串。下面是 substr 函数的通用形式：
string substr(size_t pos = 0, size_t count = npos) const;
- pos 参数表示要提取子串的起始位置（默认为 0）。
- count 参数表示要提取的字符数（默认为 npos，即直到字符串末尾）。
题目796：旋转字符串（YES）
- 解题思路：模拟，通过（i+j%n）模运算可以模拟旋转扫描,或者直接调用库函数，这是最容易的方法。
给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。
s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
例如, 若 s = ‘abcde’，在旋转一次之后结果就是’bcdea’ 。
class Solution {
public:bool rotateString(string s, string goal) {int m = s.size(), n = goal.size();//长度不等，怎么都无法旋转成功if (m != n) {return false;}//这是模拟的关键for (int i = 0; i < n; i++) {bool flag = true;for (int j = 0; j < n; j++) {if (s[(i + j) % n] != goal[j]) {flag = false;break;}}if (flag) {return true;}}return false;}
};
- 方法2：调用库函数（这种面试感觉不可取）
class Solution {
public:bool rotateString(string s, string goal) {//这里运用substr选取子串会非常容易//选转几次就是将多少长度的子串移动到后面if(s==goal){return true;}for(int i=1;i<s.size();i++){string child=s.substr(0,i);//要移动到后面的子串string last=s.substr(i,s.size()-i);if(goal==last+child){return true;}}return false;}
};题目1408：数组中字符串匹配（YES）
- 解题思路：原本不想调库函数，但是官方题解给的也是调库，直接暴力枚举每个值，比较是不是其它字符的子串，用find(temp)!=string::npos可以快速查找子串。
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 words[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
- myself
class Solution {
public:vector<string> stringMatching(vector<string>& words) {//暴力枚举vector<string>ans;//查找每个元素，看是不是别人的子串for(int i=0;i<words.size();i++){for(int j=0;j<words.size();j++){if(i==j)//与自己不比较{continue;}//检查是否是子串，掉库函数findif(words[j].find(words[i])!=string::npos){ans.push_back(words[i]);break;}}}return ans;}
};
题目1455：检查单词是否为句中其他单词的前缀（YES）
- 解题思路：扫描整个句子，当不是空格时候，说明这是单词了，就直接开始比较前缀。
给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。
如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。如果 searchWord 不是任何单词的前缀，则返回 -1 。
字符串 s 的 前缀 是 s 的任何前导连续子字符串。
- myself
class Solution {
public:int isPrefixOfWord(string sentence, string searchWord) {int ans=0;//遍历检查每一个单词int i=0;while(i<sentence.size()){if(sentence[i]==' '){i++;continue;}ans++;//提取单词并且进行比较int count=0;bool sign=true;while(i<sentence.size()&&count<searchWord.size()){if(sentence[i]!=searchWord[count]){sign=false;break;}i++;count++;}if(sign){return ans;}//单词比较结束，将该单词移动到空格位置while(i<sentence.size()&&sentence[i]!=' '){i++;}}return -1;}
};
题目2185：统计包含给定前缀的字符串（YES）
- 解题思路： 这题很简单，直接枚举每个字符串比较前缀就行。
给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为 前缀 的字符串的数目。
字符串 s 的 前缀 就是 s 的任一前导连续字符串。
- myself
class Solution {
public:int prefixCount(vector<string>& words, string pref) {//这个似乎更简单了，直接枚举就行int ans=0;for(int i=0;i<words.size();i++){if(pref.size()>words[i].size()){continue;}bool sign=true;for(int j=0;j<pref.size();j++){if(words[i][j]!=pref[j]){sign=false;break;}}if(sign){ans++;}}return ans;}
};
专题8：桶排序
题目164：最大间距（NO）
- 方法1：直接sort （排序算法题直接用sort必然不可取,这不能算通过）
class Solution {
public:int maximumGap(vector<int>& nums) {if(nums.size()<2){return 0;}sort(nums.begin(),nums.end());int maxgap=0;for(int i=1;i<nums.size();i++){if(nums[i]-nums[i-1]>maxgap){maxgap=nums[i]-nums[i-1];}}return maxgap;}
};
- 冒泡排序（这题是不适用的，时间复杂度太高，正好复习一下排序算法）
void Bubble_sort(vector<int>&nums){for(int i=0;i<nums.size()-1;i++){for(int j=0;j<nums.size()-i-1;j++){if(nums[j]>nums[j+1]){int temp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}}}专题9:计数排序
题目2710:移除字符串中的尾随零（YES）
- 解题思路：这题主要运用的还是对substr获取子串的方法,只要找出后面有几个零就可以了。
给你一个用字符串表示的正整数 num ，请你以字符串形式返回不含尾随零的整数 num 。
std::string substr(size_t pos = 0, size_t count = npos) const;
-
pos：起始位置，即子字符串的起始索引。
-
count：要提取的字符数。
-
myself
class Solution {
public:string removeTrailingZeros(string num) {//一次for从尾部开始扫描就行了int count=0;for(int i=num.size()-1;i>=0;i--){if(num[i]=='0'){count++;}else{break;}}//获取子串return num.substr(0,num.size()-count);;}
};
题目1051：高度检查器（YES）
- 解题思路：直接使用冒泡排序，然后再进行比较就行。
学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
返回满足 heights[i] != expected[i] 的 下标数量 。
- myself
class Solution {
public://冒泡排序void Bubble_sort(vector<int>&expected){for(int i=0;i<expected.size()-1;i++){for(int j=0;j<expected.size()-i-1;j++){if(expected[j]>expected[j+1]){int temp=expected[j];expected[j]=expected[j+1];expected[j+1]=temp;}}}}int heightChecker(vector<int>& heights) {vector<int>expected=heights;Bubble_sort(expected);int count=0;for(int i=0;i<heights.size();i++){if(heights[i]!=expected[i]){count++;}}return count;}
};
题目1122：数组中的相对排序（NO）
- 解题思路：sort搭配比较函数，且比较函数是lambda表达式，[&]可以捕获外部所有的变量。
给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
class Solution {
public:vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {unordered_map<int, int> rank;for (int i = 0; i < arr2.size(); ++i) {rank[arr2[i]] = i;}//[&]捕获外部所有的变量sort(arr1.begin(), arr1.end(), [&](int x, int y) {if (rank.count(x)) {//如果x存在y也存在，则下标小的放左边return rank.count(y) ? rank[x] < rank[y] : true;}else {return rank.count(y) ? false : x < y;}});return arr1;}
};- 代码分析
如果arr1中的元素x在rank中存在，且元素y也在rank中存在，则比较它们在rank中的索引值，如果x的索引小于y的索引，则返回true。
如果x存在而y不存在，则返回true。
如果y存在而x不存在，则返回false。
如果x和y都不存在于rank中，则比较它们的值的大小，返回x < y 的结果。
