华为OD机试:最长子字符串的长度(二)
题目描述
模拟一套简化的序列化传输方式,请实现下面的数据编码与解码过程
1.编码前数据格式为 [位置,类型,值],多个数据的时候用逗号分隔,位置仅支持数字,不考虑重复等场景;类型仅支持:Integer / String / Compose(Compose的数据类型表示该存储的数据也需要编码)
2.编码后数据参考图示,数据区的格式是:位置#类型#长度#数据,类型存储需要编码,Integer->0;String->1;Compose->2,长度是指数据的字符长度;数据仅允许数字、大小写字母、空格。
3.输入的编码字符长度不能超过1000,一个数据的格式错误,则解析剩下数据,其他错误输出ENCODE_ERROR。
4.输入的解码字符不能超过1000,数据区异常则跳过继续解析剩余数据区,其他异常输出DECODE_ERROR。
输入描述
输入有两行:
第一行是命令,1表示编码,2表示解码
第二行输入待编码、解码的字符
数据最多嵌套10层,[1,Compose,[1,String,Second]] 为2层嵌套。
输出描述
如果输入要求是编码,则输出编码结果;
如果输入要求是解码,则输出解码结果;
当异常时输出对应的错误字符。
用例
题目解析
1.首先判断输入的命令是编码还是解码。
2.如果是编码,遍历输入的数据列表,根据数据类型进行编码,并将结果拼接成一个字符串。
3.如果是解码,遍历输入的编码字符串,根据编码规则进行解码,并将结果存储到一个列表中。
4.在编码和解码过程中,需要注意处理异常情况,如数据格式错误、编码字符长度超过限制等。
JS算法源码 const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; const type2num = { Integer: "0", String: "1", Compose: "2" }; const num2type = { 0: "Integer", 1: "String", 2: "Compose" }; void (async function () { const command = await readline(); const str = await readline(); switch (command) { case "1": console.log(encode(str)); break; case "2": try { console.log(decode(str)); } catch (e) { console.log("DECODE_ERROR"); } break; } })(); function check_encode_str(str) { const stack = []; for (let c of str) { if (c == "]") { while (stack.length > 0 && stack.at(-1) != "[") { stack.pop(); } if (stack.length == 0) { return false; } else { stack.pop(); } } else { stack.push(c); } } return stack.length == 0; } function check_encoded(pos, type, data) { const num_regExp = /^\d+$/; const str_regExp = /^[0-9a-zA-Z\s]+$/; if (!num_regExp.test(pos)) { return false; } if (type2num[type] == undefined) { return false; } if (type == "Integer") { return num_regExp.test(data); } else if (type == "String") { return str_regExp.test(data); } return true; } function encode(str) { str = str.replaceAll("],[", "]["); if (!check_encode_str(str)) { return "ENCODE_ERROR"; } let s = str.replaceAll("[", "<").replaceAll("]", ">"); const reg = /<([^<>]+)>/; let match; while ((match = reg.exec(s))) { let [pos, type, data] = match[1].split(","); let encodeStr = ""; if (check_encoded(pos, type, data)) { encodeStr = [pos, type2num[type], data.length, data].join("#"); } s = s.replace(match[0], encodeStr); } return s; } function check_decoded(pos, type, data) { const num_regExp = /^\d+$/; const str_regExp = /^[0-9a-zA-Z\s]+$/; if (!num_regExp.test(pos)) { return false; } if (num2type[type] == undefined) { return false; } if (type == "0") { return num_regExp.test(data); } else if (type == "1") { return str_regExp.test(data); } return true; } function decode(str) { let queue = str.split("#"); const res = []; while (queue.length > 0) { if (queue.length < 4) { throw "DECODE_ERROR"; } const pos = queue.shift(); let type = queue.shift(); const len = parseInt(queue.shift()); const remain = queue.join("#"); queue.length = 0; let data = remain.slice(0, len); if (remain.length > len) { queue = remain.slice(len).split("#"); } if (type == "2") { data = decode(data); } if (check_decoded(pos, type, data)) { res.push(`[${pos},${num2type[type]},${data}]`); } } return res.join(","); }
Java算法源码 import java.util.*; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Main { static HashMap<String, String> type2num = new HashMap<>(); static HashMap<String, String> num2type = new HashMap<>(); static Pattern num_RegExp = Pattern.compile("^\\d+$"); static Pattern str_RegExp = Pattern.compile("^[0-9a-zA-Z\\s]+$"); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int command = Integer.parseInt(sc.nextLine()); String str = sc.nextLine(); type2num.put("Integer", "0"); type2num.put("String", "1"); type2num.put("Compose", "2"); num2type.put("0", "Integer"); num2type.put("1", "String"); num2type.put("2", "Compose"); switch (command) { case 1: System.out.println(encode(str)); break; case 2: try { System.out.println(decode(str)); } catch (Exception e) { System.out.println("DECODE_ERROR"); } break; } } public static boolean check_encode_str(String str) { LinkedList<Character> stack = new LinkedList<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == ']') { while (!stack.isEmpty() && stack.getLast() != '[') { stack.removeLast(); } if (stack.isEmpty()) { return false; } else { stack.removeLast(); } } else { stack.addLast(c); } } return stack.isEmpty(); } public static boolean check_encoded(String pos, String type, String data) { if (!num_RegExp.matcher(pos).find()) { return false; } if (!type2num.containsKey(type)) { return false; } if ("Integer".equals(type)) { return num_RegExp.matcher(data).find(); } else if ("String".equals(type)) { return str_RegExp.matcher(data).find(); } return true; } public static String encode(String s) { s = s.replaceAll("],\\[", "]["); if (!check_encode_str(s)) { return "ENCODE_ERROR"; } s = s.replaceAll("\\[", "<").replaceAll("]", ">"); Pattern p = Pattern.compile("<([^<>]+)>"); while (true) { Matcher m = p.matcher(s); if (!m.find()) break; String[] tmp = m.group(1).split(","); String pos = tmp[0]; String type = tmp[1]; String data = tmp[2]; String encodeStr = ""; if (check_encoded(pos, type, data)) { encodeStr = pos + "#" + type2num.get(type) + "#" + data.length() + "#" + data; } s = s.replace(m.group(0), encodeStr); } return s; } public static boolean check_decoded(String pos, String type, String data) { if (!num_RegExp.matcher(pos).find()) { return false; } if (!num2type.containsKey(type)) { return false; } if ("0".equals(type)) { return num_RegExp.matcher(data).find(); } else if ("1".equals(type)) { return str_RegExp.matcher(data).find(); } return true; } public static String decode(String str) { LinkedList<String> queue = new LinkedList<>(); Collections.addAll(queue, str.split("#")); StringJoiner res = new StringJoiner(","); while (!queue.isEmpty()) { String pos = queue.removeFirst(); String type = queue.removeFirst(); int len = Integer.parseInt(queue.removeFirst()); String remain = String.join("#", queue); queue.clear(); String data = remain.substring(0, len); if (remain.length() > len) { Collections.addAll(queue, remain.substring(len).split("#")); } if ("2".equals(type)) { data = decode(data); } if (check_decoded(pos, type, data)) { res.add("[" + pos + "," + num2type.get(type) + "," + data + "]"); } } return res.toString(); } }
Python算法源码 import re command = input() s = input() type2num = {"Integer": "0", "String": "1", "Compose": "2"} num2type = {"0": "Integer", "1": "String", "2": "Compose"} num_regExp = re.compile("^\\d+$") str_regExp = re.compile("^[0-9a-zA-Z\\s]+$") def check_encode_str(s): stack = [] for c in s: if c == ']': while len(stack) > 0 and stack[-1] != '[': stack.pop() if len(stack) == 0: return False else: stack.pop() else: stack.append(c) return len(stack) == 0 def check_encoded(pos, typ, data): if not num_regExp.match(pos): return False if typ not in type2num: return False if typ == "Integer": return num_regExp.match(data) elif typ == "String": return str_regExp.match(data) return True def encode(): global s s = s.replace("],[", "][") if not check_encode_str(s): return "ENCODE_ERROR" s = s.replace("[", "<").replace("]", ">") p = re.compile("<([^<>]+)>") m = p.search(s) while m is not None: pos, typ, data = m.group(1).split(",") res = [] if check_encoded(pos, typ, data): res.append(pos) res.append(type2num[typ]) res.append(str(len(data))) res.append(data) s = s.replace(m[0], "#".join(res)) m = p.search(s) return s def check_decoded(pos, typ, data): if not num_regExp.match(pos): return False if typ not in num2type: return False if typ == "0": return num_regExp.match(data) elif typ == "1": return str_regExp.match(data) return True def decode(string): queue = string.split("#") res = [] while len(queue) > 0: pos = queue.pop(0) typ = queue.pop(0) length = int(queue.pop(0)) remain = "#".join(queue) queue.clear() data = remain[:length] if len(remain) > length: queue = remain[length:].split("#") if typ == "2": data = decode(data) if check_decoded(pos, typ, data): res.append(f"[{pos},{num2type[typ]},{data}]") return ",".join(res) def solution(): if command == '1': print(encode()) elif command == '2': try: print(decode(s)) except: print("DECODE_ERROR") solution()
C算法源码 #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_SIZE 1001 #define TRUE 1 #define FALSE 0 typedef struct ListNode { char *ele; struct ListNode *prev; struct ListNode *next; } ListNode; typedef struct LinkedList { int size; ListNode *head; ListNode *tail; } LinkedList; LinkedList *new_LinkedList() { LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList)); link->size = 0; link->head = NULL; link->tail = NULL; return link; } void addLast_LinkedList(LinkedList *link, char *ele) { ListNode *node = (ListNode *) malloc(sizeof(ListNode)); node->ele = (char *) calloc(MAX_SIZE, sizeof(char)); strcpy(node->ele, ele); node->prev = NULL; node->next = NULL; if (link->size == 0) { link->head = node; link->tail = node; } else { link->tail->next = node; node->prev = link->tail; link->tail = node; } link->size++; } char *removeFirst_LinkedList(LinkedList *link) { if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) { link->head = NULL; link->tail = NULL; } else { link->head = link->head->next; link->head->prev = NULL; } link->size--; return removed->ele; } int isInteger(const char *s) { int i = 0; while (s[i] != '\0') { if (s[i] < '0' || s[i] > '9') { return 0; } i++; } return 1; } int isValidStr(const char *s) { int i = 0; while (s[i] != '\0') { char c = s[i]; int flag = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == ' '; if (!flag) { return 0; } i++; } return 1; } int check_encode_str(char *s) { char *pos = strstr(s, "],["); while (pos != NULL) { long long i = pos - s + 1; while (s[i] != '\0') { s[i] = s[i + 1]; i++; } pos = strstr(s, "],["); } char stack[MAX_SIZE] = {'\0'}; int stack_size = 0; int i = 0; while (s[i] != '\0') { if (s[i] == ']') { while (stack_size > 0 && stack[stack_size - 1] != '[') { stack_size--; } if (stack_size == 0) { return FALSE; } else { stack_size--; } } else { stack[stack_size++] = s[i]; } i++; } return stack_size == 0; } void encode(char *s) { if (!check_encode_str(s)) { printf("ENCODE_ERROR\n"); return; } while (TRUE) { int l = 0; while (s[l] != '\0' && s[l] != '[') { l++; } if (s[l] == '\0') { break; } int r = l + 1; while (s[r] != '\0') { if (s[r] == ']') { break; } if (s[r] == '[') { l = r; } r++; } char tmp[MAX_SIZE] = {'\0'}; strncpy(tmp, s + l + 1, r - l - 1); char *pos = strtok(tmp, ","); char *type = strtok(NULL, ","); char *data = strtok(NULL, ","); int flag = TRUE; if (strcmp(type, "Integer") == 0) { type = "0"; flag = isInteger(data); } else if (strcmp(type, "String") == 0) { type = "1"; flag = isValidStr(data); } else if (strcmp(type, "Compose") == 0) { type = "2"; } else { flag = FALSE; } if (flag) { flag = isInteger(pos); } char repl[MAX_SIZE] = {'\0'}; if (flag) { strcat(repl, pos); strcat(repl, "#"); strcat(repl, type); strcat(repl, "#"); char len[10] = {'\0'}; sprintf(len, "%lld", strlen(data)); strcat(repl, len); strcat(repl, "#"); strcat(repl, data); } char ss[MAX_SIZE] = {'\0'}; strncat(ss, s, l); strcat(ss, repl); strcat(ss, s + r + 1); memset(s, '\0', MAX_SIZE); s = strcpy(s, ss); } printf("%s\n", s); } LinkedList *split(char *s, char *separator) { char *token = strtok(s, separator); LinkedList *queue = new_LinkedList(); while (token != NULL) { addLast_LinkedList(queue, token); token = strtok(NULL, separator); } return queue; } char *pop_join(LinkedList *queue, char *separator) { char *res = (char *) calloc(MAX_SIZE, sizeof(char)); strcat(res, removeFirst_LinkedList(queue)); while (queue->size > 0) { strcat(res, separator); strcat(res, removeFirst_LinkedList(queue)); } return res; } char *decode(char *s) { LinkedList *queue = split(s, "#"); LinkedList *res = new_LinkedList(); while (queue->size > 0) { if (queue->size < 4) { return "DECODE_ERROR"; } char *pos = removeFirst_LinkedList(queue); char *type = removeFirst_LinkedList(queue); int len = atoi(removeFirst_LinkedList(queue)); char *remain = pop_join(queue, "#"); char data[MAX_SIZE] = {'\0'}; strncpy(data, remain, len); if (strlen(remain) > len) { queue = split((remain + len), "#"); } if (strcmp(type, "2") == 0) { strcpy(data, decode(data)); } int flag = TRUE; if (strcmp(type, "0") == 0) { strcpy(type, "Integer"); flag = isInteger(data); } else if (strcmp(type, "1") == 0) { strcpy(type, "String"); flag = isValidStr(data); } else if (strcmp(type, "2") == 0) { strcpy(type, "Compose"); } else { flag = FALSE; continue; } if (flag) { flag = isInteger(pos); } if (flag) { char ele[MAX_SIZE] = {'\0'}; strcat(ele, "["); strcat(ele, pos); strcat(ele, ","); strcat(ele, type); strcat(ele, ","); strcat(ele, data); strcat(ele, "]"); addLast_LinkedList(res, ele); } } return pop_join(res, ","); } int main() { int command; scanf("%d", &command); getchar(); char s[MAX_SIZE] = {'\0'}; gets(s); if (command == 1) { encode(s); } else if (command == 2) { printf("%s", decode(s)); } return 0; }
C++算法源码 #include<bits/stdc++.h> using namespace std; map<string, string> type2num; map<string, string> num2type; regex num_RegExp("^\\d+$"); regex str_RegExp("^[0-9a-zA-Z\\s]+$"); bool check_encode_str(string &s) { stack<char> stk; for (const auto &c: s) { if (c == ']') { while (!stk.empty() && stk.top() != '[') { stk.pop(); } if (stk.empty()) { return false; } else { stk.pop(); } } else { stk.push(c); } } return stk.empty(); } bool check_encoded(string &pos, string &type, string &data) { if (!regex_match(pos, num_RegExp)) { return false; } if (type2num.count(type) == 0) { return false; } if ("Integer" == type) { return regex_match(data, num_RegExp); } else if ("String" == type) { return regex_match(data, str_RegExp); } return true; } string encode(string &s) { size_t start = s.find("],["); while (start != string::npos) { s.replace(start, 3, "]["); start = s.find("],["); } if (!check_encode_str(s)) { return "ENCODE_ERROR"; } for (int i = 0; i < s.length(); i++) { if (s[i] == '[') { s[i] = '<'; } else if (s[i] == ']') { s[i] = '>'; } } regex p("<([^<>]+)>"); smatch m; while (regex_search(s, m, p)) { stringstream ss(m.str(1)); string pos; getline(ss, pos, ','); string type; getline(ss, type, ','); string data; getline(ss, data, ','); string res; if (check_encoded(pos, type, data)) { res += pos + "#"; res += type2num[type] + "#"; res += to_string(data.length()) + "#"; res += data; } s = s.replace(s.find(m.str(0)), m.str(0).length(), res); } return s; } deque<string> split(const string &s, char separator) { stringstream ss(s); string token; deque<string> queue; while (getline(ss, token, separator)) { queue.push_back(token); } return queue; } string pop_join(deque<string> &queue, char separator) { string res = queue.front(); queue.pop_front(); while (!queue.empty()) { res += separator; res += queue.front(); queue.pop_front(); } return res; } bool check_decoded(string &pos, string &type, string &data) { if (!regex_match(pos, num_RegExp)) { return false; } if (num2type.count(type) == 0) { return false; } if ("0" == type) { return regex_match(data, num_RegExp); } else if ("1" == type) { return regex_match(data, str_RegExp); } return true; } string decode(const string &str) noexcept(false) { deque<string> queue = split(str, '#'); deque<string> res; while (!queue.empty()) { if (queue.size() < 4) { return "DECODE_ERROR"; } string pos = queue.front(); queue.pop_front(); string type = queue.front(); queue.pop_front(); int len = stoi(queue.front()); queue.pop_front(); string remain = pop_join(queue, '#'); string data = remain.substr(0, len); if (remain.length() > len) { queue = split(remain.substr(len), '#'); } if ("2" == type) { data = decode(data); } if (check_decoded(pos, type, data)) { res.emplace_back("[" + pos + "," + num2type[type] + "," + data + "]"); } } return pop_join(res, ','); } int main() { string command; getline(cin, command); string str; getline(cin, str); type2num["Integer"] = "0"; type2num["String"] = "1"; type2num["Compose"] = "2"; num2type["0"] = "Integer"; num2type["1"] = "String"; num2type["2"] = "Compose"; if (command == "1") { cout << encode(str) << endl; } else if (command == "2") { cout << decode(str) << endl; } return 0; }