ຮວບຮວມພື້ນທີ່ລະຫວ່າງ ຄຳ ສັບ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ
string

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບຂໍ້ຄວາມ string ມີຈໍານວນຂອງຄໍາສັບຕ່າງໆທີ່ຖືກຈັດໃສ່ໃນບັນດາສະຖານທີ່. ຄຳ ສັບຕ່າງໆສາມາດມີຕົວອັກສອນພາສາອັງກິດນ້ອຍເທົ່ານັ້ນ. Ofcourse ແຕ່ລະຖ້ອຍ ຄຳ ຖືກແຍກອອກໄປຢ່າງ ໜ້ອຍ ໜຶ່ງ ຊ່ອງ. ພ້ອມກັນນັ້ນຂໍ້ຄວາມມີຢ່າງ ໜ້ອຍ ໜຶ່ງ ຄຳ.
ຕົວຢ່າງຂໍ້ຄວາມ =” ການປະຕິບັດເຮັດໃຫ້ດີເລີດ”
ດັ່ງທີ່ພວກເຮົາສາມາດເຫັນມີ ຈຳ ນວນພື້ນທີ່ທີ່ຕົນເອງມັກ.
ພວກເຮົາຕ້ອງປ່ຽນຕົວ ໜັງ ສືໃຫ້ເປັນຮູບແບບດັ່ງກ່າວເຊິ່ງມີ ຈຳ ນວນສະຖານທີ່ເທົ່າທຽມກັນລະຫວ່າງແຕ່ລະ ຄຳ ແລະຖ້າມີພື້ນທີ່ໃດ ໜຶ່ງ, ຫຼັງຈາກນັ້ນ ຄຳ ສັບເຫຼົ່ານັ້ນຈະຖືກສະສົມໄວ້ຫຼັງຈາກ ຄຳ ສຸດທ້າຍ.
ພວກເຮົາບໍ່ ຈຳ ເປັນຕ້ອງປ່ຽນ ຈຳ ນວນພື້ນທີ່ທັງ ໝົດ. ເຊັ່ນດຽວກັນລໍາດັບຂອງຄໍາສັບຕ່າງໆບໍ່ຄວນຈະຖືກປ່ຽນແປງ.

ຍົກຕົວຢ່າງ

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 ຊ່ອງຫວ່າງ.

ວິທີການ

ພວກເຮົາຕ້ອງເຮັດສອງ ໜ້າ ວຽກຢູ່ນີ້. ທຳ ອິດແມ່ນໄດ້ຮັບ ຄຳ ທຸກ ຄຳ ຈາກການປ້ອນຂໍ້ມູນໃຫ້ string. ອັນທີສອງ, ພວກເຮົາຄວນນັບພື້ນທີ່. ສຳ ລັບຈຸດປະສົງນີ້, ພວກເຮົາ ກຳ ລັງປ່ຽນເສັ້ນເສັ້ນເຂົ້າ. ຖ້າລັກສະນະທີ່ພົບເຫັນແມ່ນຊ່ອງຫວ່າງແລ້ວພວກເຮົາເຮັດສອງສິ່ງ, ໜຶ່ງ ແມ່ນການນັບພື້ນທີ່ນີ້ແລະອີກອັນ ໜຶ່ງ ແມ່ນການຢຸດ ຄຳ ສັບໃນປະຈຸບັນແລະໃສ່ມັນເຂົ້າໃນບັນຊີ ຄຳ.
ຖ້າຕົວລະຄອນປະຈຸບັນບໍ່ແມ່ນບ່ອນຫວ່າງແລ້ວພວກເຮົາພຽງແຕ່ຕື່ມມັນໃສ່ ຄຳ ຂອງພວກເຮົາໃນປະຈຸບັນ. ໃນທີ່ສຸດ, ຖ້າມີ ຄຳ ສັບໃດ ໜຶ່ງ ປະກົດອອກມາຫຼັງຈາກຊ່ອງຫວ່າງສຸດທ້າຍ, ພວກເຮົາກໍ່ຕື່ມ ຄຳ ສັບນັ້ນຕື່ມອີກຫຼັງຈາກທີ່ມີການປ່ຽນແປງ.

ດັ່ງນັ້ນ, ພວກເຮົາໄດ້ຮັບ ຈຳ ນວນພື້ນທີ່ແລະ ຄຳ ທີ່ຢູ່ໃນສະຕິງປ້ອນຂໍ້ມູນ. ຕອນນີ້ພວກເຮົາຕ້ອງແບ່ງພື້ນທີ່ໃຫ້ເທົ່າກັນລະຫວ່າງ ຄຳ. ແຕ່ພວກເຮົາຕ້ອງສັງເກດເຫັນກໍລະນີຂອບທີ່ອາດຈະມີພຽງ ຄຳ ດຽວໃນສາຍສະຕິງປ້ອນເຂົ້າ, ດັ່ງນັ້ນພວກເຮົາຕ້ອງກັບຄືນສາຍທີ່ມີ ຄຳ ນີ້ຕິດຕາມມາດ້ວຍທຸກຊ່ອງຫວ່າງ. ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາຕ້ອງແບ່ງພື້ນທີ່ເຫລົ່ານີ້ໃຫ້ເທົ່າທຽມກັນໃນບັນຊີລາຍຊື່ ຄຳ ສັບ.

ສົມມຸດວ່າຖ້າມີ ຄຳ ສັບ n, ຫຼັງຈາກນັ້ນ ຕຳ ແໜ່ງ ລະຫວ່າງ ຄຳ ວ່າ n-1.
ດັ່ງນັ້ນ, ພວກເຮົາຕ້ອງແບ່ງພື້ນທີ່ (ໃຫ້ນັບ) ເປັນສະຖານທີ່ n-1 ເຫຼົ່ານີ້
ດັ່ງນັ້ນຊັ້ນ (ນັບ / n-1) ຈະເປັນຄວາມກວ້າງຂອງພື້ນທີ່ເຊິ່ງຈະແຍກທຸກ ຄຳ.
ແລະ ຈຳ ນວນພື້ນທີ່ທີ່ເຫຼືອຈະຖືກຕື່ມໃສ່ຫຼັງຈາກ ຄຳ ສຸດທ້າຍ.
ie ນັບ% (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

Java Program ສຳ ລັບການຄົ້ນຫາພື້ນທີ່ລະຫວ່າງ ຄຳ ສັບ 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

ຄວາມສັບສົນເວລາ

ໂອ (n): ກ່ອນອື່ນ ໝົດ, ພວກເຮົາ ກຳ ລັງຜ່ານສາຍການປ້ອນຂໍ້ມູນຂອງພວກເຮົາເປັນເສັ້ນຊື່ແລະເກັບຮັກສາ ຄຳ ສັບທີ່ແຍກອອກໄປໃນບັນຊີຂອງພວກເຮົາ. ຈາກນັ້ນ, ພວກເຮົາ ກຳ ລັງສ້າງສະຕິງຜົນຜະລິດຂອງພວກເຮົາໃນເວລາເສັ້ນ. ດັ່ງນັ້ນ, ຄວາມສັບສົນເວລາຈະເປັນ O (n).

ຄວາມສັບສົນໃນອະວະກາດ 

ໂອ (n): ພວກເຮົາໄດ້ໃຊ້ພື້ນທີ່ເພີ່ມເຕີມເປັນເສັ້ນໃນຮູບແບບຂອງລາຍຊື່ ຄຳ ສັບແລະຜູ້ສ້າງສາຍໄຟ (ສາຍສະຕິງໃນກໍລະນີຂອງ cpp).