7. 反轉(zhuǎn)整數(shù)
描述
- 給定一個(gè) 32 位有符號(hào)整數(shù)，將整數(shù)中的數(shù)字進(jìn)行反轉(zhuǎn)。
示例
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位有符號(hào)整數(shù)，其數(shù)值范圍是 [?2^31, 2^31 ? 1]。根據(jù)這個(gè)假設(shè)，如果反轉(zhuǎn)后的整數(shù)溢出，則返回 0。
思路
- 將整數(shù)轉(zhuǎn)換為字符串?dāng)?shù)組，然后依次反轉(zhuǎn)。最后將反轉(zhuǎn)完成的字符串轉(zhuǎn)回成數(shù)字，并判斷其范圍是否溢出。
- 思路想出來(lái)比較容易，但是編碼的過(guò)程中會(huì)發(fā)現(xiàn)有些東西和預(yù)想的不一樣
(1) 正數(shù)在轉(zhuǎn)為字符串的過(guò)程中是按低位push_back，此過(guò)程本身就對(duì)字符串完成了一次revers的操作；
(2) 每個(gè)數(shù)字在被摘出來(lái)的過(guò)程中就已經(jīng)是帶符號(hào)了的，如-321%10 = -1,因此不必在轉(zhuǎn)換回去的時(shí)候特別考慮正負(fù)數(shù)的問(wèn)題。 - 有點(diǎn)被字符串這個(gè)專題誤導(dǎo)了，其實(shí)這題不一定要利用字符串實(shí)現(xiàn)，按低位摘除，在按高位加上去其實(shí)就可以了，改進(jìn)了一個(gè)LeetCode上的優(yōu)秀解，利用了一些宏定義，值得學(xué)習(xí)。
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. 字符串中的第一個(gè)唯一字符
描述
- 給定一個(gè)字符串，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引。如果不存在，則返回
-1。
示例
s = "leetcode", 返回 0.
s = "loveleetcode", 返回 2.
注意
- 您可以假定該字符串只包含小寫(xiě)字母。
思路
- 遍歷兩次，第一次建立字符出現(xiàn)次數(shù)的Map，第二次找到第一個(gè)次數(shù)為1的字符?？臻g換時(shí)間。
- 優(yōu)化點(diǎn)
(1) 因?yàn)樽址腁CII碼是連續(xù)的，所以可以將Map改為Vector，將字符的ACII碼對(duì)應(yīng)數(shù)組的小標(biāo)，Val則是出現(xiàn)的次數(shù)。
(2) 可以利用一個(gè)指針指向當(dāng)前第一個(gè)唯一的字符，這樣可以邊索引邊查找唯一字符，只需遍歷一遍。
0420：其實(shí)本質(zhì)上也是遍歷了兩次，一次字符串，一次Hash表，不過(guò)整體看來(lái)會(huì)比第一種思路少遍歷幾次。其核心思想是“一個(gè)字符一旦不是唯一的，則它永遠(yuǎn)不會(huì)再有機(jī)會(huì)成為唯一”
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}; // 假定出現(xiàn)的字符全是小寫(xiě)字母
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 永遠(yuǎn)指向當(dāng)前(所遍歷過(guò)的字符中)第一個(gè)唯一的字符
pos++;
}
}
return pos < s.length() ? pos : -1;
}
};
