面試高頻算法題補充系列：36進制減法問題

前言

了解更多常考高頻算法題可以關注

公衆号：一個搬磚的胖子

企業面試題庫:https://codetop.cc/

小程式：CodeTop

今天補充的題目是36進制減法。

實際上，我在發表過36進制加法文章後，群裡就有小夥伴被考到了減法，前段時間發現牛客上有同學又考到了這個，是以趕緊來補充下這道題。

該帖不知什麼原因現在已經删除，幸虧我保留了截圖。

一起來看看這道題吧

題目描述

36進制由0-9，a-z，共36個字元表示。

要求按照減法規則計算出任意兩個36進制正整數的差，如48-2x =1b （解釋：152-105=47）

要求：不允許使用先将36進制數字整體轉為10進制，相減後再轉回為36進制的做法

題目分析

在掌握這道題之前，一定要去熟悉下我上次寫的十進制的大數相減呀~

本題在原來的基礎上隻需修改幾行代碼即可！

以下是36進制減法核心

sub

函數的代碼。

string sub(string a, string b) {
    string res = "";
    int borrow = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0) {
        int x = i >= 0 ? getInt(a[i]) : 0;
        int y = j >= 0 ? getInt(b[j]) : 0;
        int z = (x - borrow - y + 36) % 36;
        res += getChar(z);
        borrow = x - borrow - y < 0 ? 1 : 0;
        i--, j--;
    }
    reverse(res.begin(), res.end());
    //删除前導0。循環條件是res.size()-1是為防止"0000"的情況
    int pos;
    for (pos = 0; pos < res.size() - 1; pos++) {
        if (res[pos] != '0') break;
    }
    return res.substr(pos);
}
           

細心的同學可以看到，與大數相減的

sub

函數相比，隻改動了4行代碼

1. int x = i >= 0 ? getInt(a[i]) : 0

   ：十進制大數相減時字元轉整數是

   a[i] - '0'

   ，36進制時需要實作單獨的字元轉換整數的

   getInt

   函數。

2. int y = j >= 0 ? getInt(b[j]) : 0;

   ，與1同理。

3. int z = (x - borrow - y + 36) % 36

   ：十進制減法時是

   (x - borrow - y + 10) % 10

   ，36進制需要改成36，這應該不難了解。

4. res += getChar(z);

   ：每一位減完的數需要轉成對應的字元，36進制不能再使用

   ('0' + z)

   了，需要額外實作整數轉字元的

   getChar

   函數函數。

再實作上邊所說的

getInt

函數和

getChar

函數就可以了。

char getChar(int n) {
    if (n <= 9) return n + '0';
    else return n - 10 + 'a';
}
int getInt(char ch) {
    if ('0' <= ch && ch <= '9') return ch - '0';
    else return ch - 'a' + 10;
}
           

打完收工，下面附上C++版的完整代碼~

參考代碼

#include <iostream>
#include <algorithm>
using namespace std;

char getChar(int n) {
    if (n <= 9) return n + '0';
    else return n - 10 + 'a';
}

int getInt(char ch) {
    if ('0' <= ch && ch <= '9') return ch - '0';
    else return ch - 'a' + 10;
}

string sub(string a, string b) {
    string res = "";
    int borrow = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0) {
        int x = i >= 0 ? getInt(a[i]) : 0;
        int y = j >= 0 ? getInt(b[j]) : 0;
        int z = (x - borrow - y + 36) % 36;
        res += getChar(z);
        borrow = x - borrow - y < 0 ? 1 : 0;
        i--, j--;
    }
    reverse(res.begin(), res.end());
    //删除前導0。注意：循環條件是res.size()-1是為防止"0000"的情況
    int pos;
    for (pos = 0; pos < res.size() - 1; pos++) {
        if (res[pos] != '0') break;
    }
    return res.substr(pos);
}

bool isLess(string a, string b) {
    if (a.size() == b.size()) return a < b;
    return a.size() < b.size();
}

string subStrings(string num1, string num2) {
    string res;
    if (isLess(num1, num2)) {
        res = sub(num2, num1);
        res.insert(0, "-");
    }
    else res = sub(num1, num2);
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;
    cout << subStrings(a, b) << endl;
    return 0;
}
           

參考連結

https://mp.weixin.qq.com/s/_A2Ctn3kDa21NPlpF9y-hg