搜狗2019秋招客户端工程师部分编程题合集（第一场）

一、题目
猜测输入文本的编码格式UTF-8 UTF-16 GBK 三选一，以上都不是则为OTHER
要求：不能使用语言提供的转码功能
输入：不同编码格式的文本
输出：UTF-8、UTF-16、GBK、OTHER


二、注意事项
1.测试用例不含BOM头部，其中UTF-16编码采用小端存储
2.由于牛客网字符编码有兼容性问题，故对输入文本进行再编码预处理，并规定前三个字符为文本长度。例如，文本内容（UTF8编码）为123的16进制表示形式为313233，长度为6位，故进行再编码处理后为006313233，并将其以字符串形式保存为UTF8编码格式的文本
3.预处理函数
1.C语言：
//预处理还原函数
void hexStringToIntArray(const unsigned char* buff,unsigned char* retBuff,long *retSize){
    //由于牛客网字符编码兼容性有问题，故将输入数据再编码为了16进制格式,并约定前三个数字为文本长度，这里需要将再编码的16进制还原为原始的二进制数据
    unsigned int xbuffLength = 0
    
    //编码预处理的时候把‘\n’去掉了，所以约定前三位为文本长度，这里取前三位,获取文本长度
    unsigned char temp[4]
    temp[0]=buff[0]
    temp[1]=buff[1]
    temp[2]=buff[2]
    temp[3]='\0'
    sscanf(temp, "%x", &xbuffLength)
    
    //还原
    for (unsigned int i = 3 i < (xbuffLength+3) ++i){
        if ((i-3) % 2 != 0) {
            unsigned int a
            unsigned char temp[3]
            temp[0]=buff[i-1]
            temp[1]=buff[i]
            temp[2]='\0'
            sscanf(temp, "%x", &a)
            retBuff[(*retSize)++] = a
        }
    }
    
}
使用实例：
int main() {
    unsigned char buff[2048]
    fscanf(stdin, "%s",buff)
    
    unsigned char xbuff[2048]
    long length = 0

    //将预处理的编码还原回去
    hexStringToIntArray(buff, xbuff, &length)

    //考生需要实现的函数
    char *str = verifyStringEncode(xbuff,length)
    printf("%s\n", str)
    return 0
}
2.Java语言：
十六进制字符串转short []的Java代码：
static short[] hexStringToShortArray(String s) {
  short[] data = new short[s.length() / 2]
  int i = 0
  int k = 0
  while (i < s.length()) {
   try {
    char c1 = s.charAt(i)
    char c2 = '\0'
    if (i + 1 < s.length()) {
     c2 = s.charAt(i + 1)
    }

    String temp = c1 + ""
    if (c2 != '\0') {
     temp = c1 + "" + c2
    }
    data[k] = Short.parseShort(temp, 16)
   } catch (NumberFormatException e) {
    return null
   }
   i = i + 2
   k++
  }
  return data
 }
三、编码格式介绍
UTF-8
UTF-8是在互联网上使用最广的一种Unicode的实现方式，是Unicode的实现方式之一。UTF-8 最大的一个特点，就是它是一种变长的编码方式。它可以使用1~6个字节表示一个符号，根据不同的符号而变化字节长度。
UTF-8 的编码规则很简单，只有二条：
1）对于单字节的符号，字节的第一位设为0，后面7位为这个符号的 Unicode 码。因此对于英语字母，UTF-8 编码和 ASCII 码是相同的。
2）对于n字节的符号（n > 1），第一个字节的前n位都设为1，第n + 1位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的 Unicode 码。
下表总结了编码规则，字母x表示可用编码的位。
字节数  | UTF-8编码方式
        | （二进制）
