为了赶周一hr上班，昨天凌晨完成了西安华为的OD机试。总共三道题，这里总结记录下其中一道难度一的题目。
题目要求
现已知对指定字符串存在类似加密算法，“ddd”可加密为“3d”，“aaaabbb”可加密为“4a3b”,“aabbb”可加密为“aa3b”。 也就是说，某一字符若连续重复3次及3次以上，可压缩为“重复次数+重复的字符”，其他情况则不压缩。 现需要实现相反的解密过程，如给定输入“3d”，则输出“ddd”，输入“3b10c”，则输出“bbbcccccccccc”。 若输入“aa”，则输出“aa”，若输入“2a”，则为错误加密，则输出“!error”。“11”也为错误加密，输出“!error”。 输入‘0-9’及‘a-z’之外的其他字符均为错误。 程序需遵循，标准oj输入输出。
解题思路
如果直接对格式校验再解密则会多一遍循环，所以这里采用对给定字符串直接遍历，一边遍历一边校验并解密，每次遍历都可能会将解密的内容以StringBuilder的方式追加。
遍历的过程：分三种情况，当前为字符为数字（0-9），小写字母（a-z），或其他字符。如果当前位置为数字，则需要记录下来，下次遍历的时候，如果下一位是字母，则就可以解密（数字<3除外），如果下一位为数字，就需要将两位数字转成真正的数值，多位数字同理。遍历时，还需要记录字符以及此次解密字符，便于之后比较，因为可能出现“数字+字母”后又是该字母的情况、“数字+字母”后又是同样的“数字+字母”组合，这种是不合法的，同样3次及3次以上同字母连续也是不合法的。
注意：在char与int转换时，并不是真正想要的数值，因为它是ASCII码的转换，所以转换时这里直接减去了‘a’。在char类型的数值比较时，也直接用char（‘0’-‘9’）比较的。
代码实现
这里代码以java实现，其他语言同理。同时，因为线上判题是采用oj，但这里为了便于本地测试，提前将case计入文件中，直接读取文件判断就行。代码中线上oj和本地case用例均有，取消对应注释即可。若本地case文件方式，请修改对应文件路径。
解密算法，可修改，重新实现。main方法无需变动。
/**
* 题目要求：
* 现已知对指定字符串存在类似加密算法，“ddd”可加密为“3d”，“aaaabbb”可加密为“4a3b”,“aabbb”可加密为“aa3b”。
* 也就是说，某一字符若连续重复3次及3次以上，可压缩为“重复次数+重复的字符”，其他情况则不压缩。
* 现需要实现相反的解密过程，如给定输入“3d”，则输出“ddd”，输入“3b10c”，则输出“bbbcccccccccc”。
* 若输入“aa”，则输出“aa”，若输入“2a”，则为错误加密，则输出“!error”。“11”也为错误加密，输出“!error”。
* 输入‘0-9’及‘a-z’之外的其他字符均为错误。
* 程序遵循，标准oj输入输出
*
* @author humh
* @date 2020/6/7
*/
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
/**
* 解密字符串算法
*
* @author humh
* @date 2020/6/8
* @param input 需要解密的字符串
* @return java.lang.String 解密后的未加密字符串
*/
public static String decodeStr(String input) {
char[] chars = input.toCharArray();
// 记录重复字符的重复次数（追加结果后，要先清空0，才能下次再遍历）-1为默认清空值（默认取-1，是因为字符中可能有0）
int count = -1;
// 存放上一次遍历的字符，可能是重复字符，也可能不是，根据count值判断（遍历如果是数字的话，先清空!） '!'为默认值
char charFirst = '!';
// 字母重复次数 0为默认值
int sameCount = 0;
// 最后一次解密追加的字符串
char decodeCharLast = '!';
// 最终解密的结果
StringBuilder result = new StringBuilder();
for (int i = 0; i < chars.length; i++) {
//重复字符解密追加至结果中
if (count != -1 && charFirst != '!') {
if (count < 3 || decodeCharLast == charFirst) {
// 重复次数2的加密情况，如2a，或者最后一次解密与当前解密为同一字符，如3a3a3b，均不合法
return "!error";
}
for (int j = 0; j < count; j++) {
result.append(charFirst);
}
sameCount = 2;
decodeCharLast = charFirst;
count = -1;
}
char charTemp = chars[i];
if ('a' <= charTemp && charTemp <= 'z') {
// 前位是数字，且未进行解密追加的情况
if (count != -1) {
if (charFirst != charTemp) {
charFirst = charTemp;
sameCount = 1;
} else {
return "!error";
}
} else {
if (charFirst == charTemp) {
if (sameCount == 2) {
// 连续重复第三次，如：aaa;或者加密后又重复，如：3aa
return "!error";
} else {
// 字符第二次出现
++sameCount;
result.append(charTemp);
}
} else {
// 字符第一位出现（a）、与上位字符不同（ab）或加密后字符不同（3ab）
charFirst = charTemp;
sameCount = 1;
// 这里需要记录为解密追加字符,便于下次对比,如bb3b的情况
decodeCharLast = charTemp;
result.append(charTemp);
}
}
} else if ('0' <= charTemp && charTemp <= '9') {
if (count != -1) {
// 上一个字符为数字，当前位字符仍为数字，如：12a
count = count * 10 + charTemp - '0';
} else {
// 前面没有数字，清空原先字符位，才能进行之后的重复解密追加，同时不需要再对之前的字符进行比较
charFirst = '!';
count = charTemp - '0';
sameCount = 0;
}
} else {
// 非法情况，不是‘a-z’,或者‘1-9’
return "!error";
}
}
// 解决最后一次遍历，无法解密追加问题
if (count != -1 && charFirst != '!') {
if (count < 3 || decodeCharLast == charFirst) {
return "!error";
}
for (int j = 0; j < count; j++) {
result.append(charFirst);
}
count = -1;
}
// 最后一位为数字的情况
if (count != -1) {
return "!error";
}
return result.toString();
}
public static void main (String[] args) {
// 1 oj输入
// Scanner scan = new Scanner(System.in);
// while (scan.hasNextLine()) {
// System.out.println(decodeStr(scan.nextLine()));
// }
// scan.close();
//2 本地文件输入测试
Scanner scan = null;
try {
scan = new Scanner(new FileInputStream("D:decode_case.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
String numQ;
while (scan.hasNextLine()) {
numQ = scan.nextLine();
if (!scan.nextLine().equals(decodeStr(numQ.substring(3)))) {
System.out.println(String.format("%s 处的case未通过测试", numQ.substring(0, 2)));
}
}
System.out.println("已跑完所有case");
}
}
本地case文件：
注意，旧代码昨日机试，线上case 85%， 上述代码为修改后的最新代码， 可能会有线上oj case不通过的情况，但目前还未发现。如有问题，请指正。
发表评论