【daily leetcode】20191021

目标：字符串初级入门

344 反转字符串【 void reverseString(vector<char>& s) 】
7 整数反转【int reverse(int x) 】
387 字符串的第一个唯一字符【 int firstUniqChar(string s)】
24 有效的字母异位词【bool isAnagram(string s, string t)】
125 验证回文字符串【 bool isPalindrome(string s) 】
8 字符串转换整数【int myAtoi(string str)】
28 实现strStr() 【int strStr(string haystack, string needle)】
报数【未完成】
最前公共前缀【未完成】
93 复原IP地址【vector<string> restoreIpAddresses(string s)】
错误整理

344.反转字符串 reverse string

首位双指针交换
注意传入的参数是 vector<char> 最后一个为\0

class Solution {
public:
    void reverseString(vector<char>& s) {
        
        int left = 0 ;
        int right = s.size()-1;
        
        while(left < right){
            char temp = s[right];
            s[right] = s[left];
            s[left] =temp; 
            left++;
            right--;
        }
    }
};

7.整数反转

每次取出最后一位和累计值相加

pop operation:
pop = x % 10;
x /= 10;
push operation:
rev = rev * 10 + pop;

每次相加前判断是否有溢出

2^31-1=2147483647
-2^31= -2147483648

如123 ， 0 x 3+3 =3 ，3 x 10+2 =32 ， 32 x 10+1 =321

class Solution {
public:
    int reverse(int x) {
        int rev =0;
        while(x != 0){
            int pop = x%10;
            x/=10;
            if(rev > INT_MAX/10 || ( rev == INT_MAX/10 && pop > 7 )) 
               return 0;
//如果不知道7 怎么算出来 
// if(rev > INT_MAX/10 || ( rev == INT_MAX/10 && pop > INT_MAX %10 )) 
            if(rev < INT_MIN/10 || ( rev == INT_MIN/10 && pop < -8))
                return 0;
            rev = rev*10 + pop;
        }
        return rev;
    }
};

// 2^31-1=2147483647
//-2^31=-2147483648

387. 字符串中的第一个唯一字符

哈希表第一次遍历记录每个字符出现的次数
第二次变量找出现次数为1 的字符

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> hash;
        for(char x : s){
            hash[x]++ ;
        }
        for(int i = 0; i < s.size(); i++){
            if(hash[s[i]] == 1)
                return i;
        }
        return -1;
        
    }
};

24.有效的字母异位词

什么是异位词长度相同字母出现次数相同但位置不一定一样

哈希映射##

首先判断两个字符串长度是否相等，不相等则直接返回 false
若相等，遍历字符串 s 和 t.初始化 26 个字母哈希表，
s 负责在对应位置的次数增加，t 负责在对应位置次数减少
s和t遍历结束后，遍历哈希表的值若都为 0，则二者是字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        
        if(s.size() != t.size()) return false;
        
        int hash[26] = {0};
        for(int i= 0 ; s[i] != '\0'; i++){
            hash[s[i]-'a'] ++;
            hash[t[i]-'a'] --;
        }
        
        for(auto x : hash){
            if(x != 0) return false;
        }
        
        return true;
    }
};

125.验证回文字符串

只考虑字符和数字
忽略大小写

在相同字母的大小写的二进制表示里，只有第5位不同，异或32可以起到只改变第5位的效果，从而实现大小写的转化。
只是改变第五位的效果

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        while(i < j) {
            while(i < j && !check(s[i])) i++; // 找到数字或者字符
            while(i < j && !check(s[j])) j--;
            if(s[i] != s[j] && s[i] != (s[j]^32))  return false;
            i++;
            j--;
        }
        return true;
    }
    
    bool check(char c){
        return c >= '0' && c <= '9' || c >='a' && c <='z' || c >= 'A' && c <= 'Z';
    }

};

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        while(i < j) {
            while(i < j && !check(s[i])) i++;
            while(i < j && !check(s[j])) j--;
            // if(s[i] != s[j] && s[i] != (s[j]^32))  return false;
            if(s[i] != s[j] )  {
                if (isdigit(s[i]) || isdigit(s[j])) return false;  // 如果有一个是数字的话 就直接返回、
      //都是数字的话才进行比较
                if (s[i] > s[j] &&  s[i]-s[j] !=32)
                    return false;
                if (s[i] < s[j] && s[j]-s[i] !=32)
                    return false;
            }
            
            i++;
            j--;
        }
        return true;
    }
    
    bool check(char c){
        return c >= '0' && c <= '9' || c >='a' && c <='z' || c >= 'A' && c <= 'Z';
    }

};

8.字符串转换整数

找到第一个非空字符进行判断

对非空字符的判断 //

若为 ‘+’ '- ' 进行特殊处理
若为其他如果符合数字的条件就相加

class Solution {
public:
    int myAtoi(string str) {
        long long res = 0;
        int minus = 1;
        int k = 0;
        while(k < str.size() && (str[k] == ' ' || str[k] == '\t')) k++; //定位第一个非空字符
        
        if(k >= str.size()) return 0; 
        
        if(str[k] == '-') minus=-1, k++;
        
        if(str[k] == '+') {
            if(minus == -1) return 0;
            else k++;     
        }
        // 对 + - 特殊处理
        while(str[k] >= '0' && str[k] <= '9')
        {
            res = res*10 + str[k] - '0';
            k++;
            if(res > INT_MAX) break;
        }
        
        res *= minus;
        if(res > INT_MAX) return INT_MAX;
        if(res < INT_MIN) return INT_MIN;
        
        return res;
   
    }
       
};

28.实现strStr

暴力枚举
注意外层和内层循环的循环退出的条件

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        
        for(int i = 0; i < n-m+1; i++){
            bool find = true;
             for(int j = 0; j < m; j++ ){
                if( haystack[i+j] != needle[j] ) {
                    find = false;
                    break; 
                }       
            }
            if(find)  return i;
        }
        
        return -1;
    }
};

93 .复原IP地址

回溯与递归

class Solution {
public:
    vector<string> res;
    
    vector<string> restoreIpAddresses(string s) {
        string temp;
        dfs(s,temp,0);
        return res;
    }
    
    void dfs(string s, string &temp, int word_num){
        if(word_num == 4){
            if(s.empty()) 
                res.push_back(temp);
        }
        else{
            if(word_num > 0) temp += '.';
            for(int i = 1; i <= 3 && i <= s.size(); i++){
                if(valid(s.substr(0,i))) {
                    temp += s.substr(0,i);
                    dfs(s.substr(i,s.length()-i),temp,word_num+1);
                    temp.erase(temp.length()-i,i);
                }
            }
            temp.pop_back();
        }
    }
    
    bool valid(const string &s){
        if(s.empty() || (s[0] == '0' && s.size() >1) )
            return false;
        //空串 或者 有前导0的情况
        int val = stoi(s);
        if(val >= 0 && val <= 255)
            return true;
        
        return false;
    }
};

错误整理

实现strStr

image.png