r**d
发帖数: 116 | 1 给一个用数组表示的数字，例如193 是数组［1，9，3］，实现一个加1的函数 so that
Increment([1,9,3]) returns [1,9,4]。请问C++的实现？ |
c*******r
发帖数: 610 | |
r**d
发帖数: 116 | 3 面试前匆匆做了几道leecode的题，但没有看到这道:-( 我刚才去看了一下，是的。有
什么好的解法吗？
我很笨地给了一个从数组转换到数字，加一，再转换回数组的解法。而且没有在开始就
指出有overflow的问题要处理，直到后面时间不够时才想到没有处理overflow。面试官
让我说一下怎么检查，我的方法是转换到数字，再转换回去，如果和原数组不同，就是
overflow了。他说这是一个方法。 |
q********c
发帖数: 1774 | 4 直接用数组：
class Solution {
public:
vector plusOne(vector &digits) {
int len = digits.size();
int i = len-1;
int sum;
do {
sum = digits[i] + 1;
digits[i] = sum==10?0:sum;
i--;
}while(i>=0 && sum==10);
if(sum==10) {
digits.resize(len+1);
for(int k = len-1; k >=0; k--)
digits[k+1] = digits[k];
digits[0] = 1;
}
return digits;
}
}; |
r**d
发帖数: 116 | 5 为什么要return digits? input vector 不是已经被直接修改了吗？
怎么check overflow 呢？ |
q********c
发帖数: 1774 | 6 1. 因为函数signature需要返回一个vector
2. 不需要checko verflow，因为数组操作只根内存大小有关，与数值无关.
【在 r**d 的大作中提到】
: 为什么要return digits? input vector 不是已经被直接修改了吗？
: 怎么check overflow 呢？
|
r**d
发帖数: 116 | 7
谢谢你的回答！I still have two questions:
1. Is there a special reason that you want to create this function with this
signature? since you will modify the input vector argument of this function
, why you still want to return a vector as well?
2. I think we need check the overflow, because the result array still need
to represent a valid number. The guy who interviewed me said the function
should be able to indicate (i.e. return a flag) if overflow happened.
【在 q********c 的大作中提到】
: 1. 因为函数signature需要返回一个vector
: 2. 不需要checko verflow，因为数组操作只根内存大小有关，与数值无关.
|
q********c
发帖数: 1774 | 8
this
function
You don't have to return a vector, in fact, you can just return void. I was
using my code on leetcode oj as an example.
The guy was wrong about checking overflow. Ever heard of big int?
【在 r**d 的大作中提到】
:
: 谢谢你的回答！I still have two questions:
: 1. Is there a special reason that you want to create this function with this
: signature? since you will modify the input vector argument of this function
: , why you still want to return a vector as well?
: 2. I think we need check the overflow, because the result array still need
: to represent a valid number. The guy who interviewed me said the function
: should be able to indicate (i.e. return a flag) if overflow happened.
|
w****e
发帖数: 3827 | 9 java的版本 供参考一下..
public class Solution {
public int[] plusOne(int[] digits) {
for(int i = digits.length-1; i>=0; i--){
if(digits[i] != 9){
digits[i]++;
return digits;
}
else{
digits[i] = 0;
}
}
int[] re = new int[digits.length+1];
re[0] = 1;
return re;
}
} |
w****r
发帖数: 15252 | 10 public int[] PlusOne(int[] digits){
int carry =1,sum=0;
int[] result = new int[digits.length];
for(int i = digits.length -1; i>=0; i--){
sum = carry+digits[i];
carry = sum/10;
result[i] = sum%10;
}
if(carry == 1){
int[] plusone = new int[digits.length+1];
plusone[0] = carry;
for(int i=1;i
plusone[i] = result[i-1];
return plusone;
}else{
return result;
}
} |
G****A
发帖数: 4160 | 11 void increment(vector& vec)
{
int pos = vec.size() - 1;
uint carry = 1;
do{
if (pos < 0)
vec.insert(vec.begin(), 1);
else{
int sum = vec[pos] + carry;
vec[pos] = sum % 10;
carry = sum / 10;
pos--;
}
} while(carry);
}
that
【在 r**d 的大作中提到】
: 给一个用数组表示的数字，例如193 是数组［1，9，3］，实现一个加1的函数 so that
: Increment([1,9,3]) returns [1,9,4]。请问C++的实现？
|
r**d
发帖数: 116 | 12 有1个bug
should have a break statement inside (if (pos < 0))
【在 G****A 的大作中提到】
: void increment(vector& vec)
: {
: int pos = vec.size() - 1;
: uint carry = 1;
:
: do{
: if (pos < 0)
: vec.insert(vec.begin(), 1);
: else{
: int sum = vec[pos] + carry;
|
G****A
发帖数: 4160 | 13 thanks. 看来去不了fb了:)
【在 r**d 的大作中提到】
: 有1个bug
: should have a break statement inside (if (pos < 0))
|
r**d
发帖数: 116 | 14 :-) 真的这么严格吗？
【在 G****A 的大作中提到】
: thanks. 看来去不了fb了:)
|
