leetcode字符串算法练习，不定期更新
有效的字母异位词
题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
1
2
| 输入: s = "anagram", t = "nagaram"
输出: true
|
示例 2:
1
2
| 输入: s = "rat", t = "car"
输出: false
|
说明：
你可以假设字符串只包含小写字母。
思路
字母异位词的字符串长度和相对应的字母数量是相等的，因此可以借鉴桶排序的思想来统计每个字母的数量是否是相等的，如果不相等则就不是字母异位词
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool isAnagram(string s, string t)
{
if (s.size() != t.size()) {
return false;
}
int sArr[256] = { 0 };
int tArr[256] = { 0 };
for (int i = 0; i < s.size(); ++i) {
sArr[s[i]]++;
tArr[t[i]]++;
}
for (int i = 0; i < 256; ++i) {
if (sArr[i] != tArr[i]) {
return false;
}
}
return true;
}
|
验证回文字符串
题目
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明： 本题中，我们将空字符串定义为有效的回文串。
示例 1:
示例 2:
思路
使用两个游标，一个在字符串头，一个在字符串尾，两个游标同时向中间靠拢，遇到非字母和数字就跳过
实现
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
| bool isLetterOrNum(char c)
{
if ((c >= 'A' && c <= 'Z')
|| (c >= 'a' && c <= 'z')
|| (c >= '0' && c <= '9')) {
return true;
}
return false;
}
bool compareLetter(char c, char c1)
{
if (c == c1) {
return true;
} else if (c >= 'A' && c <= 'Z') {
return c + 32 == c1;
} else if (c >= 'a' && c <= 'z') {
return c - 32 == c1;
} else {
return false;
}
}
bool isPalindrome(string s)
{
if (s.empty() || s.size() == 1) {
return true;
}
int l = 0;
int r = s.size() - 1;
while (l < r) {
while (l < s.size() && !isLetterOrNum(s[l])) {
l++;
}
while(r >= 0 && !isLetterOrNum(s[r])) {
r--;
}
if (l == s.size() || r < 0) {
return true;
}
if(!compareLetter(s[l], s[r])){
return false;
}
++l;
--r;
}
return true;
}
|
字符串转换整数(atoi)
题目
请你来实现一个 atoi 函数，使其能将字符串转换成整数.首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明： 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。
思路
根据题干分为几个步骤
- 跳开字符串前面的空格
- 判断正负号
- 判断是否是数字，如果是就计算数值
- 判断该数字是否溢出，因此需要4个字节以上的存储空间，这里选用double类型（在leetcode的环境中，long或者long long存储num都会溢出）
实现
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
| int myAtoi(string str)
{
if (str.empty()) {
return 0;
}
int i = 0;
double num = 0;
int negative = 1;
while (str[i] == ' ')++i;
if (str[i] == '-') {
negative = -1;
i++;
} else if (str[i] == '+') {
i++;
}
while (str[i] >= '0' && str[i] <= '9') {
num = str[i] - '0' + num * 10;
++i;
}
num *= negative;
if (num < INT_MIN) {
num = INT_MIN;
} else if (num > INT_MAX) {
num = INT_MAX;
}
return num;
}
|
实现strStr()
题目
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
1
2
| 输入: haystack = "hello", needle = "ll"
输出: 2
|
示例 2:
1
2
| 输入: haystack = "aaaaa", needle = "bba"
输出: -1
|
说明： 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr()以及 Java的 indexOf() 定义相符。
思路
在haystack字符串中找出needle字符串意味着haystack的字符长度大于等于needle的字符长度，而且只需要执行haystack.length()-needle.length()次比较
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int strStr(string haystack, string needle)
{
if (needle.empty()) {
return 0;
}
#if 0
return haystack.find(needle);
#else
int j;
int hlen = haystack.length(), nlen = needle.length();
for (int i = 0; i <= hlen - nlen; ++i) {
for (j = 0; j < nlen; ++j) {
if (haystack[i + j] != needle[j]) {
break;
}
}
if (j == nlen) {
return i;
}
}
return -1;
#endif
}
|
最长公共前缀
题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例 1:
1
2
| 输入: ["flower","flow","flight"]
输出: "fl"
|
示例 2:
1
2
3
| 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
|
说明： 所有输入只包含小写字母 a-z 。
思路
以数组中的第一个字符串作为基准，遍历比较字符串相应下标的字符，相等则放入vector中，如果其中一个不相等则直接返回
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| string longestCommonPrefix(vector<string>& strs)
{
string res="";
if(strs.empty())
return res;
for(int i=0; i<strs[0].size(); ++i)
{
for(int j=1; j<strs.size(); ++j)
{
if(strs[j][i]!=strs[0][i])
return res;
}
res.push_back(strs[0][i]);
}
return res;
}
|