LC: 484. Find Permutation
https://leetcode.com/problems/find-permutation/
A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:
s[i] == 'I'ifperm[i] < perm[i + 1], ands[i] == 'D'ifperm[i] > perm[i + 1].
Given a string s, reconstruct the lexicographically smallest permutation perm and return it.
Example 1:
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.Example 2:
Input: s = "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]Constraints:
1 <= s.length <= 105s[i]is either'I'or'D'.
The Essence:
In diesem Problem ist die einfachste Eingabe eine Zeichenkette wie “IIIIIIII” (achtmal ‘I’ hier), die nur aus ‘I’s besteht und einer steigenden Liste der Zahlen wie [1,2,3,4,5,6,7,8,9] entspricht. Wenn man mit 3 'D's ersetzt: "IIIIDDDI" => [1,2,3,4,8,7,6,5,9]. Man kann erkennen, dass ‘D’ ein bestimmtes Zahlenintervall umkehrt.
Details:
Die Problemlöser können die Länge des Intervalls mit ‘D’ bestimmen, dann die Zahlen in diesem Intervall umgekehrt ergänzen oder ersetzen.
Solutions:
https://github.com/spiralgo/algorithms/tree/master/src/main/java/algorithms/curated170/medium/findpermutation Default Code:
class Solution {
public int[] findPermutation(String s) {
}
}Last updated