වචන අතර අවකාශය නැවත සකස් කරන්න ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ගූගල්
String

ගැටළු ප්රකාශය

මෙම ගැටලුවේදී අපට පෙළක් ලබා දී ඇත පේළියකි අවකාශයන් අතර තැන්පත් කර ඇති වචන කිහිපයක් තිබීම. වචනවල තිබිය හැක්කේ කුඩා අකුරු පමණි. සෑම වචනයක්ම අවම වශයෙන් එක් ඉඩකින් වෙන් කරනු ලැබේ. පා text යට අවම වශයෙන් එක් වචනයක්වත් තිබේ.
උදා: පෙළ = ”පුහුණුව පරිපූර්ණ කරයි”
අපට පෙනෙන පරිදි අත්තනෝමතික අවකාශ ගණනක් ඇත.
එක් එක් වචනය අතර සමාන ඉඩ ප්‍රමාණයක් ඇති පෙළක් අප එවැනි ආකෘතියකට පරිවර්තනය කළ යුතු අතර කිසියම් ඉඩක් ඉතිරිව තිබේ නම් ඒවා අවසාන වචනයෙන් පසුව එකතු වේ.
අපට මුළු ඉඩ ප්‍රමාණය වෙනස් කිරීමට අවශ්‍ය නැත. එසේම වචනවල අනුක්‍රමය වෙනස් නොකළ යුතුය.

උදාහරණයක්

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

පැහැදිලි කිරීම:

වචන අතර අවකාශය නැවත සකස් කරන්න ලීට්කෝඩ් විසඳුම

එහි අවකාශ 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) = XNUMX අවකාශ.

ප්රවේශය

අපි මෙහි කාර්යයන් දෙකක් කළ යුතුයි. පළමුවැන්න නම් සියලු වචන ලබා දීමෙන් ලබා ගැනීමයි පේළියකි. දෙවනුව, අපි අවකාශයන් ගණන් කළ යුතුය. මෙම අරමුණු සඳහා, අපි ආදාන නූල රේඛීයව ගමන් කරන්නෙමු. සොයාගත් අක්‍ෂරය අවකාශයක් නම් අපි කාරණා දෙකක් කරන්නෙමු, එකක් මෙම අවකාශය ගණනය කිරීම සහ අනෙක වර්තමාන වචනය අවසන් කර වචන ලැයිස්තුවට ඇතුළත් කිරීමයි.
වත්මන් අක්‍ෂරය අවකාශය නොවේ නම් අපි එය අපගේ වර්තමාන වචනයට එකතු කරමු. අන්තිමේදී, කිසියම් වචනයක් අන්තිම අවකාශයෙන් පසුව දිස්වන්නේ නම්, අපි එම වචනය ගමන් කිරීමෙන් පසුවද එකතු කරමු.

ඉතින්, අපට ආදාන නූලෙහි ඇති අවකාශ ගණන සහ වචන ලැබේ. දැන් අපට අවකාශයන් වචන අතර සමානව බෙදිය යුතුය. නමුත් ආදාන නූලෙහි එක වචනයක් පමණක් තිබිය හැකි බව අපි දකිමු, එබැවින් අපට මෙම වචනය ඇති සියලුම වචන අවකාශය අනුගමනය කළ යුතුය. එසේ නොමැතිනම්, මෙම අවකාශයන් වචන ලැයිස්තුව අතර සමානව බෙදිය යුතුය.

වචන n තිබේ නම්, වචන අතර පිහිටීම් n-1 යැයි සිතමු.
මේ අනුව, අපට අවකාශයන් (ගණන් කිරීමට ඉඩ දෙන්න) මෙම n-1 ස්ථානවලට බෙදිය යුතුය
එබැවින් තට්ටුව (ගණන් / n-1) යනු අවකාශයේ පළල වන අතර එය සියලු වචන වෙන් කරයි.
අවසාන වචනයෙන් පසුව ඉතිරි අවකාශ ගණන එකතු වේ.
එනම් ගණනය කිරීම්% (n-1) යනු ඉතිරි අවකාශ ගණන වේ.

අවසාන වශයෙන්, අපි එක් එක් වචනය සහ බිම (ගණන් / n-1) එක් එක් වචන යුගල අතර ඇති අවකාශ ගණන එකතු කර අවසන් වචනයට පසුව% (n-1) අවකාශ ගණන ගණන් කර අවසන් නූල නැවත ලබා දෙන්නෙමු.

ක්රියාත්මක කිරීම

සී ++ වැඩසටහන වචන අතර පරතරය නැවත සකස් කරන්න ලීට්කෝඩ් විසඳුම

#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

වචන ලීට්කෝඩ් විසඳුම අතර අවකාශය නැවත සකස් කිරීම සඳහා ජාවා වැඩසටහන

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

වචන ලීට්කෝඩ් විසඳුම අතර අවකාශය නැවත සකස් කිරීම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත): පළමුවෙන්ම, අපි අපගේ ආදාන නූල රේඛීයව ගමන් කරමින් අවකාශය වෙන් කළ වචන අපගේ ලැයිස්තුවට ගබඩා කරමු. ඉන්පසුව, අපි අපගේ නිමැවුම් රේඛාව රේඛීය වේලාවෙන් නිර්මාණය කරමු. මේ අනුව, කාල සංකීර්ණතාව O (n) වනු ඇත.

අභ්‍යවකාශ සංකීර්ණතාව 

මත): වචන ලැයිස්තුව සහ නූල් සාදන්නා (සීපීපී නම් නූල් ප්‍රවාහය) ස්වරූපයෙන් අපි රේඛීය අමතර ඉඩ භාවිතා කර ඇත්තෙමු.