FindPermutation [source code]
public class FindPermutation {
static
/******************************************************************************/
public class Solution {
public int[] findPermutation(String s) {
char[] chs = s.toCharArray();
int[] res = new int[chs.length + 1];
int i = 0;
while (i < res.length) {
res[i] = i + 1;
if (i < chs.length && chs[i] == 'D') {
int start = i;
while (i < chs.length && chs[i] == 'D')
i++;
for (int k = start; k <= i; k++)
res[k] = start + i - k + 1;
}
i++;
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
FindPermutation.Solution tester = new FindPermutation.Solution();
String[] inputs = {
"DDIIDI",
"IIDD",
};
int[][] answers = {
{3,2,1,4,6,5,7},
{1,2,5,4,3},
};
for (int i = 0; i < inputs.length; i++) {
System.out.println(Printer.seperator());
String s = inputs[i];
String output = Printer.array(tester.findPermutation(s));
String answer = Printer.array(answers[i]);
System.out.println(Printer.wrapColor(s, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, output.equals(answer) ? "green" : "red"));
}
}
}
这个题目完全没有思路, 最后直接看答案了;
这个题目思考的时候实际上有点受到这个greedy的tag的干扰了, 最后editorial给的这个答案, 严格来说并不是一个greedy的思路, 就是一个针对这个问题专门想出来的一个算法;
另外这个问题也是属于, 还是要看懂题目, 然后想出来这么一个intuition, 就可以做出来的题目;
虽然说这个题目解题的关键是了解题目本身的策略, 但是这个问题本身写代码的时候也是有所讲究的, 比如这里的这个历史信息流算法的代码其实并不是那么好写, 自己还要在写的时候多举例来思考变量和逻辑的branch到底怎么设置: Google的题目没有trivial的算法这么一个说法;
在分段的时候, 注意, 下降段应该是两头都是inclusive的; 上升段则是随便: 剩下来是什么就直接用上升段的逻辑来处理;
即便是刚开始看完了editorial3的解答, 真正自己写代码的时候还是卡了很久. 刚开始我的想法就是很简单的, 到了一个位置之后, 判断这个位置前方的trend是I还是D. 如果是I就正常fill, 如果是D就准备reverse fill. 这样写出来的代码:
public class Solution {
public int[] findPermutation(String s) {
char[] chs = s.toCharArray();
int[] res = new int[chs.length + 1];
int i = 0;
while (i < chs.length) {
if (chs[i] == 'I') {
res[i] = i + 1;
i++;
} else {
int start = i;
while (i < chs.length && chs[i] == 'D')
i++;
for (int k = start; k <= i; k++)
res[k] = start + i - 1 - k;
i++;
}
}
return res;
}
}
这个是有问题的, 这个最后有一个问题就是res最后一个位置无法处理: 你每一个位置都依赖于判断chs的内容, 而res的最后一个位置是没有对应的chs的entry的;
正确的editorial3的写法, 其实是一个override, 而不是一个branching的逻辑; 到达一个位置, 首先我们默认认为这里是I, unless we discovered otherwise.
这个题目其实还是暴露了我个人思考方式的很多问题的, 不过是哪些方面的问题呢? 感觉shared iteration这个东西我非常的不擅长; 尤其是这一题, 其实还是两个长度不相等的shared iteration问题;
分段算法: 段落结束处理 优于 段落开头探路
其实你看看下面submission最优解的思路, 其实就比较好: 是一个非常类似分段算法的思路: 我们处理一个段落(这里是一个D区间)的时机, 不应该是段落开始的地方进行探路, 这样很麻烦! 最好的逻辑, 其实是在段落当中妥善记录就行了, 而在段落结束的时候(看到I了), 我们才开始处理段落; 这样的逻辑一个很好的特点就是流尾很好处理: 即使可能需要额外的代码, 但是很好处理;
如果非要段落开头探路, 那么或许要用override的逻辑而不是branching的逻辑? 感觉这样总结好像有点草率;
这么想想我这个问题上这么卡, 也许也可能就是这种问题接触的还不够? 段落开头探路的处理我接触的确实不是很多;
另外想想为什么段落开头探路流尾就不好处理? 因为段落开头探路的算法, 是不保存历史信息的! you know nothing about the past. 所以当你走到流尾的时候, 你手上除了这个entry自己的信息, 其他的信息一点都没有; 然而如果你想要正确的处理流尾, 你是需要这个信息的, 比如假如说流尾其实是在一个很长的D段的末尾, 那么这个整个长D段其实都是会被流尾的存在影响的;
所以段落开头探路的处理方式, 就比较依赖一个default + overriding的思路; 这个default首先就要考虑能处理流尾, 而中间的一些情况用overriding来处理;
另外一个总结: 无底洞(我站在一个entry, 我前面是D, 但是我不知道这个D段有多深), 就要想到分段总结, 而不是探路.
另外一个想法, 锯齿visual的问题, 或许一个思考点可以是用分段算法? 因为毕竟锯齿里面其实就两种trend, 两个trend不就跟分段算法是一样的吗? 波峰和波谷.
最后的速度是6ms (90%), 还可以接受.
这个问题卡的时间太长了, 暂时告一段落;
这个是editorial1:
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;
}
}
我很多时候拿到题目一点思路都没有的一个原因, 就是太急于相处一个完全general的算法, 而不去向题目本身的特性妥协. 这个题目我就是看着一个锯齿状的数组permutation的问题, 然后想要做出一个很general的算法, 最后发现这么一个算法真的不好写;
这个算法editorial的文章解释的更清楚: https://leetcode.com/problems/find-permutation/#/solution
也许一定程度上这个算法也可以说成是一个greedy, 因为他这个算法思考的起点就是从无视任何的pattern, 直接找到的一个overall min开始, 然后思考怎样调整这个overall min适应这个pattern; 因为overall min的样子是1,2,3,..,n这样的: 全都是I, 而且小的数字优先在前面; 所以我们最后找的这个smallest permutation也应该尽可能的尊重这个规律. 尤其是, 虽然我们要调整以适应signature的pattern, 但是尽可能让较小的数字处于前面的位置这个是没有变化的;
最后具体的做法就是所有decreasing subsequence对应的位置的数字全部都收集起来, 然后reverse一下就行了(用Stack完成很方便, 不用考虑边界).
所以这个算法其实核心还是要理解问题的本质: 算法本身就是一个利用了Stack的历史信息流算法, 虽然我对Stack不是很熟悉, 不过这个算法真的要是写的话, 应该还是能够写出来的, 关键就是题目都没有看懂, 一点思路都没有, 就很僵了;
如果真的要总结的话, 我觉得这里的这个问题不应该得到类似: 看到锯齿形这种带有变化trend的问题就应该考虑Stack. 这样的总结太死板了; 这题如果没有想到核心的思路, 就算知道用Stack也写不出来;
这题我自己思考的时候是稍微有点想到只考虑比如下降的trend, 而不考虑上升的, 但是当时脑子里过了一下, 感觉这样的一个选择没有任何的grounds: 凭什么只考虑下降不考虑上升, 不够general. 最后还是放弃了这个念头; 当然这个并不是这一题失败的根本原因, 根本原因还是没有想到针对这个问题的核心策略;
说起来这个是一个search for min之类的最值搜索问题, 实际上跟这个大类问题并没有什么可以总结的共性;
或许说, 可以有一个针对LeetCode类问题的特有的思路? 如果是普通的时候碰到这种最值搜索的问题, 想法肯定是穷搜, 然后顶多优化一下各种ordering的heuristic不得了了; 但是LeetCode里面碰到这种题目, 不可能让你做这么屠龙刀的解法, 写个backtracking都已经是凤毛麟角了;
比如这里的这个最值搜索问题, 实际上最后的思路, 有点类似一个最值变异的思路. 也可以回归到以前总结的一个思维方式: envision what you want as result first! 我最后最希望得到的是什么样的, 然后为什么这个不行;
这个也可以说是一种relaxation的思维方式, 其实我在设计其他的有些题目的算法的时候大概是使用过的; 这个也属于一个符合简单升级的思路, 只不过我们现在思考的不再是例子的简单升级, 而是一个算法, 或者constraint上面的简单升级; 突然发现这种relaxation的思路在算法设计的主体策略上面将非常重要;
这个的哲学观点其实跟笨办法思路是有一点类似的, 但是不完全相同. 毕竟笨办法其实也可以理解为dropped the contraint of requiring better performance (time/space);
锯齿类问题或许以后可以多一个思路: 掰直线的思路?
注意这个算法的流尾控制: 在正常的iteration的过程中, 并没有走到最后一个, 最后一个专门用来处理流尾;
editorial2使用的还是类似的思路, 不过不使用Stack来完成这个reverse的操作, 而是维护起点的指针, 然后手动一个reverse:
public class Solution {
public int[] findPermutation(String s) {
int[] res = new int[s.length() + 1];
for (int i = 0; i < res.length; i++)
res[i] = i + 1;
int i = 1;
while (i <= s.length()) {
int j = i;
while (i <= s.length() && s.charAt(i - 1) == 'D')
i++;
reverse(res, j - 1, i);
i++;
}
return res;
}
public void reverse(int[] a, int start, int end) {
for (int i = 0; i < (end - start) / 2; i++) {
int temp = a[i + start];
a[i + start] = a[end - i - 1];
a[end - i - 1] = temp;
}
}
}
这个算法本身写的很简练, 不过核心思想是不难理解的; 注意这里i和j的使用, j其实是i的一个影子指针, 或者说一个探路指针: 通过一个while循环来完成一个不定长度的探路;
注意editorial1的space是O(N), 而这个是O(1); 这个O(1)是因为我们其实是直接在output array里面操作: editorial1没有一个单独初始化length-n array的操作, 但是Stack空间很大; 而editorial2虽然有这个初始化操作, 但是这个array最后直接当output给返回了, 所以不算额外空间;
editorial3其实是在2上面的一个小优化: 不需要单独的一个初始化, 但是同时也不需要借助于Stack这样的额外空间:
public class Solution {
public int[] findPermutation(String s) {
int[] res = new int[s.length() + 1];
res[0]=1;
int i = 1;
while (i <= s.length()) {
res[i]=i+1;
int j = i;
if(s.charAt(i-1)=='D')
{
while (i <= s.length() && s.charAt(i - 1) == 'D')
i++;
for (int k = j - 1, c = i; k <= i - 1; k++, c--) {
res[k] = c;
}
}
else
i++;
}
return res;
}
}
有一个问题一直漏掉没有讲, 这里其实还有一个shared iterator的问题, 也就是这个i不仅iterate最后的这个array, 还用来iterate这个pattern string; 好好理解这个sharing的关键, 就是写一个例子, 然后用Verbal的方式跟自己说一下, 对于同一个i, 分别在两个range里面对应什么: 比如这里, res[i]对应于一个要填的数字, 而charAt(i - 1)就对应于这个数字之后的这个箭头(D/I, 用箭头来visual). 就是这样的小细节处理好了之后, 代码写起来就方便;
严格来说, 我认为这个算法其实更多的应该算作是对于editorial1的优化: 与其使用一个Stack, 不如直接就按照正确的方式来填充res; 其实每一个下降分段还是上升分段具体应该填什么我们都是清楚的, 我们需要搞清楚的其实只有这个分段的端点就行了; 所以直接一遍走下来, 然后确定每一个分段的端点. 当一个分段被确定了之后, 直接就往里面fill;
总体来说editorial这三个方法的核心思想都是一样的, 这个问题的主要难点还是这个策略的思考;
这个是discussion里面一个人写的reverse:
void reverse(int[] arr, int l, int h) {
while (l < h) {
arr[l] ^= arr[h];
arr[h] ^= arr[l];
arr[l] ^= arr[h];
l++; h--;
}
}
试了一下, 好像还真是对的:
java> 1 ^ 4
java.lang.Integer res0 = 5
java> 4 ^ 5
java.lang.Integer res1 = 1
java> 5 ^ 1
java.lang.Integer res2 = 4
不太知道这个到底是什么原理?
搜了一下, 就是一个噱头:
It's exactly the same algorithm, but you're using the XOR swap method instead of an explicit swap using a temporary variable. The XOR swap method is just a novelty and its use is rarely, if ever justified. Stick with simple, obvious implementations and then you can concentrate on more important things.
It's exactly the same algorithm, but you're using the XOR swap method instead of an explicit swap using a temporary variable. The XOR swap method is just a novelty and its use is rarely, if ever justified. Stick with simple, obvious implementations and then you can concentrate on more important things.
大概看看, 知道有这么回事就行了, 一个swap还搞这么多的幺蛾子;
这里有大量的说明, 还有测速的代码;
这个是discussion里面一个写的很简洁, 而且有介绍的代码:
Idea is pretty simple. There are 2 possibilities:
- String starts with "I". Then we should use 1 as the first item.
- String starts with "D..DI" (k letters) or the string is just "D...D". In this case we should use k, k - 1, ..., 1 to get lexicographically smallest permutation.
Then we proceed computing the rest of the array. Also we should increase min variable that is used to store minimum value in remaining part of the array.
public int[] findPermutation(String s) {
s = s + ".";
int[] res = new int[s.length()];
int min = 1, i = 0;
while (i < res.length) {
if (s.charAt(i) != 'D') {
res[i++] = min++;
} else {
int j = i;
while (s.charAt(j) == 'D') j++;
for (int k = j; k >= i; k--)
res[k] = min++;
i = j + 1;
}
}
return res;
}
注意看他这里, 最后下降段填充的时候他用一个倒序来做, 这样是为了保证可以每个iteration直接increment min就行了; 保持了代码的一致性;
这个是discussion里面另外一个解:
vector<int> findPermutation(string s) {
vector<int> ret;
for (int i = 0; i <= s.size(); ++i)
if (i == s.size() || s[i] == 'I')
for (int j = i + 1, lenTmp = ret.size(); j > lenTmp; --j)
ret.push_back(j);
return ret;
}
这个思路其实跟之前那个slack的思路是一样的, 在下降段就暂停操作(或者说只push), 而到了上升段, 就每一个位置都要fill一次; 最后的代码倒是很短;
这个是submission最优解: 5(99):
public class Solution {
public int[] findPermutation(String s) {
int dCount = 0, curNum = 0, idx = 0;
int[] result = new int[s.length() + 1];
for (char c : s.toCharArray()) {
if (c == 'D') {
dCount += 1;
} else {
if (dCount == 0) {
result[idx++] = ++curNum;
} else {
for (int i = curNum + dCount + 1; i > curNum; i--)
result[idx++] = i;
curNum += dCount + 1;
dCount = 0;
}
}
}
if (dCount == 0) {
result[idx++] = ++curNum;
} else {
for (int i = curNum + dCount + 1; i > curNum; i--)
result[idx++] = i;
curNum += dCount + 1;
dCount = 0;
}
return result;
}
}
他这个算法就非常的简练, 直接就只关注D段的长度就行了. 中间用一个counter, 有点类似分段算法当中的做法. 他这样用counter的一个好处就是, 最后到流尾的时候, 是能够知道res的最后一个位置, 也就是流尾怎么处理的: 因为counter里面还有信息;
这个很聪明; 这题的流尾问题我自己写代码的时候也是卡住了, 当时就是卡的有点懵, 没有冷静的去思考: 我面临的困难是什么? what's the uncertainty? 不要看到一个不确定性因素就觉得"完蛋了", 而应该是尝试去对这个不确定性因素进行细分, 以及相应的处理;
Problem Description
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
Difficulty:Medium
Total Accepted:4.5K
Total Submissions:8.5K
Contributor: CDY_好きだ
Companies
google
Related Topics
greedy