7. 反转整数
描述
- 给定一个 32 位有符号整数，将整数中的数字进行反转。
示例
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
思路
- 将整数转换为字符串数组，然后依次反转。最后将反转完成的字符串转回成数字，并判断其范围是否溢出。
- 思路想出来比较容易，但是编码的过程中会发现有些东西和预想的不一样
(1) 正数在转为字符串的过程中是按低位push_back，此过程本身就对字符串完成了一次revers的操作；
(2) 每个数字在被摘出来的过程中就已经是带符号了的，如-321%10 = -1,因此不必在转换回去的时候特别考虑正负数的问题。 - 有点被字符串这个专题误导了，其实这题不一定要利用字符串实现，按低位摘除，在按高位加上去其实就可以了，改进了一个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.
注意
- 您可以假定该字符串只包含小写字母。
思路
- 遍历两次，第一次建立字符出现次数的Map，第二次找到第一个次数为1的字符。空间换时间。
- 优化点
(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;
}
};
