1332. 刪除回文子序列
給你一個(gè)字符串 s，它僅由字母 'a' 和 'b' 組成米愿。每一次刪除操作都可以從 s 中刪除一個(gè)回文 子序列讼载。
返回刪除給定字符串中所有字符（字符串為空）的最小刪除次數(shù)惋啃。
「子序列」定義：如果一個(gè)字符串可以通過刪除原字符串某些字符而不改變?cè)址樞虻玫仅保敲催@個(gè)字符串就是原字符串的一個(gè)子序列。
「回文」定義：如果一個(gè)字符串向后和向前讀是一致的青伤，那么這個(gè)字符串就是一個(gè)回文督怜。
提示：
- 0 <= s.length <= 1000
-
s 僅包含字母 'a' 和 'b'
思路：
在群里的小伙伴的討論下，一時(shí)不知道怎么下手的我對(duì)這題豁然開朗
一個(gè)很重要的點(diǎn)是狠角，不要把子序列跟子字符串搞混号杠，也就是說只要相對(duì)位置不變就行了，比如abaab,取出來的bb為一個(gè)子序列擎厢，理解了這個(gè)概念以后究流，很清楚的知道結(jié)果只有0辣吃，1动遭，2三種情況，0是輸入空字符串的結(jié)果神得，那么只要輸入的字符串是回文序列厘惦，就輸出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. 餐廳過濾器
給你一個(gè)餐館信息數(shù)組 restaurants宵蕉，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]酝静。你必須使用以下三個(gè)過濾器來過濾這些餐館信息。
其中素食者友好過濾器 veganFriendly 的值可以為 true 或者 false羡玛，如果為 true 就意味著你應(yīng)該只包括 veganFriendlyi 為 true 的餐館别智，為 false 則意味著可以包括任何餐館。此外稼稿，我們還有最大價(jià)格 maxPrice 和最大距離 maxDistance 兩個(gè)過濾器薄榛，它們分別考慮餐廳的價(jià)格因素和距離因素的最大值。
過濾后返回餐館的 id让歼，按照 rating 從高到低排序敞恋。如果 rating 相同，那么按 id 從高到低排序谋右。簡(jiǎn)單起見硬猫， veganFriendlyi 和 veganFriendly 為 true 時(shí)取值為 1，為 false 時(shí)改执，取值為 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 各不相同辈挂。
思路：
后面看討論區(qū)的大佬引用了sort里面的自定義排序构眯，認(rèn)真研究理解后終于搞明白了，是真的香早龟。用法sort(x.begin(),x.end(),cmp)惫霸，還有一個(gè)注意點(diǎn)就是定義cmp（自定義函數(shù)）的時(shí)候,自定義比較函數(shù)應(yīng)該定義為static，因?yàn)閟ort的調(diào)用必須是靜態(tài)成員葱弟。不然會(huì)顯示錯(cuò)誤：reference to non-static member function must be called sort(x.begin(),x.end(),cmp);
很明顯壹店，這里的速度和消耗內(nèi)存大大降低了。果然是大佬啊芝加，膜拜硅卢。
經(jīng)過群里師兄的提醒县好，發(fā)現(xiàn)用反向迭代也可以實(shí)現(xiàn)....學(xué)到了计螺。
下面是初始源代碼：
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;
}
};
優(yōu)化過后的源代碼：
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;
}
};
古老的密碼
題目描述：
給定兩個(gè)長(zhǎng)度一樣且不超過100的字符串竭恬，判斷是否能把其中一個(gè)字符串的各個(gè)字母重排卜朗，之后對(duì)26個(gè)字母做一個(gè)一一映射，使得兩個(gè)字符串相同
例如点寥，JWPUDJSTVP重排后可以得到WJDUPSJPVT艾疟，之后把每個(gè)字母映射到它的前面一個(gè)字母，得到VICTORIOUS敢辩，輸入兩個(gè)字符串汉柒，輸出YES或者NO。
Sample Input
JWPUDJSTVP
VICTORIOUS
MAMA
ROME
HAHA
HEHE
AAA
AAA
NEERCISTHEBEST
SECRETMESSAGES
Sample Output
YES
NO
YES
YES
NO
分析：
一看到這道題的時(shí)候感覺有點(diǎn)復(fù)雜责鳍，被題目舉的例子帶歪方向了碾褂，以為固定映射前一個(gè)字母，僵住了挺久历葛，后來想了好久才知道掉進(jìn)了“映射”的坑了正塌。題目要求是通過映射使兩個(gè)字符串相同，不知道會(huì)映射到哪一個(gè)恤溶，但是必定映射會(huì)一個(gè)（坑點(diǎn)：該字母可以與原始的字母重復(fù)但是與其他字母的映射字母不相同）乓诽。比如“ABA”可以映射成“ACA”但是不能映射成“AAA”，搞清楚這點(diǎn)就很容易做啦咒程。
注意題目有個(gè)很重要的信息是“重排”鸠天，那就說明每個(gè)字母的位置不重要，所以只要用兩個(gè)數(shù)組分別統(tǒng)計(jì)這兩個(gè)字符串每個(gè)字母出現(xiàn)的次數(shù)帐姻，然后把它們進(jìn)行排序以后一一比較稠集，如果這兩個(gè)數(shù)組一樣，說明符合條件饥瓷，輸出YES剥纷，否則輸出NO，從而得出想要的結(jié)果呢铆。
代碼如下：
#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;
}
}
總結(jié)：
能夠及時(shí)理解清楚題意很重要晦鞋，它能夠幫你快速從眾多文字找準(zhǔn)擊中點(diǎn)，不然只能撓撓頭不知道怎么下手棺克，實(shí)在是想不到去網(wǎng)上翻翻討論也是一種收獲悠垛，不要盲目牛角尖；做題多想一下娜谊，學(xué)會(huì)巧解而不要強(qiáng)行去解确买，無腦暴力好用但不是百用，有個(gè)狠東西叫"超時(shí)"因俐；解出來了也不能沾沾自喜拇惋，可以延伸學(xué)習(xí)參考一下其他人的代碼并進(jìn)行學(xué)習(xí)周偎，網(wǎng)上大佬太多了抹剩，人外有人天外有天撑帖，記住了下次用上了就是賺了。
