刷题记录(初级算法-字符串篇)
[TOC]
反转字符串
和vector同样的进行swap交换就可以了
class Solution {
public:
string reverseString(string s) {
if (s.size()==0||s.size()==1) return s;
int first=0,second=s.size()-1;
while(first<second)
{
swap(s[first],s[second]);
first++;
second--;
}
return s;
}
};
虽然感觉很简单，但是网上还是有各种优秀的思路与代码（Java编写的）:
1.定义一个新的字符串，逆序遍历原来的字符串，然后输出
public static String strReverseWithReverseLoop(String string){
if(string==null||string.length()==0)return string;
StringBuilder sb = new StringBuilder();
for(int i = string.length()-1;i>=0;i--){
sb.append(string.charAt(i));
}
return sb.toString();
}
此外，可以使用栈，将字符串的每个字符都转化成char数组，再将数组中的字符一次亚茹栈中，将栈中的字符依次弹出赋值给char数组，因为栈有先进后出的原则，所以在弹出的时候就已经自动完成了逆序操作。
public static String strReverseWithStack(String string){
if(string==null||string.length()==0)return string;
Stack<Character> stringStack = new Stack<>();
char [] array = string.toCharArray();
for(Character c:array){
stringStack.push(c);
}
int length = string.length();
for(int i= 0;i<length;i++){
array[i] = stringStack.pop();
}
return new String(array);
}
颠倒整数
最初的想法是收到上一题的影响，想把int型转成string类型，然后操作string控制字符串颠倒，最后再转成int类型。但是这个思路最后却超出时间限制了，所以改成直接对int进行操作。代码如下：
class Solution {
public:
int reverse(int x) {
long long s=0;
while(x!=0)
{
s=s*10+x%10;
x=x/10;
}
if(s<INT_MIN||s>INT_MAX)
return 0;
else
return s;
}
};
字符串中的第一个唯一字符
想法是加一个计数器，两个for循环就应该可以搞定了。但是，又超时了......超时的代码如下:
class Solution {
public:
int firstUniqChar(string s) {
if(s.size()==0) return -1;
if(s.size()==1) return 0;
// for(int i=0;i<s.size();i++){
// int flag=0;
// for(int j=i+1;j<s.size();j++)
// {
// if(s[i]==s[j]) flag=1;
// }
// if(!flag) return i;
// }
// return -1;
for(int i=0;i<s.size();i++)
{
int count=0;
for(int j=0;j<s.size();j++)
{if(s[j]==s[i]) count++;}
if (count==1) return i;
}
return -1;
}
};
一般超时的话，就需要用到STL了，但是一时想不到什么样的库函数可以完成这个，然后去看了看大神的代码:用了map，代码如下:
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> m;
for(char c:s) ++m[c];
for(int i=0;i<s.szie();i++){
if(m[s[i]]==1) re
}
return -1;
}
};
有效的字母异位词
很简单，判断字母个数和字母一致就可以了:
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(),s.end());
sort(t.begin(),t.end());
if(s.size()==t.size())
{
for(int i=0;i<s.size();i++)
{
if(s[i]!=t[i]) return false;
}
return true;
}
return false;
}
};
验证回文字符串
开始的想法就是逐一进行判断，满足条件的就通过，不满足条件的就强行把它改成符合条件的，但是自己写的代码会报"内存冲突"的错误，没有解决。
class Solution {
public:
bool isPalindrome(string s) {
if (s.size()==0) return true;
string res="";
for(int i=0,j=0;i<s.size();i++,j++)
{
if(s[i]>'A'&&s[i]<'Z')
{
s[i]=s[i]-'A'+'a';
res[j]=s[i];
}
else if(s[i]>'a'&&s[i]<'z') res[j]=s[i];
else {
j--;
}
}
int first=0,second=res.size()-1;
while(first<second)
{
if(res[first]==res[second]) {first++;second--;}
else
return false;
}
return true;
}
};
网上看到一个版本:
class Solution {
public:
void makestring(string &s){
int l= s.length();
int k=0;
int i=0;
while(i<l){
if(s[i]>='0'&&s[i]<='9')s[i-k]=s[i];
else if(s[i]>='a'&&s[i]<='z')s[i-k]=s[i];
else if(s[i]>='A'&&s[i]<='Z')s[i-k]=s[i]-'A'+'a';
else k++;
i++;
}
s=s.substr(0,l-k);
}
bool isPalindrome(string s) {
makestring(s);
int l=s.length();
if(l<=1)return 1;
int i,j;
for(i=0,j=l-1;i<=j;i++,j--)
if(s[i]!=s[j])return 0;
return 1;
}
};
其中s=s.substr(0,l-k);这一行可以是非常机智了，substr从下标为0开始的s.size()-k个元素复制到原先的s中，这里的k是出现的标点符号的次数，由于前面已经执行了只要遇到标点符号(经人指出，这里用非字母比较妥当)就将这个符号利用后面的字母字符进行覆盖，所以最后前s.size()-k就是我们需要的字符串。
实现strStr()
这道题就是检验子字符串是否在母字符串中，我们不需要对母字符串每个字符进行遍历，而是遍历到剩下的字符长度为子字符串的长度即可；同时每次遍历都会遍历一遍子字符串，举个例子:比如hackstack="hello"，needle="ll"；我们可以将hello分成he、el、ll、lo，每个与ll进行比较。具体的字符检测为haystack[i+j]==needle[j]这行代码，完整代码如下:
class Solution {
public:
int strStr(string haystack, string needle) {
if(haystack.size()<needle.size()) return -1;
if(needle.empty()) return 0;
int h=haystack.size(),n=needle.size();
for(int i=0;i<=h-n;i++)
{
int j;
for(j=0;j<n;j++)
{
if(haystack[i+j]!=needle[j]) break;
}
if(j==n) return i;
}
return -1;
}
};
数数并说
这道题的逻辑性比较强，每一个循环是为了什么、如果没有这个循环又会达到什么样的效果都要弄得非常清楚才行。
比如while(i+1<res.size() && res[i]==res[i+1])这行代码，就是判断是否有连续相等的数字，如果有的话会计数加一并跳到下一个res[i]位。
class Solution {
public:
string countAndSay(int n) {
if(n<=0) return "";
string res="1";
while(--n)
{
string cur="";
for(int i=0;i<res.size();i++)
{
int cnt=1;
while(i+1<res.size() && res[i]==res[i+1])
{
cnt++;
i++;
}
cur=cur+std::to_string(cnt)+res[i];
}
res=cur;
}
return res;
}
};
最长公共前缀
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
string res="";
for(int i=0;i<strs[0].size();i++)
{
char c=strs[0][i];
for(int j=0;j<strs.size();j++)
{
if(i>=strs[i].size()||strs[j][i]!=c)
return res;
}
res.push_back(c);
}
return res;
}
};
字符串转整数(atoi)
这道题真的让我很恼火，我测试了自己能想到的正常情况，但想不到在提交时还是有各种测试用例没有通过。。。输入情况真的在做提前要好好思考一下，尤其是" 010"返回的是"10"这点要注意。
在这里贴出代码
class Solution {
/*
public:
int myAtoi(string str) {
int m=0,s=1;;
int flag=0;
for(int i=0;i<str.size();i++){
if(str[i]=='-') s=-1;
if((str[i]<'0'||str[i]>'9')&&flag==0)
{
i++;
flag=1;
}
if(str[i]>='0'&&str[i]<='9')
{
m=m*10+s*(str[i]-'0');
}
else if(flag==1)
{
break;
}
}
return m;
}*/
public:
int myAtoi(string str){
if(str.empty()) return 0;
int sign=1,base=0,i=0,n=str.size();
while(i<n && str[i]==' ') ++i;
if(str[i]=='+'||str[i]=='-')
{
sign=(str[i++]=='+')?1:-1;
}
while(i<n && str[i]>='0' && str[i]<='9')
{
if(base>INT_MAX/10 || (base==INT_MAX/10 && str[i]-'0'>7)){
return (sign==1)?INT_MAX:INT_MIN;
}
base =10*base +(str[i++]-'0');
}
return sign*base;
}
};
一个就是符号的判断，如果遇到+就返回正数，如果遇到-就返回负数，最后在结果上乘上相应的符号就可以了。
同时因为INT_MAX的值为 INT_MAX（2147483647）】 INT_MIN（-2147483648），所以为了预防在处理中超出界限，必须加上判断语句，如果下一次的操作一定会导致出界，就返回最大值即可。
通过这个题，我们也可以知道while与数组a[i++]的联合使用确实比for更为灵活些，在while里可以处理更多操作。
