[LeetCode] Plus One - 整数字符转换相加

简介:
题目概述:
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.


题目解析:
给你一个int型数组存储一个非负整数,对整数加1后输出一个int型数组。注意几点:
        1.可能存在进位操作,增加一位,如999+1=1000;
        2.数组存储如234=[2, 3, 4],它进行加1操作时从数组的高位(4)到低位(2);
        3.输出时也需要转置[0, 0, 0, 1]转成1000;
        4.C语言代码*returnSize是一维数组,注意赋值否则提示“超时异常”。

我的代码:
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 * 899+1=900 存储时digits[3]=[8,9,9] 从高位到地位 result[3]=[0,0,9]需要转置 
 * digitsSize数组长度 *returnSize为返回数组长度
 */
int* plusOne(int* digits, int digitsSize, int* returnSize) { 
    //初始时加1操作  后为进位数字0或1
    int add=1;      
    int i,j=0;
    int temp;
    //申请空间 初始化操作
    int *result=(int*)malloc(sizeof(int)*(digitsSize+1));
    memset(result, 0 , sizeof(int)*(digitsSize + 1));
    for(i=digitsSize-1; i>=0; i--) {
        result[j]=(digits[i]+add)%10;     //个位数字
        add=(digits[i]+add)/10;           //进位操作
        j++;
    }
    //最后如果add==1表示位数加1 如99+1=100
    if(add==1) {
        result[digitsSize]=1;
        *returnSize=digitsSize+1;       //注意它是一维数组
        //输出数组倒置
        for(i=0,j=digitsSize;i<j;i++,j--) {
            temp=result[i];
            result[i]=result[j];
            result[j]=temp;
        }
    }
    else {
        *returnSize=digitsSize;
        //输出数组倒置
        for(i=0,j=digitsSize-1;i<j;i++,j--) {
            temp=result[i];
            result[i]=result[j];
            result[j]=temp;
        }
    }
    return result;
}

推荐代码:
C语言代码 参考:http://www.tonzoc.info/?p=688

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
void reverse(int* digits, int start, int end) {
    int temp;
    for (int i = start; i <= (start + end) >> 1; ++i) {
        temp = digits[i];
        digits[i] = digits[end + start - i];
        digits[end + start - i] = temp;
    }
}
 
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    int num = 1;
    int* result = (int*)malloc(sizeof(int) * (digitsSize + 1));
    memset(result, 0, sizeof(int) * (digitsSize + 1));
    for (int i = digitsSize - 1; i >= 0; --i) {
        result[digitsSize - 1 - i] = (digits[i] + num) % 10;
        num = (digits[i] + num) / 10;
    }
    if (num) {
        *returnSize = digitsSize + 1;
        result[digitsSize] = num;
        reverse(result, 0, digitsSize);
    } else {
        *returnSize = digitsSize;
        reverse(result, 0, digitsSize - 1);
    }
    return result;
}
C++代码
vector<int> plusOne(vector<int> &digits) {  
    int carry=1, sum=0;  
    vector<int> result(digits.size(),0);  
    for(int i=digits.size()-1;i>=0;i--){  
        sum = carry+digits[i];  
        carry = sum/10;  
        result[i] = sum%10;  
    }  
    if(carry>0){ //进位 
        result.insert(result.begin(),carry);  
    }  
    return result;  
}  

同类题目:
二进制字符串加法 https://leetcode.com/problems/add-binary/

PS:需要注意转换方法 ((a[i]-'0')+(b[j]-'0')+add)%2+'0'当前结果和进位数字add=((a[i]-'0')+(b[j]-'0')+add)/2;同时需要注意字符串倒置的方法和对齐判断即可。

(By:Eastmount 2015-9-9 凌晨2点   http://blog.csdn.net/eastmount/)


目录
相关文章
|
11月前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
113 1
|
11月前
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
495 0
Leetcode第三题(无重复字符的最长子串)
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
282 2
|
11月前
【LeetCode】整数翻转
【LeetCode】整数翻转
55 1
|
11月前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
85 0
|
11月前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
148 0
|
11月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
121 0
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)
LeetCode第7题整数反转
该文章介绍了 LeetCode 第 7 题整数反转的解法,通过除 10 取模和乘 10 累加的方式实现整数反转,同时注意边界情况的判断,并总结了通过举例推算发现规律的解题思路。
LeetCode第7题整数反转