1 描述

2 解题

• 分析：建立一棵二叉树来处理，如果遇到0就处理左边，遇到1就处理右边
• 例如：
  
  根据用户的输入顺序来存储，先出现的编码先存到数组的前面位置，但是不影响唯一性，
  比如上图，如果下一个编码是010，那么就要从数组的第5位开始存了，下标5这个信息存储在数组第一个节点的leftpoint中，这样就串起来了
• 代码：

/*
这颗树实际上就是一个一维数组，但是和完全二叉树存储方法不同，他并不能直接使用下标来遍历
准确的说这是一个存储在顺序表中的链表
节点的左右指针（就是int数字）指向下一个元素的下标
下一个元素的下标根据下一个数的取值来定，如果是0的话就是leftpoint指向的下标
如果是1的话就是rightpoint指向的下标
*/
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;struct node
{ //读到的数字是1就处理右节点，如果是0的话就处理左节点int flag = 0;int leftpoint = 0;int rightpoint = 0;
};
typedef struct node hufftree;int main()
{int n;// 这样申请的动态数组并不会自动赋值为节点中的0，只是申请了空间// hufftree *ht;// ht = (hufftree*)malloc(sizeof(hufftree)*1000);hufftree ht[50000];char *str;int len;          //字符串（编码）的长度int treecout = 1; //这个树的长度int treeindex;    //正在处理的这个字符对应在树中的位置int i = 0;// freopen("file out.txt", "r", stdin);cin >> n;str = (char *)malloc(sizeof(char) * 100000);while (n--){cin >> str;len = strlen(str);treeindex = 0;for (i = 0; i < len; i++){if (ht[treeindex].flag == 1){ // flag为1，说明之前已经出现了一样的编码cout << str << endl;return 0; //只需要输出第一次重复的前缀就行，直接返回}if (i < len - 1){ //最后一个字符（结尾）需要单独处理，因为最后一位涉及flag，这里先讨论前面的字符if (str[i] == '0'){ //如果是0，我们就来看左指针if (ht[treeindex].leftpoint == 0){ //如果还是初始值，说明没有出现过这个编码，直接建立就行了ht[treeindex].leftpoint = treecout;treeindex = treecout++; // cout的值始终比index的值大1continue;}else{ //之前有相同的部分，直接按照leftpoint的指向得到下标treeindex = ht[treeindex].leftpoint;continue;}}else{//如果是1，就看右指针if (ht[treeindex].rightpoint == 0){ht[treeindex].rightpoint = treecout;treeindex = treecout++;continue;}else{treeindex = ht[treeindex].rightpoint;continue;}}}else{ //存最后一位if (str[i] == '0'){ //是0，针对左指针操作if (ht[treeindex].leftpoint == 0){ //当前位的左指针没有使用，把他左边指针指向下一位，并且下一位的flag置为0//记住：最后一位的相应指针是被使用了的，0：使用了leftpoint；1：使用了rightpointht[treeindex].leftpoint = treecout;ht[treecout].flag = 1;//是把下一位置的flag置为0treecout++;continue;}else{ //当前位的左指针被使用了，说明之前出现了相同的编码，而且程序运行到这说明是正在处理编码的最后一位，那么可以断定编码重复cout << str << endl;return 0;}}else{//如果是1相同的道理if (ht[treeindex].rightpoint == 0){ht[treeindex].rightpoint = treecout;ht[treecout].flag = 1;treecout++;continue;}else{cout << str << endl;return 0;}}}}}cout << "YES" << endl;return 0;
}

• 最先写的时候我把最后一位的flag置为1，而不是把下一位的flag置为1，这样就会有争议，无法确定是已经结束的这个字符串的最后一个字符是0还是1，对之后的判断产生困扰，之后我又增加了一个flag，但是还是无法完全AC，直到改成现在这个程序才过

参考来源