字符串
字符串是一个由字符构成的数组。
之后深入研究字符串,需要掌握如下知识点:
- 熟悉字符串中的基本操作,尤其是在数组中没有的独特操作;
- 理解不同比较函数之间的区别;
- 理解字符串是否可变以导致连接过程中出现的问题;
- 能够解决与字符串相关的基本问题,如排序、子串、字符串匹配等;
字符串简介
维基百科:字符串是由零个或多个字符组成的有限序列。一般记为 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 ""; string res = strs[0]; int index = 1; while(index < strs.size()){ string tmp = strs[index].substr(0, res.length()); if(tmp == res){ index++; }else{ 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; 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; 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]; 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; } };
|
声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除。