摘要:题目解答先记录中的及它出现在次数,存在里,用来记录这个最小出现的位置。
题目:
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(); }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64874.html
摘要:题目链接的思想,这题要让相同字母的距离至少为,那么首先要统计字母出现的次数,然后根据出现的次数来对字母排位置。出现次数最多的肯定要先往前面的位置排,这样才能尽可能的满足题目的要求。 358. Rearrange String k Distance Apart 题目链接:https://leetcode.com/problems... greedy的思想,这题要让相同字母的charact...
摘要:比较长度法复杂度时间空间思路虽然我们可以用的解法,看是否为,但中会超时。这里我们可以利用只有一个不同的特点在时间内完成。 One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. 比较长度法 复杂度 时间 O(N) 空间 O(1) 思路 虽然我们可以用...
摘要:复杂度思路考虑如果两个字符串的长度,是肯定当两个字符串中有不同的字符出现的时候,说明之后的字符串一定要相等。的长度比较大的时候,说明的时候,才能保证距离为。 LeetCode[161] One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Stri...
阅读 3537·2021-09-10 10:51
阅读 2507·2021-09-07 10:26
阅读 2482·2021-09-03 10:41
阅读 810·2019-08-30 15:56
阅读 2896·2019-08-30 14:16
阅读 3488·2019-08-30 13:53
阅读 2103·2019-08-26 13:48
阅读 1912·2019-08-26 13:37