โซลูชัน Leetcode ตัวคั่นพัน


ระดับความยาก สะดวกสบาย
เชือก

คำชี้แจงปัญหา

ในปัญหานี้เราจะได้รับจำนวนเต็มที่ไม่เป็นลบ เราต้องแปลงจำนวนเต็มในรูปแบบดังกล่าวซึ่งจะมีจุดบางจุดที่แยกออกเป็นพัน ๆ ทั้งหมดนั่นคือมีจุดตามแต่ละ 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 ไว้ข้างหลังเราจะใส่จุดก็ต่อเมื่อมีตัวเลขทางซ้ายมากกว่าเพราะ ควรอยู่ระหว่างตัวเลขสองตัวตามคำถาม
ดังนั้นเราจะไม่วางจุดใด ๆ

เข้าใกล้

ก่อนอื่นเรากำลังแปลงตัวเลขเป็นสตริง (ให้ str) จากนั้นเราจะข้ามสตริง str จากด้านขวา เรากำลังใช้ for loop สำหรับสิ่งนี้ ในแต่ละลูปเราจะแทรกตัวเลขสามหลักตามด้วยจุด
แต่หลังจากการแทรกแต่ละหลักเราจะตรวจสอบว่าเราได้ยื่นมือออกจากขอบเขตด้านซ้ายของ str หรือไม่ ถ้าใช่เราจะทำลายลูป มิฉะนั้นเราจะแทรกตัวเลข 3 หลักและ 1 จุดไปเรื่อย ๆ

โปรดทราบว่าการตรวจสอบครั้งที่ 3 เพื่อแทรกจุดเป็นสิ่งสำคัญซึ่งจะใช้ในสถานการณ์เช่น 123 หรือ 123.456 หรือ 123.456.789 โดยที่เราไม่จำเป็นต้องแทรกจุดก่อนหลักซ้ายสุด
เนื่องจากเรากำลังแทรกอักขระจากขวาไปซ้ายจึงจำเป็นต้องย้อนกลับสตริงที่สร้างขึ้นเพื่อให้ได้คำตอบสุดท้าย ดังนั้นหลังจากย้อนกลับไฟล์ เชือกส่งคืน

โซลูชัน Leetcode ตัวคั่นพัน

การดำเนินงาน

โปรแกรม C ++ สำหรับโซลูชัน Leetcode พันตัวคั่น

#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

โปรแกรม Java สำหรับโซลูชัน Leetcode ตัวคั่นพัน

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 (เลน): เรากำลังข้ามตัวเลขที่กำหนดจากหลักขวาไปซ้ายดังนั้นเวลา Complexity จะเป็น O (len) โดยที่ len คือจำนวนหลักในจำนวนที่กำหนด

ความซับซ้อนของอวกาศ 

O (เลน): เราได้ใช้ stringbuilder ใน java และ stringstream ใน c ++ ดังนั้นการใช้พื้นที่พิเศษทำให้ความซับซ้อนของพื้นที่ O (len)