989 Add to Array-Form of Integer 數(shù)組形式的整數(shù)加法
Description:
For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].
Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.
Example:
Example 1:
Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234
Example 2:
Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455
Example 3:
Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021
Example 4:
Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000
Note:
1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0
題目描述:
對于非負(fù)整數(shù) X 而言，X 的數(shù)組形式是每位數(shù)字按從左到右的順序形成的數(shù)組。例如，如果 X = 1231，那么其數(shù)組形式為 [1,2,3,1]。
給定非負(fù)整數(shù) X 的數(shù)組形式 A，返回整數(shù) X+K 的數(shù)組形式。
示例 :
示例 1：
輸入：A = [1,2,0,0], K = 34
輸出：[1,2,3,4]
解釋：1200 + 34 = 1234
示例 2：
輸入：A = [2,7,4], K = 181
輸出：[4,5,5]
解釋：274 + 181 = 455
示例 3：
輸入：A = [2,1,5], K = 806
輸出：[1,0,2,1]
解釋：215 + 806 = 1021
示例 4：
輸入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
輸出：[1,0,0,0,0,0,0,0,0,0,0]
解釋：9999999999 + 1 = 10000000000
提示：
1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0
思路:
注意數(shù)組 A不能轉(zhuǎn)化為整數(shù), 因?yàn)閿?shù)組長度可能為 10000, 遠(yuǎn)遠(yuǎn)超過 int能表示的范圍
- 先逆序, 然后從第一位加上 K, 然后將數(shù)組 A的元素對 10取余不斷進(jìn)位, 注意判斷數(shù)組 A的大小需要存儲值判斷, 因?yàn)閿?shù)組 A的大小會動態(tài)變化, 最后輸出時(shí)逆序
- 另開一個(gè)數(shù)組記錄, 從后往前遍歷, 按照加法設(shè)置進(jìn)位
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
vector<int> addToArrayForm(vector<int>& A, int K)
{
int len = A.size();
reverse(A.begin(), A.end());
A[0] += K;
int i = 0;
while (A[i] > 9)
{
if (i > len - 2) A.push_back(0);
A[i + 1] += A[i] / 10;
A[i] %= 10;
i++;
}
reverse(A.begin(), A.end());
return A;
}
};
Java:
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
LinkedList<Integer> result = new LinkedList<>();
int i = A.length - 1;
while (i > -1 || K > 0) {
if (i > -1) K += A[i];
result.addFirst(K % 10);
K /= 10;
i--;
}
return result;
}
}
Python:
class Solution:
def addToArrayForm(self, A: List[int], K: int) -> List[int]:
return list(map(int, str(int(''.join(map(str, A))) + K)))
