专栏名称: 九章算法

专业的北美IT求职经验分享、技术交流社区，帮助你找到好的IT工作。由硅谷顶尖IT企业工程师维护。提供专业的算法培训/面试咨询，官网 www.jiuzhang.com

Google 面试题 | 验证UTF-8

九章算法 · 公众号 · 算法 · 2017-01-24 08:51

正文

顶部引导关注动图

验证UTF-8

题目描述

我们一些数据，判断这些数据是否是合法的UTF-8的编码

样例输入

Example 1:

data = [197, 130, 1], 如果用八位字节表示

11000101 10000010 00000001 .

Return true .

Example 2:

data = [235, 140, 4], 如果用八位字节表示

11101011 10001100 00000100 .

Return false .

解题思路分析

此题难点在于对题意是否完全理解。那么我们先来解读一下题意。在题目里，已经给出了UTF-8的一些规则，如下：

通过这个表我们能够得到一些规律，当第一个数的前三位是110时，后一个数一定前两位是10，如果第一个数前四位是1110，那么后两个数的前两位的前两位是10……通过这个规则，我们就能够对这些数进行处理了。那么问题现在就变成了如果取 判断一个数的前几位是什么 ，这里我们可以通过位运算去处理。

举个例子，判断一个数的前三位是否是110，那么我们可以先将这个数右移(>>)5位(题目上给出数都是至少8位)，判断这个数是否等于0b10(二进制下的10)即可，同理可以判断前二位，前一位的情况。

参考代码

http://www.jiuzhang.com/solutions/utf-8-validation/

面试官角度分析

这道题目能够熟练的运用位运算取出一个数的前几位才是这题的hire程度，主要考察对位运算的运用。

推荐文章

算法爱好者 · 被公司辞退，拿到22万补偿金。结果在准备入职新公司时，原公司HR电话叫我回去上班，涨薪7000，但要把赔偿金还回去…

22 小时前

算法与数据结构 · 年薪154W！真心建议大家冲一冲新兴领域，工资高前景好

昨天

算法爱好者 · 再见！IBM 中国！

昨天

算法爱好者 · 普通人如何抓住 DeepSeek 红利：清华大学出品（PDF可下载）

昨天

算法爱好者 · 奔驰中国裁员赔偿 N+9！网友：现在入职还来得及吗？

3 天前

数据宝 · 【资金流向】10股尾盘主力资金净流入超3000万元

8 年前

智囊团达人 · 郑爽｜你现在这样很危险啊！

8 年前

芭莎娱乐 · 看完她们的“踩雷史”，以后买唇膏妈妈再也不担心我买错颜色了

8 年前

新华网 · 硬汉赢韩！1：0！这才是中国男足！

7 年前

央视网体育 · 【24小时看点】18:35 足球之夜；19:30 中超：广州恒大淘宝-广州富力；次日08:30 NBA：快船-马刺

7 年前