從給定序列中形成最小數


難度級別
經常問 ol石 亞馬遜 狂徒 高盛 信息邊緣 Snapchat
排列

問題“從給定序列中形成最小數”表明您已獲得某種形式的 D的 只要。 的意思 I 代表增加和減少,我們被提供 D。 問題說明要求打印滿足給定模式的最小數量。 我們必須使用1到9之間的數字,並且不應重複任何數字。

DIID
21354

解釋

第一個數字為2,然後減少它的下一個數字為1。然後增加2將使3成為大於2的最小數字。然後我們必須再次增加它,但是由於在再次增加之後,我們必須減少它。 由於數字不能重複。 因此,我們將其增加2,然後將其減少1。

因此輸出將變為2 1 3 5 4

同樣,我們增加當前數字。 但是這樣做會給我們4,而在減少之後我們將不得不使用1、2或3。並且所有這些數字都已被使用。 因此,我們需要將當前數字增加到5。這就是我們得到答案的方式。

從給定序列中形成最小數的算法

  1. 檢查給定的序列長度是否大於或等於9,如果為true,則返回-1。
  2. 聲明一個大小為n + 1的char數組,並將count的值設置為1。
  3. 開始從0到n(包括XNUMX)遍歷數組。
    1. 檢查是否 i 等於 n 或字符串的當前字符等於“ I”,如果為true,則為
      1. 從先前的值到-1遍歷數組。
        1. 通過執行以下步驟來更新輸出數組的值。
          1. 增加count的值並將其存儲到輸出數組。
          2. 檢查是否 j 如果當前索引大於0,並且字符串的當前字符為“ I”,則中斷。
  4. 返回結果。

解釋

給定一個字符串以及僅I和D的字符串,要求我們打印可以使用給定字符串形成的圖案 。 這裡 I 指的是增加,即我們必須制定或形成可以證明給定序列合理的最小數量。 假設我們說 DI,其中 D 代表減少最小數量,以使2後面跟有一個作為最小數量的21。 數字不能重複,數字只能包含1-9之間的數字。 在那之後,“ I”在那裡,我們應該形成一個最小的遞增數。 因為21已經在那裡。 我們的目標是增加數量。 因此,1後面緊跟著3,因為2已經在使用中,此後3是唯一可以連接的數字。

利用所有這些概念和想法,要求我們打印遵循並滿足給定條件的最小數量。 我們將使用輸出數組,我們將所有輸出存儲到該字符數組中。 我們為數據驗證和驗證創造了一些條件。 如果我們發現字符串的長度大於或等於9,則返回-1作為結果,因為嚴格要求我們使用1-9位數字,並且不能重複數字。

遍歷我們收到的作為輸入的字符串。 如果當前索引等於字符串的長度,或者當前字符等於“ I”。 然後只有我們進一步進行。 之後,開始從當前值(i)之前的值開始遍歷,直到達到-1。 在此循環中,我們繼續增加count的值並將其存儲在索引j + 1處的輸出數組中。 然後檢查 j 大於或等於 0 以及當前字符是否為“ I”。 如果為true,則中斷循環並繼續進行操作以獲取更多字符。

推薦碼

C ++代碼從給定序列中形成最小數

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}
21354
132
123
213
32145
13254
1325476

Java代碼從給定序列中形成最小數量

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}
21354
132
123
213
32145
13254
1325476

複雜度分析

時間複雜度

上) 哪裡 “ N” 是查詢字符串的長度。 首先,只有在到達末尾或當前索引為I時,才檢查是否進入嵌套循環。嵌套循環向後運行,如果遇到I,則退出循環。所以我們可以說當我們遇到一個I並處理在其上存儲了D的索引時,我們進入嵌套循環。 由於每個索引可以具有I或D。我們僅遍歷每個字符。 因此,時間複雜度是線性的。

空間複雜度

上),因為我們已經創建了一個輸出字符數組來存儲結果。 該問題的空間複雜度也是線性的。