Leet Code Weekly Contest 268
1. Two Furthest Houses With Different Colors
Simply enumerate all pairs of indexes. .
class Solution {
public:
int maxDistance(vector<int>& colors)
{
int ans = INT_MIN;
for (int i = 0; i < colors.size(); i++)
{
for (int j = i + 1; j < colors.size(); j++)
{
if (colors[i] != colors[j])
{
ans = max(ans, j - i);
}
}
}
return ans;
}
};2. Watering Plants
linear scan.
class Solution {
public:
int wateringPlants(vector<int>& plants, int capacity)
{
int ans = 0, rest = capacity;
for (int i = 0; i < plants.size(); i++)
{
if (rest >= plants[i])
{
ans++;
rest -= plants[i];
}
else
{
ans += (i - 1) - (-1);
ans += (i) - (-1);
rest = capacity - plants[i];
}
}
return ans;
}
};3. Range Frequency Queries
Build a map from values to the positions of values and pre-sort the positions for each value. Then the query can be done by binary search.
class RangeFreqQuery {
public:
unordered_map<int, vector<int>> pos;
RangeFreqQuery(vector<int>& arr)
{
for (int i = 0; i < arr.size(); i++)
{
int val = arr[i];
if (pos.find(val) == pos.end())
{
pos[val] = vector<int>();
}
pos[val].push_back(i);
}
for (auto &pair : pos)
{
sort(pair.second.begin(), pair.second.end());
}
}
int query(int left, int right, int value)
{
if (pos.find(value) == pos.end())
{
return 0;
}
// first pos >= left
auto a = lower_bound(pos[value].begin(), pos[value].end(), left);
// first pos > right
auto b = upper_bound(pos[value].begin(), pos[value].end(), right);
return b - a;
}
};4. Sum of k-Mirror Numbers
The first idea came into my mind is to enumerate the left part of the possible answers. But I struggled on TLE (possiblly because I used vector so the constant is literally big).
class Solution {
public:
inline ll valid(int k, ll x)
{
vector<int> digits;
while (x > 0)
{
digits.push_back(x % k);
x = x / k;
}
for (int i = 0, j = digits.size() - 1; i < j; i++, j--)
{
if (digits[i] != digits[j])
{
return false;
}
}
return true;
}
inline vector<int> digits_of(ll x, vector<int> &digits)
{
while (x > 0)
{
digits.push_back(x % 10);
x = x / 10;
}
reverse(digits.begin(), digits.end());
return digits;
}
inline ll digits_to_num(vector<int> &digits)
{
ll ret = 0;
for (int i = 0; i < digits.size(); i++)
{
ret = ret * 10 + digits[i];
}
return ret;
}
// 123 -> 123321
inline ll make_mirror_a(ll x)
{
vector<int> digits;
digits_of(x, digits);
int l = digits.size();
for (int i = l - 1; i >= 0; i--)
{
digits.push_back(digits[i]);
}
return digits_to_num(digits);
}
// 123 -> 12321
inline ll make_mirror_b(ll x)
{
vector<int> digits;
digits_of(x, digits);
int l = digits.size();
for (int i = l - 2; i >= 0; i--)
{
digits.push_back(digits[i]);
}
return digits_to_num(digits);
}
long long kMirror(int k, int n)
{
ll ans = 0;
for (int w = 1; n > 0; w++)
{
ll low = pow(10, w - 1);
ll high = pow(10, w) - 1;
// 1, 3, 5 digits.
for (ll num = low; num <= high && n > 0; num++)
{
auto x = make_mirror_b(num);
if (valid(k, x))
{
ans += x;
n--;
}
}
// 2, 4, 6 digits
for (ll num = low; num <= high && n > 0; num++)
{
auto x = make_mirror_a(num);
if (valid(k, x))
{
ans += x;
n--;
}
}
}
cout << endl;
return ans;
}
};Then I finally decided to pre-compute a table offline. For each , we can pre-compute the first 30 valid numbers.
typedef long long ll;
class Solution {
public:
vector<vector<ll>> nums = vector<vector<ll>>({
vector<ll>({ 1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939 }),
vector<ll>({ 1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138 }),
vector<ll>({ 1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715 }),
vector<ll>({ 1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121 }),
vector<ll>({ 1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654 }),
vector<ll>({ 1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446 }),
vector<ll>({ 1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355 }),
vector<ll>({ 1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442 })
});
long long kMirror(int k, int n)
{
ll ans = 0;
vector<ll> vals = nums[k - 2];
for (int i = 0; i < n; i++)
{
ans += vals[i];
}
return ans;
}
};