Leet Code Weekly Contest 269
1. Find Target Indices After Sorting Array
Naive, sort and linear-scan.
class Solution
{
public:
vector<int> targetIndices(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());
vector<int> ret;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == target)
{
ret.push_back(i);
}
}
return ret;
}
};2. K Radius Subarray Averages
Preffix sum. Don't forget to use long long.
typedef long long ll;
class Solution
{
public:
vector<int> getAverages(vector<int>& nums, int k)
{
vector<ll> sum({ 0 });
for (auto &x : nums)
{
sum.push_back(sum.back() + x);
}
vector<int> ret;
for (int i = 0; i < nums.size(); i++)
{
int l = i - k;
int r = i + k;
if (l < 0)
{
ret.push_back(-1);
continue;
}
if (r >= nums.size())
{
ret.push_back(-1);
continue;
}
ll m = (2 * k + 1);
ret.push_back((sum[r + 1] - sum[l]) / m);
}
return ret;
}
};3. Removing Minimum and Maximum From Array
- If the array has only one element, then the answer is .
- Otherwise, let's say the positions of max / min values (the numbers are unique, so there are exactly 2 positions) are and , then we got three potential answers:
- Delete from left to right:
- Delete from right to left:
- Delete from both side:
- Take the minimum value of the three expressions above.
class Solution
{
public:
int minimumDeletions(vector<int>& nums)
{
if (nums.size() == 1)
{
return 1;
}
int min_val = INT_MAX, max_val = INT_MIN;
for (auto &num : nums)
{
min_val = min(min_val, num);
max_val = max(max_val, num);
}
vector<int> pos;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == min_val || nums[i] == max_val)
{
pos.push_back(i);
}
}
int a = pos[0], b = pos[1];
if (a > b)
{
swap(a, b);
}
int n = nums.size();
return min(
min(b + 1, n - a),
n - (b - a - 1)
);
}
};4. Find All People With Secret
The problem can be seens as computing the earliest knowing-secret time for each person. And that can be done by slightly changing SPFA :)
class Solution {
public:
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson)
{
// (y, t)
vector<pair<int, int>> targets[100000];
for (auto &meeting : meetings)
{
int x = meeting[0], y = meeting[1], t = meeting[2];
targets[x].push_back(make_pair(y, t));
targets[y].push_back(make_pair(x, t));
}
targets[0].push_back(make_pair(firstPerson, 0));
int know_at[100000];
for (int i = 0; i < n; i++)
{
know_at[i] = INT_MAX;
}
know_at[0] = 0;
bool visited[100000];
memset(visited, false, sizeof(bool) * n);
visited[0] = true;
queue<int> q({ 0 });
while (!q.empty())
{
int x = q.front(); q.pop();
visited[x] = false;
for (auto &pair : targets[x])
{
int y = pair.first, t = pair.second;
if (t < know_at[x])
{
continue;
}
if (know_at[y] > t)
{
know_at[y] = t;
if (!visited[y])
{
q.push(y);
visited[y] = true;
}
}
}
}
vector<int> ret;
for (int i = 0; i < n; i++)
{
if (know_at[i] != INT_MAX)
{
ret.push_back(i);
}
}
return ret;
}
};