LeetCode Weekly Contest 279
1. Sort Even and Odd Indices Independently
Naive.
class Solution
{
public:
vector<int> sortEvenOdd(vector<int>& nums)
{
vector<int> a, b;
for (int i = 0; i < nums.size(); i++)
{
if (i % 2 == 0)
{
a.push_back(nums[i]);
}
else
{
b.push_back(nums[i]);
}
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
vector<int> ans;
for (int i = 0, j = 0; i < a.size() || j < b.size(); )
{
if (i < a.size())
{
ans.push_back(a[i++]);
}
if (j < b.size())
{
ans.push_back(b[j++]);
}
}
return ans;
}
};2. Smallest Value of the Rearranged Number
- Decide the best digit every time (largest / smallest) until all digits are taken.
- Make sure to take zero only when at least one other digit has been taken.
class Solution
{
public:
long long smallestNumber(long long num)
{
if (num == 0)
{
return 0;
}
int cnt[10] = { 0 };
long long tmp = num;
if (tmp < 0)
{
tmp = -tmp;
}
while (tmp > 0)
{
cnt[tmp % 10]++;
tmp = tmp / 10;
}
long long ans = 0;
if (num > 0)
{
while (true)
{
int x = -1;
for (int i = 0; i <= 9; i++)
{
if (cnt[i] > 0 && (ans > 0 || i != 0))
{
x = i;
cnt[i]--;
break;
}
}
if (x == -1)
{
break;
}
ans = ans * 10 + x;
}
return ans;
}
else
{
while (true)
{
int x = -1;
for (int i = 9; i >= 0; i--)
{
if (cnt[i] > 0 && (ans > 0 || i != 0))
{
x = i;
cnt[i]--;
break;
}
}
if (x == -1)
{
break;
}
ans = ans * 10 + x;
}
return -ans;
}
}
};3. Design Bitset
- Use a global boolean to indicate the flipping status.
class Bitset {
public:
vector<int> s;
bool f = false;
int cnt = 0, len;
Bitset(int size)
{
s = vector<int>(size, 0);
len = size;
}
int get(int idx)
{
return s[idx];
}
void set(int idx, int val)
{
s[idx] = val;
}
void fix(int idx)
{
if (f)
{
if (get(idx) == 1)
{
set(idx, 0);
--cnt;
}
}
else
{
if (get(idx) == 0)
{
set(idx, 1);
++cnt;
}
}
}
void unfix(int idx)
{
if (f)
{
if (get(idx) == 0)
{
set(idx, 1);
++cnt;
}
}
else
{
if (get(idx) == 1)
{
set(idx, 0);
--cnt;
}
}
}
void flip()
{
f = !f;
}
bool all()
{
return count() == len;
}
bool one()
{
return count() > 0;
}
int count()
{
if (f)
{
return len - cnt;
}
else
{
return cnt;
}
}
string toString()
{
string ret = "";
for (int i = 0; i < len; i++)
{
int x = get(i);
if (f)
{
x = 1 - x;
}
ret.push_back('0' + x);
}
return ret;
}
};4. Minimum Time to Remove All Cars Containing Illegal Goods
- Pre-compute preffix sum first.
- Let's say that we want to take the left cars and the right cars (other cars will be taken with
cost = 2if necessary), we know the cost should be . - When is determined, we know we will take the smallest .
- So we can do a linear scan and maintain the current minimum .
class Solution
{
public:
int minimumTime(string s)
{
vector<int> sum = { 0 };
for (auto &c : s)
{
sum.push_back(sum.back() + (c - '0'));
}
int n = s.length();
int pmax = 0, ans = n;
for (int i = 0; i <= n; i++)
{
int tmp = pmax + 2 * sum[i] + (n - i);
ans = min(ans, tmp);
pmax = min(pmax, i - 2 * sum[i]);
}
return ans;
}
};