题解:根据描述,第一反应模拟这个过程,超时。
string shiftingLetters(string S, vector<int>& shifts)
{
for(int i=0;i<shifts.size();i++)
{
S = shiftStr(S,shifts[i],i);
}
return S;
}
string shiftStr(string &s,int shift,int end)
{
shift%=26;
for(int i=0;i<s.length()&&i<=end;i++)
{
s[i] ='a' + (s[i]-'a'+shift)%26;
}
return s;
}
第二反应:根据上述这个模拟超时过程,想一优化,shifts数组后面开始,逐个偏移,根据描述,后面的偏移会加到前面。于是有了后缀和这一说法。
string shiftingLetters(string S, vector<int>& shifts) {
for(int i=shifts.size()-2;i>=0;--i){
shifts[i]%=26;
shifts[i]+=shifts[i+1];
//计算后缀和
}
for(int i=0;i<S.size();i++){
S[i] ='a' + (S[i]-'a'+shifts[i])%26;
}
return S;
}
题解:根据描述,本题可转换为最长连续0的长度。分三种情况,一开始就连续的0(左边无1),在中间连续的0(指0的左右都有1),在末尾连续的0(右边无1).
int maxDistToClosest(vector<int>& seats) {
int N = seats.size();
int K = 0;
int ret = 0;
for (int i = 0; i < N; ++i)
{//统计中间0的长度,
if (seats[i] == 1)
K = 0;
else
{
K++;
ret = max(ret, (K + 1) / 2);
}
}
for (int i = 0; i < N; ++i)
{//统计第一种情况
if (seats[i] == 1)
{
ret = max(ret, i);
break;
}
}
for (int i = N-1; i >= 0; --i)
{//统计第三种情况
if (seats[i] == 1)
{
ret = max(ret, N - 1 - i);
break;
}
}
return ret;
}
题解:根据描述,好像描述有点复杂,上图。
依据谁比谁更穷(比如0号选手比1号选手穷)这样的关系,构建了一个有向图。旁边红字对应的是每位选手的安静值。题目的意思就是把每位选手的安静值更新为所有比他富有的选手的安静值中,最小值对应的选手,怎么办?模拟图的深搜过程,假设DFS(i)表示所有比i号选手富有的选手的最小安静值对应的选手。那么,写成代码
vector<int>answer;
vector<vector<int>>graph;
vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet)
{
int N = quiet.size();
for(int node=0;node<N;++node)
{//邻接表初始化
vector<int>v;
graph.push_back(v);
answer.push_back(-1);
}
for(auto i:richer)
graph[i[1]].push_back(i[0]);
//邻接表赋值
for(int node=0;node<N;node++)
dfs(node,quiet);
return answer;
}
int dfs(int node,vector<int>&quiet)
{
if (answer[node] == -1)
{
answer[node] = node;
for (int child: graph[node])
{
int cand = dfs(child,quiet);
if (quiet[cand] < quiet[answer[node]])
answer[node] = cand;
}
}
return answer[node];
}
不会,待填坑,开始复习简历上的内容了。