作者： admin
[力扣] 算法 930 (C++)
930. 和相同的二元子数组
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
vector map{ 1 };
for (auto&& num : nums)
{
if (num)
{
map.emplace_back(1);
}
else
{
++map.back();
}
}
int ret = 0;
for (unsigned i = goal; i < map.size(); ++i)
{
if (goal > 0)
{
ret += map[i] * map[i - goal];
}
else
{
ret += map[i] * (map[i] - 1) / 2;
}
}
return ret;
}
};
[力扣] 算法 191 (C++)
剑指 Offer 15. 二进制中1的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);
n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);
n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);
n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF);
n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF);
return n;
}
};
[力扣] 算法 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];
}
};
[力扣] 算法 1720 (C++)
1720. 解码异或后的数组
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;
}
};
[C++] 计时函数
// #include <ctime>
inline auto click()
{
static auto begin = clock();
auto end = clock();
auto ret = (float)(end - begin) / CLOCKS_PER_SEC;
begin = end;
return ret;
}