5.14 奇安信C++笔试题解

第一题 100%

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 得到画布上白色小方格的个数
     * @param rects int整型vector<vector<>> 
     * @return int整型
     */
    
    int getWhiteCounts(vector<vector<int> >& s) {
        // write code here
        vector<vector<int> > g(101, vector<int>(101, 0));
        for(auto vec : s)
        {
            int x1 = vec[0];
            int y1 = vec[1];
            int x2 = vec[2];
            int y2 = vec[3];
            if(x1 > x2) swap(x1, x2);
			if(y1 > y2) swap(y1, y2);
            
            for(int i = x1 + 1; i <= x2; i ++)
                for(int j = y1 + 1; j <= y2; j ++)
                    g[i][j] ^= 1;

        }
        int res = 0;
        for(int i = 1; i <= 100; i ++)
            for(int j = 1; j <= 100; j ++)
                res += !g[i][j];
        return res;
    }
};

第二题 贪心题，用二分+贪心 过了50%

正确的写法

class Solution {
public:
    int maxTime(vector<int>& batteries) {
        sort(batteries.begin(), batteries.end(), greater<int>());
        int time = 0;
        int K = batteries.size();
        while(K >= 5) {
            for (int i = 0; i < 5; i++) {
                batteries[i] --;
                if (batteries[i] == 0) K--;
            }
            time++;
            sort(batteries.begin(), batteries.end(), greater<int>());
            
        }
        return time;
    }
};

50%错误的写法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 输入各台手机的剩余电量，返回能坚持的最大时间
     * @param batteries int整型vector 每台手机剩余电量，[0,100]之间
     * @return int整型
     */
    
    vector<long long> vec;
    bool check(long long mid)
    {
        priority_queue<long long> q;
        for(int i = 0; i < 5; i ++) q.push(mid);
        
        for(auto x : vec)
        {
            long long t = q.top();
            q.pop();
            q.push(t - x);
        }
        
        if(q.top() > 0) return false;
        else return true;
    }
    
    int maxTime(vector<int>& bat) {
        for(auto x : bat) vec.push_back(x);
        sort(vec.begin(), vec.end(), greater<long long>());
        int n = vec.size();
        
        long long l = 0, r = vec[0] * n / 5;
        while(l < r)
        {
            long long mid = (l + r + 1) / 2;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};