Friday, August 23, 2019

LeetCode [767] Reorganize String

767. Reorganize String
Medium
Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.
If possible, output any possible result.  If not possible, return the empty string.
Example 1:
Input: S = "aab"
Output: "aba"
Example 2:
Input: S = "aaab"
Output: ""
Note:
  • S will consist of lowercase letters and have length in range [1, 500].
 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
class Solution {
    static bool comp(const pair<char, int>& p1, const pair<char, int>& p2){
        return p1.second>p2.second;
    }
public:
    string reorganizeString(string S) {
        map<char, int> mp;
        int maxCount = 0, sz = S.size();
        char c0;//char with greatest count
        for(auto c:S){
            if(++mp[c]>maxCount){
                maxCount = mp[c];
                c0 = c;
            }
        }
        if(maxCount>ceil(sz/2.0)) return "";
        
        vector<pair<char, int>> chars(mp.begin(), mp.end());
        sort(chars.begin(), chars.end(), comp);
        
        auto it = chars.begin();
        string ret(sz, ' ');
        for(int start = 0; start<=1; start++)
        {
            for(int i=start; i<sz; i+=2){
                if(it->second==0) advance(it, 1);
                ret[i] = it->first;
                it->second--;
            }
        }
        return ret;
    }
};


 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
class Solution {
    public String reorganizeString(String S) {
        int[] count = new int[26];
        for(char c : S.toCharArray()){
            count[c-'a']++;
        }

        int charMax = 0;
        int countMax = 0;
        for(int i=0; i<26; ++i){
            if(count[i]>countMax){
                countMax = count[i];
                charMax = i;
            }
        }
        if(countMax>(S.length()+1)/2) return "";

        char[] res = new char[S.length()];
        int index = 0;
        while(count[charMax]>0){
            res[index] = (char)(charMax+'a');
            index+=2;
            count[charMax]--;
        }

        for(int i=0; i<26; ++i){
            while(count[i]>0){
                if(index>=S.length()) index = 1;
                res[index] = (char)(i+'a');
                index += 2;
                count[i]--;
            }
        }

        return String.valueOf(res);
    }
}

第四轮，白人小哥，刷题网没刷到过（有认出来的请评论下），给一堆学生的id和国籍，如果让他们排队站，如何尽可能的不让两个或者以上的相同国籍的学生站一起。比如有5个国家C的学生和1个国家X的学生， 那CCCCXC的站法比CCCXCC的站法好， 因为后者5个国家C的学生身边都有自己国家的同学，前者只有4个国家C的学生身边有自己国家的同学。 一开始想的的是先按国家sort一遍，隔一个位置放一个人直到填满，后来试了个test case发现不行，改成先把有几个国家用set记录下来，然后while loop一直遍历这个set，逐个放对应的学生，如果没有这个国家的学生了就把国家从set里删除。 最后说了下时间空间复杂度，测了几个test case都ok，不知道是不是最优解。。

第四轮的隔开放学生我面完也没get到，感觉像是找基础的规律之类的数学题吧

第四轮和767那题不一样的是assume input一定有一个解，比如 input: aaab -> output: aaba

第四题，感觉类似lc 旗留旗；用priorityqueue来储存每个国家的count；从大到小，每次poll两个出来，这样alternative placement

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)