weekly contest 222
2020.1.3 元旦假期
1710. Maximum Units on a Truck
class Solution
{
public:
int maximumUnits(vector<vector<int>> &boxTypes, int truckSize)
{
auto comp = [](const vector<int> &v1, const vector<int> &v2) {
return v1[1] > v2[1];
};
sort(boxTypes.begin(), boxTypes.end(), comp);
int ret = 0;
int count = truckSize;
for (int i = 0; count > 0 && i < boxTypes.size(); i++)
{
int x = min(count, boxTypes[i][0]);
ret += x * boxTypes[i][1];
count -= x;
}
return ret;
}
};
1711. Count Good Meals
1712. Ways to Split Array Into Three Subarrays
1713. Minimum Operations to Make a Subsequence
weekly contest 223
2020.01.10 以后就做后两题吧
1722. Minimize Hamming Distance After Swap Operations
1723. Find Minimum Time to Finish All Jobs
weekly contest 224
2020.01.17
1727. Largest Submatrix With Rearrangements
1728. Cat and Mouse II
weekly contest 225
2020.01.24
1738. Find Kth Largest XOR Coordinate Value
1739. Building Boxes
weekly contest 230
2021.02.28
1775. Equal Sum Arrays With Minimum Number of Operations
两个数组nums1和nums2，由整数1-6构成。每个step能将一个数组中的某个数改成另一个数（1-6），问最少需要多少步骤能让两个数组和相同。如果不能，返回-1.
先求和，计算差 diff 。 假设sum1 > sum2，将nums1降序排列，nums2升序排列。比较二者能获得的diff，即nums1-1和6-nums2，取较大的。
class Solution
{
public:
int minOperations(vector<int>& nums1, vector<int>& nums2)
{
int s1 = 0, s2 = 0;
for (int i = 0; i < nums1.size(); i++)
s1 += nums1[i];
for (int i = 0; i < nums2.size(); i++)
s2 += nums2[i];
if (s1 < s2)
return minOperations(nums2, nums1);
int diff = s1 - s2;
if (diff == 0)
return 0;
sort(nums1.begin(), nums1.end(), greater<int>());
sort(nums2.begin(), nums2.end());
int p1 = 0, p2 = 0;
while (diff > 0)
{
if (p1 < nums1.size() && (p2 >= nums2.size() || (nums1[p1] - 1 > 6 - nums2[p2])))
{
diff -= nums1[p1] - 1;
p1++;
}
else if (p2 < nums2.size())
{
diff -= 6 - nums2[p2];
p2++;
}
else
{
return -1;
}
}
return p1 + p2;
}
};
1776. Car Fleet II
weekly contest 231
1786. Number of Restricted Paths From First to Last Node
1787. Make the XOR of All Segments Equal to Zero
weekly contest 232
2020.03.14
1792. Maximum Average Pass Ratio
1793. Maximum Score of a Good Subarray
好久没有好好学习了呀
Weekly Contest 237
2021.04.18
1832 Easy. Check if the Sentence Is Pangram
func checkIfPangram(sentence string) bool {
var visited [26]int
for i := 0; i < len(sentence); i++ {
visited[sentence[i]-'a'] = 1
}
for i := 0; i < len(visited); i++ {
if visited[i] == 0 {
return false
}
}
return true
}
1833 Medium. Maximum Ice Cream Bars
1834 Medium. Single-Threaded CPU
1835 Hard. Find XOR Sum of All Pairs Bitwise AND
Weekly Contest 238
2021.04.25
1837 Easy. Sum of Digits in Base K
1838 Medium. Frequency of the Most Frequent Element
1839 Medium. Longest Substring Of All Vowels in Order
1840 Hard. Maximum Building Height
weekly contest 239
2021.05.02 跑去无锡玩了。喜欢这座城市
1850 Medium. Minimum Adjacent Swaps to Reach the Kth Smallest Number
1851 Hard. Minimum Interval to Include Each Query
Weekly Contest 240
2021.05.09 今天母亲节
1856 Medium. Maximum Subarray Min-Product
1857 Hard. Largest Color Value in a Directed Graph
Weekly Contest 241
2021.05.16
第三题给我整自闭了
1865 Medium. Finding Pairs With a Certain Sum
1866 Hard. Number of Ways to Rearrange Sticks With K Sticks Visible
Weekly Contest 242
2021.05.23
1870 Medium. Minimum Speed to Arrive on Time
经典二分
class Solution
{
public:
int minSpeedOnTime(vector<int> &dist, double hour)
{
int l = 1, r = 1e7;
if (hour <= dist.size() - 1)
return -1;
while (l < r)
{
int speed = (l + r) / 2;
int total = 0;
for (int i = 0; i < dist.size() - 1; i++)
{
total += dist[i] / speed;
total += (dist[i] % speed) != 0;
}
if (hour >= total + dist.back() * 1.0 / speed)
r = speed;
else
l = speed + 1;
}
return r;
}
};
1871 Medium. Jump Game VII
这题不难。因为高点的复杂度也能过。
class Solution
{
public:
bool canReach(string s, int minJump, int maxJump)
{
vector<int> dp;
dp.push_back(0);
for (int j = 1; j < s.size(); j++)
{
if (s[j] == '1')
continue;
for (int i = dp.size() - 1; i >= 0; i--)
{
if (dp[i] + minJump <= j && dp[i] + maxJump >= j)
{
dp.push_back(j);
break;
}
}
}
return dp.back() == s.size() - 1;
}
};
1872 Hard. Stone Game VIII
BiWeekly contest 53
2021.05.29 第一次参加双周赛
第三题的brute-force就很恶心
1879. Minimum XOR Sum of Two Arrays
Weekly Contest 243
2021.05.30
熟练度不够呀
1882 Medium. Process Tasks Using Servers
1883 Hard. Minimum Skips to Arrive at Meeting On Time
Weekly Contest 244
2021.06.06
1886 Easy. Determine Whether Matrix Can Be Obtained By Rotation
这道题就是考旋转n*n矩阵。然而旋转是medium，这个是easy
1888 Medium. Minimum Number of Flips to Make the Binary String Alternating
利用s+s 来处理旋转的情况，再用滑动窗口。
class Solution
{
public:
int minFlips(string s)
{
int n = s.size();
s += s;
string s1, s2;
for (int i = 0; i < s.size(); i++)
{
s1 += i % 2 ? '0' : '1';
s2 += i % 2 ? '1' : '0';
}
int ans1 = 0, ans2 = 0, ans = INT_MAX;
for (int i = 0; i < s.size(); i++)
{
if (s1[i] != s[i])
++ans1;
if (s2[i] != s[i])
++ans2;
if (i >= n)
{
if (s1[i - n] != s[i - n])
--ans1;
if (s2[i - n] != s[i - n])
--ans2;
}
if (i >= n - 1)
ans = min({ans1, ans2, ans});
}
return ans;
}
};
1889 Hard. Minimum Space Wasted From Packaging
装箱问题。排序+二分搜素。浪费的空间=盒子总大小-包裹总大小
class Solution
{
public:
int minWastedSpace(vector<int>& A, vector<vector<int>>& boxes)
{
sort(A.begin(), A.end());
long res = LONG_MAX, mod = 1e9 + 7, sumA = 0;
for (int a : A)
sumA += a;
for (auto& B : boxes)
{
sort(B.begin(), B.end());
if (B[B.size() - 1] < A[A.size() - 1])
continue;
long cur = 0, i = 0, j;
for (int b : B)
{
j = upper_bound(A.begin(), A.end(), b) - A.begin();
cur += b * (j - i);
i = j;
}
res = min(res, cur);
}
return res < LONG_MAX ? (res - sumA) % mod : -1;
}
};
Weekly Contest 245
2021.06.13
端午假期~
1898 Medium. Maximum Number of Removable Characters
一道二分的题目，写函数参数的时候忘记加&了，一直超时。。因为题目没有加&，而我直接复制题目的..
class Solution
{
public:
int maximumRemovals(string s, string p, vector<int> &removable)
{
int n = removable.size();
int l = 0, r = n;
while (l < r)
{
int mid = (l + r + 1) / 2;
if (isSubseq(s, p, removable, mid))
{
l = mid;
}
else
r = mid - 1;
}
return r;
}
bool isSubseq(string &s1, string &s2, vector<int> &removable, int n)
{
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(removable[i]);
int p1, p2;
p1 = p2 = 0;
while (p2 < s2.length() && p1 < s1.length())
{
if (!s.count(p1) && s2[p2] == s1[p1])
{
p2++;
}
p1++;
}
return p2 == s2.length();
}
};
1900 Hard. The Earliest and Latest Rounds Where Players Compete
Weekly Contest 246
2021.06.20
上海中考。
1904 Medium. The Number of Full Rounds You Have Played
这道题"00:01","00:02"这个case，测试数据没有测出来。。
class Solution
{
public:
int numberOfRounds(string startTime, string finishTime)
{
int start = 60 * stoi(startTime.substr(0, 2)) + stoi(startTime.substr(3));
int finish = 60 * stoi(finishTime.substr(0, 2)) + stoi(finishTime.substr(3));
if (start > finish)
finish += 60 * 24;
return max(0, finish / 15 - (start + 14) / 15);
}
};
1905 Medium. Count Sub Islands
这道题减少时间复杂度的关键是：只对第二张图进行dfs。如果dfs的过程中发现对应位置在第一张图里为0，则不是sub island
class Solution
{
public:
int dfs(vector<vector<int>> &grid, int x, int y, vector<vector<int>> &grid1)
{
if (x >= 0 && x <= grid.size() - 1 && y >= 0 && y <= grid[0].size() - 1 && grid[x][y] == 1)
{
int ret = 1;
grid[x][y] = 0;
ret &= dfs(grid, x - 1, y, grid1);
ret &= dfs(grid, x + 1, y, grid1);
ret &= dfs(grid, x, y + 1, grid1);
ret &= dfs(grid, x, y - 1, grid1);
ret &= (grid1[x][y] == 1);
return ret;
}
else
return 1;
};
int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2)
{
int ret = 0;
int m = grid2.size();
int n = grid2[0].size();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid2[i][j] == 1)
{
ret += dfs(grid2, i, j, grid1);
}
}
}
return ret;
}
};
1906 Medium. Minimum Absolute Difference Queries
Biweekly Contest 55
2021.06.27 做了前两题
1911. Maximum Alternating Subsequence Sum
求数组的子序列，是的奇数index数的和-偶数index数的和最大。
long long maxAlternatingSum(vector<int>& A)
{
long long odd = 0, even = 0;
for (int& a : A)
even = max(even, odd + a),
odd = even - a;
return even;
}
1912. Design Movie Rental System
Weekly Contest 247
2021.06.27
1914 Medium. Cyclically Rotating a Grid
class Solution
{
public:
void rotate(vector<vector<int>>& grid, int top, int left, int down, int right, int k)
{
vector<int> nums;
int i = top, j = left;
for (; j < right; j++)
nums.push_back(grid[i][j]);
for (; i < down; i++)
nums.push_back(grid[i][j]);
for (; j > left; j--)
nums.push_back(grid[i][j]);
for (; i > top; i--)
nums.push_back(grid[i][j]);
k = k % nums.size();
i = top, j = left;
for (; j < right; j++)
grid[i][j] = nums[k++ % nums.size()];
for (; i < down; i++)
grid[i][j] = nums[k++ % nums.size()];
for (; j > left; j--)
grid[i][j] = nums[k++ % nums.size()];
for (; i > top; i--)
grid[i][j] = nums[k++ % nums.size()];
}
vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k)
{
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < min(m, n) / 2; i++)
{
rotate(grid, i, i, m - i - 1, n - i - 1, k);
}
return grid;
}
};
1915 Medium. Number of Wonderful Substrings
用bitmask来记录各个字符出现的次数。一开始都是0。cur来统计当前的字符出现次数。那么count[cur]是之前的出现次数，这两个前缀和相减得到的字串，所有字符都是偶数个，满足要求。因为可以有一个奇数次字符的出现，所以可以在cur的基础上加一个字符。
class Solution
{
public
long wonderfulSubstrings(String word)
{
long res = 0, count[] = new long[1024];
int cur = 0;
count[0] = 1L;
for (int i = 0; i < word.length(); ++i)
{
cur ^= 1 << (word.charAt(i) - 'a');
// 统计所有字符都出现偶数次的次数
res += count[cur]++;
// 统计最多有一个字符出现奇数次的次数
for (int j = 0; j < 10; ++j)
res += count[cur ^ (1 << j)];
}
return res;
}
};
1916 Hard. Count Ways to Build Rooms in an Ant Colony
Weekly Contest 248
2021.07.04
1922 Medium. Count Good Numbers
取mod的快速幂
class Solution
{
public:
int countGoodNumbers(long long n)
{
if (n == 1)
{
return 5;
}
if (n % 2 != 0)
{
long long ret = (long long)5 * countGoodNumbers(n - 1);
return ret % 1000000007;
}
else
{
long long ret = Pow(20, n / 2) % 1000000007;
return ret % 1000000007;
}
}
int Pow(long long a, long long n)
{
long long ans = 1;
while (n)
{
if (n & 1)
ans *= a;
ans %= 1000000007;
a *= a; //a自乘
a %= 1000000007;
n >>= 1; //n往右移一位
}
return ans;
}
};
1923 Hard. Longest Common Subpath
Biweekly Contest 56
1927. Sum Game
一道数学题目
1928. Minimum Cost to Reach Destination in Time
迪杰斯特拉算法，加上了两个cost
Weekly Contest 249
2021.07.11
这周有两道hard..都不会
1931 Hard. Painting a Grid With Three Different Colors
1932 Hard. Merge BSTs to Create Single BST
Weekly Contest 250
2021.07.18
前两题都比较简单。第三题直接O(m*n*n)的递归会超时，需要进行分析降低复杂度，需要技巧。将求abs拆分成left和right两类，然后可以得到单调的left max 和 right max
1937 Medium. Maximum Number of Points with Cost
class Solution
{
public:
long long maxPoints(vector<vector<int>> &points)
{
vector<vector<long long>> dp(points.size(), vector<long long>(points[0].size(), -1));
for (int i = 0; i < points[0].size(); ++i)
{
dp[0][i] = points[0][i];
}
for (int i = 1; i < points.size(); ++i)
{
vector<long long> left_dp(points[i].size(), -1);
vector<long long> right_dp(points[i].size(), -1);
left_dp[0] = dp[i - 1][0];
for (int k = 1; k < points[i].size(); ++k)
{
left_dp[k] = max(left_dp[k - 1], dp[i - 1][k] + k);
}
right_dp.back() = dp[i - 1].back() - points[i].size() + 1;
for (int k = points[i].size() - 2; k >= 0; --k)
{
right_dp[k] = max(right_dp[k + 1], dp[i - 1][k] - k);
}
for (int j = 0; j < points[i].size(); ++j)
{
dp[i][j] = max(left_dp[j] - j, right_dp[j] + j) + points[i][j];
}
}
long long max_ans = -1;
for (const auto v : dp.back())
{
max_ans = max(max_ans, v);
}
return max_ans;
}
};
1938 Hard. Maximum Genetic Difference Query
Weekly Contest 251
2021.07.25
烟花来袭。这次做了3题
1947 Medium. Maximum Compatibility Score Sum
直接暴力求解就能过。本来想着怎么用bitmask来压缩的
class Solution
{
public:
int maxCompatibilitySum(vector<vector<int>> &students, vector<vector<int>> &mentors)
{
int m = students.size();
vector<int> pairs(m);
for (int i = 0; i < m; i++)
pairs[i] = i;
int maxret = 0;
do
{
int temp = 0;
for (int i = 0; i < m; i++)
{
auto &vs = students[i];
auto &vm = mentors[pairs[i]];
for (int j = 0; j < vs.size(); j++)
{
if (vs[j] == vm[j])
temp++;
}
}
maxret = max(maxret, temp);
} while (next_permutation(pairs.begin(), pairs.end()));
return maxret;
}
};
1948 Hard. Delete Duplicate Folders in System
Weekly Contest 252
2021.08.01
数学题为主
1953 Medium. Maximum Number of Weeks for Which You Can Work
class Solution
{
public:
long long numberOfWeeks(vector<int> &milestones)
{
long long sum = 0;
int maxval = 0;
for (int i = 0; i < milestones.size(); i++)
{
sum += milestones[i];
maxval = max(milestones[i], maxval);
}
long long other = sum - maxval;
if (other + 1 >= maxval)
return sum;
else
return other * 2 + 1;
}
};
1954 Medium. Minimum Garden Perimeter to Collect Enough Apples
二分法
class Solution
{
public:
long long minimumPerimeter(long long neededApples)
{
long long l = 1;
long long r = 1e6;
while (l < r)
{
long long mid = (l + r) / 2;
if (2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples)
r = mid;
else
l = mid + 1;
}
return l * 8;
}
};
1955 Hard. Count Number of Special Subsequences
dp
Biweekly Context
2021.08.07 经典只会前两题。
1959. Minimum Total Space Wasted With K Resizing Operations
1960. Maximum Product of the Length of Two Palindromic Substrings
Weekly Contest 253
2021.08.08 做了三题。这周题目不难。
1963 Medium. Minimum Number of Swaps to Make the String Balanced
先把字符串化简，拿到剩下的不匹配的个数，直接求得结果
class Solution
{
public:
void myreplace(string& s)
{
stack<char> st;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '[')
st.push(s[i]);
else
{
if (!st.empty() && st.top() == '[')
st.pop();
else
st.push(']');
}
}
string ret = "";
while (!st.empty())
{
ret.push_back(st.top());
st.pop();
}
reverse(ret.begin(), ret.end());
s = ret;
}
int minSwaps(string s)
{
myreplace(s);
int n = s.size();
return (1 + n / 2) / 2;
}
};
1964 Hard. Find the Longest Valid Obstacle Course at Each Position
升级版的最长不减子序列
class Solution
{
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles)
{
vector<int> res;
vector<int> dp;
for (int i = 0; i < obstacles.size(); i++)
{
auto it = std::upper_bound(dp.begin(), dp.end(), obstacles[i]);
res.push_back(it - dp.begin() + 1);
if (it == dp.end())
dp.push_back(obstacles[i]);
else
*it = obstacles[i];
}
return res;
}
};
Weekly Contest 254
2021.08.15
做了两题。第二第三题都是数学题。第四题没看，但点赞数很多，留着之后看
1968 Medium. Array With Elements Not Equal to Average of Neighbors
1969 Medium. Minimum Non-Zero Product of the Array Elements
1970 Hard. Last Day Where You Can Still Cross
BiWeekly Contest 59
做了两题，1000多名
1976. Number of Ways to Arrive at Destination
Dijkstra
第四题不会
Weekly Contest 255
2021.08.22 日常只会做两题
1981 Medium. Minimize the Difference Between Target and Chosen Elements
1982 Hard. Find Array Given Subset Sums
Weekly Contest 256
Weekly Contest 256
2021.08.29
1985 Medium. Find the Kth Largest Integer in the Array
注意comp函数在相等的时候要返回false
class Solution
{
public:
string kthLargestNumber(vector<string>& nums, int k)
{
auto comp = [](string& str1, string& str2)
{
if (str1.size() == str2.size())
{
for (int i = 0; i < str1.length(); i++)
if (str1[i] > str2[i])
return true;
else if (str1[i] < str2[i])
return false;
}
return str1.size() > str2.size();
};
nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), comp);
return nums[k - 1];
}
};
1986 Medium. Minimum Number of Work Sessions to Finish the Tasks
1987 Hard. Number of Unique Good Subsequences
Biweekly Contest 60
2021.09.04
1994. The Number of Good Subsets
Weekly Contest 257
2021.09.05
做了前两题，给跪了
1996 Medium. The Number of Weak Characters in the Game
一个tricky的排序
class Solution {
public:
int numberOfWeakCharacters(vector<vector<int>>& properties) {
auto comp = [](const vector<int>& p1, const vector<int>& p2){
return p1[0] == p2[0] ? p1[1] > p2[1] : p1[0] < p2[0];
};
sort(properties.begin(), properties.end(), comp);
int ans = 0, maxSecond = INT_MIN, n = properties.size();
for(int i = n - 1; i >= 0; i--){
if(properties[i][1] < maxSecond){
ans++;
}
maxSecond = max(maxSecond, properties[i][1]);
}
return ans;
}
};
1997 Medium. First Day Where You Have Been in All the Rooms
1998 Hard. GCD Sort of an Array
Weekly Contest 258
2021.09.12
日常做两题
2002 Medium. Maximum Product of the Length of Two Palindromic Subsequences
2003 Hard. Smallest Missing Genetic Value in Each Subtree
Weekly Contest 261
2021.10.03
做了两题
2029 Medium. Stone Game IX
2030 Hard. Smallest K-Length Subsequence With Occurrences of a Letter
Weekly Contest 262
2021.10.10
2033 Medium. Minimum Operations to Make a Uni-Value Grid
将所有的数字变成中位数
2034 Medium. Stock Price Fluctuation
map+multiset
2035 Hard. Partition Array Into Two Arrays to Minimize Sum Difference
2n的数组分成2个长度为n的数组，求两个数组差的最小值
Weekly Contest 264
2021.10.24 程序员节
2048 Medium. Next Greater Numerically Balanced Number
brute force
2049 Medium. Count Nodes With the Highest Score
2050 Hard. Parallel Courses III
Weekly Contest 266
2021.11.09
第三题是道经典二分。
2063 Medium. Vowels of All Substrings
这道题看lee得解答是茅塞顿开
long long countVowels(string s) {
long res = 0, n = s.size();
for (int i = 0; i < n; ++i)
if (string("aeiou").find(s[i]) != string::npos)
res += (i + 1) * (n - i);
return res;
}
2065 Hard. Maximum Path Quality of a Graph
Weekly Contest 269
2021.11.28
2090 Medium. K Radius Subarray Averages
滑动窗口
2091 Medium. Removing Minimum and Maximum From Array
strait forward
2092 Hard. Find All People With Secret
Weekly Contest 270
2021.12.05
2096 Medium. Step-By-Step Directions From a Binary Tree Node to Another
找LCA。 看到了天才般的解法
- Build directions for both start and destination from the root.
Say we get "LLRRL" and "LRR". - Remove common prefix path.
We remove "L", and now start direction is "LRRL", and destination - "RR" - Replace all steps in the start direction to "U" and add destination direction.
The result is "UUUURR".
bool find(TreeNode* n, int val, string &path) {
if (n->val == val)
return true;
if (n->left && find(n->left, val, path))
path.push_back('L');
else if (n->right && find(n->right, val, path))
path.push_back('R');
return !path.empty();
}
string getDirections(TreeNode* root, int startValue, int destValue) {
string s_p, d_p;
find(root, startValue, s_p);
find(root, destValue, d_p);
while (!s_p.empty() && !d_p.empty() && s_p.back() == d_p.back()) {
s_p.pop_back();
d_p.pop_back();
}
return string(s_p.size(), 'U') + string(rbegin(d_p), rend(d_p));
}
2097 Hard. Valid Arrangement of Pairs
Weekly Contest 271
2021.12.12
2104 Medium. Sum of Subarray Ranges
lee提供了O(n)的解法
2106 Hard. Maximum Fruits Harvested After at Most K Steps
Weekly Contest 272
2021.12.19。环贸一日游。
2111 Hard. Minimum Operations to Make the Array K-Increasing
先拆分成k个子序列，再求最长单调递增子序列，op个数=n-LIS
Weekly Contest 273
2021.12.26
今天看了真爱至上
2120 Medium. Execution of All Suffix Instructions Staying in a Grid
brute force可以过。但有O(m)的答案。