1332. 删除回文子序列
给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。
提示：
- 0 <= s.length <= 1000
-
s 仅包含字母 'a' 和 'b'
思路：
在群里的小伙伴的讨论下，一时不知道怎么下手的我对这题豁然开朗
一个很重要的点是，不要把子序列跟子字符串搞混，也就是说只要相对位置不变就行了，比如abaab,取出来的bb为一个子序列，理解了这个概念以后，很清楚的知道结果只有0，1，2三种情况，0是输入空字符串的结果，那么只要输入的字符串是回文序列，就输出1，否则都是2。
代码如下：
class Solution {
public:
int removePalindromeSub(string s) {
int min=0,max=s.length()-1;
if(max<0)return 0;
while(min<max){
if(s[min]!=s[max]) return 2;
min++;
max--;
}
return 1;
}
};
1333. 餐厅过滤器
给你一个餐馆信息数组 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，它们分别考虑餐厅的价格因素和距离因素的最大值。
过滤后返回餐馆的 id，按照 rating 从高到低排序。如果 rating 相同，那么按 id 从高到低排序。简单起见， veganFriendlyi 和 veganFriendly 为 true 时取值为 1，为 false 时，取值为 0 。
提示：
1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= idi, ratingi, pricei, distancei <= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendlyi 和 veganFriendly 的值为 0 或 1 。
所有 idi 各不相同。
思路：
后面看讨论区的大佬引用了sort里面的自定义排序，认真研究理解后终于搞明白了，是真的香。用法sort(x.begin(),x.end(),cmp)，还有一个注意点就是定义cmp（自定义函数）的时候,自定义比较函数应该定义为static，因为sort的调用必须是静态成员。不然会显示错误：reference to non-static member function must be called sort(x.begin(),x.end(),cmp);
很明显，这里的速度和消耗内存大大降低了。果然是大佬啊，膜拜。
经过群里师兄的提醒，发现用反向迭代也可以实现....学到了。
下面是初始源代码：
class Solution {
public:
void cmp(vector<int> &a, vector<int> &b){
vector<int>temp;
if(a[1]<b[1]){
temp=a;
a=b;
b=temp;
}
else if(a[1]==b[1]){
if(a[0]<b[0]){
temp=a;
a=b;
b=temp;
}
}
}
vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
vector<vector<int>> res;
for(int i=0;i<restaurants.size();i++){
if(((veganFriendly==restaurants[i][2]) || (0 == veganFriendly)) &&
(maxPrice >= restaurants[i][3]) && (maxDistance >= restaurants[i][4])){
res.push_back(restaurants[i]);
}
}
for(int i=0;i<res.size();i++){
for(int j=i+1;j<res.size();j++)
cmp(res[i],res[j]);
}
vector<int> ans;
for(int i = 0; i < res.size(); i++)
ans.push_back(res[i][0]);
return ans;
}
};
优化过后的源代码：
class Solution {
public:
static bool cmp(vector<int> &a, vector<int> &b){
return (a[1]==b[1])?(a[0]>b[0]):(a[1]>b[1]);
}
vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
vector<int> res;
sort(restaurants.begin(),restaurants.end(),cmp);
for(int i=0;i<restaurants.size();i++){
if(((veganFriendly==restaurants[i][2]) || (0 == veganFriendly)) &&
(maxPrice >= restaurants[i][3]) && (maxDistance >= restaurants[i][4])){
res.push_back(restaurants[i][0]);
}
}
return res;
}
};
古老的密码
题目描述：
给定两个长度一样且不超过100的字符串，判断是否能把其中一个字符串的各个字母重排，之后对26个字母做一个一一映射，使得两个字符串相同
例如，JWPUDJSTVP重排后可以得到WJDUPSJPVT，之后把每个字母映射到它的前面一个字母，得到VICTORIOUS，输入两个字符串，输出YES或者NO。
Sample Input
JWPUDJSTVP
VICTORIOUS
MAMA
ROME
HAHA
HEHE
AAA
AAA
NEERCISTHEBEST
SECRETMESSAGES
Sample Output
YES
NO
YES
YES
NO
分析：
一看到这道题的时候感觉有点复杂，被题目举的例子带歪方向了，以为固定映射前一个字母，僵住了挺久，后来想了好久才知道掉进了“映射”的坑了。题目要求是通过映射使两个字符串相同，不知道会映射到哪一个，但是必定映射会一个（坑点：该字母可以与原始的字母重复但是与其他字母的映射字母不相同）。比如“ABA”可以映射成“ACA”但是不能映射成“AAA”，搞清楚这点就很容易做啦。
注意题目有个很重要的信息是“重排”，那就说明每个字母的位置不重要，所以只要用两个数组分别统计这两个字符串每个字母出现的次数，然后把它们进行排序以后一一比较，如果这两个数组一样，说明符合条件，输出YES，否则输出NO，从而得出想要的结果。
代码如下：
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
while(true){
string str1,str2;
int c1[26],c2[26];
cin>>str1>>str2;
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
int num=str1.size();
for(int i=0;i<num;++i){
c1[str1[i]-'A']++;
c2[str2[i]-'A']++;
}
sort(c1,c1+26);
sort(c2,c2+26);
bool flag=true;
for(int i=0;i<26;++i){
if(c1[i]!=c2[i]){
flag=false;
break;
}
}
if(flag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
总结：
能够及时理解清楚题意很重要，它能够帮你快速从众多文字找准击中点，不然只能挠挠头不知道怎么下手，实在是想不到去网上翻翻讨论也是一种收获，不要盲目牛角尖；做题多想一下，学会巧解而不要强行去解，无脑暴力好用但不是百用，有个狠东西叫"超时"；解出来了也不能沾沾自喜，可以延伸学习参考一下其他人的代码并进行学习，网上大佬太多了，人外有人天外有天，记住了下次用上了就是赚了。
