力扣第301场周赛
一.装满杯子需要的最短总时长
1.原题链接：
2.解题思路：
先将冷水、温水、热水的杯子数量从小到大排序，目标是匹配尽量多不同的饮料。
若amount[0] + amount[1] <= amount[2], 则答案就是amount[2]；
若amount[0] + amount[1] > amount[2]，考虑超出的部分t = amount[0] + amount[1] - amount[2]
若t为偶数，我们可以先把amount[0]和amount[1]互相匹配t/2次进行“内部消化”，操作过后有amount[0] + amount[1] = amount[2]，此时用一个amount[2]和一个amount[0]或amount[1]匹配即可，则答案为t / 2 + amount[2]；
若t为奇数，我们可以先把amount[0]和amount[1]互相匹配(t - 1) / 2次进行“内部消化”，操作过后有amount[0] + amount[1] - 1= amount[2]，此时每次用一个amount[2]和一个amount[0]或amount[1]匹配，剩下一杯无法匹配，则答案为（t -1）/ 2 + amount[2] + 1；
综上当t为偶数或奇数得到的结果表达式，可以合并为（t + 1）/ 2 + amount[2]；
3.参考代码：
class Solution {
public:
int fillCups(vector<int>& amount) {
sort(amount.begin(), amount.end());
if(amount[0] + amount[1] <= amount[2])return amount[2];
else
{
int t = amount[0] + amount[1] - amount[2];
return (t + 1) / 2 + amount[2];
}
}
};
二.无限集中的最小数字
1.原题链接：
2.解题思路：
1.使用set存储已经删除的元素；
2.popSmallest：i从1开始判断，如果i不在set 中，就返回 i；
3.addBack：从st中删除num即可；
3.参考代码：
class SmallestInfiniteSet {
public:
unordered_set<int> st;
SmallestInfiniteSet() {
}
int popSmallest() {
for (int i = 1; ; i++) {
if (st.count(i) == 0) {
st.insert(i);
return i;
}
}
return 0;
}
void addBack(int num) {
st.erase(num);
}
};
三.移动片段得到字符串
1.原题链接：
2.解题思路：
1.去掉'-'后的剩余字符应该是相同的，若不同直接返回false ;
2.然后用双指针遍历start[i]和target[j]
若当前start[i]为L并且 i < j，由于L无法向右移动，则返回false；
若当前start[i]为R并且 i > j，由于R无法向左移动，则返回false；
3.参考代码：
class Solution {
public:
bool canChange(string start, string target) {
int i , j = 0;
int n = start.size();
string s1, s2;
for(int i = 0; i < n; i++)
{
if(start[i] != '_')s1 += start[i];
}
for(int j = 0; j < n; j++)
{
if(target[j] != '_') s2 += target[j];
}
if(s1 != s2) return false;
for( int i = 0; i < n; i++){
if(start[i] == '_') continue;
while(target[j] == '_')j++;
if(start[i] == 'R' && i > j || start[i] == 'L' && i < j)return false;
j++;
}
return true;
}
};
力扣第82场双周赛
一.计算布尔二叉树的值
1.原题链接：
2.解题思路：
1.如果当前节点没有孩子，说明是叶子节点，返回自己的值即可；
2.如果有孩子，递归调用evaluateTree函数获得左右孩子的布尔值，然后根据自身的val值，来决定对这两个布尔值进行或运算还是与运算。返回运算的结果即可。
3.参考代码：
class Solution {
public:
bool evaluateTree(TreeNode* root) {
if(root -> left){
bool l = evaluateTree(root -> left);
bool r = evaluateTree(root -> right);
if(root -> val == 2)return l | r;
else return l & r;
}
else{
return root -> val;
}
}
};
二.坐上公交的最晚时间
1.原题链接：
2.解题思路：
遍历每辆公交车，处理可以上车的乘客；
如果要上车，需要在当前乘客前面时刻上车，更新上车时间；
如果可以在最后发车时间上车，更新为发车时刻；
遍历每辆公交车，更新最大出发时刻；
3.参考代码：
class Solution {
public:
int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
set<int> st;
for (auto &p :passengers) {
st.insert(p);
}
sort(buses.begin(), buses.end());
auto it = st.begin();
int ans = 0;
for (auto &bus : buses) {
int cnt = 0;
while (cnt++ < capacity && it != st.end() && *it <= bus) {
/* 更新为当前可上车乘客的时间-1 */
if (it == st.begin() || *prev(it) != *it - 1) {
ans = *it - 1;
}
it++;
}
/* 更新为发车时刻 */
if (cnt <= capacity && st.count(bus) == 0) {
ans = bus;
}
}
return ans;
}
};
AcWing第59场周赛
一.数组操作
1.原题链接：
2.解题思路：
1.累加数组a[N]的所有元素，得到元素和s；
2.用b[N]记录a[N]的前缀和，并从小到大排序，则b[0]即为a[N]的最小前缀和
特别注意：按题目要求，当a[N]的所有元素均大于0时，则a[N]的最小前缀和为0
3.参考代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int a[N],b[N],n,s = 0;
int main()
{
cin >> n;
for(int i = 0; i < N; i++)
{ cin >> a[i],s += a[i];}
//求数组a[N]的前缀和，并存储于数组b[N]中
for(int i = 0; i < N; i++)
{
if(i == 0)b[i] = a[i];
else{
b[i] = b[i - 1] + a[i];
}
}
for(int i = 0 ; i < N;i ++)
{if(a[i] > 0)b[i] = 0;
else sort(b, b + N);
}
cout << s - b[0] << endl;
return 0;
}
二.减法操作
1.原题链接：
2.解题思路：
1.若n为偶数，则减的次数为 n/2，因为n的最小质因数为2 做差之后每次循环其最小质因数都为2
2.若n为奇数，则减的次数为 (n-n的最小质因数) / 2+1 ，因为n-n的最小质因数一定为偶数
3.参考代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long long find(long long n){
for(long long i=3;i<=n/i;i++){
if(n%i==0){
return i;
}
}
return n;
}
int main(){
long long n;
scanf("%lld",&n);
long long cnt;
if(n%2==0) cnt=n/2;
else cnt=1+(n-find(n))/2;
printf("%lld",cnt);
return 0;
}
