484. Find Permutation

LeetCode medium original: C# #array #csharp #graph #leetcode #medium #search #stack #string

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

s[i] == 'I', если perm[i] < perm[i + 1], и

s[i] == 'D', если perm[i] > perm[i + 1].

Дана chaîne s, восстановите лексикоgrapheически наименьшую перестановку perm и return её.

Exemple:

Input: s = "I"

Output: [1,2]

Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

C# solution

correspondant/original

public class Solution {
    public int[] FindPermutation(string s) {
        int[] res = new int[s.Length + 1];
        Stack<int> stack = new Stack<int>();
        int j = 0;
        for (int i = 1; i <= s.Length; i++) {
            if (s[i - 1] == 'I') {
                stack.Push(i);
                while (stack.Count > 0) {
                    res[j++] = stack.Pop();
                }
            } else {
                stack.Push(i);
            }
        }
        stack.Push(s.Length + 1);
        while (stack.Count > 0) {
            res[j++] = stack.Pop();
        }
        return res;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& FindPermutation(string s) {
        vector<int>& res = new int[s.size() + 1];
        stack<int> stack = new stack<int>();
        int j = 0;
        for (int i = 1; i <= s.size(); i++) {
            if (s[i - 1] == 'I') {
                stack.push(i);
                while (stack.size() > 0) {
                    res[j++] = stack.pop();
                }
            } else {
                stack.push(i);
            }
        }
        stack.push(s.size() + 1);
        while (stack.size() > 0) {
            res[j++] = stack.pop();
        }
        return res;
    }
}

Java solution

correspondant/original

public class Solution {
    public int[] findPermutation(String s) {
        int[] res = new int[s.length() + 1];
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i - 1) == 'I') {
                stack.push(i);
                while (!stack.isEmpty()) {
                    res[j++] = stack.pop();
                }
            } else {
                stack.push(i);
            }
        }
        stack.push(s.length() + 1);
        while (!stack.isEmpty()) {
            res[j++] = stack.pop();
        }
        return res;
    }
}

JavaScript solution

correspondant/original

var findPermutation = function(s) {
    let res = new Array(s.length + 1).fill(0)
    let stack = []
    let j = 0
    for (let i = 1; i <= s.length; i++) {
        if (s[i - 1] === 'I') {
            stack.push(i)
            while (stack.length) {
                res[j++] = stack.pop()
            }
        } else {
            stack.push(i)
        }
    }
    stack.push(s.length + 1)
    while (stack.length) {
        res[j++] = stack.pop()
    }
    return res
}

Python solution

correspondant/original

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = [0] * (len(s) + 1)
        stack = []
        j = 0
        for i in range(1, len(s) + 1):
            if s[i - 1] == 'I':
                stack.append(i)
                while stack:
                    res[j] = stack.pop()
                    j += 1
            else:
                stack.append(i)
        stack.append(len(s) + 1)
        while stack:
            res[j] = stack.pop()
            j += 1
        return res

Go solution

correspondant/original

func findPermutation(s string) []int {
    res := make([]int, len(s)+1)
    stack := []int{}
    j := 0
    for i := 1; i <= len(s); i++ {
        if s[i-1] == 'I' {
            stack = append(stack, i)
            for len(stack) > 0 {
                res[j] = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                j++
            }
        } else {
            stack = append(stack, i)
        }
    }
    stack = append(stack, len(s)+1)
    for len(stack) > 0 {
        res[j] = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        j++
    }
    return res
}

Algorithm

Инициализация

Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.

Для каждого числа i

Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все elementы из стека и добавьте их в result.

Завершение

Добавьте n в стек и извлеките все elementы из стека, добавив их в result. return список result, который представляет лексикоgrapheически наименьшую перестановку.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.