Leet Code Weekly Contest 271
1. Rings and Rods
Native.
class Solution {
public:
int countPoints(string rings)
{
bool has[10][3];
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 3; j++)
{
has[i][j] = false;
}
}
int n = rings.length() / 2;
for (int i = 0; i < n; i++)
{
char c = rings[i * 2];
int p = rings[i * 2 + 1] - '0';
if (c == 'R')
{
has[p][0] = true;
}
if (c == 'G')
{
has[p][1] = true;
}
if (c == 'B')
{
has[p][2] = true;
}
}
int ans = 0;
for (int i = 0; i < 10; i++)
{
if (has[i][0] && has[i][1] && has[i][2])
{
ans++;
}
}
return ans;
}
};2. Sum of Subarray Ranges
- brute-force.
- Don't forget long long.
class Solution {
public:
long long subArrayRanges(vector<int>& nums)
{
int n = nums.size();
long long ans = 0;
for (int i = 0; i < n; i++)
{
long long a = nums[i], b = nums[i];
for (int j = i; j < n; j++)
{
a = min(a, (long long) nums[j]);
b = max(b, (long long) nums[j]);
ans += b - a;
}
}
return ans;
}
};3. Watering Plants II
Well, basically we just simulate the process as they described.
class Solution {
public:
int minimumRefill(vector<int>& plants, int capacityA, int capacityB)
{
int n = plants.size();
int pa = 0, pb = n - 1;
int ca = capacityA, cb = capacityB;
int ans = 0;
while (pa <= pb)
{
if (pa == pb)
{
if (max(ca, cb) < plants[pa])
{
ans++;
}
break;
}
else
{
if (plants[pa] > ca)
{
ca = capacityA;
ans++;
}
ca -= plants[pa++];
if (plants[pb] > cb)
{
cb = capacityB;
ans++;
}
cb -= plants[pb--];
}
}
return ans;
}
};4. Maximum Fruits Harvested After at Most K Steps
- First, we can prove that we will never turn over the direction more than one time.
- Based on that, we can enumerate the position where we turn over the direction in time.
- Once we know where we turn over the direction, we can performa a binary search and preffix sum to compute the points.
- The overall time complexity is .
class Solution
{
public:
int maxv(vector<int> nums)
{
int ret = INT_MIN;
for (auto x : nums)
{
ret = max(ret, x);
}
return ret;
}
int minv(vector<int> nums)
{
int ret = INT_MAX;
for (auto x : nums)
{
ret = min(ret, x);
}
return ret;
}
int calc(vector<int> &pos, vector<int> &sum, int left, int right)
{
int a = lower_bound(pos.begin(), pos.end(), left) - pos.begin();
int b = upper_bound(pos.begin(), pos.end(), right) - pos.begin();
int ret = sum[b] - sum[a];
// cout << left << ", " << right << " -> " << ret << endl;
return ret;
}
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k)
{
int n = fruits.size();
int ans = 0;
vector<int> positions;
vector<int> sum = { 0 };
for (int i = 0; i < n; i++)
{
positions.push_back(fruits[i][0]);
sum.push_back(sum.back() + fruits[i][1]);
}
for (int i = 0; i < n; i++)
{
int pos = positions[i];
int d = abs(pos - startPos);
if (d > k)
{
continue;
}
int r = k - d;
// 1. pos + r, pos, startPos
ans = max(ans, calc(positions, sum,
minv(vector<int>({ pos + r, pos, startPos })),
maxv(vector<int>({ pos + r, pos, startPos }))
));
// 2. pos - r, pos, startPos
ans = max(ans, calc(positions, sum,
minv(vector<int>({ pos - r, pos, startPos })),
maxv(vector<int>({ pos - r, pos, startPos }))
));
}
return ans;
}
};