leetcode 484

问题

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:

1
2
3
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:

1
2
3
4
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

分析

思路1: 采用拓扑排序的思路，按照输入的字符串指示构建一张图，由填充值小的下标指向填充值大的下标。然后构建一个由下标升序的有限队列，每出队一个确定一个对应位置的数值，并将其子节点的入度都减1，若子节点的入度为0则加入到优先队列中。直到队列为空，则完成返回数组的赋值。时间复杂度O(nlogn)，空间复杂度O(n)。

思路2: 首先将返回数组初始化为 “123..n” ，在输入字符串遇到连续的 ‘D’ 后，将返回数组中对应的部分 reverse 即可。时间复杂度O(n)。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// O(nlogn)
class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.size()+1;
        vector<int> ans(n, 0);
        vector<int> deg(n, 0);
        vector<vector<int>> e(n);
        priority_queue<int,vector<int>,greater<int>> pq;
        
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == 'D') {
                e[i+1].push_back(i);
                deg[i]++;
            } else {
                e[i].push_back(i+1);
                deg[i+1]++;
            }
        }
        
        for (int i = 0; i < n; ++i) {
            if (deg[i] == 0)
                pq.push(i);
        }
        
        int tot = 1;
        while (pq.size() != 0) {
            int x = pq.top();
            pq.pop();
            
            ans[x] = tot++;
            for (int y: e[x]) {
                if (--deg[y] == 0)
                    pq.push(y);
            }
        }
        
        return ans;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.size()+1;
        vector<int> ans(n, 0);
        for (int i = 0; i < n; ++i) {
            ans[i] = i+1;
        }

        int i = 0;
        while (i < s.size()) {
            if (s[i] == 'D') {
                int j = i;
                while (i < s.size() && s[i] == 'D') {
                    i++;
                }
                reverse(ans.begin()+j, ans.begin()+i+1);
            } else
                ++i;
        }
        return ans;
    }
};