Given a number represented as an array of digits, plus one to the number.
A:
--------------- 先加,最后不行了,再 enlarge array -------------
public class Solution { public int[] plusOne(int[] digits) { if(digits == null || digits.length==0){ digits = new int[1]; digits[0] = 1; return digits; } //if digits is not empty int carryOn=0,j; int originalDigit; for( j=digits.length-1;j>=0;j--){ originalDigit = digits[j]; if(j == digits.length-1){// if it is the less siginificant digit digits[j] = (originalDigit+1)%10; carryOn = (int)((originalDigit+1)/10); }else{ digits[j] = (digits[j]+carryOn)%10; if(originalDigit+carryOn>=10){ carryOn=1; }else{ carryOn = 0; } } } if(j < 0 && carryOn ==1){ //Overflow,enlarge the size of array int[] newDigits = new int[digits.length+1]; newDigits[0] = 1; for(int i =0;i<digits.length;i++){ newDigits[i+1] = digits[i]; } digits=newDigits; } return digits; } }
Mistakes:
1: 没有看明白,当overflow的时候,要扩增数组的size。
2: 当加到倒数第二位的时候, 我们已经不需要再加1 了。(只加在最后一位,别的作为进位carryon 即可)
哎,调试的时候,在eclipse里和leetcode里 交叉调试,就导致了,在一方面改动, 可能在另一边忘了改。
Learned:
1: 在leetcode中, 即使我们不检查参数为null的情况,也可以通过。-----?????????这样是不是不对啊? 不用 digits == null ?
-------------------------第二遍------------预先检查了,是不是全部是9, -------
public class Solution { public int[] plusOne(int[] digits) { if(digits.length ==0){ digits = new int[1]; digits[0] = 1; return digits; } // if all are 9, creates a a new digits with one large boolean all9 = true; for(int i =0;i<digits.length;i++){ if(digits[i]!= 9){ all9=false; break; } } if(all9){ int[] result = new int[digits.length +1]; result[0] = 1; return result; } // now, no creatting needed int carry = 1; // plus 1 for(int i= digits.length-1;i>=0;i--){ if(carry == 0){ break; }else{ // carry == 1 carry = (carry+digits[i]>=10)?1:0; digits[i] = (digits[i]+1) %10; } } return digits; } }
-----------------------------------------3 rd Pass ----------------------------------
-----------------没有先检查全9, 而是直接加,最后看carry ==1?-------------
public class Solution { public int[] plusOne(int[] digits) { int carry = 1; int n = digits.length; for(int i =n-1;i>=0;i--){ if(carry==0) return digits; int a = digits[i] + carry; digits[i] = a%10; carry = a/10; } if(carry==1){ int[] newDigits = new int[n+1]; newDigits[0]=1; return newDigits; }else{ return digits; } } }
No comments:
Post a Comment