分类： C/C++

class Solution {
public:
	vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
		vector<long long> tmp(candiesCount.size());
		tmp[0] = candiesCount[0];
		for (size_t i = 1, size = tmp.size(); i < size; ++i)
		{
			tmp[i] += tmp[i - 1] + candiesCount[i];
		}
		vector<bool> ret(queries.size());
		for (size_t i = 0, size = queries.size(); i < size; ++i)
		{
			auto&& query = queries[i];
			int favoriteType = query[0];
			int favoriteDay = query[1];
			long dailyCap = query[2];

			// 往死里吃，必须保证最喜欢的糖果之前的糖果已经全部吃完
			int atLeast = favoriteType > 0 ? tmp[favoriteType - 1] : 0;
			// 一颗一颗吃，必须保证当天至少剩一颗最喜欢的糖
			int limit = tmp[favoriteType];
			// 总共花费的天数
			long day = favoriteDay + 1;

			ret[i] = dailyCap * day > atLeast && 1 * day <= limit;
		}
		return ret;
	}
};

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        for (size_t i = 1, size = arr.size(); i < size; ++i) {
            arr[i] ^= arr[i - 1];
        }
        vector<int> ret(queries.size());
        for (size_t i = 0, size = queries.size(); i < size; ++i) {
            int from = queries[i][0], to = queries[i][1];
            ret[i] = arr[to] ^ (from ? arr[from - 1] : 0);
        }
        return ret;
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        const int m = grid.size();
        const int n = grid[0].size();
        for (int i = m - 2; i >= 0; --i)
            grid[i][n - 1] += grid[i + 1][n - 1];
        for (int i = n - 2; i >= 0; --i)
            grid[m - 1][i] += grid[m - 1][i + 1];
        for (int i = m - 2; i >= 0; --i)
            for (int j = n - 2; j >= 0; --j)
                 grid[i][j] += min(grid[i + 1][j], grid[i][j + 1]);
        return grid[0][0];
    }
};

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> ret;
        ret.push_back(first);
        for (int i = 0, size = encoded.size(); i < size; i++)
            ret.push_back(first ^= encoded[i]);
        return ret;
    }
};

class Solution {
public:
    bool judgeSquareSum(int c) {
        auto i = 0L;
        auto j = long(sqrt(c));
        while(i <= j) {
            auto rsl = i * i + j * j;
            if (rsl == c)
                return true;
            if (rsl < c)
                i++;
            else
                j--;
        }
        return false;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int left = 0, right = row * col - 1;
        while (left < right) {
            auto mid = (left + right) / 2;
            auto num = matrix[mid / col][mid % col];
            if (num == target) 
                return true;
            if (num < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return matrix[left / col][left % col] == target;
    }
};

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        auto ret = (n >> 16) | (n << 16);// ((ret & 0xffff0000) >> 16) | ((ret & 0x0000ffff) << 16)
        ret = ((ret & 0xff00ff00) >> 8) | ((ret & 0x00ff00ff) << 8);
        ret = ((ret & 0xf0f0f0f0) >> 4) | ((ret & 0x0f0f0f0f) << 4);// 1111 0000
        ret = ((ret & 0xcccccccc) >> 2) | ((ret & 0x33333333) << 2);// 1100 0011
        ret = ((ret & 0xaaaaaaaa) >> 1) | ((ret & 0x55555555) << 1);// 1010 0101
        return ret;
    }
};