Leetcode: Find Permutation(Unsolve lock problem)
LeetCode Find lock Problem Permutation
2023-09-11 14:14:07 时间
By now, you are given a secret signature consisting of character 'D' and 'I'. 'D' represents a decreasing relationship between two numbers, 'I' represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature "DI" can be constructed by array [2,1,3] or [3,1,2], but won't be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can't represent the "DI" secret signature. On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, ... n] could refer to the given secret signature in the input. Example 1: Input: "I" Output: [1,2] Explanation: [1,2] is the only legal initial spectial string can construct secret signature "I", where the number 1 and 2 construct an increasing relationship. Example 2: Input: "DI" Output: [2,1,3] Explanation: Both [2,1,3] and [3,1,2] can construct the secret signature "DI", but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3] Note: The input string will only contain the character 'D' and 'I'. The length of input string is a positive integer and will not exceed 10,000
还没研究:
For example, given IDIIDD
we start with sorted sequence 1234567
Then for each k
continuous D
starting at index i
we need to reverse [i, i+k]
portion of the sorted sequence.
IDIIDD
1234567 // sorted
1324765 // answer
1 public class Solution { 2 public int[] findPermutation(String s) { 3 int n = s.length(), arr[] = new int[n + 1]; 4 for (int i = 0; i <= n; i++) arr[i] = i + 1; // sorted 5 for (int h = 0; h < n; h++) { 6 if (s.charAt(h) == 'D') { 7 int l = h; 8 while (h < n && s.charAt(h) == 'D') h++; 9 reverse(arr, l, h); 10 } 11 } 12 return arr; 13 } 14 15 void reverse(int[] arr, int l, int h) { 16 while (l < h) { 17 arr[l] ^= arr[h]; 18 arr[h] ^= arr[l]; 19 arr[l] ^= arr[h]; 20 l++; h--; 21 } 22 } 23 }
相关文章
- [LeetCode] Remove Duplicates from Sorted List - 链表问题
- Java实现 LeetCode 783 二叉搜索树节点最小距离(遍历)
- Java实现 LeetCode 738 单调递增的数字(暴力)
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- SQL Server实现 LeetCode 178 分数排名
- Java实现 LeetCode 167 两数之和 II - 输入有序数组
- Java实现 LeetCode 162 寻找峰值
- Java实现 LeetCode 138 复制带随机指针的链表
- LeetCode(73):矩阵置零
- LeetCode(23):合并K个排序链表
- [LeetCode] Find Peak Element
- LeetCode(76): 最小覆盖子串
- LeetCode(72):编辑距离
- leetcode 7. 整数反转
- Find Minimum in Rotated Sorted Array 旋转数组中找最小值 @LeetCode
- 【LeetCode Python实现】635. 设计日志存储系统(中等)
- Leetcode 2089. 找出数组排序后的目标下标
- Leetcode 1342. 将数字变成 0 的操作次数
- leetcode 501. Find Mode in Binary Search Tree
- leetcode 744. Find Smallest Letter Greater Than Target
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- LeetCode 226. 翻转二叉树
- 【LeetCode】 134.加油站