1332. 刪除回文子序列

給你一個字符串 s，它僅由字母 'a' 和 'b' 組成。每一次刪除操作都可以從 s 中刪除一個回文 子序列。
返回刪除給定字符串中所有字符（字符串為空）的最小刪除次數(shù)。
「子序列」定義：如果一個字符串可以通過刪除原字符串某些字符而不改變原字符順序得到，那么這個字符串就是原字符串的一個子序列。
「回文」定義：如果一個字符串向后和向前讀是一致的，那么這個字符串就是一個回文。

提示：

• 0 <= s.length <= 1000

• s 僅包含字母 'a' 和 'b'

  
  

思路：
在群里的小伙伴的討論下，一時不知道怎么下手的我對這題豁然開朗
一個很重要的點是，不要把子序列跟子字符串搞混，也就是說只要相對位置不變就行了，比如abaab,取出來的bb為一個子序列，理解了這個概念以后，很清楚的知道結(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. 餐廳過濾器

給你一個餐館信息數(shù)組 restaurants，其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必須使用以下三個過濾器來過濾這些餐館信息。
其中素食者友好過濾器 veganFriendly 的值可以為 true 或者 false，如果為 true 就意味著你應(yīng)該只包括 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 各不相同。

思路：

后面看討論區(qū)的大佬引用了sort里面的自定義排序，認真研究理解后終于搞明白了，是真的香。用法sort(x.begin(),x.end(),cmp)，還有一個注意點就是定義cmp（自定義函數(shù)）的時候,自定義比較函數(shù)應(yīng)該定義為static，因為sort的調(diào)用必須是靜態(tài)成員。不然會顯示錯誤：reference to non-static member function must be called sort(x.begin(),x.end(),cmp);
很明顯，這里的速度和消耗內(nèi)存大大降低了。果然是大佬啊，膜拜。

經(jīng)過群里師兄的提醒，發(fā)現(xiàn)用反向迭代也可以實現(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;
    }
};

古老的密碼

題目描述：

給定兩個長度一樣且不超過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

分析：

一看到這道題的時候感覺有點復(fù)雜，被題目舉的例子帶歪方向了，以為固定映射前一個字母，僵住了挺久，后來想了好久才知道掉進了“映射”的坑了。題目要求是通過映射使兩個字符串相同，不知道會映射到哪一個，但是必定映射會一個（坑點：該字母可以與原始的字母重復(fù)但是與其他字母的映射字母不相同）。比如“ABA”可以映射成“ACA”但是不能映射成“AAA”，搞清楚這點就很容易做啦。
注意題目有個很重要的信息是“重排”，那就說明每個字母的位置不重要，所以只要用兩個數(shù)組分別統(tǒng)計這兩個字符串每個字母出現(xiàn)的次數(shù)，然后把它們進行排序以后一一比較，如果這兩個數(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é)：

能夠及時理解清楚題意很重要，它能夠幫你快速從眾多文字找準(zhǔn)擊中點，不然只能撓撓頭不知道怎么下手，實在是想不到去網(wǎng)上翻翻討論也是一種收獲，不要盲目牛角尖；做題多想一下，學(xué)會巧解而不要強行去解，無腦暴力好用但不是百用，有個狠東西叫"超時"；解出來了也不能沾沾自喜，可以延伸學(xué)習(xí)參考一下其他人的代碼并進行學(xué)習(xí)，網(wǎng)上大佬太多了，人外有人天外有天，記住了下次用上了就是賺了。