Date:20210414 7:30pm
A:100case
key:1.首先明确所有的反转都是由内到外进行的，因此第一次反转是发生在从左到右第一次碰到')'的时候。
2.直觉告诉我们可以用栈来一个个装，当碰到)时。持续弹出到一个队列里(因为要反转)直到栈顶是(，这是还要再pop一次，因为此时栈顶是(。这时再将
队列里全部pop到栈，这样就完成了一次反转。
3.注意最后栈弹出是反的，因此全部弹出到一个vector里，i=V.size()-1,逆序输出即可。
A:100case
key:1.首先明确所有的反转都是由内到外进行的，因此第一次反转是发生在从左到右第一次碰到')'的时候。
2.直觉告诉我们可以用栈来一个个装，当碰到)时。持续弹出到一个队列里(因为要反转)直到栈顶是(，这是还要再pop一次，因为此时栈顶是(。这时再将
队列里全部pop到栈，这样就完成了一次反转。
3.注意最后栈弹出是反的，因此全部弹出到一个vector里，i=V.size()-1,逆序输出即可。
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
void res(stack<char>& S)
{
queue<char>S1;
while (S.top() != '(')
{
S1.push(S.top());
S.pop();
}
S.pop();
while (!S1.empty())
{
S.push(S1.front());
S1.pop();
}
}
int main()
{
stack<char>S;
string s;
cin >> s;
for (int i = 0; i < s.size(); i++)
{
if (s[i] != ')')
{
S.push(s[i]);
}
else
{
//弹出到(,反转再塞回去
res(S);
}
}
vector<char>V;
while (!S.empty())
{
V.push_back(S.top());
S.pop();
}
for (int i = V.size()-1; i >= 0; i--)
{
cout << V[i];
}
} B:15case
Date:20210414 21:00pm1.显然题目太长，主要分为两种流程，每次通过差值确认有没有进入abe流程。abe那个太复杂，只写了周期报告的情况有15%case，太罗嗦，没时间写。
2.差值只能只能看到是不是abe状态有没有发生，而不是abe有可能是刚结束abe而不是正常报告，需要多一个变量来确认是不是结束abe状态。
3.流程间的切换有太多变量要初始化，容易搞混。
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
void jump(int* A, int* B,int &i, int& n)
{
//遍历i及的右边A[i]个
int new_i=i;
int j;
int max_len = 0;
for (j = i; j <= i + A[i]; j++)
{
//cout << j << " ";
if (B[j] >= max_len)
{
new_i = j;
max_len = B[j];
//if (j + A[j]+1 >= n)
//{
// i = n;
// return;
//}
}
}
i = new_i;
}
int main()
{
/*
*/
int i, j, n;
vector<int>V;
cin >> n;
if (n == 0) { cout << 0; return 0; }
int* A = new int[n];
for (i = 0; i < n; i++)
{
cin >> A[i];
}
int T = 59;
V.push_back(A[0]);
bool flag = 0;
//每次通过差值确认有没有进入abe流程
for (i = 1; i < n; i++)
{
if (A[i] - A[i - 1] >= 9)
{
//abe开始，另一个周期要清零吧
T = 60;
flag = 1;
}
else
{
V.push_back(A[i]);
if (flag)
{
flag = 0;
}
if (T == 0)
{
cout << V[V.size() - 61] << "," << V[V.size() - 1];
T = 60;
continue;
}
T--;
}
}
} C:85case
Date:20210414 20:25pm
key:1.经典动态规划，跳格子问题。对于第i个位置，考虑i到i+A[i]这个区间中哪个元素能跳的最远，最远的设置为新的i。
2.注意i-A[i]到i为什么不用考虑，因为如果前面的能跳得超过i(从左往i已经考虑了每一个点)，那当前的点就不可能是i，这是个悖论。因此从左往右时不用考虑i-A[i]到i。
3.一开始用一个最远距离数组存每个点能到的最远点，类似:B[i]=i+A[i]
Date:20210414 20:25pm
key:1.经典动态规划，跳格子问题。对于第i个位置，考虑i到i+A[i]这个区间中哪个元素能跳的最远，最远的设置为新的i。
2.注意i-A[i]到i为什么不用考虑，因为如果前面的能跳得超过i(从左往i已经考虑了每一个点)，那当前的点就不可能是i，这是个悖论。因此从左往右时不用考虑i-A[i]到i。
3.一开始用一个最远距离数组存每个点能到的最远点，类似:B[i]=i+A[i]
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
void jump(int* A, int* B,int &i, int& n)
{
//遍历i及的右边A[i]个
int new_i=i;
int j;
int max_len = 0;
for (j = i; j <= i + A[i]; j++)
{
//cout << j << " ";
if (B[j] >= max_len)
{
new_i = j;
max_len = B[j];
//if (j + A[j]+1 >= n)
//{
// i = n;
// return;
//}
}
}
i = new_i;
}
int main()
{
/*4
2 3 1 1*/
//相当于在第i个格子，要检查[i-A[i],i+A[i]]里最大的。
//这是在比较往右的最远距离,假设j在i-A[i]->i+A[i].
//j<i时，最远距离为i-j+A[j].j>i时，最远距离为j-i+A[j].
//先假设j<i不存在试试
int i, j, n;
cin >> n;
if (n == 0) { cout << 0; return 0; }
int* A = new int[n];
for (i = 0; i < n; i++)
{
cin >> A[i];
}
//每个点能到的最远
int* B = new int[n];
for (i = 0; i < n; i++)
{
B[i] = i + A[i];
}
i = 0;
int count = 0;
while (1)
{
//每次把下标起点放入
jump(A,B, i,n);
//cout << i << " ";
count++;
//因为i是下标所以要+1
if (i+1 >= n)
{
break;
}
}
cout << count;
} 最后吐槽一下，字节不要我，阿里不要我，腾讯不要我，网易不要我，微保不要我，西山居剑心也不要我。就华为的笔试题感觉做的还可以，希望我能坚强。暑期实习真不容易，找到的都是大佬啊。
全部评论
(5) 回帖