leetcode 484. Find Permutation 思维题

https://leetcode.com/contest/leetcode-weekly-contest-16a/problems/find-permutation/

设原本的数字是0，那么按照它的DI来模拟，D就减1，I就+1

比如DDIIDI，就是0、-1、-2、-1、0、-1、0

那么找到第一个最小的，现在是-2，那么把它安排去第一个没出现过的数字，也就是1了，

然后，它左边的全部，就要确定了，3、2、1

然后再把[4, en]继续这样模拟。

需要注意的是，遇到一个I，就马上停止了，不然DDDIIIIDDDDDDDDDDD这样的数据会hack。其实停止也很正常，也就是因为是上升了，是有很多种情况的，首先把前面的贪心优先字典树最小后再说，I的话，可以设置成很大也没问题，字典序已经是最有了。

class Solution {

public:

    vector<int> findPermutation(string s) {

        vector<int> t;

        vector<int> ans;

        ans.push_back();

        t.push_back();

        for (int i = ; i < s.size(); ++i) {

            if (s[i] == 'D') t.push_back(t[i] - );

            else t.push_back(t[i] + );

            ans.push_back();

        }

        int want = ;

        int be = , en = t.size() - ;

        while (want <= s.size() + ) {

            int pos = tofind(t, be, en);

            for (int i = pos; i >= be; --i) {

                ans[i] = want++;

            }

            be = pos + ;

        }

        return ans;

    }

    int tofind(vector<int> &num, int be, int en) {

        int now = 1e9;

        int id = be;

        for (int i = be; i <= en; ++i) {

            if (i -  >= be && num[i] > num[i - ]) return id;

            if (now > num[i]) {

                id = i;

                now = num[i];

            }

        }

        return id;

    }

};

巴特西

leetcode 484. Find Permutation 思维题

最新文章

热门文章