LeetCode 补充题 21. 字符串相减

Categories:

题目描述
思路分析
1. 解法一：字符串模拟减法（推荐）
相似题目

题目描述

✅ 补充题 21. 字符串相减

思路分析

解法一：字符串模拟减法（推荐）

核心思路：

先比较两个数字字符串的大小，确定结果符号，并保证用较大数减较小数。

从最低位开始逐位相减，维护借位 borrow，将结果反向拼接。

去掉前导零，若结果为空则返回 0。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，其中 n 表示结果字符串长度。

import java.util.*;

class Solution {
    public String subtractStrings(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return "";
        }

        String a = trimLeadingZeros(num1);
        String b = trimLeadingZeros(num2);

        int cmp = compare(a, b);
        if (cmp == 0) {
            return "0";
        }

        boolean negative = false;
        if (cmp < 0) {
            negative = true;
            String tmp = a;
            a = b;
            b = tmp;
        }

        String res = subtractNonNegative(a, b);
        return negative ? "-" + res : res;
    }

    private int compare(String a, String b) {
        if (a.length() != b.length()) {
            return a.length() > b.length() ? 1 : -1;
        }
        return a.compareTo(b);
    }

    private String trimLeadingZeros(String s) {
        int i = 0;
        while (i < s.length() && s.charAt(i) == '0') {
            i++;
        }
        return i == s.length() ? "0" : s.substring(i);
    }

    private String subtractNonNegative(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int borrow = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0) {
            int da = i >= 0 ? a.charAt(i) - '0' : 0;
            int db = j >= 0 ? b.charAt(j) - '0' : 0;

            int diff = da - borrow - db;
            if (diff < 0) {
                diff += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }

            sb.append(diff);
            i--;
            j--;
        }

        while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
            sb.deleteCharAt(sb.length() - 1);
        }

        return sb.reverse().toString();
    }
}

package main

import "strings"

func subtractStrings(num1, num2 string) string {
	a := trimLeadingZeros(num1)
	b := trimLeadingZeros(num2)

	cmp := compare(a, b)
	if cmp == 0 {
		return "0"
	}

	negative := false
	if cmp < 0 {
		negative = true
		a, b = b, a
	}

	res := subtractNonNegative(a, b)
	if negative {
		return "-" + res
	}
	return res
}

func compare(a, b string) int {
	if len(a) != len(b) {
		if len(a) > len(b) {
			return 1
		}
		return -1
	}
	if a == b {
		return 0
	}
	if a > b {
		return 1
	}
	return -1
}

func trimLeadingZeros(s string) string {
	i := 0
	for i < len(s) && s[i] == '0' {
		i++
	}
	if i == len(s) {
		return "0"
	}
	return s[i:]
}

func subtractNonNegative(a, b string) string {
	i := len(a) - 1
	j := len(b) - 1
	borrow := 0
	var sb strings.Builder

	for i >= 0 || j >= 0 {
		da := 0
		db := 0
		if i >= 0 {
			da = int(a[i] - '0')
		}
		if j >= 0 {
			db = int(b[j] - '0')
		}

		diff := da - borrow - db
		if diff < 0 {
			diff += 10
			borrow = 1
		} else {
			borrow = 0
		}

		sb.WriteByte(byte(diff + '0'))
		i--
		j--
	}

	res := sb.String()
	k := len(res) - 1
	for k > 0 && res[k] == '0' {
		k--
	}

	out := res[:k+1]
	bts := []byte(out)
	for l, r := 0, len(bts)-1; l < r; l, r = l+1, r-1 {
		bts[l], bts[r] = bts[r], bts[l]
	}
	return string(bts)
}

相似题目

题目	难度	考察点
67. 二进制求和	简单	字符串模拟、进位处理
415. 字符串相加	简单	字符串模拟、大数运算
43. 字符串相乘	中等	字符串模拟、大数乘法
2. 两数相加	中等	链表、模拟进位
445. 两数相加 II	中等	链表、栈、模拟
989. 数组形式的整数加法	简单	数组模拟、进位处理
66. 加一	简单	数组模拟、进位

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/94248529