415.字符串相加

LeetCode LeetCode 字符串 数字 模拟
发布时间 :
字数:1.9k 阅读 : 评论:
  1. 415.字符串相加
    1. 415.1 题目
    2. 415.2 题解
      1. 逐位相加
      2. char转int后计算
    3. 415.3 代码
    4. 415.4 运行结果

415.字符串相加

415.1 题目

给定两个字符串形式的非负整数 num1 和 num2，计算它们的和并同样以字符串形式返回。

你不能使用任何内建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"

提示：

  • 1 <= num1.length, num2.length <= 10^4
  • num1 和 num2 都只包含数字 0-9
  • num1 和 num2 都不包含任何前导零

415.2 题解

逐位相加

// 方法一：逐位相加
// 从最低位（个位）开始逐位相加，注意进位的处理
// 两个指针 i 和 j分别从两个字符串的Length - 1处开始左移
// 需要一个变量记录进位值
// 需要一个变量记录结果，结果字符串拼接时要注意左右方向
// 每一位字符转数字，我们可以不用强转，而是计算字符编码的插值 因为数字字符的编码是连续的，比如 '9' - '0' = 9
static string AddStrings1(string num1, string num2)
{
    int carry = 0; // 用于存储进位的变量
    int i = num1.Length - 1, j = num2.Length - 1; // 初始化两个指针分别指向两个字符串的最低位
    List<char> result = new List<char>(); // 用于存储相加后的结果

    // 从最低位开始逐位相加，直到两个字符串和进位都处理完
    while (i >= 0 || j >= 0 || carry > 0)
    {
        // 取得当前位数的数字，如果已经超过字符串长度，则默认为0
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;

        // 计算当前位的和，包括前一位的进位
        int sum = x + y + carry;

        // 将当前位的数字加入结果列表
        result.Add((char)(sum % 10 + '0'));

        // 更新进位
        carry = sum / 10;

        // 移动指针到下一位
        i--;
        j--;
    }

    // 最后反转结果列表，生成最终的字符串形式的和
    result.Reverse();
    return new string(result.ToArray());
}

char转int后计算

// 方法二：char转int后计算
static string AddStrings2(string num1, string num2)
{
    // 使用 StringBuilder 来构建最终的结果字符串
    StringBuilder stringBuilder = new StringBuilder();

    // 初始化两个指针分别指向两个字符串的最低位
    int i = num1.Length - 1;
    int j = num2.Length - 1;

    // 用于存储进位的变量
    int carry = 0;

    // 从最低位开始逐位相加，直到两个字符串和进位都处理完
    while (i >= 0 || j >= 0 || carry != 0)
    {
        // 取得当前位的字符，如果已经超过字符串长度，则默认为 '0'
        char c1 = i >= 0 ? num1[i] : '0';
        char c2 = j >= 0 ? num2[j] : '0';

        // 将字符转换为数字
        int n1 = int.Parse(c1.ToString());
        int n2 = int.Parse(c2.ToString());

        // 计算当前位的和，包括前一位的进位
        int sum = n1 + n2 + carry;

        // 计算当前位的值
        int nowVal = sum % 10;
        // 更新进位
        carry = sum / 10;

        // 将当前位的值插入结果字符串的开头
        stringBuilder.Insert(0, nowVal);

        // 移动指针到下一位
        i--;
        j--;
    }

    // 返回最终的结果字符串
    return stringBuilder.ToString();
}

415.3 代码

using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。
        // 你不能使用任何内建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

        // 示例 1：
        // 输入：num1 = "11", num2 = "123"
        // 输出："134"

        // 示例 2：
        // 输入：num1 = "456", num2 = "77"
        // 输出："533"

        // 示例 3：
        // 输入：num1 = "0", num2 = "0"
        // 输出："0"

        // 提示：
        // 1 <= num1.length, num2.length <= 104
        // num1 和 num2 都只包含数字 0-9
        // num1 和 num2 都不包含任何前导零

        #endregion

        #region 测试

        // 示例 1
        // 示例 1
        string num1_1 = "11";
        string num2_1 = "123";
        string result1_1 = AddStrings1(num1_1, num2_1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        string result1_2 = AddStrings2(num1_1, num2_1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        string num1_2 = "456";
        string num2_2 = "77";
        string result2_1 = AddStrings1(num1_2, num2_2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        string result2_2 = AddStrings2(num1_2, num2_2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        string num1_3 = "0";
        string num2_3 = "0";
        string result3_1 = AddStrings1(num1_3, num2_3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        string result3_2 = AddStrings2(num1_3, num2_3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：逐位相加
    // 从最低位（个位）开始逐位相加，注意进位的处理
    // 两个指针 i 和 j分别从两个字符串的Length - 1处开始左移
    // 需要一个变量记录进位值
    // 需要一个变量记录结果，结果字符串拼接时要注意左右方向
    // 每一位字符转数字，我们可以不用强转，而是计算字符编码的插值 因为数字字符的编码是连续的，比如 '9' - '0' = 9
    static string AddStrings1(string num1, string num2)
    {
        int carry = 0; // 用于存储进位的变量
        int i = num1.Length - 1, j = num2.Length - 1; // 初始化两个指针分别指向两个字符串的最低位
        List<char> result = new List<char>(); // 用于存储相加后的结果

        // 从最低位开始逐位相加，直到两个字符串和进位都处理完
        while (i >= 0 || j >= 0 || carry > 0)
        {
            // 取得当前位数的数字，如果已经超过字符串长度，则默认为0
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;

            // 计算当前位的和，包括前一位的进位
            int sum = x + y + carry;

            // 将当前位的数字加入结果列表
            result.Add((char)(sum % 10 + '0'));

            // 更新进位
            carry = sum / 10;

            // 移动指针到下一位
            i--;
            j--;
        }

        // 最后反转结果列表，生成最终的字符串形式的和
        result.Reverse();
        return new string(result.ToArray());
    }

    // 方法二：char转int后计算
    static string AddStrings2(string num1, string num2)
    {
        // 使用 StringBuilder 来构建最终的结果字符串
        StringBuilder stringBuilder = new StringBuilder();

        // 初始化两个指针分别指向两个字符串的最低位
        int i = num1.Length - 1;
        int j = num2.Length - 1;

        // 用于存储进位的变量
        int carry = 0;

        // 从最低位开始逐位相加，直到两个字符串和进位都处理完
        while (i >= 0 || j >= 0 || carry != 0)
        {
            // 取得当前位的字符，如果已经超过字符串长度，则默认为 '0'
            char c1 = i >= 0 ? num1[i] : '0';
            char c2 = j >= 0 ? num2[j] : '0';

            // 将字符转换为数字
            int n1 = int.Parse(c1.ToString());
            int n2 = int.Parse(c2.ToString());

            // 计算当前位的和，包括前一位的进位
            int sum = n1 + n2 + carry;

            // 计算当前位的值
            int nowVal = sum % 10;
            // 更新进位
            carry = sum / 10;

            // 将当前位的值插入结果字符串的开头
            stringBuilder.Insert(0, nowVal);

            // 移动指针到下一位
            i--;
            j--;
        }

        // 返回最终的结果字符串
        return stringBuilder.ToString();
    }

    #endregion
}

415.4 运行结果

示例1 方法1 输出：134
示例1 方法2 输出：134
示例2 方法1 输出：533
示例2 方法2 输出：533
示例3 方法1 输出：0
示例3 方法2 输出：0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