სივრცის გადალახვა სიტყვებს შორის Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Google
სიმებიანი

პრობლემის განცხადება

ამ პრობლემის დროს, ჩვენ გვეძლევა ტექსტი სიმებიანი სიტყვების გარკვეული რაოდენობა, რომლებიც განთავსებულია სივრცეებს ​​შორის. სიტყვებს შეიძლება ჰქონდეთ მხოლოდ პატარა ინგლისური ასოები. რა თქმა უნდა, თითოეული სიტყვა გამოყოფილია მინიმუმ ერთი ინტერვალით. ასევე ტექსტს აქვს ერთი სიტყვა მაინც.
მაგალითად, ტექსტი = ”პრაქტიკა სრულყოფს”
როგორც ვხედავთ, სივრცეების თვითნებური რაოდენობაა.
ჩვენ უნდა გადავიყვანოთ ტექსტი ისეთ ფორმატში, რომელშიც თანაბარი რაოდენობის სივრცეა თითოეულ სიტყვას შორის და თუ ადგილი დარჩება, მაშინ ისინი დაგროვდება ბოლო სიტყვის შემდეგ.
ჩვენ არ უნდა შევცვალოთ ფართების საერთო რაოდენობა. ასევე არ უნდა შეიცვალოს სიტყვების თანმიმდევრობა.

მაგალითი

text = " practice makes perfect"
"practice makes perfect "

განმარტება:

სივრცის გადალახვა სიტყვებს შორის Leetcode Solution

მას აქვს 7 სივრცე და 3 სიტყვა.
თანაბრად გავყოფთ 7 ადგილს, რომ სიტყვებს შორის დავტოვოთ 3-1 = 2 სიცარიელე. ამრიგად, ჩვენს გამოცემაში 7/2 = 3 სივრცე იქნება სიტყვებს შორის და ბოლო სიტყვის შემდეგ დაგროვდება 7-6 = 1 დარჩენილი სივრცე.
ამიტომ შედეგი იქნება "პრაქტიკა სრულყოფს".

text = " this is a sentence "
"this is a sentence"

განმარტება:

სულ 9 სივრცე და 4 სიტყვაა. შეგვიძლია თანაბრად დავყოთ 9 სივრცე სიტყვებს შორის: 9 / (4-1) = 3 სივრცე.

მიდგომა

აქ ორი დავალება უნდა შევასრულოთ. პირველი არის ყველა სიტყვის მიღება input input- იდან სიმებიანი. მეორე, ჩვენ უნდა დავთვალოთ სივრცეები. ამ მიზნით, ჩვენ ხაზობრივად ვათვალიერებთ შეყვანის სტრიქონს. თუ ნაპოვნი სიმბოლო არის სივრცე, ჩვენ ორ რამეს ვაკეთებთ, ერთი ამ სივრცის დათვლა და სხვა არის მიმდინარე სიტყვის დასრულება და ჩასმა სიტყვების სიაში.
თუ ამჟამინდელი სიმბოლო არ არის სივრცე, ჩვენ მას ვუერთდებით ჩვენს ახლანდელ სიტყვას. დაბოლოს, თუ ბოლო სიტყვის შემდეგ გამოჩნდება რომელიმე სიტყვა, გავლის შემდეგ მას ვამატებთ.

ასე რომ, ვიღებთ სივრცეების რაოდენობას და სიტყვებს შეყვანის სტრიქონში. ახლა ჩვენ სივრცეები თანაბრად უნდა დავყოთ სიტყვებს შორის. მაგრამ ჩვენ უნდა შევნიშნოთ ზღვრული შემთხვევა, რომ შეყვანის სტრიქონში შეიძლება იყოს მხოლოდ ერთი სიტყვა, ამიტომ ჩვენ უნდა დავუბრუნოთ სტრიქონი, რომელსაც აქვს ეს სიტყვა, რომელსაც მოჰყვება ყველა სივრცე. წინააღმდეგ შემთხვევაში, ეს სივრცეები თანაბრად უნდა დავყოთ სიტყვების ჩამონათვალში.

დავუშვათ, თუ არსებობს n სიტყვა, მაშინ სიტყვებს შორის პოზიციებია n-1.
ამრიგად, ჩვენ უნდა დავყოთ სივრცეები (დავთვალოთ) ამ n-1 ადგილებად
შესაბამისად, სართული (რიცხვი / n-1) იქნება ფართების სიგანე, რომელიც გამოყოფს ყველა სიტყვას.
ხოლო სივრცეების დარჩენილი რაოდენობა დაერთვება ბოლო სიტყვის შემდეგ.
ანუ რიცხვი% (n-1) იქნება სივრცეების დარჩენილი რაოდენობა.

