[力扣] 算法 525 (C++)

525. 连续数组

class Solution {
	static inline int f(int x)
	{
		return 2 * x - 1;
	}
public:
	int findMaxLength(vector<int>& nums) {
		unordered_map<int, size_t> map;
		nums[0] = f(nums[0]);
		map.emplace(nums[0], 0);
		size_t ret = 0;
		for (size_t i = 1, size = nums.size(), tmp; i < size; ++i)
		{
			nums[i] = nums[i - 1] + f(nums[i]);
			if (nums[i] == 0 && (tmp = i + 1) > ret)
			{
				ret = tmp;
			}
			else
			{
				auto found = map.find(nums[i]);
				if (found == map.end())
				{
					map.emplace(nums[i], i);
				}
				else if ((tmp = i - found->second) > ret)
				{
					ret = tmp;
				}
			}
		}
		return ret;
	}
};

[力扣] 算法 523 (C++)

523. 连续的子数组和

class Solution {
public:
	bool checkSubarraySum(vector<int>& nums, int k) {
		if (nums.size() < 2)
		{
			return false;
		}
		unordered_map<int, size_t> map;
		map[nums[0] % k] = 0;
		for (size_t i = 1; i < nums.size(); ++i)
		{
			nums[i] += nums[i - 1];
			nums[i] %= k;
			if (nums[i] == 0)
			{
				return true;
			}
			auto found = map.find(nums[i]);
			if (found == map.end())
			{
				map[nums[i]] = i;
			}
			else
			{
				if (i - found->second > 1)
				{
					return true;
				}
			}
		}
		return false;
	}
};

[力扣] 算法 1744 (C++)

1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗?

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;
	}
};

[力扣] 算法 1310 (C++)

1310. 子数组异或查询

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;
    }
};

[力扣] 算法 64 (C++)

64. 最小路径和

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];
    }
};