Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

数组和字符串-04

字符串

字符串是一个由字符构成的数组。
之后深入研究字符串,需要掌握如下知识点:

  • 熟悉字符串中的基本操作,尤其是在数组中没有的独特操作;
  • 理解不同比较函数之间的区别;
  • 理解字符串是否可变以导致连接过程中出现的问题;
  • 能够解决与字符串相关的基本问题,如排序、子串、字符串匹配等;

字符串简介

维基百科:字符串是由零个或多个字符组成的有限序列。一般记为 s = a1a2…an。它是编程语言中表示文本的数据类型。

为什么单独讨论字符串

虽然字符串与数组有很多的相似之处,但是还是要单独讨论字符串,为什么呢?原因有以下几点:

1.字符串的基本操作对象通常是字符串整体或者其中的子串

例如: I love you 你想将这个字符串反向输出,你肯定不想得到 uoy evol I 想得到的肯定是 you love I

维持单词本身的顺序可以让我们很方便的做其他的操作,这其中每个单词就被称为子串

2.字符串操作要比其他数据类型更复杂(例如:比较、连接操作)

对于不同的编程语言,字符串的某些操作会有所不同。

下来继续撸代码了:

题目:最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串””。

示例:

1
2
3
4
5
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:
所有输入只包含小写字母 a-z

个人理解
公共前缀,直接一个一个往下比较即可,第一个比较第二个,用公共的前缀,再去和第三个比较。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return ""; // 特殊判定
// 此处其实也是特判,如果只有一个字符串,会将第一个return
string res = strs[0];
int index = 1;
while(index < strs.size()){ // 遍历数组中所有字符串
string tmp = strs[index].substr(0, res.length()); // 第一个字符串所有的均被放入缓存
//if(!strs[index].empty() && tmp.empty()) break;
if(tmp == res){ // 缓存和结果对比,如果相等,则继续对比下一个字符串
index++;
}else{ // 如果不相等,则将res的最后一位去掉,继续比较
/* 当去空的时候,res为空,res.length为0,导致获取的tmp也为空。所以循环结束。 */
res = res.substr(0,res.length() - 1);
}
cout << index << endl;
}
return res;
}
};

题目:最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例:

1
2
3
4
5
6
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

个人理解
最开始觉得就暴力法就行,后来学了一下,了解到动态规划。这很合理。
如果一个字符串为回文串,那他去掉两边肯定还是回文串。这就得到了一个动态规划方程:
res[i][j] = res[i+1][j-1]; 一步一步判断就完了。
反正动态规划好理解,实现复杂点,不懂的话需要多看看。

代码如下(C++):

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:
string longestPalindrome(string s) {
int len = s.size();
if(len <= 1) return s; // 如果长度小于等于1,返回自己
vector<vector<int>> res (len,vector<int>(len,0));
for(int i = 0; i < len; i++)res[i][i] = 1; // 给出对角条件
int start = 0;
int maxlength = 1;
for(int j = 1; j < len; j++){ // 从第一列开始扫描
for(int i = 0; i < j; i++){ // 只需要扫描上半部分
if(s[i] == s[j]){ // 两头相等
if(j-i < 3) res[i][j] = 1; // 如果长度为2或3,那肯定是回文串
else res[i][j] = res[i+1][j-1]; // 如果长度更长,那就看子串是不是
}
if(res[i][j]){ // 子串回文就更新最大长度
if(j-i+1 > maxlength){
maxlength = j-i+1; // 获取末尾索引
start = i; // 获取起始索引
}
}
}
}
return s.substr(start,maxlength); // 返回最长回文子串
}
};

题目:翻转字符串里的单词

给定一个字符串,逐个翻转字符串中的每个单词。

示例:

1
2
3
4
5
6
7
8
9
10
输入: "the sky is blue"
输出: "blue is sky the"

输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

个人理解
这个我先想到的就是用栈,遇到空格就把单词推入栈中,最后再推出来,加上空格即可。

代码如下(C++):

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:
string reverseWords(string s) {
int left = 0, right = s.size() - 1;
/* 删除两端空格 */
while(left <= right && s[left] == ' ') left++;
while(left <= right && s[right] == ' ') right--;
stack<string> st;
string word; // 缓存
while(left <= right){ // 遍历字符串
char c = s[left]; // 注意这里是char
if(!word.empty() && c == ' '){
st.push(word);
word = "";
}else if(c != ' ') word += c;
left++;
}
st.push(word); // 一定要记得加最后一个单词
string ans;
while(!st.empty()){ // 将字符串出栈
ans += st.top();
st.pop();
if(!st.empty()) ans += ' ';
}
return ans;
}
};

题目:实现 strStr()

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置(从 0 开始)。如果不存在,则返回-1。

示例:

1
2
3
4
5
输入: haystack = "hello", needle = "ll"
输出: 2

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

  • 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
  • 对于本题而言,当 needle 是空字符串时我们应当返回 0。这与 C 语言的 strstr()以及 Java 的 indexOf()定义相符。

个人理解
使用开窗法,用子串逐一比较,时间复杂度为线性。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int strStr(string haystack, string needle) {
int h_len = haystack.size(), n_len = needle.size();
if(n_len == 0) return 0; // 特殊判定
if(n_len > h_len) return -1;
for(int i = 0; i < h_len - n_len + 1; i++){ // 逐一匹配
if(haystack.substr(i,n_len) == needle) return i;
}
return -1;
}
};

声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~