დაბოლოს, ჩვენ გავაგრძელებთ თითოეული სიტყვის და იატაკის (count / n-1) ფართების რაოდენობას თითოეულ წყვილ სიტყვებს შორის და დავთვლით% (n-1) ადგილების რაოდენობას ბოლო სიტყვის შემდეგ და დავაბრუნებთ საბოლოო სტრიქონს.

განხორციელება

C ++ პროგრამის სიტყვების სივრცეების გადანაწილება Leetcode Solution

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

string reorderSpaces(string text) 
{
        int count=0;
        stringstream ss;
        vector<string> list;
        for(int i=0;i<text.length();i++){
            if(text[i]==' '){
                if(ss.str().size()>0)list.push_back(ss.str());//if there is some character present, only then 
                // insert into list
                count++;
                ss.str("");//empties the stringstream object
            }else{
                ss<<text[i];
            }
        }
        if(ss.str().size()>0)list.push_back(ss.str());//in case if any string is after the last space, that is not inserted into list.
        
        
        int wid=0,rem=0,l=0;
        if(list.size()==1){
            wid=0;
            rem=count;
        }else{
        /*number of positions between n words is n-1. thus l = list.size()-1*/
        l=list.size()-1;
        /*distributing the spaces equally in l places*/
        wid=count/l;
        /*and the remaining spaces will be appended at last*/
        rem=count%l;
        }
        ss.str("");
        for(int i=0;i<list.size();i++){
            ss<<list[i];//appending a word
            int w=wid;
            if(i<list.size()-1)
            while(w--!=0)ss<<' ';//appending spaces which is width we calculated above
        }
        while(rem--!=0)ss<<' ';//finally appending all the remaining spaces
        return ss.str();
}

int main()
{
    cout << reorderSpaces("  this   is  a sentence ");
}
this   is   a   sentence

Java პროგრამა სიტყვებს შორის სივრცეების გადალაგებისათვის Leetcode Solution

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

class Rextester
{  
    public static void main(String args[])
    {
        System.out.println(reorderSpaces("  this   is  a sentence "));
    }
    
    public static String reorderSpaces(String text) 
    {
        int count=0;
        StringBuilder sb=new StringBuilder();
        List<String> list=new ArrayList<String>();
        for(int i=0;i<text.length();i++){
            if(text.charAt(i)==' '){
                if(sb.length()>0)list.add(sb.toString());//if there is some non-space character also present, only then 
                // insert into list
                count++;//counting spaces
                sb=new StringBuilder();//empties the stringstream object
            }else{
                sb.append(text.charAt(i));
            }
        }
        if(sb.length()>0)list.add(sb.toString());//in case if any string is after the last space, that is not inserted into list.
        
        
        int wid=0,rem=0,l=0;
        if(list.size()==1){
            wid=0;
            rem=count;
        }else{
       /*number of positions between n words is n-1. thus l = list.size()-1*/
        l=list.size()-1;
      /*distributing the spaces equally in l places*/
        wid=count/l;
       /*and the remaining spaces will be appended at last*/
        rem=count%l;
        }
        sb=new StringBuilder();
        for(int i=0;i<list.size();i++){
            sb.append(list.get(i));//appending a word
            int w=wid;
            if(i<list.size()-1)
            while(w--!=0)sb.append(' ');//appending spaces which is width we calculated above
        }
        while(rem--!=0)sb.append(' ');//finally appending all the remaining spaces
        return sb.toString();
    }
}
this   is   a   sentence

სირთულის ანალიზი სიტყვებს შორის სივრცეების გადალაგებისათვის Leetcode Solution

დროის სირთულე

O (n): პირველ რიგში, ჩვენ ხაზგასმულად ვათვალიერებთ ჩვენი შეყვანის სტრიქონს და ჩვენს სიაში ვინახავთ გამოყოფილ სიტყვებს. შემდეგ, ჩვენ ვქმნით გამომავალ სტრიქონს სწორხაზოვან დროში. ამრიგად, დროის სირთულე იქნება O (n).

სივრცის სირთულე 

O (n): ჩვენ გამოვიყენეთ ხაზოვანი დამატებითი სივრცე სიტყვების ჩამონათვალისა და სიმების შემქმნელის სახით (სიმებიანი ნაკადი cpp– ს შემთხვევაში).