LeetCodeDay07 —— 反转整数&字符串中的第一个唯一

7. 反转整数

描述

• 给定一个 32 位有符号整数，将整数中的数字进行反转。

示例

示例 1:
  输入: 123
  输出: 321
示例 2:
  输入: -123
  输出: -321
示例 3:
  输入: 120
  输出: 21

注意

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

思路

1. 将整数转换为字符串数组，然后依次反转。最后将反转完成的字符串转回成数字，并判断其范围是否溢出。
2. 思路想出来比较容易，但是编码的过程中会发现有些东西和预想的不一样
   (1) 正数在转为字符串的过程中是按低位push_back，此过程本身就对字符串完成了一次revers的操作；
   (2) 每个数字在被摘出来的过程中就已经是带符号了的，如-321%10 = -1,因此不必在转换回去的时候特别考虑正负数的问题。
3. 有点被字符串这个专题误导了，其实这题不一定要利用字符串实现，按低位摘除，在按高位加上去其实就可以了，改进了一个LeetCode上的优秀解，利用了一些宏定义，值得学习。

class Solution_07_01 {
 public:
  int reverse(int x) {
    string s = IntToString(x);
    bool isNegative = (x < 0);
    return StringToInt(s, isNegative);
  }
  string IntToString(int x) {
    string str;
    while (x != 0) {
      str.push_back(x % 10);
      x /= 10;
    }
    return str;
  }
  int StringToInt(string str, bool isNegative) {
    long num = 0;
    for (char ch : str) {
      num = num * 10 + (ch - '0');
    }
    if (isNegative) {
      num = 0 - num;
    }
    if (num > (exp2(31) - 1) || num < -(exp2(31))) {
      num = 0;
    }
    return num;
  }
};

class Solution_07_02 {
 public:
  int reverse(int x) {
    int64_t num = 0;
    while (x != 0) {
      num = num * 10 + x % 10;
      x = x / 10;
    }
    return (num > INT32_MAX || num < INT32_MIN) ? 0 : num;
  }
};

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

描述

• 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回
  -1。

示例

  s = "leetcode", 返回 0.
  s = "loveleetcode", 返回 2.

注意

• 您可以假定该字符串只包含小写字母。

思路

1. 遍历两次，第一次建立字符出现次数的Map，第二次找到第一个次数为1的字符。空间换时间。
2. 优化点
   (1) 因为字符的ACII码是连续的，所以可以将Map改为Vector，将字符的ACII码对应数组的小标，Val则是出现的次数。
   (2) 可以利用一个指针指向当前第一个唯一的字符，这样可以边索引边查找唯一字符，只需遍历一遍。
   0420：其实本质上也是遍历了两次，一次字符串，一次Hash表，不过整体看来会比第一种思路少遍历几次。其核心思想是“一个字符一旦不是唯一的，则它永远不会再有机会成为唯一”

class Solution_387_01 {
 public:
  int firstUniqChar(string s) {
    unordered_map<char, int> hash;
    for (char ch : s) {
      ++hash[ch];
    }
    int index = 0;
    for (char ch : s) {
      if (hash[ch] == 1) return index;
      ++index;
    }
    return -1;
  }
};

class Solution_387_02 {
 public:
  int firstUniqChar(string s) {
    int hash[26] = {0};  // 假定出现的字符全是小写字母
    int pos = 0;
    for (int i = 0; i < s.length(); ++i) {
      hash[s[i] - 'a']++;
      while (pos < s.length() &&
             hash[s[pos] - 'a'] >
                 1) {  // pos 永远指向当前(所遍历过的字符中)第一个唯一的字符
        pos++;
      }
    }
    return pos < s.length() ? pos : -1;
  }
};