በቃላት መካከል ያሉ ቦታዎችን እንደገና ያስተካክሉ Leetcode Solution


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ 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 ክፍተቶች ፡፡

ቀረበ

እዚህ ሁለት ሥራዎችን መሥራት አለብን ፡፡ በመጀመሪያ ሁሉንም ቃላት ከእርዳታ ግብዓት ማግኘት ነው ክር. በሁለተኛ ደረጃ, ቦታዎቹን መቁጠር አለብን. ለዚሁ ዓላማ የግብዓት ገመዱን በቅደም ተከተል እያለፍን ነው ፡፡ የተገኘው ገጸ-ባህሪ ቦታ ከሆነ ሁለት ነገሮችን እናደርጋለን ፣ አንደኛው ይህንን ቦታ መቁጠር ሲሆን ሌላኛው ደግሞ የአሁኑን ቃል ማቋረጥ እና በቃላት ዝርዝር ውስጥ ማስገባት ነው ፡፡
የአሁኑ ገጸ-ባህሪ ቦታ ካልሆነ ታዲያ አሁን ባለው ቃላችን ውስጥ ብቻ እናያይዘዋለን ፡፡ በመጨረሻ ፣ ካለፈው ቦታ በኋላ የትኛውም ቃል እየታየ ከሆነ ፣ እኛ ደግሞ ቃሉን ከጉዞው በኋላ እንጨምረዋለን።

ስለዚህ ፣ በግብዓት ገመድ ውስጥ ያሉ የቦታዎች ብዛት እና ቃላቶችን እናገኛለን። አሁን ቦታዎቹን በቃላት መካከል በእኩል መከፋፈል አለብን ፡፡ ነገር ግን በግብዓት ገመድ ውስጥ አንድ ቃል ብቻ ሊኖር ስለሚችል የጠርዝ ጉዳይን ማስተዋል አለብን ፣ ስለሆነም ይህንን ቦታ የያዘውን ቃል በሁሉም ቦታዎች የተከተተውን አንድ ክር መመለስ አለብን። አለበለዚያ እነዚህን ክፍተቶች በቃላት ዝርዝር መካከል እኩል መከፋፈል አለብን ፡፡

N ቃላት ካሉ እንበል ፣ ከዚያ በቃላቱ መካከል ያሉት ቦታዎች n-1 ናቸው ፡፡
ስለዚህ ፣ ቦታዎቹን (ቁጥር እንቆጥራቸው) በእነዚህ n-1 ቦታዎች መከፋፈል አለብን
ስለዚህ ወለል (ቆጠራ / n-1) ሁሉንም ቃላት የሚለያቸው የቦታዎች ስፋት ይሆናል።
እና ከመጨረሻው ቃል በኋላ ቀሪዎቹ የቦታዎች ብዛት ይሟላሉ።
ማለትም ቆጠራ% (n-1) ቀሪዎቹ የቦታዎች ብዛት ይሆናል።

በመጨረሻም ፣ እያንዳንዱን ቃል እና የወለል ንጣፍ (ቆጠራ / 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

የቃላት ሌቲኮድ መፍትሔዎች መካከል ቦታዎችን እንደገና ለማቀናበር የጃቫ ፕሮግራም

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

የጊዜ ውስብስብነት

ኦ (n): በመጀመሪያ ፣ የግብዓት ህብረቁምፊችንን በመስመር ላይ እያለፍን እና የተለያቸውን ቦታ ቃላትን ወደ ዝርዝራችን ውስጥ እናከማቸዋለን። ከዚያ እኛ የውጤታማ ገመድችንን በመስመር ጊዜ ውስጥ እየፈጠርን ነው። ስለዚህ ፣ የጊዜ ውስብስብነት O (n) ይሆናል።

የቦታ ውስብስብነት 

ኦ (n): የቃላት ዝርዝር እና የሕብረቁምፊ ገንቢ (ሲፒፕ ቢኖር የክር ዥረት) መስመራዊ ተጨማሪ ቦታን ተጠቅመናል ፡፡