Мянган тусгаарлагч Leetcode шийдэл


Хэцүү байдлын түвшин Easy
String

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд сөрөг бус бүхэл тоо өгөгдсөн болно. Бид бүхэл тоог ийм форматад хөрвүүлэх ёстой бөгөөд үүнд хэдэн мянган цэгүүдийг зааглах цэгүүд байх болно, өөрөөр хэлбэл баруун тийш 3 байрлал бүрийн дараа цэгүүд байрлана.

Жишээ нь

#1

n = 987
"987"

#2

n = 123456789
"123.456.789"

Тайлбар:

Дугаар нь 123456789. Хамгийн баруун цэг нь баруун талаас 3 байрлалтай байна. Тиймээс баруун талаас нь харвал 9,8 ба 7-г ардаа үлдээгээд 6-7 хооронд цэг тавина. Дараа нь 6,5, 4-ийг ардаа үлдээгээд 3-аас 4 хооронд цэг тавина.
Одоо 3,2 ба 1-ийг ардаа орхисон тул зүүн талд илүү олон тоо байвал бид цэг тавих болно. гэсэн асуултын дагуу хоёр тооны хооронд байх ёстой.
Тиймээс бид цэг тавихгүй.

арга барил

Юуны өмнө бид тоог мөр болгон хөрвүүлж байна (let str). Дараа нь бид str мөрийг баруун талаас нь дайрч байна. Бид for for loop ашиглаж байна. Давталт бүрт бид гурван цифрийг оруулаад цэг орууллаа.
Гэхдээ цифр оруулах бүрийн дараа бид str-ийн зүүн хязгаараас гарсан эсэхээ шалгана. Хэрэв тийм бол бид давталтыг таслах болно. Үгүй бол бид 3 цифр, дараа нь 1 цэг оруулсаар байх болно.

Цэг оруулах 3 дахь шалгалт нь хамгийн чухал цифр бөгөөд 123 эсвэл 123.456 эсвэл 123.456.789 гэх мэт хувилбаруудад ашиглагдах бөгөөд энэ тохиолдолд бид хамгийн зүүн цифрээс өмнө цэг оруулах шаардлагагүй болно.
Бид тэмдэгтүүдийг баруунаас зүүн тийш оруулж байгаа тул эцсийн хариултыг авахын тулд бидний бүтээсэн мөрийг буцааж өөрчлөх шаардлагатай байна. Тиймээс, мөр, буцааж өг.

Мянган тусгаарлагч Leetcode шийдэл

Хэрэгжүүлэх

Мянган тусгаарлагчийн Leetcode шийдэлд зориулсан C ++ програм

#include <bits/stdc++.h> 
using namespace std;
string thousandSeparator(int n) {
    string str=to_string(n);
    stringstream ss;
    for(int i=str.length()-1;i>=0;){
        ss<<str[i];//inserting 1st digit
        i--;
        if(i==-1)break;//checking if we are out of left bound
        ss<<str[i];//inserting 2nd digit
        i--;
        if(i==-1)break;//checking if we are out of left bound
        ss<<str[i];//inserting 3rd digit
        i--;
        if(i==-1)break;//checking if we are out of left bound
        ss<<".";//after 3 digits insertion, finally inserting a dot "."
    }
    str= ss.str();
    reverse(str.begin(),str.end());//reversing the final string
    return str;
}

int main()
{
    cout << thousandSeparator(123456789);
}
123.456.789

Мянган тусгаарлагчийн Leetcode шийдлийн Java програм

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

class Solution
{  
    public static  String thousandSeparator(int n) 
    {
        String str=n+"";
        StringBuilder sb=new StringBuilder();
        for(int i=str.length()-1;i>=0;){
            sb.append(str.charAt(i));//inserting 1st digit
            i--;
            if(i==-1)break;//checking if we are out of left bound
            sb.append(str.charAt(i));//inserting 2nd digit
            i--;
            if(i==-1)break;//checking if we are out of left bound
            sb.append(str.charAt(i));//inserting 3rd digit
            i--;
            if(i==-1)break;//checking if we are out of left bound
            sb.append(".");//after 3 digits insertion, finally inserting a dot "."
        }
        return sb.reverse().toString();//reverse and return the final string
    }
    
    public static void main(String args[])
    {
        System.out.println(thousandSeparator(123456789));
    }
}
123.456.789

Мянга тусгаарлагчийн Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (len): Бид өгөгдсөн тоог баруун цифрээс зүүн тийш дайран өнгөрөх тул төвөгтэй байдал нь O (len) байх бөгөөд len нь тухайн тооны цифрүүдийн тоо юм.

Сансрын нарийн төвөгтэй байдал 

O (len): бид java-д stringbuilder, c ++ дээр stringstream ашиглаж байсан тул нэмэлт орон зайг ашиглан O (len) орон зайг төвөгтэй болгодог.