358. Rearrange String k Distance Apart

oogh 发布于2019-08-14 14:12 / 2315人阅读

摘要：题目解答先记录中的及它出现在次数，存在里，用来记录这个最小出现的位置。

题目：
Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:
str = " ", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.
Example 2:
str = "aaabc", k = 3

Answer: ""

It is not possible to rearrange the string.
Example 3:
str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

解答：

//先记录str中的char及它出现在次数，存在count[]里，用valid[]来记录这个char最小出现的位置。
    //每一次把count值最大的数选出来，append到新的string后面
    public int selectedValue(int[] count, int[] valid, int i) {
        int select = Integer.MIN_VALUE;
        int val = -1;
        for (int j = 0; j < count.length; j++) {
            if (count[j] > 0 && i >= valid[j] && count[j] > select) {
                select = count[j];
                val = j;
            }
        }
        return val;
    }
    
    public String rearrangeString(String str, int k) {
        int[] count = new int[26];
        int[] valid = new int[26];
        //把每个出现了的char的个数记下来
        for (char c : str.toCharArray()) {
            count[c - "a"]++;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            //选出剩下需要出现次数最多又满足条件的字母，即是我们最应该先放的数
            int curt = selectedValue(count, valid, i);
            //如果不符合条件，返回“”
            if (curt == -1) return "";
            //选择好后，count要减少，valid要到下一个k distance之后
            count[curt]--;
            valid[curt] = i + k;
            sb.append((char)("a" + curt));
        }
        
        return sb.toString();
    }

GPU云服务器云服务器 Apart Rearrange Distance String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64874.html

358. Rearrange String k Distance Apart

摘要：题目链接的思想，这题要让相同字母的距离至少为，那么首先要统计字母出现的次数，然后根据出现的次数来对字母排位置。出现次数最多的肯定要先往前面的位置排，这样才能尽可能的满足题目的要求。 358. Rearrange String k Distance Apart 题目链接：https://leetcode.com/problems... greedy的思想，这题要让相同字母的charact...

Taonce 2019-08-14 17:35 评论0 收藏0
[Leetcode] One Edit Distance 编辑距离为一

摘要：比较长度法复杂度时间空间思路虽然我们可以用的解法，看是否为，但中会超时。这里我们可以利用只有一个不同的特点在时间内完成。 One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. 比较长度法复杂度时间 O(N) 空间 O(1) 思路虽然我们可以用...

lewinlee 2019-08-14 12:48 评论0 收藏0
Leetcode[161] One Edit Distance

摘要：复杂度思路考虑如果两个字符串的长度，是肯定当两个字符串中有不同的字符出现的时候，说明之后的字符串一定要相等。的长度比较大的时候，说明的时候，才能保证距离为。 LeetCode[161] One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Stri...

周国辉 2019-08-14 15:58 评论0 收藏0