刷题笔记合集🔗

N进制减法

问题描述

小基期望你实现一个基于字符串的N进制的减法。

需要对输入的两个字符串按照给定的N进制进行减法操作，输出正负符号和表示结果的字符串。

输入格式

输入有三个参数：

. 第一个参数是整数形式的进制N值，N值范围为大于等于 、小于等于 。

. 第二个参数为被减数字符串。

. 第三个参数为减数字符串。

有效的字符包括0-9以及小写字母a-z，字符串有效字符个数最大为100个字符，另外还有结尾的\0。

限制：

输入的被减数和减数，除了单独的0以外，不能是以0开头的字符串。

如果输入有异常或计算过程中有异常，此时应当输出-1表示错误。

输出格式

输出有2个。

其一为减法计算的结果，-1表示出错，0表示结果为整数，1表示结果为负数。

其二为表示结果的字符串。

样例输入

2 11 1

8 07 1

样例输出

0 10

-1

数据范围

• 
• 字符串长度最大为100个字符

题解

这道题目要求实现一个N进制的减法运算，并且对输入有多种异常情况需要处理。

解题思路很直接：将N进制数转换成十进制，进行减法运算，然后将结果再转换回N进制。但难点在于各种边界条件和异常处理。

需要处理的异常情况包括：

1. N值必须在2到35之间
2. 输入的字符串只能包含数字0-9和小写字母a-z
3. 除了单独的"0"以外，不能有前导0
4. 字符串长度不能超过100
5. 字符串中的每个字符必须是有效的N进制数字，例如在2进制中，只能出现0和1

处理步骤：

1. 首先检查N是否在有效范围内
2. 然后验证两个输入字符串是否符合要求
3. 将两个N进制字符串转换为十进制数
4. 计算差值的绝对值，并确定结果的符号
5. 将差值转换回N进制字符串
6. 输出符号和结果字符串

在实现时需要注意的技巧：

• 对于非数字字符，可以使用字符的ASCII码值减去一个偏移量（如'a'的码值减87）来得到对应的数值
• 在Java和C++中需要使用长整型来避免可能的整数溢出
• 在检查字符是否为有效的N进制数字时，要区分数字字符和字母字符的处理方式

时间复杂度：O(L)，其中L是输入字符串的最大长度。主要操作是字符串处理和进制转换，都是线性时间复杂度。 空间复杂度：O(L)，主要用于存储处理过程中的字符串。

参考代码

• Python

import sys
import re
input = lambda:sys.stdin.readline().strip()

# 输入获取
n_str, b_sub, sub = input().split()
n = int(n_str)

# 将十进制数转换为n进制字符串
def to_base_n(num, base):
    if num == 0:
        return "0"
    
    chars = "0123456789abcdefghijklmnopqrstuvwxyz"
    result = ""
    
    while num > 0:
        result = chars[num % base] + result
        num //= base
    
    return result

# 验证字符串是否符合N进制规则
def is_valid(s, n):
    # 检查前导0
    if s.startswith("0") and s != "0":
        return False
    
    # 检查非法字符
    if re.search("[^0-9a-z]", s):
        return False
    
    # 检查长度
    if len(s) > 100:
        return False
    
    # 检查每个字符是否为有效的n进制数字
    for c in s:
        val = int(c, 36)  # 使用36进制解析，可以处理0-9和a-z
        if val >= n:
            return False
    
    return True

# 主函数
def solve():
    # 检查进制范围
    if n < 2 or n > 35:
        return "-1"
    
    # 验证输入字符串
    if not is_valid(b_sub, n) or not is_valid(sub, n):
        return "-1"
    
    # 将n进制转换为十进制
    try:
        dec_b_sub = int(b_sub, n)
        dec_sub = int(sub, n)
    except ValueError:
        return "-1"
    
    # 计算差值并确定符号
    diff = abs(dec_b_sub - dec_sub)
    sign = "1" if dec_b_sub < dec_sub else "0"
    
    # 转换结果为n进制
    result = to_base_n(diff, n)
    
    return f"{sign} {result}"

# 输出结果
print(solve())

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 将十进制数转换为N进制字符串
string toBaseN(long long num, int base) {
    if (num == 0) return "0";
    
    string re