Рубрики

Генерация последовательности с заданными операциями

Учитывая строку который содержит только (увеличить) и (Уменьшение). Задача состоит в том, чтобы вернуть любую перестановку целых чисел [0, 1,…, N], где N ≤ Длина S, такую, что для всех i = 0,…, N-1 :

  1. Если S [i] == «D», то A [i]> A [i + 1]
  2. Если S [i] == «I», то A [i] <A [i + 1].

Обратите внимание, что выходные данные должны содержать различные элементы.

Примеры:

Input: S = “DDI”
Output: [3, 2, 0, 1]

Input: S = “IDID”
Output: [0, 4, 1, 3, 2]

Подход: если S [0] == «I» , то выберите как первый элемент. Аналогично, если S [0] == «D» , выберите как первый элемент. Теперь для каждого операции, выберите следующий максимальный элемент, который не был выбран ранее, из диапазона [0, N] и для операции, выберите следующий минимум.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ Реализация вышеуказанного подхода
#include<bits/stdc++.h>

using namespace std;

    // функция для поиска минимально необходимой перестановки

    void  StringMatch(string s) 

    {

    int lo=0, hi = s.length(), len=s.length(); 

    vector<int> ans;

    for (int x=0;x<len;x++)

    {

        if (s[x] == 'I'

        {

            ans.push_back(lo) ;

            lo += 1;

            }

        else

        {

            ans.push_back(hi) ;

            hi -= 1;

            }

    }

            ans.push_back(lo) ;

    cout<<"[";

    for(int i=0;i<ans.size();i++)

    {

    cout<<ans[i];

    if(i!=ans.size()-1)

    cout<<",";

    }

    cout<<"]";

}
// Код драйвера

int main()

{

string S = "IDID";

StringMatch(S); 

return 0;

}
// предоставлено Арнабом Кунду

Джава

// Java-реализация вышеуказанного подхода

import java.util.*;

  

class GFG 

{

  
// функция для поиска минимально необходимой перестановки

static void StringMatch(String s) 

{

    int lo=0, hi = s.length(), len=s.length(); 

    Vector<Integer> ans = new Vector<>();

    for (int x = 0; x < len; x++)

    {

        if (s.charAt(x) == 'I'

        {

            ans.add(lo) ;

            lo += 1;

        }

        else

        {

            ans.add(hi) ;

            hi -= 1;

        }

    }

            ans.add(lo) ;

    System.out.print("[");

    for(int i = 0; i < ans.size(); i++)

    {

        System.out.print(ans.get(i));

        if(i != ans.size()-1)

            System.out.print(",");

    }

    System.out.print("]");

}

  
// Код драйвера

public static void main(String[] args)

{

    String S = "IDID";

    StringMatch(S); 

}
}

  
// Этот код предоставлен Rajput-Ji

питон

# Python Реализация вышеуказанного подхода

  
# функция для поиска минимально необходимой перестановки

def StringMatch(S):

    lo, hi = 0, len(S)

    ans = []

    for x in S:

        if x == 'I':

            ans.append(lo)

            lo += 1

        else:

            ans.append(hi)

            hi -= 1

  

    return ans + [lo]

  
# Код драйвера

S = "IDID"

print(StringMatch(S))

C #

// C # Реализация вышеуказанного подхода

using System;

using System.Collections.Generic;

  

class GFG 

{

  
// функция для поиска минимально необходимой перестановки

static void StringMatch(String s) 

{

    int lo=0, hi = s.Length, len=s.Length; 

    List<int> ans = new List<int>();

    for (int x = 0; x < len; x++)

    {

        if (s[x] == 'I'

        {

            ans.Add(lo) ;

            lo += 1;

        }

        else

        {

            ans.Add(hi) ;

            hi -= 1;

        }

    }

            ans.Add(lo) ;

    Console.Write("[");

    for(int i = 0; i < ans.Count; i++)

    {

        Console.Write(ans[i]);

        if(i != ans.Count-1)

            Console.Write(",");

    }

    Console.Write("]");

}

  
// Код драйвера

public static void Main(String[] args)

{

    String S = "IDID";

    StringMatch(S); 

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

[0, 4, 1, 3, 2]

Рекомендуемые посты:

Генерация последовательности с заданными операциями

0.00 (0%) 0 votes