Word Wrap көйгөйү


Кыйынчылык деңгээли катуу
Көп суралган Арцезий Factset GreyOrange Microsoft Myntra Ola Cabs PayU
Динамикалык программалоо

Маселени билдирүү

Сөздүн оролушуна байланыштуу маселе, сөздөрдүн удаалаштыгын киргизүү катары бергендиктен, бир эле учурда бир сапка батыра турган сөздөрдүн санын табышыбыз керек. Демек, бул үчүн биз басылып чыккан документ жагымдуу көрүнүшү үчүн, берилген ырааттуулукка тыныгуу бердик. Microsoft Office, Libre Office жана башка документ шаймандары сыяктуу сөз редакторлору документтин жагымдуу көрүнүшү үчүн саптык тыныгууларды колдонушат. Бул жерде биз мейкиндиктерди бирдей жайылып жайгаштыралы дегенбиз. Кошумча боштуктары бар, айрымдары аз өлчөмдөгү сызыктар болбошу керек.

Бул жерде, ошондой эле, биздин сөздүн узундугу сызык өлчөмүнөн ашпайт деп ойлойбуз. Бир аз жалпы нерсени жаратуу үчүн, суроонун const функциясын (Кошумча мейкиндиктин саны) ^ 3 деп эсептейбиз, антпесе ал оңой болмок. Бул чыгым функциясы берилген суроого жараша өзгөрүлүшү мүмкүн.

Word Wrap Dp ыкмасы

мисал

Бул жерде биз сөздөрдүн санын, сөздүн көлөмүн жана сап көлөмүн киргизүү катары беребиз.

number of words = 4

wordSize = { 3, 2, 2, 5}

lineSize = 6
28

Түшүндүрмө: 1-сапка 1-орунга 3 ашыкча боштук, 2-жана 3-сөз, 2-сапка, 1 кошумча боштук, ал эми акыркы сөз, 3-сапка ашыкча орун калтырып койсок болот (акыркы сөздөн кийинки боштуктарды эске албайбыз) кошумча мейкиндик катары). Ошентип, өздүк нарк функциясын колдонуп, биз 28 деп эсептейбиз.

number of words = 3

wordSize = { 1, 1, 1}

lineSize = 10
00

Түшүндүрмө: Бул жерде биз бардык сөздөрдү бир сапка жайгаштыра алабыз, башкача айтканда 1-сапка, демек, чыгым = 0.

 

Сөздүн оролушуна байланыштуу маселе

Акылга келген биринчи ыкма - бул жөн эле сөздөрдү бир сапка жайгаштыра берген ач көздүк. Сөздү бир эле сапка жайгаштыра албагандан кийин, экинчи сапка өтөбүз. Бул жакшы эле иштейт окшойт, бирок бир нерсе бар. Бул алгоритм оптималдуу натыйжа бербейт, анткени мындай ашыкча мейкиндикти өзгөрткөндө, глобалдык чечимге келүүбүз мүмкүн.

Ач көз мамилени колдонуп чыгыңыз

”cat is an animal”, line size = 6
65

 

Жөнөкөй түшүнүк үчүн, биз текстти wordSize ордуна сөздөр катары көрсөттүк.

Түшүндүрмө: мышык

                        an____

                        жаныбар

Бул жерде, экинчи сапта 4 жана үчүнчү сапта 1 ашыкча боштук бар.

Эсептөө: 4 ^ 3 + 1 ^ 3 = 65

 

Андан да жакшы чечим бар,

cat___

an_

жаныбар

Бизге жалпы 28 (3 ^ 3 + 1 ^ 3 + 0 ^ 3) наркын берүү, бул 65тен жакшы.

Эми, сөздү ороп көйгөйүн колдонуп чечебиз Динамикалык программалоо. Биздин маселе глобалдык оптималдуу чечимге муктаж экендигин жана мурунку алгоритм натыйжада жергиликтүү оптимумду бергенге аракет кылып жаткандыгын билебиз. Бул жерде биз ар бир сапта алынган ашыкча орунду табабыз жана ошону менен катар ар бир сап үчүн бааны табабыз. Биз ExtraSpace матрицасын колдойбуз, ал экстра мейкиндикти сапта калтырат, и ден j ге чейинки сөздөр бир сапта турат. Андан ары минималдуу чыгымды табуу үчүн бул ExtraSpace матрицасын колдонобуз.

коду

Сөз оромосундагы көйгөй үчүн C ++ коду

