第一題：刪除回文子序列
題目鏈接：https://leetcode-cn.com/problems/remove-palindromic-subsequences/

題目描述：

image.png

題目要點(diǎn)：
1、子序列不是子串，一開始我誤將子序列當(dāng)成了子串，耽誤了很多時(shí)間。子序列是不要求字符連續(xù)的，所以找到滿足條件的子序列要比找到滿足條件的子串要容易的多。
2、由于題目只包含兩種字符，又需要找回文子序列，所以找的時(shí)候只需要找到全a或者全b的情況，不就是一個(gè)回文子序列了么。
3、還要注意一中情況，那就是babababab或abababa這種雖然有兩個(gè)字符，但直接就作為一個(gè)回文子序列那一種。需要額外判斷。

代碼如下：

int removePalindromeSub(string s) {
    int num=0;
    int one=0, two=0;
    int i, j;
    int flag=0;
    int flag_two=1;

    if (s.length() == 0) return 0;//如果字符串里面什么都沒有，就返回0.

    for (i = 0;i < s.length();i++) {//如果從頭到尾都是a或者b，就返回1.
        if (!(s[i] == s[s.length() - 1-i]))
        {
            flag_two = 0;
            break;
        }
    }
    if (flag_two == 1) return 1;

    for (i = 0;i < s.length();i++) {//找ababa這種情況
        if (s[i] == 'a' && flag == 0) {
            one++;
            flag = 1;
        } 
        else if (s[i] = 'b' && flag == 1) {
            one++;
            flag = 0;       
        } 
    }
    if (flag == 0) one--;//如果最后一個(gè)并不是以a收尾，說明并不構(gòu)成回文串，但又具有兩種字符

    for (i = 0;i < s.length();i++) {{//找babab這種情況
        if (s[i] == 'b' && flag == 0) {
            two++;
            flag = 1;
        }
        else if (s[i] == 'a' && flag == 1) {
            two++;
            flag = 0;
        }
    }
    if (flag == 0) two--;//如果最后一個(gè)并不是以b收尾，說明并不構(gòu)成回文串，但又具有兩種字符

    if (one == s.length() || two == s.length())//如果剛剛好是回文串，就返回1
        return 1;

    else return 2;//不是回文串，就返回2
    }

時(shí)候?qū)Ρ攘讼略u(píng)論區(qū)的答案，心情有點(diǎn)沉重

image.png

無論全a還是全b還是ababa還是babab不都是回文么我分開來判斷干嘛！

int removePalindromeSub(char * s){
    int length=strlen(s);
    if(length==0)
      return 0;
    int low=0,high=length-1;

    while(low<high)//縮減
    {
        if(s[low]!=s[high])
        return 2;
        low++;
        high--;
    }
    return 1;
}

第二題：餐廳過濾器

題目鏈接：https://leetcode-cn.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance/
題目描述：

image.png

好直接不拐彎抹角的題目，寫個(gè)交換函數(shù)就行了。
代碼如下：

void sort_vector(vector<int>& a, vector<int>& b) {
    vector<int> temp;
    if (a[1] > b[1])
    {
        temp = b;
        b = a;
        a = temp;
    }
    else if (a[1] == b[1])
    {
        if (a[0] > b[0])
        {
            temp = b;
            b = a;
            a = temp;
        }
    }
}

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
    int i,j; 
    int n = restaurants.size();
    vector<vector<int>> filter;
    vector<int> number;

    if (veganFriendly == 1)    
        for (i = 0;i < n;i++) 
            if(restaurants[i][2]==1&& restaurants[i][3]<=maxPrice&& restaurants[i][4]<=maxDistance)//如果滿足素食
                filter.push_back(restaurants[i]);
    else 
        for (i = 0;i < n;i++)
            if (restaurants[i][3] <= maxPrice && restaurants[i][4] <= maxDistance)
                filter.push_back(restaurants[i]);

    for (i = 0;i < filter.size();i++)
        for (j = 0;j < filter.size();j++)
            sort_vector(filter[i],filter[j]);

    for (i = 0;i < filter.size();i++)
        number.push_back(filter[i][0]);

    return number;
}

由于題目邏輯很簡(jiǎn)單，所以與網(wǎng)上的代碼相比，也只是排序的先后順序有差別。

image.png

網(wǎng)上的答案使用了sort自定義cmp函數(shù)。