LeetCode 补充题 10. 36进制减法

Categories:

题目描述
思路分析
1. 解法一：模拟借位（推荐）
相似题目

题目描述

✅ 补充题 10. 36进制减法

思路分析

解法一：模拟借位（推荐）

核心思路：

将字符映射到 0~35 的数值，支持 0-9 与 a-z。

从最低位开始逐位相减并处理借位。

去除前导零，必要时添加负号。

复杂度分析：

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

空间复杂度：O(n)，用于结果构建。

class Solution {
    public String sub36(String a, String b) {
        boolean negative = false;
        if (compare(a, b) < 0) {
            negative = true;
            String tmp = a;
            a = b;
            b = tmp;
        }

        int i = a.length() - 1;
        int j = b.length() - 1;
        int borrow = 0;
        StringBuilder builder = new StringBuilder();

        while (i >= 0 || j >= 0) {
            int x = i >= 0 ? val(a.charAt(i)) : 0;
            int y = j >= 0 ? val(b.charAt(j)) : 0;
            int cur = x - y - borrow;
            if (cur < 0) {
                cur += 36;
                borrow = 1;
            } else {
                borrow = 0;
            }
            builder.append(digit(cur));
            i--;
            j--;
        }

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

        if (negative) {
            builder.append('-');
        }

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

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

    private int val(char c) {
        if (c >= '0' && c <= '9') {
            return c - '0';
        }
        if (c >= 'A' && c <= 'Z') {
            return c - 'A' + 10;
        }
        return c - 'a' + 10;
    }

    private char digit(int v) {
        if (v < 10) {
            return (char) ('0' + v);
        }
        return (char) ('a' + v - 10);
    }
}

func sub36(a string, b string) string {
	negative := false
	if compare36(a, b) < 0 {
		negative = true
		a, b = b, a
	}

	i := len(a) - 1
	j := len(b) - 1
	borrow := 0
	res := make([]byte, 0, len(a)+1)

	for i >= 0 || j >= 0 {
		x := 0
		if i >= 0 {
			x = val36(a[i])
		}
		y := 0
		if j >= 0 {
			y = val36(b[j])
		}

		cur := x - y - borrow
		if cur < 0 {
			cur += 36
			borrow = 1
		} else {
			borrow = 0
		}

		res = append(res, digit36(cur))
		i--
		j--
	}

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

	if negative {
		res = append(res, '-')
	}

	reverseBytes(res)
	return string(res)
}

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

func val36(c byte) int {
	if c >= '0' && c <= '9' {
		return int(c - '0')
	}
	if c >= 'A' && c <= 'Z' {
		return int(c-'A') + 10
	}
	return int(c-'a') + 10
}

func digit36(v int) byte {
	if v < 10 {
		return byte('0' + v)
	}
	return byte('a' + v - 10)
}

func reverseBytes(arr []byte) {
	for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
}

相似题目

题目	难度	考察点
2. 两数相加	中等	链表进位
67. 二进制求和	简单	进位模拟
415. 字符串相加	简单	进位模拟
43. 字符串相乘	中等	高精度模拟
989. 数组形式的整数加法	简单	进位模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/56232054