2020-02-09 刷题 3（字符串）

344 反转字符串

用双指针原地反转，很简单

time: 30.43%, memory:8.04%
class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0, j = s.size() - 1;
        while(i < j){
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            i++;
            j--;
        }
    }
};

7 整数反转

标签：栈 字符串 溢出
这个题目是一个典型的用栈的题，如果不考虑整数溢出的话，是非常简单的。但是由于解题过程中各种溢出，调试了好久，提交四次才终于通过。。

最终没有用栈，而是用了string，因为string可以比较字符串大小。先将整数转换成字符串，由于问题性质，转换完就是反转的形式，然后定义一个“s=0000000000”字符串，将转换完成的字符串复制到s后面，这样，就可以跟“2147483647”以及“2147483648”比较了，大则溢出，返回0.
代码：

time:100%, memory:66.06%
class Solution {
public:
int reverse(int x) {
    if(x == 0) return x;
    bool is_neg = (x < 0);
    // x = abs(x); // 检查绝对值也会溢出，-2147483648时
    string cur_s, s = "0000000000";
    int idx = 0;
    while(x != 0){
        cur_s = cur_s + char(abs(x % 10) + '0');
        x = x / 10;
    }
    s.replace(10-cur_s.size(), cur_s.size()+1, cur_s);
    if((!is_neg && s > "2147483647") || (is_neg && s > "2147483648"))  // 判断是否溢出
        return 0;
    int i = s.size() - 1, m = 1;
    x = 0;
    while(i > 0){
        x += (s[i] - '0') * m;
        m *= 10;
        i--;
    }
    x += (s[0] - '0') * m;  // 最后一次放在循环里会溢出
    if (is_neg) x *= -1;
    return x;
}
};

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

标签：哈希表，字符串
还是用哈希表，只不过由于哈希表不是有序的，第二次遍历的时候，需要选择下标最小的数，作为第一个唯一字符的下标。
代码：

time: 22.44%, memory:5.01%
class Solution {
public:
    int firstUniqChar(string s) {
        map<char, int> char_map;
        for(int i = 0; i < s.size(); i++){
            if(char_map.count(s[i]) == 0) char_map[s[i]] = i;
            else{
                char_map[s[i]] = -1;
            }
        }
        map<char, int>::iterator iter;
        int idx = s.size();
        for(iter = char_map.begin(); iter != char_map.end(); iter++){
            if(iter->second != -1) {
                if(iter->second < idx) idx = iter->second;
            }
        }
        if(idx >= 0 && idx < s.size()) return idx;
        return -1;
    }
};