串_数据结构
Index
- 知识点
- 进制转换
- 字符串大小写转换
- 括号的生成
- 电话号码对应字符的集合
- 无效的括号
- 把顺序不同的元素集中起来# Group Anagrams
- 有效的最长的括号 #Longest Valid Parentheses
- 二进制字符串相加 #Add Binary
知识点
0.注意区分char和string
char叫字符类型，一般用单引号'a'来表示；string叫字符串类型，一般用双引号"abcd"来表示
可以利用char[]来表示字符数组。string只是一个模板template或者说是一个容器。
重要的一点是，char表示的字符可以和其他数据类型直接进行转换int,因为char存储的内容是ASCII码。
1.python中字符串也是可以实现 str.pop()操作
2.C++中，对于“vector string ans {}; 整个vector可以进行 ans.size(）， 对于其中的每个元素也可以实现 ans[i].size()”
3.注意字符串会有有"\0"的位置。位于字符串的尾部，要注意内外内存开销，防止字符串的越界。
进制转换
10进制转任意进制
from string import digits, ascii_uppercase, ascii_lowercase
Alphabet = digits + ascii_lowercase + ascii_uppercase
print(Alphabet) # "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"递归方法
def ten2any(n, b=62):
""""""
assert b <= 62
n, index = divmod(n, b) # n = n // b, index = n % b
if n > 0:
return ten2any(n, b) + Alphabet[index]
else:
return Alphabet[index]迭代方法
def ten2any_2(n, b=62):
""""""
ret = ""
while n > 0:
n, index = divmod(n, b)
ret = Alphabet[index] + ret
return ret任意进制转10进制
迭代方法
from string import digits, ascii_uppercase, ascii_lowercase
Alphabet = digits + ascii_lowercase + ascii_uppercase
print(Alphabet) # "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def any2ten(s, base=62):
""""""
n = 0
for i, c in enumerate(reversed(s)): # reversed(s)
index = Alphabet.index(c)
n += index * pow(base, i)
return n
大小写转换
// 使用范围for语句改变字符串中的字符
string str("Hello,World!!!!");
for(auto & c:str)
c=tolower(c);
count<<s<<endl;class solution{
public:
string to_lower_case(string str){
char cstr[str.size()+1];
for(int i=0;i<str.size();i++){
int c=str[i];
if(c<="Z" && c>="A")
cstr[i]=int("a")-int("A")+c;
else
cstr[i]=str[i];
}
return cstr;
}
};
Generate Parentheses
// 我一开始的想法是利用两个栈进行存储半边括号，但是对于出栈的顺序以及个数有很大的问题，特别是对于出栈的个数
//别人的代码考虑使用递归函数来进行解决
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
int l,r=0;
string s;
parenthesis(s,result,0,0,n);//调用一个辅助函数
return result;
}
private:
void parenthesis(string s,vector<string>&result,int l,int r,int n){//主要是要进行深度递归
if(r==n)
result.push_back(s);
else if(l==n){
s+=')';
parenthesis(s,result,l,r+1,n);
}
else {
if(l>r)
parenthesis(s+')',result,l,r+1,n); // 注意不可能出现l<r的情况出现 这个要注意 无非就是l=r 或者l>r
parenthesis(s+'(',result,l+1,r,n);
}
}
};
电话号码对应的字符
// 这个一段很好的代码
// 充分考虑到代码的鲁棒性，以及边界条件的检测
// 主要考虑到vector<string>与其中元素的对比
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(digits.empty())
return vector<string>();
vector<string> result;
result.push_back("");
static const vector<string> v={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
for(int i=0;i<digits.size();i++){
int index=digits[i]-'0';
// determind the index value is legal
if(index<0 || index>9)
break;
const string &candidate=v[index];
// determind the string is correct
if(candidate.empty())
continue;
vector<string> tmp;
for(int j=0;j<candidate.size();j++)
for(int k=0;k<result.size();k++)
tmp.push_back(result[k]+candidate[j]);
// 交换临时变量给结果
// 不能用push_back（tmp）,tmp也是vector<string>
result.swap(tmp);
}
return result;
}
};
20.valid parentheses
// 自己的想法就是利用栈来实现
// 这个程序的错误是 runtime error
// 可能就是栈的定义？出栈元素与当前元素相对比的判断出了一点问题
class Solution {
public:
bool isValid(string s) {
if(s.size()==0)
return false;
stack<char> store;
for(int i=0;i<s.size();i++){
if(s[i]=='[' || s[i]=='(' || s[i]=='{')
store.push(s[i]);
while(s[i]==']'){
if (store.empty())
return false;
char tmp=store.top();
store.pop();
if(tmp!='[')
return false;
if(tmp=='[' && store.empty())
return true;
}
while(s[i]==')'){
if (store.empty())
return false;
char tmp=store.top();
store.pop();
if(tmp!='(')
return false;
if(tmp=='(' && store.empty())
return true;
}
while(s[i]=='}'){
if (store.empty())
return false;
char tmp=store.top();
store.pop();
if(tmp!='{')
return false;
if(tmp=='{' && store.empty())
return true;
}
}
}
};
// 改进版本使用stack来存储元素
class Solution {
public:
bool isValid(string s) {
if(s.size()==0)
return true;
stack<char> store;
for(int i=0;i<s.size();i++){
if(s[i]=='[' || s[i]=='(' || s[i]=='{')
store.push(s[i]);
else{
if(store.empty()) return false;
char tmp=store.top();
if(s[i]==']'&& tmp!='[')
return false;
if(s[i]==')'&& tmp!='(')
return false;
if(s[i]=='}'&& tmp!='{')
return false;
store.pop();
}
}
if(store.size()>0)
return false;
return true;
}
};
//使用vector来模拟栈，实现栈的功能。
// 这个版本的好处就是 vector要比实现stack的效率高很多
class Solution {
public:
/*
题意：输入一个只包含括号的字符串，判断括号是否匹配
模拟堆栈，读到左括号压栈，读到右括号判断栈顶括号是否匹配
*/
bool isValidParentheses((string s) {
int len = s.length();
vector<char> stack;
for (int i = 0; i < len; i++) {
// 左括号压栈
if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack.push_back(s[i]);
else {
// 右括号出栈
if (stack.empty()) return false;
char top = stack[stack.size() - 1];
if (s[i] == ')' && top != '(')
return false;
if (s[i] == ']' && top != '[')
return false;
if (s[i] == '}' && top != '{')
return false;
stack.pop_back();
}
}
// 栈中无多余左括号
if (stack.size() > 0) return false;
return true;
}
};
49.Group Anagrams
//关联容器的基本结构及操作需要补充
//这是一道很漂亮的题
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,multiset<string>> mp;
// 关联容器的插入
for(auto s:strs){
string tmp=s;
sort(tmp.begin(),tmp.end()); // string tmp=strSort(s); 结合private函数实现
mp[tmp].insert(s);
}
// 关联容器vlaue值的读取
vector<vector<string>> anagrams;
for(auto m:mp){
vector<string> anagram(m.second.begin(),m.second.end());
anagrams.push_back(anagram);
}
return anagrams;
}
};
// 还有一个非常重要的函数
// 实现字符串的顺序输出
private:
string strSort(string& s) {
int count[26] = {0}, n = s.length();
for (int i = 0; i < n; i++)
count[s[i] - 'a']++;
int p = 0;
string t(n, 'a');
for (int j = 0; j < 26; j++)
for (int i = 0; i < count[j]; i++)
t[p++] += j;
return t;
}
32.Longest Valid Parentheses
//考虑错误版本，这个有效括号是连续的
//这个是非连续版本
class Solution {
public:
int longestValidParentheses(string s) {
if(s.size()<2)
return 0;
stack<char> store;
int num=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
store.push(s[i]);
}
else{
if(!store.empty()){
char tmp=store.top();
if (tmp=='('){
store.pop();
num=num+2;
}
}
else
continue;
}
}
return num;
}
};
//另一种解题的思路
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1);
int maxL=0;
for(int i=0;i<s.size();i++)
{
int t=stk.top();
if(t!=-1&&s[i]==')'&&s[t]=='(')
{
stk.pop();
maxL=max(maxL,i-stk.top());
}
else
stk.push(i);
}
return maxL;
}
};
Add Binary
// 这一种解法就是需要硬记住的
// 不行就给背下来
class Solution
{
public:
string addBinary(string a, string b)
{
string s = "";
int c = 0, i = a.size() - 1, j = b.size() - 1;
while(i >= 0 || j >= 0 || c == 1)
{
c += i >= 0 ? a[i --] - '0' : 0;
c += j >= 0 ? b[j --] - '0' : 0;
s = char(c % 2 + '0') + s; // 确定char 是1还是0
c /= 2; // 把进数进行确定，是否进1
}
return s;
}
};
CVTE公司福利 264人发布
投递完美世界等公司10个岗位 >
