LeetCode 1812. 判断国际象棋棋盘中一个格子的颜色

横纵坐标之和

class Solution {
public:
    bool squareIsWhite(string c) {
        return (c[0] + c[1]) % 2;
    }
};

LeetCode 1813. 句子相似性 III

找前缀，后缀
利用stringstream切分单词

class Solution {
public:
    bool areSentencesSimilar(string s1, string s2) {
        if(s1.size() > s2.size()) return areSentencesSimilar(s2,s1); // s1 < s2

        // 利用stringstream来分割单词
        stringstream ssin1(s1), ssin2(s2);
        string s;
        vector<string> a,b; // a < b
        while(ssin1 >> s) a.push_back(s);
        while(ssin2 >> s) b.push_back(s);

        int i = 0,j = a.size() - 1; 
        for(int k = 0;k < b.size() && i < a.size();k ++ ) // i越界
            if(a[i] == b[k]) i ++;
            else break;

        for(int k = b.size() - 1;k >= 0 && j >= 0; k -- )
            if(a[j] == b[k]) j --;
            else break;

        return i > j; // 不能加 = ，必须覆盖
    }
};

LeetCode 1814. 统计一个数组中好对子的数目

哈希表

stoi()

写法1：我的写法，边插入变统计

class Solution {
public:

    int rev(int x)
    {
        int t = 0;
        while(x){
            t  = t * 10 + x % 10;
            x /= 10;
        }
        return t;
    }

    int countNicePairs(vector<int>& nums) {
        int n = nums.size();
        int mod = 1e9 + 7;
        unordered_map<int,int> hash;
        int res = 0;

        for(int i = 0;i < nums.size();i ++ )
        {
            int x = nums[i] - rev(nums[i]);
            res = (res + hash[x]) % mod;
            hash[x] ++;
        }
        return res;
    }
};

写法2：y总写法，从一个集合里选两个

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(auto x : nums){
            string t = to_string(x);
            reverse(t.begin(),t.end());
            int y = stoi(t); // stoi() 函数
            hash[x - y] ++ ;
        }

        int res = 0;
        int mod = 1e9 + 7;
        for(auto [k ,v] : hash){
            res = (res + ((long long)v * (v - 1)) / 2) % mod;// C[n][2];
        }
        return res;
    }
};

LeetCode 1815. 得到新鲜甜甜圈的最多组数

模拟退火

class Solution {
public:

    /*
    模拟退火 算法 :

    一个可以尽量达到全局最优的算法

    每次随机交换序列中的两个位置 来判断当前的序列是否可以比原始序列更优

    1. 若比原始序列更优,则保留交换
    2. 否则按一定概率保留交换 (这样才有机会达到全局最优) // 一定概率exp(delta / t) > (double)rand() / RAND_MAX

    */




    int n, m;
    vector<int> w;
    int ans;

    int calc() {
        int res = 1;
        for (int i = 0, s = 0; i < n; i ++ ) {
            s = (s + w[i]) % m;
            if (!s && i < n - 1) res ++ ;
        }
        ans = max(ans, res);
        return res;
    }

    void simulate_anneal() {
        random_shuffle(w.begin(), w.end());

        for (double t = 1e6; t > 1e-5; t *= 0.97) {
            int a = rand() % n, b = rand() % n;
            int x = calc(); // 原先序列的"值"
            swap(w[a], w[b]);
            int y = calc(); // 交换后序列的"值"
            //int delta = x - y; // 评价函数
            int delta = y - x; // 评价函数

            if(delta >0 ){} // 更优的解，接收
            else if (!(exp(delta / t) > (double)rand() / RAND_MAX)) // 以一定概率exp(delta / t) > (double)rand() / RAND_MAX接收，取!,表示不接受，就换回去！

                swap(w[a], w[b]);
        }
    }

    int maxHappyGroups(int batchSize, vector<int>& groups) {
        w = groups;
        n = w.size();
        m = batchSize;
        ans = 0;
        for (int i = 0; i < 80; i ++ ) simulate_anneal();
        return ans;
    }
};