פתרון בסיס 7 של Leetcode


רמת קושי קַל
נשאל לעתים קרובות בלומברג garena
מתמטיקה

הבעיה Base 7 Leetcode Solution, מבקשת מאיתנו להמיר מספר למספר בסיס 7. המספר הנתון יכול להיות שלילי או חיובי עד 10 מיליון, בשני הכיוונים בשורת המספרים. הבעיה נראית פשוטה והיא המרה פשוטה של ​​מספר עשרוני לבסיס אחר. ממש כמו המרה של מספר בפורמט בינארי. במקום שהבסיס יהיה 2, הבסיס הוא 7. הערך החוזר צריך להיות מחרוזת. בואו נסתכל על כמה דוגמאות.

דוגמה

100
"202"

הסבר: המספר 202 בבסיס 7 לאחר ההמרה מניב 100 בפורמט עשרוני. 202 בבסיס 7 = 2 * (7 ^ 2) + 0 * (7 ^ 1) + 2 * (7 ^ 0) = 100 בבסיס 7.

פתרון בסיס 7 של Leetcode

-7
"-10"

הסבר: המספר הנתון -7 לאחר ההמרה לבסיס 7 ייתן -10.

גישה לפתרון Leetcode בסיס 7

הבעיה Base 7 Leetcode Solution, מספק לנו מספר או מספר שלם ומבקש מאיתנו להמיר אותו לבסיס 7. ההמרה לא רק לבסיס 7, היא פעולה פשוטה. אנו ממשיכים לחלק את המספר הנתון עם הבסיס הנדרש שלנו. לאחר חלוקת המספר, השאר מאוחסן. ואז התוצאה שנמצאה לאחר חלוקת המספר נשלחת שוב לחלוקה החוזרת. אנו ממשיכים לאחסן את השאר שהיא התשובה לשאלה. התהליך החוזר על עצמו נעצר ברגע שהמספר הופך להיות פחות מהבסיס הנתון.

אז בואו ניקח בחשבון 100 כקלט. ראשית, אנו מחלקים את המספר ב- 7, המנה היא 14 והשאר היא 2. ואז השארית נשמרת והמנה שוב נשלחת לחלוקה. כעת, המנה הופכת ל -2 והשאר מאוחסן. עד כה המספר המומר הופך להיות 20. ואז המנה נשלחת שוב לחלוקה אך מוחזרת מכיוון שהיא פחותה מהבסיס הנתון (7). לפיכך, התוצאה הסופית יוצאת 202.

קופונים

קוד C ++ לפתרון Base 7 Leetcode

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

string convertToBase7(int num) {
    if(num < 0)return "-" + convertToBase7(-num);
    else if(num < 7) return to_string(num);
    else
        return convertToBase7(num/7) + convertToBase7(num%7);
}

int main(){
    cout<<convertToBase7(100);
}
202

קוד Java עבור Base 7 Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static String convertToBase7(int num) {
        if(num < 0)return "-" + convertToBase7(-num);
        else if(num < 7) return Integer.toString(num);
        else
            return convertToBase7(num/7) + convertToBase7(num%7);
    }
    
    public static void main(String[] args){
    	System.out.print(convertToBase7(100));
    }
}
202

ניתוח מורכבות

מורכבות זמן

O (M (n) log n), כאשר n הוא אורך הקלט הנתון, M (n) הוא הזמן שלוקח לחלק שני מספרים דו-סיביים. לכן, מורכבות הזמן היא לוגריתמית.

מורכבות בחלל

O (יומן n), השטח המשמש את ערימת המהדר. כאן n מייצג את אורך המספר. לכן, מורכבות החלל היא גם לוגריתמית.