#include <bits/stdc++.h>
using namespace std;

int wordWrap (int wordSize[], int n, int lineSize) 
{ 
  int extraSpace[n+1][n+1];
  int minCost[n+1];

  for (int i=1;i<=n;i++) 
  { 
    extraSpace[i][i] = lineSize - wordSize[i-1];
    for (int j=i+1;j<=n;j++) 
        extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
  }
  
  minCost[0] = 0; 
  for (int i = 1; i <= n; i++) 
  { 
    minCost[i] = INT_MAX;
    for (int j = 1; j <= i; j++) 
    { 
        int cost; // stores cost of storing words[i,j] in single line
        
        //if extraSpace required is negative, then we can't place
        //words[i,j] in a single line, else if we placed our last
        //word, then we don't consider extraSpace, else calculate
        //cost as per given cost function.
        if(extraSpace[j][i]<0)cost = INT_MAX;
        else if(i==n && extraSpace[j][i]>=0)cost = 0;
        else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
        
      if (minCost[j-1] != INT_MAX && cost != INT_MAX
      && (minCost[j-1] + cost < minCost[i])) 
        minCost[i] = minCost[j-1] + cost;
    }
  }
  
  return minCost[n];
} 

int main() 
{
    int t;cin>>t;
    while(t--) {
       int n;cin>>n;
       int wordSize[n];
       for(int i=0;i<n;i++)
            cin>>wordSize[i];
       int lineSize;cin>>lineSize;
       int ans = wordWrap(wordSize, n, lineSize);
       cout<<ans<<endl;
    }
}
3
4
3 2 2 6
6
3
1 1 1
10
4
1 1 1 1
5
28
0
0

Сөздүн оролушуна байланыштуу Java коду

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{ 
  static int wordWrap (int wordSize[], int n, int lineSize) 
  { 
    int extraSpace[][] = new int[n+1][n+1]; 
    int minCost[] = new int[n+1];
  
    for (int i=1;i<=n;i++) 
    { 
      extraSpace[i][i] = lineSize - wordSize[i-1];
      for (int j=i+1;j<=n;j++) 
          extraSpace[i][j] = extraSpace[i][j-1] - wordSize[j-1] - 1; 
    } 
    
    	minCost[0] = 0; 
    	for (int i = 1; i <= n; i++) 
    	{ 
    		minCost[i] = Integer.MAX_VALUE;
    		for (int j = 1; j <= i; j++) 
    		{ 
    		    int cost; // stores cost of storing words[i,j] in single line
    		    
    		    //if extraSpace required is negative, then we can't place
    		    //words[i,j] in a single line, else if we placed our last
    		    //word, then we don't consider extraSpace, else calculate
    		    //cost as per given cost function.
    		    if(extraSpace[j][i]<0)cost = Integer.MAX_VALUE;
    		    else if(i==n && extraSpace[j][i]>=0)cost = 0;
    		    else cost = extraSpace[j][i]*extraSpace[j][i]*extraSpace[j][i];
    		    
    			if (minCost[j-1] != Integer.MAX_VALUE && cost != Integer.MAX_VALUE
    			&& (minCost[j-1] + cost < minCost[i])) 
    				minCost[i] = minCost[j-1] + cost;
    		}
    	}
  
    return minCost[n];
  } 

  public static void main(String args[]) 
  {
      Scanner sc = new Scanner(System.in);
      
      int t = sc.nextInt();
      while(t-- > 0) {
         int n = sc.nextInt();
         int wordSize[] = new int[n];
         for(int i=0;i<n;i++)
              wordSize[i] = sc.nextInt();
         
         int lineSize = sc.nextInt();
         int ans = wordWrap(wordSize, n, lineSize);
         System.out.println(ans);
      }
  }
} 

 

3 
4 
3 2 2 6
6 
3 
1 1 1 
10 
4 
1 1 1 1 
5 
28 
0 
0

Комплекстик анализ

Убакыттын татаалдыгы: O (n ^ 2)

Бул жерде биздин тышкы цикл 1 ден nге чейин, ал эми ички цикл 1 ден i ге чейин иштегендиктен, бизде O (n ^ 2) полиномдук убакыт татаалдыгы бар.

Космостун татаалдыгы: O (n ^ 2)

Бул жерде биздин ExtraSpace массивибиз N * N өлчөмүндөгү 2D массив болуп саналат, ал бизге O (N ^ 2) полиномдук мейкиндик татаалдыгын берет.