我正在解决“HackerRank”页面上的一个问题,特别是名为“追加和删除”的问题,但我无法使所有情况都正确。
https://www.hackerrank.com/challenges/append-and-delete/problem
"You have a string of lowercase English alphabetic letters. You can perform two types of operations on the string:
Append a lowercase English alphabetic letter to the end of the string. Delete the last character in the string. Performing this operation on an empty string results in an empty string. Given an integer, , and two strings, and , determine whether or not you can convert to by performing exactly of the above operations on . If it's possible, print Yes. Otherwise, print No.
For example, strings and . Our number of moves, . To convert to , we first delete all of the characters in moves. Next we add each of the characters of in order. On the move, you will have the matching string. If there had been more moves available, they could have been eliminated by performing multiple deletions on an empty string. If there were fewer than moves, we would not have succeeded in creating the new string.
Function Description
Complete the appendAndDelete function in the editor below. It should return a string, either Yes or No.
appendAndDelete has the following parameter(s):
s: the initial string t: the desired string k: an integer that represents the number of operations".
int cont = 0;
int limite = 0;
if (s.length() < t.length()){
limite += s.length();
} else if (s.length() >= t.length()){
limite += t.length();
}
for (int i = 0; i < limite; i++){
if (s.charAt(i) != t.charAt(i)){
cont += 2;
}
}
int diferen = 0;
if (s.length() != t.length()){
diferen += (Math.abs(t.length() - s.length()));
}
cont += diferen;
if(cont <= k){
return "Yes";
} else {
return "No";
}
最佳答案
简介
为了发现代码中的问题,让我们简化它。
简化 limite
计算
计算limite
值,您使用 if/else
block 如下:
if (s.length() < t.length()){
limite += s.length();
} else if (s.length() >= t.length()){
limite += t.length();
}
但是,自从您的 limite
总是0
在此 block 之前,您要查找的是最短字符串的长度,您可以简单地将其替换为:
int limite = Math.min(s.length(), t.length());
简化 diferen
计算
再说一次,你不需要任何 if
block 来计算您的 diferen
- 如果两个字符串长度相等,则 diferen
就是0
这就是Math.abs(t.length() - s.length())
也会有收获。
所以,不要这样:
int diferen = 0;
if (s.length() != t.length()) {
diferen += (Math.abs(t.length() - s.length()));
}
你可以简单地写一句:
int diferen = (Math.abs(t.length() - s.length()));
更好的变量名称
您的变量名称如 diferen
或cont
或limite
很困惑。相反,您可以将这些变量重命名为 absLengthDifference
, operationCount
和commonLength
.
您的简化代码
static String appendAndDelete(String s, String t, int k) {
int operationCount = 0;
int shorterStringLength = Math.min(s.length(), t.length());
for (int i = 0; i < commonLength; i++) {
if (s.charAt(i) != t.charAt(i)) {
operationCount += 2;
}
}
int absLengthDifference = (Math.abs(t.length() - s.length()));
operationCount += absLengthDifference;
if(operationCount <= k) {
return "Yes";
}
return "No";
}
查找逻辑错误
因此,根据简介中所做的修改,我们将找出程序产生错误结果的原因。
让我们考虑如下输入:
ab
bb
2
您的程序将对此做出肯定的判断,因为 operationCount
将是2
但是operationCount <= 2
。所以,这是不正确的,因为为了转换 ab
至bb
使用任务中的操作,我们必须执行以下操作:
'ab' -> 'a' | the only way to get to 'a' is to remove 'b'
'a' -> '' | the only way to correct 'a' is to remove it first
'' -> 'b' | and then append 'b'
'b' -> 'bb' | finally, append 'b' again
如您所见,我们花了 4
操作以达到期望的结果,而不是 2
。因此,下面的 block 是错误的:
for (int i = 0; i < commonLength; i++) {
if (s.charAt(i) != t.charAt(i)) {
operationCount += 2;
}
}
还不够添加 2
。如果发现不匹配,则必须删除末尾的所有字符才能找到它(如示例所示)。
此外,if(operationCount <= k)
是错误的,因为操作数必须恰好是 k
.
修复解决方案
- 首先要意识到的是,如果
k
大于或等于字符串长度之和,则答案为Yes
。我们可以删除原始字符串s
中的所有字符。并继续从空字符串0
中删除一个字符或多次,然后附加目标字符串t
中的字符. - 否则,如果找到长度
commonLength
两者的公共(public)字符串,那么我们可以转换s
进入t
在s.length() + t.length() - 2*commonLength
脚步。该值minOperationCount
但是,不能大于k
出于显而易见的原因。另外,如果它小于k
,然后k - minOperationCount
必须是2
的倍数。如果不是,则可以精确地进行转换k
步骤。
代码
// Complete the appendAndDelete function below.
static String appendAndDelete(String s, String t, int k) {
int totalLength = s.length() + t.length();
if (totalLength <= k) {
return "Yes";
}
int commonLength = 0;
for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
if (s.charAt(i) != t.charAt(i)) {
break;
}
commonLength++;
}
int minOperationCount = totalLength - 2 * commonLength;
if(minOperationCount <= k && ((k - minOperationCount) % 2 == 0)) {
return "Yes";
}
return "No";
}
关于java - 给定 2 个字符串和整数 k,只需 k 步将一个字符串转换为另一个字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60012267/