leetcode 299.猜数字游戏

原题传送门

题目描述

不想用哈希，用哈希都没意思了。用两个数组就行了。主要是如果找到两个共有的元素，并且位置不同的元素，就是B前面的系数。根据水桶原理，两者计数并且取最小值就是错误的个数，正确的个数直接比较就行了，时间复杂度O(n).
没有暴力哦！

class Solution {
public:
    string getHint(string secret, string guess) {

        // 寻找两个元素 共有的元素个数， 
        // 减去 匹配 的 个数 得到 错误的个数
        int s[10] = {0};
        int g[10] = {0};

        int right = 0;

        int n = secret.size();
        for (int i = 0; i < n; i ++ ){
            if (secret[i] == guess[i]) right ++ ;
            else {
                s[secret[i] - '0'] ++ ;
                g[guess[i] - '0'] ++ ;
            }
        }
        int wrong = 0;
        for (int i = 0; i < 10; i ++ ){
            // 最小的就是两个都有的。
            if (s[i] && g[i]) wrong += min(s[i], g[i]);
        }

        string ans = to_string(right) + "A" + to_string(wrong) + "B";
        return ans;

    }
};