8.23刷题题解代码

202 快乐数

class Solution {
public:
    bool isHappy(int n) {
        set<int> rec;
        int sum=digitalSum(n);
        while(rec.find(sum)==rec.end()){
            rec.insert(sum);
            if(sum==1)
                return true;
            sum=digitalSum(sum);
        }
        return false;
    }
private:
    int digitalSum(int n){
        int sum=0;
        while(n!=0){
            int data=n%10;
            sum+=data*data;
            n/=10;
        }
        return sum;
    }
};

205 同构字符串

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> s1=transeStr(s);
        vector<int> s2=transeStr(t);
        int n=s1.size();
        if(n!=s2.size())
            return false;
        for(int i=0;i<n;i++){
            if(s1[i]!=s2[i])
                return false;
        }
        return true;
    }
private:
    vector<int> transeStr(string s){
        vector<int> ret; 
        if(s.empty())
            return ret;
        map<int,int> rec;
        int val=1;
        for(int i=0;i<s.size();i++){
            if(rec.find(s[i])==rec.end())
                rec.insert(make_pair(s[i],val++));                
            ret.push_back(rec[s[i]]);
            
        }
        return ret;
    }
    

};

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int n=s.size();
        if(n!=t.size())
            return false;
        
        map<char,char> rec;
        set<char> val;
        for(int i=0;i<n;i++){
            if(rec.find(s[i])==rec.end()){
                if(val.find(t[i])!=val.end())
                    return false;
                rec.insert(make_pair(s[i],t[i]));
                val.insert(t[i]);
            }
            else{
                if(rec[s[i]]!=t[i])
                    return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int map[256];
        memset(map,-1,sizeof(map));
        int mapped[256];
        memset(mapped,false,sizeof(mapped));
        
        int n=s.size();
        for(int i=0;i<n;i++){
            if(map[s[i]]==-1){
                if(mapped[t[i]]==true)
                    return false;
                map[s[i]]=t[i];
                mapped[t[i]]=true;
            }
            else{
                if(map[s[i]]!=t[i])
                    return false;
            }
        }
        return true;
    }
};

思路总结：
第1种，把字符串转换成了数组，通过比较数组是否相等来判断字符串是否同构
第2种，利用map表直接映射2个字符串，把第一个字符串相应位置的值映射到第2个字符串中，需要注意的是要求映射为一一对应的关系，即第一个字符串中不能有2个不同的字符映射到第二个字符串中同一个字符上（设计了一个map容器存储映射关系，一个set容器存储是否已被映射）
第3种是第2种的数组实现，相当于利用2个简单数组来替代了第2种解法中的2个容器的作用

242 有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int n=s.size();
        if(n!=t.size())
            return false;
        int rec[256];
        memset(rec,0,sizeof(rec));
        
        for(int i=0;i<n;i++){
            rec[s[i]]++;
            rec[t[i]]--;
        }
        for(int i=0;i<256;i++)
            if(rec[i]!=0)
                return false;
        
        return true;         
       
        
    }
};

290单词规律

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<char,string> rec;
        set<string> val;
       
        vector<string> s=split(str);
        int n=s.size();
        if(n!=pattern.size())
            return false;
        
        for(int i=0;i<n;i++){
            if(rec.find(pattern[i])==rec.end()){
                if(val.find(s[i])!=val.end())
                    return false;
                rec.insert(make_pair(pattern[i],s[i]));
                val.insert(s[i]);
            }
            else{
                if(rec[pattern[i]]!=s[i])
                    return false;
            }
        }
        return true;
    }
private:
    vector<string> split(string str){
        vector<string> ret;
        if(str.empty())
            return ret;
        int start=0;
        for(int i=0;i<=str.size();i++){
            if(i==str.size()||str[i]==' '){
                ret.push_back(str.substr(start,i-start));
                start=i+1;                
            }        
       }
        return ret;
    }
};

思路：
cpp中没有split字符串的方法，自己实现了一个，要记住。
利用了一个map表实现了二者的映射关系，又利用了一个set容器记录了后者是否已经被前者映射过，因为要求一一对应

415 两个字符串相加

class Solution {
public:
    string addStrings(string num1, string num2) {
        num1=reverse(num1);
        num2=reverse(num2);
        int n1=num1.size();
        int n2=num2.size();
        int i=0,carry=0;
        string ret;
        int n=n1>n2?n1:n2;
        while(i<n){      
            int d1=i<n1?num1[i]-'0':0,d2=i<n2?num2[i]-'0':0;
            int sum=d1+d2+carry;
            if(sum>9){
                carry=1;
                sum%=10;
            }
            else
                carry=0;
            ret+=to_string(sum);
            i++;
        }
       if(carry==1)
           ret+='1';
        return reverse(ret);
        
    }
private:
    string reverse(string &str){
        int n=str.size();
        for(int i=0;i<n/2;i++){
            swap(str[i],str[n-1-i]);
        }
        return str;
    }
};

思路：
相当于是大数加法的解决思路，难点在于最高位的处理，若单独处理情况比较多，因此放一起处理。

使用了翻转字符串的子方法，翻转后，2个字符串都是从低位加起，方便运算

2个字符串的长度可能不相等，因此取长度最大值为基准，每次取数时，判断一下是否越界，越界则取0，求和时记得进位符也要相加

最后求和完以后，还要注意一下进位符

另外本算法有副作用，会对输入的两个str进行翻转