STL String
https://stackoverflow.com/questions/1466073/how-is-stdstring-implemented
earse
Erase characters from string
sequence (1)
string& erase (size_t pos = 0, size_t len = npos);
character (2)
iterator erase (const_iterator p);
range (3)
iterator erase (const_iterator first, const_iterator last);
// string::erase
#include <iostream>
#include <string>
int main ()
{
std::string str ("This is an example sentence.");
std::cout << str << '\n';
// "This is an example sentence."
str.erase (10,8); // ^^^^^^^^
std::cout << str << '\n';
// "This is an sentence."
str.erase (str.begin()+9); // ^
std::cout << str << '\n';
// "This is a sentence."
str.erase (str.begin()+5, str.end()-9); // ^^^^^
std::cout << str << '\n';
// "This sentence."
return 0;
}
//Result
This is an example sentence.
This is an sentence.
This is a sentence.
This sentence.
insert
这个里面需要注意的是对于字符的插入和对于字符串的插入,采用的不同的传参,对于字符的插入,可以使用iterator来进行。
string (1) //Inserts a copy of str.
string& insert (size_t pos, const string& str);
substring (2)
//Inserts a copy of a substring of str. The substring is the portion of str that
//begins at the character position subpos and spans sublen characters
//(or until the end of str, if either str is too short or if sublen is npos).
string& insert (size_t pos, const string& str, size_t subpos, size_t sublen);
c-string (3)
string& insert (size_t pos, const char* s);
buffer (4)
string& insert (size_t pos, const char* s, size_t n);
fill (5)
string& insert (size_t pos, size_t n, char c);
iterator insert (const_iterator p, size_t n, char c);
single character (6)
iterator insert (const_iterator p, char c);
range (7)
template <class InputIterator>
iterator insert (iterator p, InputIterator first, InputIterator last);
initializer list (8)
string& insert (const_iterator p, initializer_list<char> il);
Replace
find
匹配第一个符合规定的子串
string (1)
size_t find (const string& str, size_t pos = 0) const noexcept;
c-string (2)
size_t find (const char* s, size_t pos = 0) const;
buffer (3)
size_t find (const char* s, size_t pos, size_type n) const;
character (4)
size_t find (char c, size_t pos = 0) const noexcept;
Split String
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
/*
std::string split implementation by using delimiter as a character.
*/
std::vector<std::string> split(std::string strToSplit, char delimeter)
{
std::stringstream ss(strToSplit);
std::string item;
std::vector<std::string> splittedStrings;
while (std::getline(ss, item, delimeter))
{
splittedStrings.push_back(item);
}
return splittedStrings;
}
/*
std::string split implementation by using delimeter as an another string
*/
std::vector<std::string> split(std::string stringToBeSplitted, std::string delimeter)
{
std::vector<std::string> splittedString;
int startIndex = 0;
int endIndex = 0;
while( (endIndex = stringToBeSplitted.find(delimeter, startIndex)) < stringToBeSplitted.size() )
{
std::string val = stringToBeSplitted.substr(startIndex, endIndex - startIndex);
splittedString.push_back(val);
startIndex = endIndex + delimeter.size();
}
if(startIndex < stringToBeSplitted.size())
{
std::string val = stringToBeSplitted.substr(startIndex);
splittedString.push_back(val);
}
return splittedString;
}
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
/*
std::string split implementation by using delimeter as a character.
*/
std::vector<std::string> split(std::string strToSplit, char delimeter)
{
std::stringstream ss(strToSplit);
std::string item;
std::vector<std::string> splittedStrings;
while (std::getline(ss, item, delimeter))
{
splittedStrings.push_back(item);
}
return splittedStrings;
}
/*
std::string split implementation by using delimeter as an another string
*/
std::vector<std::string> split(std::string stringToBeSplitted, std::string delimeter)
{
std::vector<std::string> splittedString;
int startIndex = 0;
int endIndex = 0;
while( (endIndex = stringToBeSplitted.find(delimeter, startIndex)) < stringToBeSplitted.size() )
{
std::string val = stringToBeSplitted.substr(startIndex, endIndex - startIndex);
splittedString.push_back(val);
startIndex = endIndex + delimeter.size();
}
if(startIndex < stringToBeSplitted.size())
{
std::string val = stringToBeSplitted.substr(startIndex);
splittedString.push_back(val);
}
return splittedString;
}
int main()
{
std::string str = "Lets split this line using split functions";
// Spliting the string by ''
std::vector<std::string> splittedStrings = split(str, ' ');
for(int i = 0; i < splittedStrings.size() ; i++)
std::cout<<splittedStrings[i]<<std::endl;
// Spliting the string by an another std::string
std::vector<std::string> splittedStrings_2 = split(str, "split");
for(int i = 0; i < splittedStrings_2.size() ; i++)
std::cout<<splittedStrings_2[i]<<std::endl;
return 0;
}
Reverse String
Using Build-in Function
#include <iostream>
//The library below must be included for the reverse function to work
#include<bits/stdc++.h>
using namespace std;
int main() {
string greeting = "Hello";
//Note that it takes the iterators to the start and end of the string as arguments
reverse(greeting.begin(),greeting.end());
cout<<greeting<<endl;
}
String lower and upper
int toupper (int c);
std::string data = "This is a sample string.";
// convert string to upper case
std::for_each(data.begin(), data.end(), [](char & c){
c = ::toupper(c);
});
int tolower (int c);
std::string data = "THIS IS A SAMPLE STRING.";
// convert string to back to lower case
std::for_each(data.begin(), data.end(), [](char & c){
c = ::tolower(c);
});
#include <iostream>
#include <string>
#include <algorithm>
int main() {
std::string data = "This is a sample string.";
// convert string to upper case
std::for_each(data.begin(), data.end(), [](char & c) {
c = ::toupper(c);
});
std::cout << "In Upper Case : " << data << std::endl;
// convert string to back to lower case
std::for_each(data.begin(), data.end(), [](char & c) {
c = ::tolower(c);
});
std::cout << "In Lower Case : " << data << std::endl;
}
// In Upper Case : THIS IS A SAMPLE STRING.
// In Lower Case : this is a sample string.
Example
Leetcode 125 Valid Palindrome
Reverse String & String lower and upper
- Valid Palindrome Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose of this problem, we define empty string as valid palindrome. Example 1: Input: “A man, a plan, a canal: Panama” Output: true
Example 2:
Input: “race a car”
Output: false
Constraints:
s
consists only of printable ASCII characters.
class Solution {
public:
bool isPalindrome(string s) {
string news;
for(auto &ch : s)
{
if((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
news += tolower(ch);
}
s = news;
reverse(news.begin(), news.end());
return s == news;
}
};
Leecode9 回文数
9. 回文数
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。
示例 1:
输入:x = 121
输出:true
示例 2:
输入:x = -121
输出:false
解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入:x = 10
输出:false
解释:从右向左读, 为 01 。因此它不是一个回文数。
示例 4:
输入:x = -101
输出:false
提示:
-231 <= x <= 231 - 1
进阶:你能不将整数转为字符串来解决这个问题吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
bool isPalindrome(int x) {
string tmp = to_string(x);
string rev = tmp;
reverse(rev.begin(), rev.end());
return tmp == rev;
}
};
Leetcode 22 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2:
输入:n = 1
输出:[“()”]
提示:
1 <= n <= 8
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
采用emplace_back可以加快整体的速度
class Solution {
public:
map<int, vector<string>>dict;
vector<string> generateParenthesis(int n) {
vector<string>ret;
if(n <= 0)
return ret;
if(n == 1)
{
ret.emplace_back("()");
return ret;
}
if(dict.find(n) != dict.end())
return dict[n];
for(int i = 0; i < n; i++)
{
vector<string>part1 = generateParenthesis(i);
vector<string>part2 = generateParenthesis(n - 1 - i);
if(part1.size() != 0)
{
string tmp;
for(auto &str : part1)
{
tmp = "(" + str + ")";
if(part2.size() != 0)
{
for(auto &str1 : part2)
{
ret.emplace_back(tmp + str1);
}
}
else
{
ret.emplace_back(tmp);
}
}
}
else
{
for(auto &str : part2)
ret.emplace_back("()" + str);
}
}
dict[n] = ret;
return ret;
}
};
如果只是计算数量的话,可以采用如下动态规划法
int generateParenthesis(int n) {
vector<int>dp(n+1);
dp[0] = 1;
dp[1] = 1;
for(int num = 2; num <= n; num++)
{
for(int inside = 0; inside < num; inside++)
{
dp[num] += dp[inside] * dp[num - inside - 1];
}
}
return dp[n];
}