weekly contest 195
2020.6.28
周赛刚开始，题还没看，leetcode竟然崩了！看来周赛越来越火了。
做了前两题。
1496. Path Crossing
给一个由上下左右构成的行动路径，判断按照此路径走会不会重复走一个点。
使用set保存走过的点即可
class Solution
{
public:
bool isPathCrossing(string path)
{
int x = 0, y = 0;
set<pair<int, int>> pos;
pos.insert({0, 0});
bool cross = false;
for (int i = 0; i < path.size(); i++)
{
if (path[i] == 'N')
y++;
else if (path[i] == 'E')
x--;
else if (path[i] == 'S')
y--;
else
x++;
if (pos.find({x, y}) != pos.end())
return true;
pos.insert({x, y});
}
return cross;
}
};
1497. Check If Array Pairs Are Divisible by k
给一串数字（偶数个），将其分成两两一组，判断是否能满足每一组的和都是k的倍数。
首先，对每个数字进行%k操作，如果是负数，再+k，这样，所有的数都被等价转换为[0,k-1]。对其进行技术，需要保证count(i)和count(k-i)个数相等，因为他们必须两两配对。count(0)的个数任意。当k为偶数的时候，需要考虑count(k/2)也是偶数，这样才能两两配对
class Solution
{
public:
bool canArrange(vector<int> &arr, int k)
{
vector<int> count(k, 0);
for (int i = 0; i < arr.size(); i++)
{
arr[i] %= k;
if (arr[i] < 0)
arr[i] += k;
count[arr[i]]++;
}
for (int i = 1; i <= k / 2; i++)
{
if (count[i] != count[k - i])
return false;
}
if (k % 2 == 0 && count[k / 2] % 2 != 0)
return false;
return true;
}
};
1498. Number of Subsequences That Satisfy the Given Sum Condition
对一个数组序列，求有多少个子序列，其最大值最小值之和，不超过target值。
这个题主要是要想到，对数组进行排序。因为是子序列，而且用的最大最小值，所以结果与原数组的顺序是没有关系的，排完序求min和max就方便许多。
第二，要利用有序数组的two sum思想，使用left、right两个指针，当两数相加大于target时，right--，否则，能构成满足条件的子序列，此时，只要保证最小值是left，其他所有的子序列都满足，共有pow(2,right-left)个。计算完之后left++，更新最小值
第三，利用pows[i] = pows[i - 1] * 2 % big快速求出pow的值
class Solution
{
public:
int numSubseq(vector<int> &nums, int target)
{
sort(nums.begin(), nums.end());
static constexpr int big = 1000000007;
vector<int> pows(nums.size(), 1);
for (int i = 1; i < nums.size(); i++)
pows[i] = pows[i - 1] * 2 % big;
int count = 0;
int left = 0, right = nums.size() - 1;
while (left <= right)
{
if (nums[left] + nums[right] > target)
{
right--;
}
else
{
count += pows[right - left];
count %= big;
left++;
}
}
return count;
}
};
1499. Max Value of Equation
依然没看题
weekly contest 196
2020.07.05
做了前两题。难顶啊
1502. Can Make Arithmetic Progression From Sequence
判断数组重排序后能否组成等差数列。排个序判断一下。
class Solution
{
public:
bool canMakeArithmeticProgression(vector<int> &arr)
{
sort(arr.begin(), arr.end());
int d = arr[1] - arr[0];
for (int i = 1; i < arr.size() - 1; i++)
{
if (arr[i + 1] - arr[i] != d)
return false;
}
return true;
}
};
1503. Last Moment Before All Ants Fall Out of a Plank
主要是别被题目迷惑了，其实两只蚂蚁碰撞后，可以理解为互换了身份，其实并没有什么影响。所以只需要找到离边最远的那只蚂蚁即可。
class Solution
{
public:
int getLastMoment(int n, vector<int> &left, vector<int> &right)
{
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int l = left.size() == 0 ? 0 : left.back();
int r = right.size() == 0 ? 0 : n - right[0];
return max(l, r);
}
};
1504. Count Submatrices With All Ones
求矩阵的所有全1子矩阵个数
以[i][j]作为矩阵的右下角，dp[i][j]表示从[i][j]起往上数，有多少个1.用动态规划很容易求得。
得到这个数后，再考虑将1*dp[i][j]的矩阵往左，求出min(minv, dp[i][k]); 即能得到更"宽"的全1矩阵个数
class Solution
{
public:
int numSubmat(vector<vector<int>> &mat)
{
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (mat[i][j] == 0)
continue;
dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + 1;
int minv = dp[i][j];
for (int k = j; k >= 0; k--)
{
minv = min(minv, dp[i][k]);
ret += minv;
}
}
}
return ret;
}
};
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits
给一个由数字组成的string，和整数K。在K次交换相邻两个数字后，能得到的最小数是多少
weekly contest 197
2020.7.12
做了前三题，最后一题参考了python版本的代码，可惜没有来得及做出来。
1512. Number of Good Pairs
class Solution
{
public:
int numIdenticalPairs(vector<int> &nums)
{
unordered_map<int, int> count;
for (int i = 0; i < nums.size(); i++)
count[nums[i]]++;
int ret = 0;
for (auto it = count.begin(); it != count.end(); it++)
{
ret += it->second * (it->second - 1) / 2;
}
return ret;
}
};
1513. Number of Substrings With Only 1s
求01字符串有多少个全1子串。
先利用dp计算出所有长为n的全1串有多少字串，再找到字符串中的所有最长全1串
从discussion中抄了个nb的代码
int numSub(string s)
{
int res = 0, count = 0, mod = 1e9 + 7;
for (char c : s)
{
count = c == '1' ? count + 1 : 0;
res = (res + count) % mod;
}
return res;
}
1514. Path with Maximum Probability
一开始想着用类似A-star算法进行求解，但发现排序的操作太耗时了，改用priority_queue能过。看了评论发现可以用vector<double>来记录概率，并记录该点是否需要访问，非常巧妙
class Solution
{
public:
double maxProbability(int n, vector<vector<int>> &edges, vector<double> &succProb, int start, int end)
{
//将参数数据进行转换。
vector<vector<pair<int, double>>> myedge(n);
for (int i = 0; i < edges.size(); i++)
{
myedge[edges[i][0]].push_back({edges[i][1], succProb[i]});
myedge[edges[i][1]].push_back({edges[i][0], succProb[i]});
}
//利用一个vector存储所有点当前的最大概率。只有当求出来的概率比当前概率大时，才去访问对应的路径
vector<double> probs(n, 0);
probs[start] = 1.0;
vector<int> nodes;
nodes.push_back(start);
while (!nodes.empty())
{
vector<int> new_nodes;
for (auto e : nodes) //遍历当前的所有点，求出到达的下一个点的概率
{
for (int i = 0; i < myedge[e].size(); i++)
{
//仅当新概率比原概率高的时候，更新概率，并继续遍历。
if (probs[e] * myedge[e][i].second > probs[myedge[e][i].first])
{
probs[myedge[e][i].first] = probs[e] * myedge[e][i].second;
new_nodes.push_back(myedge[e][i].first);
}
}
}
swap(nodes, new_nodes);
}
return probs[end];
}
};
1515. Best Position for a Service Centre
给出平面内很多个二维点(x,y)，找到一个点，使其到所有这些点的距离之和最小。基准点选择所有点的算术中心点。
竟然考了道数学题。利用机器学习中的梯度下降法求解。
class Solution
{
public:
double dist(vector<double> &p1, vector<int> &p2)
{
return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));
}
double cost(vector<double> &point, vector<vector<int>> &positions)
{
double sum = 0;
for (int i = 0; i < positions.size(); i++)
{
sum += dist(point, positions[i]);
}
return sum;
}
pair<double, double> gradient(vector<double> &point, vector<vector<int>> &positions)
{
double dx = 0, dy = 0;
for (int i = 0; i < positions.size(); i++)
{
if (dist(point, positions[i]) != 0)
{
dx += (point[0] - positions[i][0]) / dist(point, positions[i]);
dy += (point[1] - positions[i][1]) / dist(point, positions[i]);
}
}
double s = sqrt(dx * dx + dy * dy);
dx /= s;
dy /= s;
return {dx, dy};
}
double getMinDistSum(vector<vector<int>> &positions)
{
double rate = 0.01;
int step = 100000;
vector<double> point(2, 0);
for (int i = 0; i < positions.size(); i++)
{
point[0] += positions[i][0];
point[1] += positions[i][1];
}
point[0] /= positions.size();
point[1] /= positions.size();
point.push_back(positions[0][0] + 1e-8);
point.push_back(positions[0][1] + 1e-8);
double epsilon = 1e-7;
for (int i = 0; i < step; i++)
{
double cost_ori = cost(point, positions);
auto g = gradient(point, positions);
vector<double> newpoint;
newpoint.push_back(point[0] - rate * g.first);
newpoint.push_back(point[1] - rate * g.second);
double cost_new = cost(newpoint, positions);
if (cost_ori - cost_new > epsilon)
{
point = newpoint;
}
else if (cost_new - cost_ori > epsilon)
rate *= 0.3;
else
break;
}
return cost(point, positions);
}
};
weekly contest 198
2020.07.19
这次的周赛也太难了...一小时就做出一道题,再加半小时应该还能再做出一题,我太菜了。
1518. Water Bottles
经典空瓶换饮料。
class Solution
{
public:
int numWaterBottles(int numBottles, int numExchange)
{
int ret = 0;
int empty = 0;
while (numBottles > 0 || empty >= numExchange)
{
ret += numBottles;
empty += numBottles;
numBottles = empty / numExchange;
empty %= numExchange;
}
return ret;
}
};
1519. Number of Nodes in the Sub-Tree With the Same Label
给一个树，求以每个结点作为根节点的子树，label出现次数。dfs
这道题卡常..可以说在leetcode非常少见。优化了以后才过的。再不行就把vector换成指针。
class Solution
{
public:
vector<int> countSubTrees(int n, vector<vector<int>> &edges, string labels)
{
vector<vector<int>> map(n);
for (int i = 0; i < edges.size(); i++)
{
map[edges[i][0]].push_back(edges[i][1]);
map[edges[i][1]].push_back(edges[i][0]);
}
vector<int> ret(n, 0);
helper(0, map, labels, ret);
return ret;
}
vector<int> helper(int node, vector<vector<int>> &edge, string &labels, vector<int> &ret)
{
vector<int> r(26, 0);
ret[node]++;
r[labels[node] - 'a']++;
auto nextnode = edge[node];
for (int i = 0; i < nextnode.size(); i++)
{
if (ret[nextnode[i]] != 0)
continue;
auto count = helper(nextnode[i], edge, labels, ret);
for (int i = 0; i < 26; i++)
{
r[i] += count[i];
}
}
ret[node] = r[labels[node] - 'a'];
return r;
}
};
1520. Maximum Number of Non-Overlapping Substrings
后面两题都没看
1521. Find a Value of a Mysterious Function Closest to Target
weekly contest 199
2020.07.26
今天出去玩啦，并没有参加，题目是晚上补的。前两天很简单，第三题有点难，看评论说第四题特别难，我选择不看hhh
1528. Shuffle String
class Solution
{
public:
string restoreString(string s, vector<int> &indices)
{
string rtn = s;
for (int i = 0; i < indices.size(); i++)
{
rtn[indices[i]] = s[i];
}
return rtn;
}
};
1529. Bulb Switcher IV
灯泡亮灭问题。其实逻辑很简单，判断相邻的两个灯是否初始状态相同即可。用pre保存上一个灯的状态，一开始为默认的状态‘0’
class Solution
{
public:
int minFlips(string target)
{
int rtn = 0;
char pre = '0';
for (int i = 0; i < target.size(); i++)
{
if (target[i] != pre)
{
rtn++;
pre = target[i];
}
}
return rtn;
}
};
1530. Number of Good Leaf Nodes Pairs
判断树的叶节点之间的距离，有多少对小于distance。
dfs吧，不太会。
1531. String Compression II
weekly contest 200
2020.08.02
这次的周赛题目难度相对简单一点。1小时做了3题
1534. Count Good Triplets
brute force
class Solution
{
public:
int countGoodTriplets(vector<int> &arr, int a, int b, int c)
{
int count = 0;
for (int i = 0; i < arr.size() - 2; i++)
{
for (int j = i + 1; j < arr.size() - 1; j++)
{
if (fabs(arr[i] - arr[j]) > a)
continue;
for (int k = j + 1; k < arr.size(); k++)
{
if (fabs(arr[i] - arr[k]) > c || fabs(arr[j] - arr[k]) > b)
continue;
count++;
}
}
}
return count;
}
};
1535. Find the Winner of an Array Game
主要是保存head（当前最大值）
class Solution
{
public:
int getWinner(vector<int> &arr, int k)
{
int head = arr[0];
int count = 0;
for (int i = 1; i < arr.size(); i++)
{
if (arr[i] > head)
{
head = arr[i];
count = 0;
}
if (++count == k)
return head;
}
return head;
}
};
1536. Minimum Swaps to Arrange a Binary Grid
这道题其实没那么复杂。先统计每行有多少个连续的0（从右往左）
根据贪心策略，第i行需要n-i-1个0，那么找到最近能满足的那一行，进行交换（注意交换是相邻的，所以有一个移动操作）。如果不满足，则返回-1
class Solution
{
public:
int minSwaps(vector<vector<int>> &grid)
{
int n = grid.size();
vector<int> rowZeroCount(n, 0);
for (int i = 0; i < n; i++)
{
for (int j = n - 1; j >= 1; j--)
{
if (grid[i][j] == 0)
rowZeroCount[i]++;
else
break;
}
}
int rtn = 0;
for (int k = n - 1; k >= 1; k--)
{
int s = n - k - 1;
int i = s;
for (; i < n; i++)
{
if (rowZeroCount[i] >= k)
{
rtn += i - s;
for (int x = i; x > s; x--)
{
rowZeroCount[x] = rowZeroCount[x - 1];
}
break;
}
}
if (i == n)
return -1;
}
return rtn;
}
};
1537. Get the Maximum Score
看了眼题，看解答也不是很复杂的样子，留个坑以后填吧
weekly contest 201
2020.08.09
今天出去玩了，没参赛。题目应该只会做两题。
1544. Make The String Great
brute-force。主要是要注意大写加小写和小写加大写都算vice-versa
class Solution
{
public:
string makeGood(string s, int sz = 0)
{
while (sz != s.size())
{
sz = s.size();
for (int i = 0; i + 1 < s.size(); ++i)
if (s[i] != s[i + 1] && tolower(s[i]) == tolower(s[i + 1]))
{
s = s.substr(0, i) + s.substr(i + 2);
}
}
return s;
}
};
1545. Find Kth Bit in Nth Binary String
用递归解。注意是reverse+invert
class Solution
{
public:
char findKthBit(int n, int k)
{
if (n == 1)
return '0';
int len = (1 << n) - 1;
if (k == len / 2 + 1)
{
return '1';
}
else if (k > len / 2 + 1)
{
return findKthBit(n - 1, len - k + 1) == '1' ? '0' : '1';
}
else
return findKthBit(n - 1, k);
}
};
1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
求最多能有多少个不重叠的子数组，和为target
dp？
1547. Minimum Cost to Cut a Stick
weekly contest 202
2020.08.16
做了前两题，很简单。后两题顶不住
1550. Three Consecutive Odds(https://leetcode.com/problems/three-consecutive-odds)
class Solution
{
public:
bool threeConsecutiveOdds(vector<int> &arr)
{
if (arr.size() < 3)
return false;
for (int i = 0; i < arr.size() - 2; i++)
{
if ((arr[i] % 2 == 1) && (arr[i + 1] % 2 == 1) && (arr[i + 2] % 2 == 1))
return true;
}
return false;
}
};
1551. Minimum Operations to Make Array Equal(https://leetcode.com/problems/minimum-operations-to-make-array-equal/)
class Solution
{
public:
int minOperations(int n)
{
return (n % 2 == 0) ? (n / 2) * (n / 2) : (n / 2) * (n / 2 + 1);
}
};
```cpp
### 1552. Magnetic Force Between Two Balls(https://leetcode.com/problems/magnetic-force-between-two-balls/)
给定n个位置，和m个球，如何放置能够使得球与球之间的距离最小值最大？
二分法?
### 1553. Minimum Number of Days to Eat N Oranges(https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/)
n个橘子，每天有三种吃法：
* 吃1个
* n%3==0,吃掉2/3
* n%2==0,吃掉1/2
最少需要多少天能吃完？
用unordered_map作为dp
```cpp
class Solution
{
public:
unordered_map<int, int> dp;
int minDays(int n)
{
if (n <= 1)
return n;
if (dp.count(n) == 0)
dp[n] = 1 + min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3));
return dp[n];
}
};
weekly contest 203
2020.08.23
昨天加班到12点。今天起来头晕晕的，做了前两题。都比较简单
1560. Most Visited Sector in a Circular Track
第一题的难点主要在于读懂题目。只要关心头尾两个数就行了。
哈哈哈哈这道题全是👎，我也情不自禁点了一个
class Solution
{
public:
vector<int> mostVisited(int n, vector<int> &rounds)
{
int start = rounds[0];
int end = rounds.back();
vector<int> ret;
if (end >= start)
{
for (int i = start; i <= end; i++)
ret.push_back(i);
}
else if (end < start)
{
for (int i = 1; i <= end; i++)
ret.push_back(i);
for (int i = start; i <= n; i++)
ret.push_back(i);
}
return ret;
}
};
1561. Maximum Number of Coins You Can Get
抓硬币问题。很简单，排个序，去掉1/3个最小的，然后隔两个取一个就行了。记得leetcode有类似的题。说实话这道题注水很严重，不配medium难度。
class Solution
{
public:
int maxCoins(vector<int> &piles)
{
sort(piles.begin(), piles.end());
int n = piles.size();
int k = n / 3;
int rtn = 0;
for (int i = k; i < n; i += 2)
rtn += piles[i];
return rtn;
}
};
1562. Find Latest Group of Size M
难。
1563. Stone Game V
难。
weekly contest 204
2020.8.30
就做了一题。我也太菜了吧。
1566. Detect Pattern of Length M Repeated K or More Times
brute-force即可
class Solution
{
public:
bool containsPattern(vector<int> &arr, int m, int k)
{
for (int i = 0; i < arr.size(); i++)
{
bool flag = true;
for (int n = 0; n < m; n++)
{
int p = i;
for (int j = 1; j < k; j++)
{
p += m;
if ((p + n) >= arr.size() || arr[i + n] != arr[p + n])
{
flag = false;
break;
}
}
}
if (flag)
return true;
}
return false;
}
};
1567. Maximum Length of Subarray With Positive Product
给一个int数组，求最长子数组，其乘积为正数。
1568. Minimum Number of Days to Disconnect Island
1569. Number of Ways to Reorder Array to Get Same BST
weekly contest 205
2020.09.06
做了前三题。比较简单
1576. Replace All ?'s to Avoid Consecutive Repeating Characters
一道让我缓缓打出？并连答案也不想放的题
1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers
每次看完大佬写的代码再看看我写的辣鸡代码，都会怀疑人生
class Solution
{
public:
int cal(vector<int> &nums1, unordered_map<int, int> &counter2)
{
int ret = 0;
unordered_map<int, int> dp;
for (int i = 0; i < nums1.size(); i++)
{
if (dp.find(nums1[i]) != dp.end())
{
ret += dp[nums1[i]];
}
else
{
long long mul = (long long)nums1[i] * nums1[i];
for (int m = 1; m <= nums1[i]; m++)
{
if (mul % m == 0)
{
if (counter2.find(m) != counter2.end() && counter2.find(mul / m) != counter2.end())
{
if (m == mul / m)
{
ret += counter2[m] * (counter2[m] - 1) / 2;
}
else
ret += counter2[m] * counter2[mul / m];
}
}
}
}
}
return ret;
}
int numTriplets(vector<int> &nums1, vector<int> &nums2)
{
unordered_map<int, int> counter1, counter2;
for (int i = 0; i < nums1.size(); i++)
counter1[nums1[i]]++;
for (int i = 0; i < nums2.size(); i++)
counter2[nums2[i]]++;
return cal(nums1, counter2) + cal(nums2, counter1);
}
};
1578. Minimum Deletion Cost to Avoid Repeating Letters
太辣鸡了，没法看。什么时候能一遍写出优美的代码啊
class Solution
{
public:
int del(int start, int end, vector<int> &cost)
{
int maxval = cost[start];
int sum = 0;
for (int i = start; i < end; i++)
{
maxval = max(cost[i], maxval);
sum += cost[i];
}
return sum - maxval;
}
int minCost(string s, vector<int> &cost)
{
int ret = 0;
for (int i = 0; i < s.length();)
{
int j = i + 1;
for (; j < s.length();)
{
if (s[i] == s[j])
j++;
else
{
ret += del(i, j, cost);
break;
}
}
if (j == s.length())
{
ret += del(i, j, cost);
}
i = j;
}
return ret;
}
};
1579. Remove Max Number of Edges to Keep Graph Fully Traversable
weekly contest 206
2020.09.13
做了两题
1582. Special Positions in a Binary Matrix
brute-force
class Solution
{
public:
int numSpecial(vector<vector<int>> &mat)
{
int m = mat.size();
int n = mat[0].size();
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (mat[i][j] == 1)
{
bool flag = true;
for (int k = 0; k < m; k++)
{
if (k != i && mat[k][j] == 1)
{
flag = false;
break;
}
}
for (int k = 0; k < n; k++)
{
if (k != j && mat[i][k] == 1)
{
flag = false;
break;
}
}
if (flag)
ret++;
}
}
}
return ret;
}
};
1583. Count Unhappy Friends
傻逼题目。。
1584. Min Cost to Connect All Points
给一些二维点，求一个最小子树，使得连接的代价最小。两个点的代价是|x1-x2|+|y1-y2|
prime或者kruskal算法。但好像会TLE？
1585. Check If String Is Transformable With Substring Sort Operations
weekly contest 207
2020.09.20
做了前两题
1592. Rearrange Spaces Between Words
主要是要注意只有一个单词的情况
class Solution
{
public:
string reorderSpaces(string text)
{
vector<string> words;
std::istringstream is(text);
do
{
std::string substr;
is >> substr;
if (substr != "")
words.push_back(substr);
} while (is);
int spaceCount = 0;
for (int i = 0; i < text.length(); i++)
if (text[i] == ' ')
spaceCount++;
if (words.size() == 1)
{
string ret = words[0];
for (int j = 0; j < spaceCount; j++)
ret += ' ';
return ret;
}
int x = spaceCount / (words.size() - 1);
int y = spaceCount % (words.size() - 1);
string ret = "";
for (int i = 0; i < words.size() - 1; i++)
{
ret += words[i];
for (int j = 0; j < x; j++)
ret += ' ';
}
ret += words.back();
for (int j = 0; j < y; j++)
ret += ' ';
return ret;
}
};
1593. Split a String Into the Max Number of Unique Substrings
把一个字符串分成一定数量的子串，使得每个子串各不相同，问最多能分成多少个子串。dfs
class Solution
{
public:
int maxsize;
int helper(string &str, set<string> &strs)
{
if (str == "")
{
int n = strs.size();
maxsize = max(n, maxsize);
return 0;
}
for (int i = 1; i <= str.length(); i++)
{
string tempstr = str.substr(0, i);
if (strs.count(tempstr))
continue;
auto it = strs.insert(tempstr);
auto xx = str.substr(i);
helper(xx, strs);
strs.erase(tempstr);
}
return 0;
}
int maxUniqueSplit(string s)
{
maxsize = 0;
set<string> myset;
helper(s, myset);
return maxsize;
}
};
1594. Maximum Non Negative Product in a Matrix
一个矩形有正有负，求从左上到右下按一定的路径走能获得的最大乘积。（只能往下或者往右走） dp
1595. Minimum Cost to Connect Two Groups of Points
weekly contest 208
2020.09.30
因为国庆调休，并没有参加。今天放假了，补一下。
1598. Crawler Log Folder
class Solution
{
public:
int minOperations(vector<string> &logs)
{
int ret = 0;
for (const auto &str : logs)
{
if (str == "./")
continue;
else if (str == "../")
{
if (ret > 0)
ret--;
}
else
ret++;
}
return ret;
}
};
1599. Maximum Profit of Operating a Centennial Wheel
class Solution {
public:
int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
if(boardingCost*4 <=runningCost)
return -1;
int waiting = 0;
int times = 0;
int maxValue = 0;
int value = 0;
int ret = -1;
int i = 0;
while(i<customers.size()|| waiting!=0)
{
if(i<customers.size())
waiting+=customers[i++];
int board = waiting>4?4:waiting;
waiting-=board;
value += board*boardingCost-runningCost;
if(value>maxValue)
{
maxValue= value;
ret = times+1;
}
times++;
}
return ret;
}
};
1600. Throne Inheritance
1601. Maximum Number of Achievable Transfer Requests
weekly contest 209
2020.10.04
以为今天周六，就错过了。。定了个闹钟，以防下次又忘了
1608. Special Array With X Elements Greater Than or Equal X
求x，使得nums中大于等于x的数的个数为x
先排序，然后用lower_bound，求出大于等于x的数的个数。
class Solution
{
public:
int specialArray(vector<int> &nums)
{
sort(nums.begin(), nums.end());
for (int i = 0; i <= nums.size(); i++)
{
auto it = lower_bound(nums.begin(), nums.end(), i);
if (nums.end() - it == i)
return i;
}
return -1;
}
};
1609. Even Odd Tree
判断是否是奇偶二叉树：奇数层严格递减，偶数层严格递增。奇数层都是偶数，偶数层都是奇数。
dfs
class Solution
{
public:
unordered_map<int, int> m;
bool dfs(TreeNode *root, int level)
{
if (root == NULL)
return true;
int flag_level = level % 2;
int flag_val = root->val % 2;
if (!flag_level && !flag_val || flag_level && flag_val)
{
return false;
}
if (m.find(level) != m.end())
{
if (!flag_level && m[level] >= root->val || flag_level && m[level] <= root->val)
return false;
}
m[level] = root->val;
return dfs(root->left, level + 1) && dfs(root->right, level + 1);
}
bool isEvenOddTree(TreeNode *root)
{
return dfs(root, 0);
}
};
1610. Maximum Number of Visible Points
1611. Minimum One Bit Operations to Make Integers Zero
weekly contest 210
2020.10.11
做了3题，都比较常规，第四题没时间看。第三题需要优化
1614. Maximum Nesting Depth of the Parentheses(https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/)
题目哔哔了一大堆，结果就是求个括号最大深度。。
class Solution
{
public:
int maxDepth(string s)
{
int depth = 0;
int ret = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(')
{
depth++;
ret = max(ret, depth);
}
else if (s[i] == ')')
depth--;
}
return ret;
}
};
1615. Maximal Network Rank(https://leetcode.com/problems/maximal-network-rank/)
没注意题目给的n很小，所以只需要O(n^2)遍历就可以了。
class Solution
{
public:
int maximalNetworkRank(int n, vector<vector<int>> &roads)
{
vector<int> cnt(n);
size_t res = 0;
set<pair<int, int>> adjacent;
for (auto r : roads)
{
++cnt[r[0]];
++cnt[r[1]];
adjacent.insert({min(r[0], r[1]), max(r[0], r[1])});
}
for (auto i = 0; i < n; ++i)
for (auto j = i + 1; j < n; ++j)
res = max(res, cnt[i] + cnt[j] - adjacent.count({i, j}));
return res;
}
};
1616. Split Two Strings to Make Palindrome(https://leetcode.com/problems/split-two-strings-to-make-palindrome/)
判断a，b两个字符串能否分割后构成回文序列。求两个穿中间的部分是否是回文序列即可。
class Solution
{
public:
bool isPa(string &s, int i, int j)
{
for (; i < j; ++i, --j)
if (s[i] != s[j])
return false;
return true;
}
bool check(string &a, string &b)
{
for (int i = 0, j = a.size() - 1; i < j; ++i, --j)
if (a[i] != b[j])
return isPa(a, i, j) || isPa(b, i, j);
return true;
}
bool checkPalindromeFormation(string a, string b)
{
return check(a, b) || check(b, a);
}
};
1617. Count Subtrees With Max Distance Between Cities
Weekly Contest 211
2020.10.18
有点难啊，只会做第一题。这周好累，今天补觉
1624. Largest Substring Between Two Equal Characters
求字符串中相同两个字母最大间距
class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
int ret = -1;
vector<int> last(26,-1);
for(int i =0;i<s.length();i++)
{
if(last[s[i]-'a'] == -1)
last[s[i]-'a'] = i;
else
{
ret = max(ret,i-last[s[i]-'a']-1);
}
}
return ret;
}
};
1625. Lexicographically Smallest String After Applying Operations
dfs 暴力求解。
1626. Best Team With No Conflicts
组建一个球队，每个队员有能力值score，年龄age，选则出一个球队使sum(score)最大，且年龄大的球员score不低于年龄小的球员
dp
class Solution
{
public:
int bestTeamScore(vector<int> &scores, vector<int> &ages)
{
vector<pair<int, int>> players;
int n = scores.size();
for (int i = 0; i < n; i++)
{
players.push_back({ages[i], scores[i]});
}
sort(players.begin(), players.end(), greater<>());
int ans = 0;
vector<int> dp(n + 1);
dp[0] = 0;
for (int i = 0; i < n; i++)
{
int score = players[i].second;
dp[i] = score;
for (int j = 0; j < i; j++)
{
if (players[j].second >= players[i].second)
{ // age of j is certainly >= i, so only important part to check
// before we add i and j in the same team is the score.
dp[i] = max(dp[i], dp[j] + score);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};
1627. Graph Connectivity With Threshold
Weekly Contest 212
2020.10.25 做了两题，第三题dfs超时
1629. Slowest Key
class Solution
{
public:
char slowestKey(vector<int>& releaseTimes, string keysPressed)
{
vector<int> diff(releaseTimes.size());
diff[0] = releaseTimes[0];
int maxvalue = diff[0];
for (int i = 1; i < releaseTimes.size(); i++)
{
diff[i] = releaseTimes[i] - releaseTimes[i - 1];
maxvalue = max(maxvalue, diff[i]);
}
char retch = 'a';
for (int i = 0; i < diff.size(); i++)
{
if (diff[i] == maxvalue && keysPressed[i] > retch)
retch = keysPressed[i];
}
return retch;
}
};
1630. Arithmetic Subarrays
判断是不是等差数列，brute force即可
class Solution
{
public:
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r)
{
vector<bool> ret(l.size(), true);
for (int i = 0; i < l.size(); i++)
{
vector<int> tmp(nums.begin() + l[i], nums.begin() + r[i] + 1);
sort(tmp.begin(), tmp.end());
if (tmp.size() < 2)
{
ret[i] = true;
continue;
}
int d = tmp[1] - tmp[0];
for (int j = 0; j + 1 < tmp.size(); j++)
{
if (tmp[j] + d != tmp[j + 1])
{
ret[i] = false;
break;
}
}
}
return ret;
}
};
1631. Path With Minimum Effort
1632. Rank Transform of a Matrix
weekly contest 213
2020.11.1
今天睡懒觉了，起来做了两题
1640. Check Array Formation Through Concatenation
brute-force就行。hashmap更好
class Solution
{
public:
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces)
{
for (auto& piece : pieces)
{
bool flag = false;
for (int i = 0; i < arr.size(); i++)
{
bool same = true;
for (int j = 0; j < piece.size(); j++)
{
if (i + j > arr.size() || arr[i + j] != piece[j])
{
same = false;
break;
}
}
flag = same;
if (flag)
break;
}
if (flag == false)
return false;
}
return true;
}
};
1641. Count Sorted Vowel Strings
动态规划
class Solution
{
public:
int countVowelStrings(int n)
{
vector<vector<int>> dp(n + 1, vector<int>(5, 1));
for (int i = 2; i <= n; i++)
{
int sum = 0;
for (int j = 0; j < 5; j++)
{
sum += dp[i - 1][j];
dp[i][j] = sum;
}
}
int sum = 0;
for (int j = 0; j < 5; j++)
{
sum += dp[n][j];
}
return sum;
}
};
1642. Furthest Building You Can Reach
1643. Kth Smallest Instructions
Weekly Contest 214
2020.11.8 做了前两题
1646. Get Maximum in Generated Array
class Solution
{
public:
int getMaximumGenerated(int n)
{
if (n <= 1)
return n;
vector<int> nums(n + 1);
nums[0] = 0;
nums[1] = 1;
for (int i = 2; i <= n; i++)
{
if (i % 2 == 0)
{
nums[i] = nums[i / 2];
}
else
{
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
}
int ret = 0;
for (int i = 0; i <= n; i++)
{
ret = max(ret, nums[i]);
}
return ret;
}
};
1647. Minimum Deletions to Make Character Frequencies Unique
代码好烂...
class Solution
{
public:
int minDeletions(string s)
{
vector<int> f(26, 0);
for (int i = 0; i < s.length(); i++)
{
f[s[i] - 'a']++;
}
sort(f.begin(), f.end());
set<int> visited;
int ret = 0;
for (int i = 0; i < f.size(); i++)
visited.insert(f[i]);
for (int i = 0; i < f.size() - 1; i++)
{
if (f[i] == 0)
continue;
if (f[i] == f[i + 1])
{
for (int j = f[i] - 1; j >= 0; j--)
{
if (j == 0)
{
ret += f[i];
continue;
}
if (!visited.count(j))
{
ret += f[i] - j;
visited.insert(j);
break;
}
}
}
}
return ret;
}
};
1648. Sell Diminishing-Valued Colored Balls
1649. Create Sorted Array through Instructions
weekly contest 215
做了第一题..题目也太难懂了
1656. Design an Ordered Stream
class OrderedStream
{
public:
int ptr;
vector<string> strs;
set<int> ids;
OrderedStream(int n)
{
ptr = 1;
strs.resize(n + 1);
}
vector<string> insert(int id, string value)
{
strs[id] = value;
vector<string> ret;
ids.insert(id);
if (ids.count(ptr) == 1)
{
for (int i = ptr; i < strs.size(); i++)
{
if (ids.count(i) == 1)
{
ret.push_back(strs[i]);
}
else
break;
}
ptr = ptr + ret.size();
}
return ret;
}
};
1657. Determine if Two Strings Are Close
1658. Minimum Operations to Reduce X to Zero
1659. Maximize Grid Happiness
weekly contest 216
2020.11.21 今天实在太困了，没有参加。
1662. Check If Two String Arrays are Equivalent
可能是上周的第一题太难了，这周是送分题
class Solution
{
public:
bool arrayStringsAreEqual(vector<string> &word1, vector<string> &word2)
{
string str1 = "";
string str2 = "";
for (auto &word : word1)
str1 += word;
for (auto &word : word2)
str2 += word;
return str1 == str2;
}
};
1663. Smallest String With A Given Numeric Value
经典写垃圾代码
class Solution
{
public:
string getSmallestString(int n, int k)
{
int remain = n;
int value = k;
string ret = "";
while (value - remain + 1 >= 26)
{
ret += "z";
value -= 26;
remain -= 1;
}
if (value > 0)
{
int v = (value - remain + 1) % 26;
value -= v;
if (v > 0)
ret += 'a' + v - 1;
}
remain--;
for (int i = 0; i < remain; i++)
ret += 'a';
reverse(ret.begin(), ret.end());
return ret;
}
};
1664. Ways to Make a Fair Array
1665. Minimum Initial Energy to Finish Tasks
weekly contest 217
2020.11.28 起晚了，做了第一题吃饭去了。
1672. Richest Customer Wealth
class Solution
{
public:
int maximumWealth(vector<vector<int>> &accounts)
{
int maxsum = 0;
for (int i = 0; i < accounts.size(); i++)
{
int temp = 0;
for (int money : accounts[i])
temp += money;
maxsum = max(temp, maxsum);
}
return maxsum;
}
};
1673. Find the Most Competitive Subsequence
1674. Minimum Moves to Make Array Complementary
1675. Minimize Deviation in Array
weekly contest 218
2020.12.06 今天不想学习。每天都不想学习
1678. Goal Parser Interpretation
1679. Max Number of K-Sum Pairs
1680. Concatenation of Consecutive Binary Numbers
1681. Minimum Incompatibility
weekly contest 219
2020.12.13 今天睡了懒觉
1688. Count of Matches in Tournament
n个队伍打比赛，两两比赛，每次淘汰败者，决出冠军一共要打多少场比赛？
因为要淘汰n-1个队，所以打n-1场。
1689. Partitioning Into Minimum Number Of Deci-Binary Numbers
class Solution
{
public:
int minPartitions(string n)
{
char maxch = '0';
for (int i = 0; i < n.size(); i++)
{
maxch = max(n[i], maxch);
}
return maxch - '0';
}
};
1690. Stone Game VII
1691. Maximum Height by Stacking Cuboids
weekly contest 220
2020.12.19 床实在是太粘人了
1694. Reformat Phone Number
class Solution
{
public:
string reformatNumber(string number)
{
string v;
for (int i = 0; i < number.size(); i++)
{
if (number[i] >= '0' && number[i] <= '9')
{
v += number[i];
}
}
int n = v.size();
string ret;
int i = 0;
while (n > 4)
{
ret += v.substr(i, 3) + "-";
i += 3;
n -= 3;
}
if (n == 4)
{
ret += v.substr(i, 2) + "-" + v.substr(i + 2, 2);
}
else
{
ret += v.substr(i, n);
}
return ret;
}
};
[1695. Maximum Erasure Value
](https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/)
求不重复的连续字串，sum最大
class Solution
{
public:
int maximumUniqueSubarray(vector<int> &nums)
{
int start = 0;
int end = 0;
set<int> temp;
int maxret = 0;
int sum = 0;
while (end < nums.size())
{
while (temp.count(nums[end]))
{
temp.erase(nums[start]);
sum -= nums[start];
start++;
}
sum += nums[end];
temp.insert(nums[end]);
end++;
if (maxret < sum)
maxret = sum;
}
return maxret;
}
};
1696. Jump Game VI
1697. Checking Existence of Edge Length Limited Paths
weekly contest 221
1704. Determine if String Halves Are Alike
没啥花头
class Solution
{
public:
bool halvesAreAlike(string s)
{
set<char> chs = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int count1 = 0;
int count2 = 0;
for (int i = 0; i < s.length() / 2; i++)
{
if (chs.count(s[i]))
count1++;
}
for (int i = s.length() / 2; i < s.length(); i++)
{
if (chs.count(s[i]))
count2++;
}
return count1 == count2;
}
};