Mündəricat
Problem bəyanat
Bu problemdə bizə bir mətn verilir sim boşluqlar arasında yerləşdirilən bəzi sözlərə sahib olmaq. Sözlərdə yalnız kiçik ingilis hərfləri ola bilər. Əlbətdə hər söz ən azı bir boşluqla ayrılır. Mətndə ən azı bir söz var.
məsələn mətn = "təcrübə mükəmməl edir"
Gördüyümüz kimi ixtiyari boşluq sayı var.
Mətni elə bir formata çevirməliyik ki, hər bir söz arasında bərabər sayda boşluq olsun və hər hansı bir boşluq qalsın, onda son sözdən sonra yığılacaq.
Boşluqların ümumi sayını dəyişdirmək məcburiyyətində deyilik. Həm də sözlərin ardıcıllığı dəyişdirilməməlidir.
misal
text = " practice makes perfect"
"practice makes perfect "
Explanation:
7 boşluq və 3 sözdən ibarətdir.
Sözlər arasındakı 7-3 = 1 boşluğu uyğunlaşdırmaq üçün 2 boşluğu bərabər şəkildə böləcəyik. Beləliklə, çıxışımızda sözlər arasında 7/2 = 3 boşluq olacaq və son sözdən sonra 7-6 = 1 boşluq yığılacaq.
Bu səbəbdən nəticə “təcrübə mükəmməl edir” olacaqdır.
text = " this is a sentence "
"this is a sentence"
Explanation:
Cəmi 9 boşluq və 4 söz var. 9 boşluğu sözlər arasında bərabər şəkildə bölə bilərik: 9 / (4-1) = 3 boşluq.
Yanaşma
Burada iki tapşırıq etməliyik. Birincisi, giriş sözündən bütün sözləri əldə etməkdir sim. İkincisi, boşluqları saymalıyıq. Bu məqsədlə giriş sətirini xətti keçirik. Tapılan xarakter boşluqdursa, iki şey edirik, biri bu boşluğu saymaq, digəri isə mövcud sözü sonlandırmaq və sözlər siyahısına əlavə etməkdir.
Mövcud xarakter boşluq deyilsə, onu cari sözümüzə əlavə edirik. Nəhayət, son boşluqdan sonra hər hansı bir söz görünürsə, keçiddən sonra da bu sözü əlavə edirik.
Beləliklə, boşluq sayını və giriş sətirindəki sözləri alırıq. İndi boşluqları sözlər arasında bərabər bölməliyik. Ancaq giriş sətirində yalnız bir söz ola biləcəyinə dair bir vəziyyətə diqqət yetirməliyik, buna görə də bu sözün ardından bütün boşluqları olan bir simli qaytarmalıyıq. Əks təqdirdə, bu boşluqları sözlər siyahısı arasında bərabər şəkildə bölməliyik.
Tutaq ki, n söz varsa, sözlər arasındakı mövqelər n-1-dir.
Beləliklə, boşluqları (sayaq) bu n-1 yerlərə bölməliyik
bu səbəbdən mərtəbə (count / n-1) bütün sözləri ayıracaq boşluqların eni olacaqdır.
və qalan boşluq sayı son sözdən sonra əlavə olunacaq.
yəni% (n-1) sayı boşluqların qalan sayı olacaqdır.
Nəhayət, hər bir söz və hər bir söz cütü arasındakı boşluq sayını (say / n-1) əlavə etməyə davam edəcəyik və son sözdən sonra boşluqların% (n-1) sayıb son sətri qaytarırıq.
Həyata keçirilməsi
C ++ Proqramı Sözlər Leetcode Həlli Arasında Boşluqları Yenidən Düzəldin
#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
Sözlər arasındakı boşluqların yenidən təşkil edilməsi üçün Java Proqramı Leetcode Həlli
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
Sözlər Leetcode Həlli Arasında Yenidən Düzəldilmiş Boşluqlar üçün Mürəkkəblik Analizi
Zamanın mürəkkəbliyi
O (n): Birincisi, giriş xəttimizi xətti keçirik və boşluqdan ayrılmış sözləri siyahımızda saxlayırıq. Daha sonra çıxış xəttimizi xətti vaxtda yaradırıq. Beləliklə, zaman mürəkkəbliyi O (n) olacaqdır.
Kosmik Mürəkkəblik
O (n): Sözlər siyahısı və sətir düzəldicisi (cpp halında sətir axını) şəklində xətti əlavə yerdən istifadə etdik.
