首页 > 代码库 > 微软校招编程题"Beautiful String"的状态机解法
微软校招编程题"Beautiful String"的状态机解法
昨天碰巧看到一道微软校招的编程题,题目大意如下:
如果一个字符串包括三组或者更多组的连续升序字母,每组长度相等,那么我们就称这个字符串是Beautiful String如下是一些Beautiful String的例子:abc、cde、aabbcc、aaabbbccc这些不是Beautiful String:abd、cba、aabbc、zab输入一个只含有小写字母的字符串,如果它含有一个Beautiful的子串,就输出YES,否则输出NO输入:第一行是案例个数,之后的每一行是一个数字,一个字符串,数字表示字符串长度,长度小于10MB输出:YES或者NO
很容易想到可以用一个指针依次往前扫描,看是否符合Beautiful的条件,当出现不匹配时,从上次扫描起点的下一个位置开始新的尝试。这种判断过程可以用一个状态机来描述,我之前一直有一种模糊的想法,利用goto来实现不同状态的跳转,现在有这个题作为背景,正好可以试验一下这种想法,代码如下:
#include <stdio.h>#include <stdlib.h>int main(void){ int n, length; char * str; char *p; char * p_bak; int count[3]; char pre; scanf("%d", &n); while (n--) { scanf("%d", &length); str = (char*)malloc(sizeof(char) * (length + 1)); scanf("%s", str); p = str; count[0] = 0; count[1] = 0; count[2] = 0; p_bak = p; goto SECTION_0; REWIND: count[0] = 0; count[1] = 0; count[2] = 0; p = ++p_bak; goto SECTION_0; SUCCESS: printf("YES\n"); free(str); continue; FAIL: printf("NO\n"); free(str); continue; SECTION_0: pre = *p; SECTION_A: if (*p == ‘\0‘) goto FAIL; if (*p == pre) { ++p; ++count[0]; goto SECTION_A; } else if (*p == pre + 1) { goto SECTION_B; } else { goto REWIND; } SECTION_B: if (*p == ‘\0‘) { goto FAIL; goto FAIL; //向苹果致敬(●‘?‘●),参见 http://coolshell.cn/articles/11112.html } if (*p == pre + 1) { ++p; ++count[1]; goto SECTION_B; } else if (*p == pre + 2) { goto SECTION_C; } else { goto REWIND; } SECTION_C: if (count[0] != count[1]) goto REWIND; if (*p == ‘\0‘) goto FINAL_CHECK; if (count[2] == count[1]) goto SUCCESS; if (*p == pre + 2) { ++p; ++count[2]; goto SECTION_C; } FINAL_CHECK: if (count[2] != count[1]) goto REWIND; else goto SUCCESS; } return 0;}
从没写过这种就像汇编一样的面条代码,写完之后感觉整个人都要坏掉了,当然,一次AC。
(用C实现状态机应该可以利用switch case等功能来实现状态跳转,而不用goto,以后有时间再重构吧。)
微软校招编程题"Beautiful String"的状态机解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。