----------------------+---------------------------------------------
1字节   | 0xxxxxxx
2字节   | 110xxxxx 10xxxxxx
3字节   | 1110xxxx 10xxxxxx 10xxxxxx
4字节   | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
5字节   | 111110xx 10xxxxxx 10xxxxxx 10xxxxxx
6字节   | 1111110x 10xxxxxx 10xxxxxx 10xxxxxx
跟据上表，解读 UTF-8 编码非常简单。如果一个字节的第一位是0，则这个字节单独就是一个字符；如果第一位是1，则连续有多少个1，就表示当前字符占用多少个字节。此外，UTF-8编码的文本文档，有的带有BOM (Byte Order Mark, 字节序标志)，即0xEF, 0xBB, 0xBF，有的没有。


GBK
GB2312是1981年开始实施的一套汉字处理的编码方案，GB是“基本”的意思，GB2312是对ASCII进行了扩展。GB2312编码共收录汉字6763个，其中一级汉字3755个，二级汉字3008个，一级汉字比二级汉字更常用。同时，GB2312编码收录了包括拉丁字母、希腊字母、日文平假名及片假名字母、俄语西里尔字母在内的682个全角字符。GB2312编码范围：A1A1－FEFE，并对所收录字符进行了“分区”处理，共94个区，每区含有94个位，共8836个码位，编码是从0xA1开始1区，到94区结束，这种表示方式也称为区位码。GB2312规定对ASCII采用单字节表示，对收录的汉字及符号采用两个字节表示，第一个字节为“高字节”，对应94个区；第二个字节为“低字节”，对应94个位。所以它的区位码范围是：0101－9494。区号和位号分别加上0xA0就是GB2312编码。
GBK是对GB2312的扩充，扩展到总体编码范围为8140-FEFE，首字节在81-FE 之间，尾字节在40-FE 之间，剔除 xx7F一条线。总计23940 个码位。
1.GBK用一个字节表示一个英文字符和一些基本符号和半角符号，用两个字节表示一个汉字和全角符号和一些我们日常使用的符号。
2.GBK利用了ASCII的127个字符之后空余的部分。
3.数值小于127的字节表示ASCII中原有字符，两个连续数值都大于127的字节表示一个汉字字符。
4.使用GBK编码，当读取到一个数值上小于127的字节时当作一个ASCII中原有的字符处理。读到一个数值大于127的字节时必定会继续读取下一个字节，下一个字节的数值无需大于127，将两个字节一起组合形成一个汉字字符。


UTF-16
UTF-16也是Unicode的实现方式之一，但UTF-16和UTF-8是彻底不同的两种Unicode实现形式。Unicode是一个符号集，它对世界上大部分的文字系统进行了整理、编码，使得电脑可以用更为简单的方式来呈现和处理文字。解决传统的字符编码方案的局限。Unicode一开始由两个字节表示（usc-2），后来扩充到了四个字节（usc-4）。usc-4的格式定义为第一个字节的首位固定为0，后面的7位表示128个组，每个组又有256个面，每个面可以表示65536个字符。其总表示的范围为00000000 - 7FFFFFFF。0组0面的字符集合被称为BMP（Basic Multilingual Plane）也被称为基本多文种平面，对应于usc-2。其中平面15和平面16上只是定义了两个各占65534个码位的专用区（Private Use Area），分别是0xF0000-0xFFFFD和0x100000-0x10FFFD。所谓专用区，就是保留给大家放自定义字符的区域，可以简写为PUA。平面0（基本多文种平面）也有一个专用区：0xE000-0xF8FF，有6400个码位。平面0的0xD800-0xDFFF，共2048个码位，是一个被称作代理区（Surrogate）的特殊区域。代理区的目的用两个UTF-16字符表示BMP以外的字符。
UTF-16编码涉及大小端问题，通常情况下,UTF-16的文本会通过在文件开头以名为BOM（Byte Order Mark）的字符来表明文件是Big Endian（大端）还是Little Endian（小段）。小端BOM为0xFF, 0xFE，大端BOM为0xFE, 0xFF，但携带BOM并不是强制要求。UTF-16 编码以16位无符号整数为单位进行编码，其中汉字的编码区间为0x4E00–0x9FA5。此外，UTF-16通过基本多文种平面的代理区的编码空间0xD800-0xDFFF来对0x10000到0x0FFFF（即辅助平面）进行字符映射。