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ù)值范圍是 [?231, 231 ? 1]毡泻。根據(jù)這個(gè)假設(shè)刘离，如果反轉(zhuǎn)后的整數(shù)溢出，則返回 0抑片。
常規(guī)思路解題卵佛，求余數(shù)，需要注意的是溢出判斷敞斋。
class Solution {
public:
int reverse(int x) {
int t = 0;
while (x != 0)
{
//溢出判斷
if (t >INT_MAX / 10 || t <(INT_MIN) / 10)
return 0;
t= t * 10 + x % 10;
x /= 10;
}
return t;
}
};
8. 字符串轉(zhuǎn)整數(shù) (atoi)
實(shí)現(xiàn) atoi截汪，將字符串轉(zhuǎn)為整數(shù)。
在找到第一個(gè)非空字符之前植捎，需要移除掉字符串中的空格字符衙解。如果第一個(gè)非空字符是正號(hào)或負(fù)號(hào)，選取該符號(hào)焰枢，并將其與后面盡可能多的連續(xù)的數(shù)字組合起來(lái)蚓峦，這部分字符即為整數(shù)的值。如果第一個(gè)非空字符是數(shù)字济锄，則直接將其與之后連續(xù)的數(shù)字字符組合起來(lái)暑椰，形成整數(shù)。
字符串可以在形成整數(shù)的字符后面包括多余的字符荐绝，這些字符可以被忽略一汽，它們對(duì)于函數(shù)沒(méi)有影響。
當(dāng)字符串中的第一個(gè)非空字符序列不是個(gè)有效的整數(shù)低滩；或字符串為空召夹；或字符串僅包含空白字符時(shí)，則不進(jìn)行轉(zhuǎn)換恕沫。
若函數(shù)不能執(zhí)行有效的轉(zhuǎn)換监憎，返回 0。
說(shuō)明：
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位有符號(hào)整數(shù)昏兆，其數(shù)值范圍是 [?231, 231 ? 1]枫虏。如果數(shù)值超過(guò)可表示的范圍妇穴，則返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個(gè)非空白字符為 '-', 它是一個(gè)負(fù)號(hào)隶债。
我們盡可能將負(fù)號(hào)與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來(lái)腾它，最后得到 -42 。
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 '3' 死讹，因?yàn)樗南乱粋€(gè)字符不為數(shù)字瞒滴。
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個(gè)非空字符是 'w', 但它不是數(shù)字或正、負(fù)號(hào)赞警。
因此無(wú)法執(zhí)行有效的轉(zhuǎn)換妓忍。
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數(shù)字 "-91283472332" 超過(guò) 32 位有符號(hào)整數(shù)范圍。
因此返回 INT_MIN (?231) 愧旦。
其實(shí)就是atoi的函數(shù)實(shí)現(xiàn)世剖，依然較為簡(jiǎn)單，依次判斷所有條件即可笤虫∨蕴保空格，正負(fù)號(hào)琼蚯，溢出酬凳，是否為數(shù)字
class Solution {
public:
int myAtoi(string str) {
if (str.empty()) {
return 0;
}
int sign = 1, base = 0, i = 0,n = str.size();
while (i < n && str[i] == ' ') {
I++;
}
if (str[i] == '+' || str[i] == '-') {
sign = (str[i] == '+') ? 1: -1;
I++;
}
while (i <n && str[i] >= '0' && str[i] <= '9') {
if (base > INT_MAX/10 || (base == INT_MAX/10 && str[i] - '0' >7)) {
return (sign ==1) ? INT_MAX : INT_MIN;
}
base = 10 * base + (str[i] - '0');
I++;
}
return sign *base;
}
};
62. 不同路徑
一個(gè)機(jī)器人位于一個(gè) *m x n *網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步遭庶。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）宁仔。
問(wèn)總共有多少條不同的路徑？
<small style="box-sizing: border-box; font-size: 12px;">例如峦睡，上圖是一個(gè)7 x 3 的網(wǎng)格翎苫。有多少可能的路徑？</small>
說(shuō)明：m 和 *n *的值均不超過(guò) 100赐俗。
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開(kāi)始拉队，總共有 3 條路徑可以到達(dá)右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
除了DFS和BFS搜索算法阻逮，這題其實(shí)典型的動(dòng)態(tài)規(guī)劃粱快。我們可以假設(shè)dp[i][j]的值就是第i行，j列的路徑數(shù)叔扼，很明顯i = 0.的所有值都是1事哭，j = 0的所有值都為1，只有一條路徑瓜富。而除此之外dp[i][j] = dp[i-1][j] + dp[i][j-1];時(shí)間復(fù)雜度O(nm),空間復(fù)雜度O(nm)
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m][n];
for (int i = 0; i<m; i++) {
for (int j = 0; j <n; j++) {
if (i == 0 || j == 0) {
//只有一種
dp[i][j] = 1;
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
給定一個(gè)鏈表鳍咱，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)与柑。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后谤辜，鏈表變?yōu)?1->2->3->5.
說(shuō)明：
給定的 n 保證是有效的蓄坏。
進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？
思路一趟掃描丑念，使用雙指針涡戳，可以指定兩個(gè)相差n的節(jié)點(diǎn)指針遍歷鏈表，這樣前面的指針遍歷到鏈表尾部的時(shí)候脯倚，后面的指針正好在倒數(shù)第n+1個(gè)節(jié)點(diǎn)的位置,刪除節(jié)點(diǎn)只需要改變next指向即可渔彰。代碼并不復(fù)雜。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
struct ListNode *headCache = new ListNode(0);
headCache->next = head;
ListNode *end = headCache;
for (int i = 0; i <n; i++) {
head = head->next;
}
while (head != NULL) {
head = head->next;
end = end->next;
}
//刪除結(jié)點(diǎn)
end->next = end->next->next;
return headCache->next;
}
};
