C++實(shí)現(xiàn)LeetCode(66.加一運(yùn)算)
[LeetCode] 66. Plus One 加一運(yùn)算
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Example 3:
Input: digits = [0]
Output: [1]
Constraints:
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
將一個(gè)數(shù)字的每個(gè)位上的數(shù)字分別存到一個(gè)一維向量中,最高位在最開(kāi)頭,我們需要給這個(gè)數(shù)字加一,即在末尾數(shù)字加一,如果末尾數(shù)字是9,那么則會(huì)有進(jìn)位問(wèn)題,而如果前面位上的數(shù)字仍為9,則需要繼續(xù)向前進(jìn)位。具體算法如下:首先判斷最后一位是否為9,若不是,直接加一返回,若是,則該位賦0,再繼續(xù)查前一位,同樣的方法,知道查完第一位。如果第一位原本為9,加一后會(huì)產(chǎn)生新的一位,那么最后要做的是,查運(yùn)算完的第一位是否為0,如果是,則在最前頭加一個(gè)1。代碼如下:
C++ 解法一:
class Solution { public: vector<int> plusOne(vector<int> &digits) { int n = digits.size(); for (int i = n - 1; i >= 0; --i) { if (digits[i] == 9) digits[i] = 0; else { digits[i] += 1; return digits; } } if (digits.front() == 0) digits.insert(digits.begin(), 1); return digits; } };
Java 解法一:
public class Solution { public int[] plusOne(int[] digits) { int n = digits.length; for (int i = digits.length - 1; i >= 0; --i) { if (digits[i] < 9) { ++digits[i]; return digits; } digits[i] = 0; } int[] res = new int[n + 1]; res[0] = 1; return res; } }
我們也可以使用跟之前那道 Add Binary 類似的做法,將 carry 初始化為1,然后相當(dāng)于 digits 加了一個(gè)0,處理方法跟之前那道題一樣,參見(jiàn)代碼如下:
C++ 解法二 :
class Solution { public: vector<int> plusOne(vector<int>& digits) { if (digits.empty()) return digits; int carry = 1, n = digits.size(); for (int i = n - 1; i >= 0; --i) { if (carry == 0) return digits; int sum = digits[i] + carry; digits[i] = sum % 10; carry = sum / 10; } if (carry == 1) digits.insert(digits.begin(), 1); return digits; } };
Java 解法二 :
public class Solution { public int[] plusOne(int[] digits) { if (digits.length == 0) return digits; int carry = 1, n = digits.length; for (int i = digits.length - 1; i >= 0; --i) { if (carry == 0) return digits; int sum = digits[i] + carry; digits[i] = sum % 10; carry = sum / 10; } int[] res = new int[n + 1]; res[0] = 1; return carry == 0 ? digits : res; } }
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(66.加一運(yùn)算)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)加一運(yùn)算內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(73.矩陣賦零)
- C++實(shí)現(xiàn)LeetCode(72.編輯距離)
- C++實(shí)現(xiàn)LeetCode(71.簡(jiǎn)化路徑)
- C++實(shí)現(xiàn)LeetCode( 69.求平方根)
- C++實(shí)現(xiàn)LeetCode(68.文本左右對(duì)齊)
- C++實(shí)現(xiàn)LeetCode(67.二進(jìn)制數(shù)相加)
- C++實(shí)現(xiàn)LeetCode(174.地牢游戲)
- C++實(shí)現(xiàn)LeetCode(81.在旋轉(zhuǎn)有序數(shù)組中搜索之二)
相關(guān)文章
關(guān)于c++11與c風(fēng)格路徑拼接的速度對(duì)比
這篇文章主要介紹了關(guān)于c++11與c風(fēng)格路徑拼接的速度對(duì)比分析,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-07-07淺析C++中boost.variant的幾種訪問(wèn)方法
variant類型在C++14并沒(méi)有加入,若想在不支持C++17的編譯器上使用variant類型,我們可以通過(guò)boost的variant類型,variant類型可以表示任意一種類型和any類型有些相似,但還是有些區(qū)別下面將淺談variant的幾種訪問(wèn)方法,感興趣的朋友們下面來(lái)一起看看吧。2016-10-10