如何转换字符串，使其只包含出现次数大于或等于给定值的元音？ [英] How to transform a string such that it only contains vowels which have occurences equal or greater than their given values?
问题描述
在一次采访中有人问我这个问题。我们有一个字符串 s （所有小写字符），我们需要根据它们创建一个新的字符串 p ，例如： / p>
- 字符串中 a 的总数应等于或大于int的给定值变量
a。 - 字符串中 e 的总数应等于或大于int变量
e的给定值。 - 字符串中 i 的总数应该等于或大于整数变量
i的给定值。 - o 应该等于或大于int变量
o的给定值。 - <字符串中的em> u 应该等于或大于int变量
u的给定值。
使用约束是为了得到结果字符串，我们可以将任何字符替换为其他任何较低的ca se字符。我们可以执行任意次，但是每次替换都有相应的成本。用 c2 替换 c1 的成本是 ASCII值的绝对差c1 和 c2 。例如。将 b 替换为 e 的成本为3，将 c 替换为 a 的成本为2。
我们需要找到将s转换为p的最低成本。给出的是：
- 字符串s
- 五个整数-a，e，i，o，u
我的方法是先对字符串进行排序，然后在每次遇到相应字符时减小给定int的给定值，然后无论哪个给定变量大于0，我们将从字符串的开头开始，并且ig teh char不是元音，我们将计算用其对应变量大于零的元音替换它的成本，并减小它。似乎没有效果。
请让我知道您的解决方法。如果有任何不清楚的信息，请在评论中告诉我。谢谢
这是我的代码：
公共类VowelCount {
static int minCount（String s，int a，int e，int i，int o，int u）{
char [] array = s.toCharArray（）;
List< Character> list = new ArrayList<>（）;
list.add（’a’）;
list.add（’e’）;
list.add（’i’）;
list.add（’o’）;
list.add（’u’）;
Arrays.sort（array）;
for（int j = 0; j< s.length（）; j ++）{
if（s.charAt（j）=='a'& a> ; 0）{
a--;
}
else if（s.charAt（j）==‘e’&& a> 0）{
e--;
}
else if（s.charAt（j）==‘i’&& a> 0）{
i--;
}
else if（s.charAt（j）==‘o’&& a> 0）{
o--;
}
else if（s.charAt（j）==‘u’&& a> 0）{
u--;
}
}
int count = 0;
for（int j = 0; j< array.length; j ++）{
int count1 = 0，count2 = 0，count3 = 0，count4 = 0，count5 = 0，semicount1 = 0， semicount2 = 0，fincount = 0;
if（！list.contains（array [j]））{
if（a> 0）{
int c1 =（int）array [j];
int c2 =（int）'a';
count1 = Math.abs（c1-c2）;
a--;
}
if（e> 0）{
int c1 =（int）array [j];
int c2 =（int）‘e’;
count1 = Math.abs（c1-c2）;
e--;
}
if（i> 0）{
int c1 =（int）array [j];
int c2 =（int）'i';
count1 = Math.abs（c1-c2）;
我-;
}
if（o> 0）{
int c1 =（int）array [j];
int c2 =（int）'o';
count1 = Math.abs（c1-c2）;
o--;
}
if（u> 0）{
int c1 =（int）array [j];
int c2 =（int）'u';
count1 = Math.abs（c1-c2）;
u--;
}
if（count1！= 0&& count2！= 0）{
semicount1 = Math.min（count1，count2）;
}否则，如果（count1 == 0）{
semicount1 = count2;
}否则，如果（count2 == 0）{
semicount1 = count1;
}
if（count3！= 0&& count4！= 0）{
semicount2 = Math.min（count3，count4）;
}否则，如果（count3 == 0）{
semicount2 = count4;
} else if（count4 == 0）{
semicount2 = count3;
}
System.out.println（ adding to count）;
fincount = Math.min（semicount1，semicount2）;
if（count5！= 0）{
count + = Math.min（count5，fincount）;
} else count + = fincount;
}
}
System.out.println（count）;
返回计数；
}
public static void main（String [] args）{
minCount（ beiou，1，1，1，1，1）;
}
}
I 'm假设 a ， b ， c ， d 和 e 最多为 s.length 。
此问题可以在线性时间内解决。解决问题之前，请考虑以下三种情况：
- s = bc，a = 1，e = 1，最佳p = ae，最佳成本= 1 + 2
- s = dj，a = 1，e = 1，最佳p = ae，最佳成本= 3 + 5
- s = fj，a = 1，e = 1，最佳p = ae，最优成本= 5 + 5
我们可以认为字符是数字线中的点。在第一种情况下，辅音位于元音之间。在第二个中，辅音在元音之间，另一个在外面。在第三个示例中，他们两个都在外面。我们可以看到，总是最好首先选择具有较低ASCII键的元音并为其获取最便宜的常量。
因此，现在的方法是，以最便宜的成本将所有常数转换为我们需要的'a'。然后选择b，然后选择c，依此类推。
编辑：
我想念的一个特殊情况是，如果我们有两个选择的话从相同的成本。我们应该选择哪一个？答案是选择ASCII值较低的那个。感谢Tushar Makkar指出来。
I was asked this question in an interview. We have a string s (all lowercase characters) from which we need to make a new string p such that :
- The total number of a's in the string should be equal or greater than the given value of an int variable
a. - The total number of e's in the string should be equal or greater than the given value of an int variable
e. - The total number of i's in the string should be equal or greater than the given value of an int variable
i. - The total number of o's in the string should be equal or greater than the given value of an int variable
o. - The total number of u's in the string should be equal or greater than the given value of an int variable
u.
Constraint was the in order to get the resultant string, we can replace any character with any other lower case character. We can do this any number of times but each replacement has a cost associated with it. the cost of replacing c1 with c2 is the absolute difference of ASCII value of c1 and c2. For eg. replacing b with e has a cost 3 and c with a has a cost 2.
We need to find the minimum cost of converting s into p. Given is:
- String s
- Five ints - a, e, i, o, u
My approach was to first sort the string, then decrease the given value of given int's each time we encounter the respective character, and then whichever given variable is greater than 0, we'll start from the beginning of the string and ig teh char is not a vowel, we'll calculate the cost of replacing it with the vowel of which corresponding variable is greater than zero and decrease it. It doesn't seem to work out. Please let me know your approach to solve it. If any information is obscure, let me know in comments. Thanks
here's my code:
public class VowelCount {
static int minCount(String s, int a, int e, int i, int o, int u) {
char[] array = s.toCharArray();
List<Character> list = new ArrayList<>();
list.add('a');
list.add('e');
list.add('i');
list.add('o');
list.add('u');
Arrays.sort(array);
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == 'a' && a > 0) {
a--;
}
else if (s.charAt(j) == 'e' && a > 0) {
e--;
}
else if (s.charAt(j) == 'i' && a > 0) {
i--;
}
else if (s.charAt(j) == 'o' && a > 0) {
o--;
}
else if (s.charAt(j) == 'u' && a > 0) {
u--;
}
}
int count =0;
for (int j = 0; j < array.length; j++) {
int count1=0, count2=0, count3=0, count4=0, count5=0, semicount1=0, semicount2=0, fincount=0;
if (!list.contains(array[j])) {
if (a > 0) {
int c1 =(int) array[j];
int c2 = (int) 'a';
count1 = Math.abs(c1-c2);
a--;
}
if (e > 0) {
int c1 =(int) array[j];
int c2 = (int) 'e';
count1 = Math.abs(c1-c2);
e--;
}
if (i > 0) {
int c1 =(int) array[j];
int c2 = (int) 'i';
count1 = Math.abs(c1-c2);
i--;
}
if (o > 0) {
int c1 =(int) array[j];
int c2 = (int) 'o';
count1 = Math.abs(c1-c2);
o--;
}
if (u > 0) {
int c1 =(int) array[j];
int c2 = (int) 'u';
count1 = Math.abs(c1-c2);
u--;
}
if (count1!=0 && count2!=0) {
semicount1 = Math.min(count1, count2);
} else if (count1 == 0) {
semicount1 = count2;
} else if (count2 == 0) {
semicount1 = count1;
}
if (count3 != 0 && count4 != 0) {
semicount2 = Math.min(count3, count4);
} else if (count3 == 0) {
semicount2 = count4;
} else if (count4 == 0) {
semicount2 = count3;
}
System.out.println("adding to count");
fincount = Math.min(semicount1, semicount2);
if (count5 != 0) {
count+= Math.min(count5, fincount);
} else count+= fincount;
}
}
System.out.println(count);
return count;
}
public static void main(String[] args) {
minCount("beiou", 1, 1, 1, 1 ,1);
}
}
I'm assuming that the sum of a, b, c, d and e is at most s.length.
This problem can be solved in linear time. Before solving the problem, lets consider three scenarios:
- s = "bc", a = 1, e = 1, best p = "ae", optimal cost = 1 + 2
- s = "dj", a = 1, e = 1, best p = "ae", optimal cost = 3 + 5
- s = "fj", a = 1, e = 1, best p = "ae", optimal cost = 5 + 5
We can think the characters as points in number line. In the first scenario, the consonants lie between the vowels. In the second one, on consonant lie between the vowels and other one is outside. In the third example, both of them are outside. And we can see that, it is always better to choose the vowel with lower ASCII key at first and grab the cheapest constant for it.
So, now the approach would be, to convert all the constant to 'a' that we need, in cheapest cost. Then go for b, then c and so on.
EDIT: One particular case I've missed is that, if we've two options to choose from with same cost. Which one should we choose? The answer is to choose the one with lower ASCII value. Thanks to Tushar Makkar for pointing it out.
这篇关于如何转换字符串，使其只包含出现次数大于或等于给定值的元音？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
