7. 反轉(zhuǎn)整數(shù)
給定一個 32 位有符號整數(shù)，將整數(shù)中的數(shù)字進行反轉(zhuǎn)。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設(shè)我們的環(huán)境只能存儲 32 位有符號整數(shù)，其數(shù)值范圍是 [?231, 231 ? 1]。根據(jù)這個假設(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)
實現(xiàn) atoi，將字符串轉(zhuǎn)為整數(shù)。
在找到第一個非空字符之前，需要移除掉字符串中的空格字符。如果第一個非空字符是正號或負(fù)號，選取該符號，并將其與后面盡可能多的連續(xù)的數(shù)字組合起來，這部分字符即為整數(shù)的值。如果第一個非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成整數(shù)。
字符串可以在形成整數(shù)的字符后面包括多余的字符，這些字符可以被忽略，它們對于函數(shù)沒有影響。
當(dāng)字符串中的第一個非空字符序列不是個有效的整數(shù)；或字符串為空；或字符串僅包含空白字符時，則不進行轉(zhuǎn)換。
若函數(shù)不能執(zhí)行有效的轉(zhuǎn)換，返回 0。
說明：
假設(shè)我們的環(huán)境只能存儲 32 位有符號整數(shù)，其數(shù)值范圍是 [?231, 231 ? 1]。如果數(shù)值超過可表示的范圍，則返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個非空白字符為 '-', 它是一個負(fù)號。
我們盡可能將負(fù)號與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來，最后得到 -42 。
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 '3' ，因為它的下一個字符不為數(shù)字。
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個非空字符是 'w', 但它不是數(shù)字或正、負(fù)號。
因此無法執(zhí)行有效的轉(zhuǎn)換。
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數(shù)字 "-91283472332" 超過 32 位有符號整數(shù)范圍。
因此返回 INT_MIN (?231) 。
其實就是atoi的函數(shù)實現(xiàn)，依然較為簡單，依次判斷所有條件即可?？崭瘢?fù)號，溢出，是否為數(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. 不同路徑
一個機器人位于一個 *m x n *網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問總共有多少條不同的路徑？
<small style="box-sizing: border-box; font-size: 12px;">例如，上圖是一個7 x 3 的網(wǎng)格。有多少可能的路徑？</small>
說明：m 和 *n *的值均不超過 100。
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
除了DFS和BFS搜索算法，這題其實典型的動態(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];時間復(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個節(jié)點
給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的。
進階：
你能嘗試使用一趟掃描實現(xiàn)嗎？
思路一趟掃描，使用雙指針，可以指定兩個相差n的節(jié)點指針遍歷鏈表，這樣前面的指針遍歷到鏈表尾部的時候，后面的指針正好在倒數(shù)第n+1個節(jié)點的位置,刪除節(jié)點只需要改變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é)點
end->next = end->next->next;
return headCache->next;
}
};
