共 12 篇文章
传送门 T1：截断句子 思路 签到题，用python会比cpp简单很多。直接按空格split然后分片就行。 代码 ```python class Solution(object): def truncateSentence(self, s, k): """ :type s: str :type k: int :rtype: str """ ss = s.split(" ") if k == len(ss): return s ans = " ".join(ss[:k]) return ans ``` 赛后感觉写的太冗长了，可以精简成一句： ```python class Solution(object): def truncateSentence(self, …
Trie树是一个很有价值的中级数据结构啊，花点功夫再深究一下。 模板 Trie树的实现比较特殊，每一个节点上不是一个单独的字符，而是一个映射表： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2021/02/image-1-1024x686.png 如上图所示，每一个节点里包含当前位置字母的一个映射表，然后再有每个字母指向下一层节点。 代码 ```cpp class Trie { private: bool isEnd; Trie *next[26]; public: /** Initialize your data structure here. */ Trie() { isEnd = false; memset(next, 0, sizeof(next)); } /** Inserts a word into the trie. */ void insert(string word) { Trie *node = this; …
传送门 T1替换隐藏数字得到的最晚时间 思路 签到题，注意一些细节就行。 代码 ```cpp class Solution { public: string maximumTime(string time) { if (time[0] == '?' && time[1] >= '4' && time[1] != '?') time[0] = '1'; else if (time[0] == '?') time[0] = '2'; if (time[1] == '?' && time[0] == '2') …
法1：hash 思路 很简单的思路，用一个hash表，键为字符，值为一个pair，pair的first成员存字符的出现次数，second成员为该字符的下标，维护一个下标最小值为答案即可。 代码 ```cpp class Solution { public: int firstUniqChar(string s) { unordered_map> mp; for(int i = 0; i < s.size(); i++) { mp[s[i]].first++; mp[s[i]].second = i; } int pos = INT_MAX; for(auto el: mp) { if((el.second).first == 1) { pos = min(pos, (el.second).second); } } return …
传送门 T1重新格式化电话号码 思路 周赛经典的字符串处理题。难倒是不难，但是处理起来感觉比往期的签到题麻烦不少啊... 主要思路就是replace掉'-'与空格，然后每三个一组分片，塞进列表，最后再对单出来的元素特殊处理。 代码 ```python class Solution: def reformatNumber(self, number: str) -> str: number = number.replace('-', '').replace(' ', '') ans, N = [], len(number) for i in range(0, N, 3): ans.append(number[i:i+3]) if len(ans[-1]) == 1: last = ans.pop() sec_last = ans.pop() ans.append(sec_last[:2]) …
传送门 之前忙着开学，有相当一段时间没有做题了，实在是罪过... 数组 t1寻找数组的中心索引 找到数组中的一个位置，这个位置之前的所有元素和等于这个位置之后的所有元素和。如果没有就返回-1。 感觉思路有点滑动窗口的味道。维护两个变量lsum与rsum，分别表示当前位置左边的元素和与右边的元素和，然后根据题意O(n)遍历判断就行了。 ```cpp class Solution { public: int pivotIndex(vector& nums) { int rsum = 0, lsum = 0; const int n = nums.size(); if(n == 0) return -1; for(auto& el: nums) rsum += el; rsum -= nums[0]; if(rsum == 0) return …
传送门 t1 千位分隔数 给定一个整型数，给它每三位加上一个分隔符。 做法有很多，憨一点可以用取出每一位数字来做，但看这个范围估计是要炸的，所以我这里选择转成string来做。 转成string，计数，每三位加上一个"."最后翻转一下就行了，记得处理一下前缀“.”。 ```cpp class Solution { public: string thousandSeparator(int n) { string str = to_string(n); if(n < 1000) return str; int m = str.size(); string ans = ""; int cnt = 0; for(int i = m-1; i >= 0; i--) { …
传送门 很经典的字符串问题。给定一个字符串，返回它最长且无重复字符的子串。 可以很直接的想到一个枚举的做法，两重循环遍历字符串去枚举子串，复杂度略小于O(n²)，但肯定会超时。于是想到滑动窗口。 滑动窗口可以在母串上维护一个检索区间，从而避免因为匹配失败而导致的低效下标回溯操作。 具体来说，如果窗口右端检索到一个重复字符，那么左端收缩，直到不存在重复字符位置。每次滑动结束后维护ans字符串即可。 ```cpp class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); int ans = -INT_MAX, left = 0; unordered_setstr; if(!n) return 0; for(int right = 0; right < n; right++) { while(str.find(s[right]) != str.end()) { str.erase(s[left]); left++; } …
传送门 题目大意 给定一个由小写字母组成的字符串S。你要执行一系列操作。有以下两种操作：1、修改：给定一个整数x，你需要根据x的值来修改S。如果x是正数，就把S中最左边的x个字母移到S的右边；否则，就把S中最右边的|x|个字母移到S的左边。2、查询：给定一个正整数x，输出字符串中第x个字符。 思路 题面很简单，朴实的字符串位移操作。上手十分钟写了个string模拟 ```cpp #include using namespace std; int q; string str; int main() { cin >> str; scanf("%d", &q;); while(q--) { int x; char op; scanf("%d", &op;); switch (op) { case 'A': scanf("%d", &x;); printf("%c\n", str[x-1]); break; case 'M': scanf("%d", &x;); …
传送门 题目大意 对于字符串s，定义s∞=ss...sss。给定字符串s,t，判断 s∞ 与 t∞ 的字典序大小关系。(|s|<1e5) 思路 两个字符串长度相等自然没话说，直接比较就行。这题的核心在处理字符串长度不等的情况。 最开始想到的朴素做法是延长两个字符串至长度为二者的最小公倍数，再来比较，但是会双超。参阅了大佬的题解后了解到了一种全新的做法：直接比较s+t与t+s。 这样做的正确性是显然地。设s的长度为lens，t的长度为lent，lens<lent。在前lens个字符进行比较时，s[i]与t[i]是一一对应的，不存在对齐问题，而进行到lens+1时，如果执行s+t操作，相当于把之前已经确认相等的子串接在s后面，即两个字符串做了等价放大。 ```cpp #include using namespace std; string x, y; int main() { while(cin >> x >> y) { if(x + y < y + x) puts("<"); else if(x + y > y + x) puts(">"); …
传送门 题目大意 给一个长度为n的序列A={1,2,3,...,n}以及置换的次数k，在对A使用k次置换P后得到新的排列B。 输入n,k和B，输出A，如果无解则输出-1。 思路 这种“给出原序列、目标序列与置换规则”的题一般都是置换群。 首先给你一个序列，假如： s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 比如这样 第一次：6 3 4 2 1 5 第二次：5 4 2 3 6 1 第三次：1 2 3 4 5 …
传送门 给出一个英文句子，要求判断它是否是回文串。判断时忽略大小写、标点以及空格，同时空字符串视为回文串。 我的思路是O(n)扫过去清掉标点和空格并统一大小写，然后翻转字符串判断它与初始字符串是否相等。确实可以A但是时间复杂度惨不忍睹，感觉可以优化到O(1)，学习后会更新。 ```cpp class Solution { public: bool isPalindrome(string s) { string str = ""; int n = s.size(); for(int i = 0; i < n; i++) if(isalpha(s[i])) str += tolower(s[i]); else if(isdigit(s[i])) str += s[i]; string str1 = str; reverse(str1.begin(), str1.end()); return str1 …