Сөздер арасындағы кеңістікті қайта реттеу Leetcode Solution


Күрделілік дәрежесі оңай
Жиі кіреді Google
String

Проблемалық мәлімдеме

Бұл мәселеде бізге мәтін беріледі жол бос орындардың арасында орналастырылған бірнеше сөздер бар. Сөздерде тек кіші ағылшын әріптері болуы мүмкін. Әрине, әр сөз кем дегенде бір бос орынмен бөлінеді. Сондай-ақ, мәтінде кем дегенде бір сөз бар.
мысалы, мәтін = «тәжірибе керемет етеді»
Көріп отырғанымыздай, кеңістіктің ерікті саны бар.
Біз мәтінді осындай форматқа ауыстыруымыз керек, онда әр сөздің арасында бірдей бос орын бар, егер бос орын қалса, онда олар соңғы сөзден кейін жинақталады.
Бос орындардың жалпы санын өзгертудің қажеті жоқ. Сонымен қатар сөздердің ретін өзгертуге болмайды.

мысал

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 бос орын.

жақындау

Біз мұнда екі тапсырма орындауымыз керек. Біріншіден, кіріс сөзінен барлық сөздерді алу жол. Екіншіден, біз бос орындарды санауымыз керек. Осы мақсатта біз енгізу жолын сызықтық түрде өтіп жатырмыз. Егер табылған таңба бос орын болса, онда біз екі нәрсе жасаймыз, бірі - осы кеңістікті санау, екіншісі - қолданыстағы сөзді тоқтату және оны сөздер тізіміне қосу.
Егер қазіргі таңба бос орын болмаса, онда біз оны жай қолданыстағы сөзге қосамыз. Ақыр соңында, егер соңғы кеңістіктен кейін қандай-да бір сөз пайда болса, біз бұл сөзді өтпелі жолдан кейін де қосамыз.

Сонымен, біз енгізу жолындағы бос орындар мен сөздерді аламыз. Енді бос орындарды сөздердің арасына тең бөлу керек. Бірақ біз енгізу жолында бір ғана сөз болуы мүмкін екенін ескеруіміз керек, сондықтан осы сөзден кейін барлық кеңістіктен тұратын жолды қайтаруымыз керек. Әйтпесе, біз осы кеңістікті сөздер тізіміне бірдей бөлуіміз керек.

Егер n сөз болса, онда сөздер арасындағы позициялар n-1 болады делік.
Осылайша, кеңістікті осы n-1 орындарға бөлуге тура келеді (санайық)
демек, қабат (count / n-1) барлық сөздерді бөлетін кеңістіктің ені болады.
және бос орындардың қалған саны соңғы сөзден кейін қосылады.
яғни% (n-1) саны бос орындардың қалған саны болады.

Соңында, біз әр сөзді қосамыз және әр сөз жұбы арасындағы бос орындардың санын (count / n-1) және соңғы сөзден кейін% (n-1) бос орын санын санап, соңғы жолды қайтарамыз.

Іске асыру

C ++ бағдарламасы сөздердің арасындағы кеңістікті қайта құру Leetcode шешімі

#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 бағдарламасы

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 болған жағдайда жол ағыны).