leetcode 刷题笔记- string.
- cout and say
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<iostream>
#include<string>
using namespace std;
string cout_and_say(int n)
{
string res ="1"; // 这个初始化意味着需要少循环一次，
while ( --n )
{
string tmp;
for(int i =0; i< res.size() ; i++)
{
int j =i; // 常用的一种遍历手段
while(j < res.size() && res[j] ==res[i]) j +=1;
tmp =to_string(j -i) +res[i];
i =j -1;
}
res =tmp;
}
return res;
}
int main()
{
int n ;
cin >>n;
string res =cout_and_say(n);
for(auto u: res)
cout << u;
cout << endl;
return 0;
}
|
- group anagrams
sort 函数是 in-place() 的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
// 思路很简单， 先是放到一个 hash，然后再遍历一遍dictionary
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;
for(auto str : strs)
{
string key =str;// sort 函数是 in-place() 的操作
sort(key.begin(), key.end());
hash[key].push_back(str);
}
vector<vector<string>> res ;
for (auto item : hash)
{
res.push_back(item.second);
}
return res;
}
};
|
- reverse words in a sting
LeetCode题目链接
c++ 中绝大部分都是左闭右开， 比如说reverse() .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<iostream>
#include<string>
using namespace std;
string reverse_string(string str)
{
string res;
int n =str.size() ;
int k =0;
for(int i =0; i< n; i++)
{
while (i < n && str[i] ==' ') i ++;
if (i > n) break;
int j =i ;
while(j < n && str[j] != ' ') j ++;
reverse(str.begin() +i, str.begin() +j);
if(k ) str[k ++] =' ';
// 赋值回来, 这个语句是非常秒的, 把 i 的index 补充了回来
while(i < j) str[k ++] =str[i ++];
}
str.erase(str.begin() +k , str.end());
reverse(str.begin(), str.end());
return str;
}
int main()
{
string input =" the sky is blue";
string res =reverse_string(input);
for(auto u : res)
cout<< u;
cout << endl;
return 0;
}
|
- compare-version-numbers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<iostream>
#include<string>
using namespace std;
int cmpVersion(string str1, string str2)
{
int n =str1.size() , m = str2.size();
int i =0, j =0;
while(i < n || j < m)
{
int x =i, y =j;
while( x< n && str1[x] != '.') x ++;
while( y< m && str2[y ] != '.') y ++;
int sum1 = x ==i ? 0 : atoi(str1.substr(i, x -i).c_str());
int sum2 = x ==j ? 0: atoi(str2.substr(j, y -j).c_str());
i =x +1, j = y +1;
if(sum1< sum2) return -1;
if (sum1 > sum2) return 1;
}
return 0;
}
int main()
{
string str1; // 0.1
string str2; //1.1
getline(cin, str1);
getline(cin, str2);
cout<< cmpVersion(str1, str2)<< endl;
return 0;
}
|
- Unique Email Addresses
这里给出了一种如何去读入 vector，最简单的方法就是多定义一个循环，这样的话就可以完整的读入所有的string，可能再最后的结果中有 +1 或者 -1 的操作。最后看效果，稍微猜测推一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include<iostream>
#include<unordered_set>
#include<string>
#include<vector>
using namespace std;
// 比较简单 ，分成 name 和 domain 两个方面进行处理
int numUniqueEmails(vector<string> emails)
{
unordered_set<string> hash;
for(auto email: emails)
{
int at =email.find("@");
string name =email.substr(0, at); // 写成 email.begin() 吧
string domain =email.substr(at +1);// 默认是到最后的，如果只是有一个参数的话
string tmp;
for(auto ch : name)
{
if (ch =='+') break;
else if(ch != '.') tmp += ch;
}
string res =tmp+'@'+ domain;
hash.insert(res);
}
return hash.size()-1;
}
int main()
{
//vector<string> emails={"a@a.com", "b@b.com"};
vector<string> emails;
// 对于字符串 数组的输入是不不会的
int n ;
cin >> n;
n ++;
while(n --)
{
string tmp;
getline(cin, tmp);
emails.push_back(tmp);
}
cout << numUniqueEmails(emails)<< endl;
return 0;
}
|
- longest palindromic substring
返回结果是子串的问题，一般使用双指针（可以处理连续的问题）。针对本题，先是枚举中心点，然后向着左右两边扩展，算法时间复杂度是$O(n^2)$。使用马拉车算法可以在$O(n)$的时间复杂度内解决，但是只能处理回文串问题，比较局限，不像kmp 算法。
在实现的时候，尽量使用 i+1 而不要使用 i-1，因为对于两个数字的相邻关系，使用 i-1 , i 和 i ， i+1 都是可以表示的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
string longestPalindrome(string s) {
//时间复杂度是 On^2()， 先枚举中心点，然后向着左右两边进行扩展，最优的解法是 马拉车，但是太局限了，所以没有学习
int n = s.size();
string res ;
for(int i =0; i< n; i++)
{
for(int j =i, k =i ; j >= 0 && k < n&& s[j] ==s[k]; j --, k ++)
{
if(k -j +1 > res.size())
res =s.substr(j, k-j +1);
}
for(int j =i, k =i +1; j >=0 && k < n && s[j] ==s[k]; j --, k ++)
if( k -j +1 > res.size())
res =s.substr(j, k-j +1);
}
return res;
}
};
|
- zigzag conversion
好好理解一下，当for 循环的时候， 第三个参数就是等差数列中公差。for 循环是可以模拟 等差数列和等比数列的，初始化，判别条件和步伐是能够和公差公比相对应的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
// 找规律的题目
// 如果是首行和尾行，公差是 2(n -1)，
// 如果是中间行, 那么是两个交错的等差数列
string convert(string s, int n) {
if (n ==1) return s;
string res;
for(int i =0; i< n; i++)
{
if(! i || i ==n-1 )
{
for(int j =i; j< s.size(); j += 2*(n -1))
res += s[j];
}
else
{
// 两个交叉的数列, 只是初始化的值需要注意一下
for(int j =i, k =2*(n-1) -i ; j < s.size() || k < s.size() ; j += 2*(n -1) , k += 2*(n -1) )
{
if(j < s.size()) res += s[j];
if(k < s.size() ) res += s[k];
}
}
}
return res;
}
};
|
- longest substring without repeating characters
~~一开始还以为使用dp，但是使用双指针+ dictionary 就可以解决。~~求解的是子串（不是子序列），所以一定是一个连续的区间 [i, j]，有点贪心的思想，通用的“滑动窗口 + 哈希表” 的做法。由于 $i$, $j$ 最多增加 $n$ 次，且hash 表的插入和更新时间复杂度是$O(1)$， 所以总的时间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
i, res =0, 0
dic ={}
for (j, ch ) in enumerate(s):
if ch in dic and i <= dic[ch]:
i =dic[ch] +1
else:
res =max(res, j -i+1)
dic[ch] =j # dic 是一个记录 char 到index 的映射关系的dictionary
return res
|
- implement Trie(Predix Tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
class Trie {
public:
// 使用一个结构体存储一个结点
struct Node{
bool is_end;
Node * son[26];
// 这个类似构造函数，是对结构体进行初始化
Node()
{
is_end =false;
for(int i=0; i< 26; i++)
son[i] =NULL;
}
}*root;
// 这个是结构体变量
/** Initialize your data structure here. */
Trie() {
root =new Node();
}
/** Inserts a word into the trie. */
void insert(string word) {
auto p = root;
for(auto c: word)
{
auto u =c -'a';
if(p->son[u] ==NULL) p ->son[u] =new Node();
p =p->son[u];
}
p->is_end =true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
auto p =root;
for(auto c : word)
{
auto u =c -'a';
if(p ->son[u] ==NULL) return false;
p =p->son[u];
}
return p->is_end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
auto p =root;
for(auto c :prefix)
{
auto u =c -'a';
if(p ->son[u] ==NULL) return false;
p =p->son[u];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
|
关于trie 的理论讲解可以参考这篇博客, 这里主要讲解实现。
- integer to English Words
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution {
public:
string small[20] ={"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
"Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
string mid[10] ={"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
string big[4] ={"Billion", "Million", "Thousand", ""};
string numberToWords(int num) {
if(! num) return small[0];
string res;
for(int i =1000000000,j =0; i>0; i /=1000, j++)
{
if(num >=i)
{
res += get_part(num /i) +big[j] +" ";
num %= i;
}
}
while(res.back() ==' ') res.pop_back();
return res;
}
string get_part(int n)
{
string res;
if(n >=100)
{
res += small[n /100] +" Hundred ";
n %= 100;
}
if(!n) return res;
if(n >=20)
{
res += mid[n/10] +' ';
n %=10;
}
if(!n) return res;
res += small[n]+' ';
return res;
}
};
|
KMP 专题
首先最简单的是字符串的匹配问题， 如果暴力枚举，那么时间复杂度是 $O(mn) $，其中 $m$ 和$n$ 分别表示两个字符串的长度。如果使用kmp 算法，那么时间复杂度是 $O(m +n)$
这个是模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
|
这个是投机取巧的方式， 但是可以掌握关于 string:: npos 这种判断条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n, m;
string p, s;
cin >> n>> p>> m>> s;
auto found =s.find(p);
while(found != string::npos)
{
cout << found << " ";
found =s.find(p, found+1);
}
return 0;
}
|
使用 kmp 算法的正解。(KMP字符串)(https://www.acwing.com/problem/content/description/833/)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<iostream>
using namespace std;
const int N =1e4+11;
const int N1 =1e5+11;
int nex[N];
char p[N];
char s[N1];
int n, m;
void get_next()
{
for(int i =2,j =0; i<=n; i++)
{
while(j && p[i] != p[j+1]) j =nex[j];
if(p[i ] ==p[j+1]) j ++;
nex[i] =j;
}
}
int main()
{
// 这种写法对于一次性的读入，还是非常有效率的，学习
cin >> n >> p+1>> m >> s+1;
get_next();
for(int i =1, j =0; i<=m; i++)
{
while(j && s[i] != p[j+1]) j =nex[j];
if( s[i] ==p[j+1]) j +=1;
if(j ==n)
{
printf("%d ", i-n);
j =nex[j];
}
}
return 0;
}
|
周期
next[n] 的含义： 表示以 n 为结尾的后缀和以 1位起点的前缀，相同的string ， 最大长度。 n-next[n] 表示最小的循环节，那么 n/(n -next[n]) 就是最多的个数。
以i 为结点的最大的后缀和前缀相等，这个后缀的长度就是next[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<iostream>
using namespace std;
const int N =1e6+11;
int nex[N];
char str[N];
int n;
//在所有的前缀中 最小循环节的最大重复个数
// 考察 n-next[n] 是表示最小的循环节
void get_next()
{
for(int i =2, j =0; i<=n ; i++)
{
// while 和 nex[i] 是容易出粗
while(j && str[i] != str[j+1]) j =nex[j];
if(str[i] ==str[j+1]) j++;
nex[i] =j;
}
}
int main()
{
int T =1;
// 如果n ==0，那么就跳出了
while(scanf("%d", &n), n)
{
scanf("%s\n", str+1); // 这种 \n 在读入字符串中还是非常有用，对于cin 函数，你就知道多有用了
get_next();
printf("Test case #%d\n", T++);
for(int i =1; i<=n; i++)
{
int t =i -nex[i];
if(t != i && i%t ==0) printf("%d %d\n", i, i/t);
}
puts("");
}
return 0;
}
|
对于string 的题目，一般可以hash 或者 kmp 算法求解。
160. 匹配统计
视频讲解
我觉得可以理解的地方是，kmp 算法求解next 数组，kmp 算法进行字符串匹配，n-next[n] 表示最大的循环节的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
// f[i] 表示匹配长度至少是 i的情况下， 这样的后缀有多少个
// 最少是 x -最少是x+1 的，那么得到的就是 x
#include<iostream>
using namespace std;
const int N =2e5+11;
int n, m, q;
char a[N], b[N];
int ne[N];
int f[N];
// next 数组本质上就是前缀和后缀的匹配的最大长度
// next 数组不止可以操作同一个string，还是可以操作另外的数组
int main()
{
cin >>n >>m>> q;
scanf("%s%s", a+1, b+1); // 读入了两个字符串数组
//对于 b 求解kmp 数组
for(int i =2, j =0;i <=m; i++)
{
while(j && b[i] != b[j+1]) j =ne[j];
if(b[i] ==b[j+1]) j++;
ne[i] =j;
}
// 求解a 的后缀和b 的前缀的匹配,
for(int i =1, j =0; i<=n; i++)
{
while(j && a[i] != b[j+1]) j =ne[j];
if(a[i] ==b[j+1]) j ++;
// 这里是不理解的
f[j] ++;
}
// 这里也是不懂的
for(int i=m; i; i--) f[ne[i]] += f[i];
while( q--)
{
int x ;
cin >>x;
cout << f[x]- f[x+1] <<endl;
}
return 0;
}
|
奶牛矩阵
视频讲解
太难了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N =10010, M =80;
int n, m;
char str[N][M];
int ne[N];
bool st[M];
int main()
{
cin >>n>>m;
memset(st, true, sizeof st);
for(int i =1 ;i<=n; i++)
{
scanf("%s", str[i]);
for(int j =1; j<=m; j++)
{
if(st[j])
{
for(int k =j; k<m; k+=j)
{
for(int u =0; u<j && k+ u< m; u++)
{
if(str[i][u] != str[i][k+u])
{
st[j] =false;
break;
}
}
if(!st[j]) break;
}
}
}
}
int width;
for(int i =1; i<=m; i++)
{
if(st[i])
{
width =i;
break;
}
}
for(int i =1; i<=n; i++) str[i][width] =0;
// strcmp(str1, str2) 如果相等返回 0， 如果str1< str2 返回-1， 如果大于 返回+1
for(int i =2, j =0; i<=n; i++)
{
while(j && strcmp(str[i], str[j+1])) j =ne[j];
if(!strcmp(str[i], str[j+1])) j++;
ne[i] =j;
}
int height =n -ne[n];
//cout << width <<" "<< height<< endl;
cout << width *height <<endl;
return 0;
}
|
超市
主要是练习 小根堆和pair 的组合使用。是一个贪心算法，很经典的、时间复杂度是 $nlogn$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> PAIR;
// 使用pair 这种结构是可以按照第一关键字先排序，然后按照第二关键字排序
// 按照过期时间排序，维护一个小根堆，每次把利润小的给 pop出去
int main()
{
int n;
while(cin >>n)
{
vector<PAIR> products(n);
// 这种写法，真是非常的简洁，使用vector<pair<int, int>> 的格式，list 中嵌套了 pair
// 先是按照过期时间进行排序，如果相同，那么按照金额进行排序,都是从小到大进行排序，因为sort() 默认的按照增序进行排序的
for(int i =0; i<n; i++) cin >> products[i].second >> products[i].first;
sort(products.begin(), products.end());
// 定义小根堆
// 使用greater<int> ,less<int> ，头文件不写也行的
priority_queue<int , vector<int> , greater<int>> heap;
for(auto p: products)
{
heap.push(p.second);
if(heap.size() > p.first) heap.pop();
}
int res =0;
while(heap.size() ) res += heap.top(), heap.pop();
cout << res<< endl;
}
return 0;
}
|
第二次写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int> PAIR;
int main()
{
int n ;
while(cin >>n)
{
vector<PAIR> products(n);
// 下面是index 访问，那么就需要初始化，否则是段错误；或者使用 push_back() 进行访问
for(int i =0; i< n; i++)
{
cin >> products[i].second >> products[i].first;
}
sort(products.begin(), products.end());
priority_queue<int, vector<int>, greater<int>> heap;
for(auto product: products)
{
// 先是无脑放，如果发现不满足条件，那么弹出
heap.push(product.second);
if(heap.size() > product.first) heap.pop();
}
int res =0;
while(heap.size())
{
res +=heap.top();
heap.pop();
}
cout << res<< endl;
}
return 0;
}
|
Implement strStr()
注意这个不是从 1 开始计数的，这个使用边界条件是需要记录一下的。kmp 算法的应用，如果暴力求解，那么算法复杂度是 $O(mn)$，但使用KMP 算法，时间复杂度是$O(m +n)$，其中$m$, $n$ 分别是两个字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
int strStr(string haystack, string needle) {
int n =haystack.size() , m =needle.size();
if(m ==0) return 0;
vector<int> nex(m);
nex[0] =-1;
for(int i =1, j =-1; i< m; i++)
{
while( j > -1 && needle[i] != needle[j +1] ) j =nex[j];
if(needle[i] ==needle[j +1]) j ++;
nex[i] =j;
}
for(int i =0, j =-1; i<n; i++)
{
while( j> -1 && haystack[i] != needle[j +1] ) j =nex[j];
if(haystack[i] ==needle[j +1]) j ++;
if( j ==m -1)
return i -m +1;
}
return -1;
}
};
|
459. Repeated Substring Pattern
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
// 考察kmp 中 i -nex[i] 是循环节的长度。更加具体的是 在这个题目中 n -nex[n] 是最小循环节的长度，
// 这个是可以用来判断是否完美切分
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector<int> nex(n);
nex[0] =-1;
for(int i =1, j =-1; i< n; i++)
{
while(j > -1 && s[i] != s[j+1]) j =nex[j];
if(s[i] ==s[j+1]) j ++;
nex[i] =j;
}
int t =n-1 -nex[n-1];
return t !=n&& n%t ==0; // 字符串本身不能作为一个循环节
}
};
|
214. Shortest Palindrome
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
// 考察kmp 的前后缀的理解
string shortestPalindrome(string s) {
int n =s.size();
// 这种情况专门就是指的是 s =="" 没有其他的情况了
if (n ==0) return s;
string t(s.rbegin(), s.rend());
vector<int> nex(n);
nex[0] =-1;
for(int i =1, j =-1; i< n; i++)
{
while(j > -1 && s[i] != s[j+1]) j =nex[j];
if(s[i] ==s[j+1]) j ++;
nex[i] =j;
}
// 做的kmp 的匹配
int j =-1;
// 比较的是 t 的前缀和 s 的后缀的相同的最大的长度
for(int i =0; i<n; i++)
{
while(j > -1 && t[i] != s[j+1]) j =nex[j];
if(t[i] ==s[j+1]) j ++;
}
return t +s.substr(j +1, n -j -1);
}
};
|
LeetCode 179. Largest Number
这个主要是考虑到排序算法。如果字符串表示的比较大， 那么最后是数字表示也是比较大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
static bool cmp(string& a, string& b)
{
return a+b > b+a;
}
string largestNumber(vector<string> & nums)
{
string res="";
sort(nums.begin(), nums.end(), cmp);
for(string t: nums)
res += t;
return res;
}
int main()
{
int n ;
cin >>n;
vector<string> nums;
for(int i =0; i< n; i++)
{
string tmp;
cin >> tmp;
nums.emplace_back(tmp);
}
string res =largestNumber(nums);
cout << res<< endl;
return 0;
}
|
LeetCode 242. Valid Anagram
这个时间复杂度是$O(n)$，空间复杂度是$O(1)$。空间的优化是有技巧的，因为这里只有26个字母，所以空间大小是固定的，比较nice的东西。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
// 这种应该是最少的时间复杂度了
bool isAnagram(string s, string t) {
vector<int> hash(26, 0);
for(char ch: s)
hash[c- 'a'] ++;
for(char ch: t)
hash[c -'a'] --;
for(int i =0; i< 26; i++)
if(hash[i] != 0)
return false;
return true;
}
};
|
415. Add Strings
c++ 中注意不同数据类型，int 和int 之间使用 += , string 和string 之间使用 += 才有意义。
···c++
class Solution {
public:
string addStrings(string num1, string num2) {
string res;
int carry =0;
int m =num1.size() -1, n =num2.size() -1;
while ( m >=0 && n >= 0)
{
carry = (num1[m–] -‘0’ ) + (num2[n –] -‘0’) + carry;
res += (carry %10 +‘0’);
carry =carry/ 10;
}
while (m >=0)
{
carry = (num1[m–] - ‘0’) + carry;
res += (carry %10 +‘0’);
carry /= 10;
}
while( n >=0)
{
carry = (num2[n –] -‘0’) + carry;
res += ( carry %10 + ‘0’);
carry /= 10;
}
if( carry)
res += (carry %10 +‘0’);
reverse(res.begin(), res.end());
return res;
}
};
···
python 中 ord 和 chr 函数
chr()函数用整数作参数，返回一个对应的字符
ord()函数是chr()函数的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的ASCII数值，或者Unicode数值
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j =len(num1) -1, len(num2) -1
ans =""
carry =0
while i >=0 or j >=0 or carry:
a = ord(num1[i]) - ord('0') if i >= 0 else 0
b = ord(num2[j]) - ord('0') if j >= 0 else 0
n =a +b + carry
ans = chr( n%10 + ord('0')) + ans # 注意顺序, + ord('0') 处理bad case： 都为0
carry = carry //10
i, j = i -1, j -1
return ans
|