账号
周赛记录
- 第136场周赛:
- 通过题目数: 3/4
- 排名: 29/789
- 反思:贪心有问题的话尝试思考一下能不能用dp搞,字符串水平太垃圾了,有时间可以提升一下。
- 部分题解:
- 分隔数组以得到最大和(Medium):定义dp[i]为考虑前i个位置的最大和,然后枚举分割点即可,分割点到第i个位置的最大值随便拿个数据结构维护一下或者暴力预处理即可,因为序列长度真的很小= =。
- 第130场周赛:
- 通过题目数:3/4
- 排名:68/1293
- 反思:神志要清醒,不要时间紧迫急忙打比赛,样例都测完再交。
- 部分题解:
- 链表中的下一个更大节点(Medium):本质是要求每个数右边第一个比它大的数,然后这个东西就是维护一个单调栈的过程,用栈维护数组的下标,比栈头小就入栈,否则就不断出栈然后更新答案即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int>ans;
for (;;){
ans.push_back(head->val);
head=head->next;
if (head==NULL) break;
}
vector<int>res(ans.size());
stack<int>S;
for (int i=0;i<(int)ans.size();){
if(S.empty() || ans[S.top()]>=ans[i]) S.push(i++);
else{
res[S.top()]=ans[i];
S.pop();
}
}
while(!S.empty()){
res[S.top()]=0;
S.pop();
}
return res;
}
};
- 第129场周赛:
- 通过题目数:4/4
- 排名:1/758
- 反思:二进制转十进制从哪里开始遍历不要搞混。
- 第128场周赛(VP):
- 通过题目数:4/4
- 排名:2/1250
- 反思:全局变量放class外面的时候记得初始化
- 部分题解:
- 至少有1位重复的数字(Hard):设dp[i][S][0/1][0/1][0/1]表示从高到低考虑前i位数字已经出现过的数字集合为S,是否重复出现,是否出现前导零,等于n还是小于n为方案数,转移即可。
- 第127场周赛:
- 第126场周赛:
- 第125场周赛:
- 第124场周赛: