LeetCode 484 - Find Permutation

http://bookshadow.com/weblog/2017/01/22/leetcode-find-permutation/

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

X. http://www.cnblogs.com/grandyang/p/6366738.html

这道题给了我们一个由D和I两个字符组成的字符串，分别表示对应位置的升序和降序，要我们根据这个字符串生成对应的数字字符串。由于受名字中的permutation的影响，感觉做法应该是找出所有的全排列然后逐个数字验证，这种方法十有八九无法通过OJ。其实这题用贪婪算法最为简单，我们来看一个例子：

D D I I D I

1 2 3 4 5 6 7

3 2 1 4 6 5 7

我们不难看出，只有D对应的位置附近的数字才需要变换，而且变换方法就是倒置一下字符串，我们要做的就是通过D的位置来确定需要倒置的子字符串的起始位置和长度即可。通过观察，我们需要记录D的起始位置i，还有D的连续个数k，那么我们只需要在数组中倒置[i, i+k]之间的数字即可

https://leetcode.com/articles/find-permutation/

In order to reverse the subsections of the $min$ array, as discussed in the last approach, we can also start by initializing the resultant arrangement $res$ with the $min$ array i.e. by filling with elements $(1,n)$ in ascending order. Then, while traversing the pattern $s$, we can keep a track of the starting and ending indices in $res$ corresponding to the D's in the pattern $s$, and reverse the portions of the sub-arrays in $res$corresponding to these indices. The reasoning behind this remains the same as discussed in the last approach.

  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;

    }

  }

X. 

下面这种方法没有用到数组倒置，而是根据情况来往结果res中加入正确顺序的数字，我们遍历s字符串，遇到D直接跳过，遇到I进行处理，我们每次先记录下结果res的长度size，然后从i+1的位置开始往size遍历，将数字加入结果res中即可

    vector<int> findPermutation(string s) {
        vector<int> res;
        for (int i = 0; i < s.size() + 1; ++i) {
            if (i == s.size() || s[i] == 'I') {
                int size = res.size();
                for (int j = i + 1; j > size; --j) {
                    res.push_back(j);
                }
            }
        }
        return res;
    }

直接构造法 时间复杂度O(n)

初始令数组nums = [1,2, ..., n]，令数组ans = []

执行如下循环直到s为空：

  记s中的当前字符为c
  
  若c == 'I'，则直接将nums中的最小元素移除并加入ans；将c从s中移除
  
  否则，记连续的字符'D'的个数为cnt，将nums[0 ... cnt+1]移除，逆置后加入ans；将cnt个'D'从s中移除，如果后面有字符'I'，则一并移除。

https://discuss.leetcode.com/topic/76276/1-liner-and-5-liner-visual-explanation

If it's all just I, then the answer is the numbers in ascending order. And if there are streaks of D, then just reverse the number streak under each:

X. https://discuss.leetcode.com/topic/76213/greedy-o-n-java-solution-with-explanation

Idea is pretty simple. There are 2 possibilities:

1. String starts with "I". Then we should use 1 as the first item.
2. 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;
}

X. Two Pointers
Instead of initializing the $res$ array once with ascending numbers, we can save one iteration over $res$ if we fill it on the fly. To do this, we can keep on filling the numbers in ascending order in $res$ for I's found in the pattern $s$. Whenever we find a D in the pattern $s$, we can store the current position(counting from 1) being filled in the $res$ array in a pointer $j$. Now, whenever we find the first I following this last consecutive set of D's, say at the $i^{th}$ position(counting from 1) in $res$, we know, that the elements from $j^{th}$ position to the $i^{th}$position in $res$ need to be filled with the numbers from $j$ to $i$ in reverse order. Thus, we can fill the numbers in $res$ array starting from the $j^{th}$ position, with $i$ being the number filled at that position and continue the filling in descending order till reaching the $i^{th}$ position. In this way, we can generate the required arrangement without initializing $res$.

  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;

  }

X. Stack

  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;

  }

X.
https://discuss.leetcode.com/topic/76221/java-o-n-clean-solution-easy-to-understand

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.

1 2 3

IDIIDD 1234567 // sorted 1324765 // answer

    public int[] findPermutation(String s) {

        int n = s.length(), arr[] = new int[n + 1];

        for (int i = 0; i <= n; i++) arr[i] = i + 1; // sorted

        for (int h = 0; h < n; h++) {

            if (s.charAt(h) == 'D') {

                int l = h;

                while (h < n && s.charAt(h) == 'D') h++;

                reverse(arr, l, h);

            }  

        }  

        return arr;

    }  

    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--;

        }  

    }

http://www.learn4master.com/interview-questions/leetcode/leetcode-find-permutation
A simple solution is to use dfs search and back tracking.

    public int[] findPermutation(String s) {

        int n = s.length() + 1;

        boolean[] visited = new boolean[n + 1];

        int[] res = new int[n];

        for(int i = 1; i <= n; i++) {

            visited[i] = true;

            res[0] = i;

            if(find(1, visited, s, res)) {

                return res;

            }

            visited[i] = false;

        }

        return new int[0];

    }

    

    boolean find(int i, boolean[] visited, String s, int[] res) {

        if(i == visited.length - 1) {

            return true;

        }

        for(int k = 1; k < visited.length; k++) {

            if(visited[k]) continue;

            if(s.charAt(i - 1) == 'D') {

                if(k < res[i - 1]) {

                    res[i] = k;

                    visited[k] = true;

                    if(find(i + 1, visited, s, res)) {

                        return true;

                    }

                    visited[k] = false;

                    res[i] = 0;

                }

            }

            if(s.charAt(i - 1) == 'I') {

                if(k > res[i - 1]) {

                    res[i] = k;

                    visited[k] = true;

                    if(find(i + 1, visited, s, res)) {

                        return true;

                    }

                    visited[k] = false;

                    res[i] = 0;

                }

            }

        }

        return false;

    }

第一题：给一个pattern “IIDDI”, D代表decrease, I代表increase，找出能满足这个pattern的由数字1到n组成的值最小的Permutation，n=pattern.length+1，比如上面这个例子结果就是125436

思路：

先将原数组升序排列，满足了所有的I, 然后对于连续的D，全部reverse

code:

class Solution {

   public int[] findPermutation(String s) {

       int len = s.length();

       int[] res = new int[len + 1];

       for(int i = 0 ; i < res.length ; i++) {

           res[i] = i + 1;

       }

       for(int i = 0 ; i < len ; i++) {

           if(s.charAt(i) == 'D') {

               int j = i;

               while(j < len && s.charAt(j) == 'D') j++;

               reverse(res, i, j);

               i = j - 1;

           }

       }

       return res;

   }

   private void reverse(int[] arr, int left, int right) {

       int l = left, r = right;

       while(l < r) {

           swap(arr, l++, r--);

       }

   }

   private void swap(int[] arr, int i, int j) {

       int tmp = arr[i];

       arr[i] = arr[j];

       arr[j] = tmp;

   }

}