UTF-8 Validation

Kahn 发布于2019-08-14 17:18 / 3452人阅读

摘要：题目链接这道题关键是搞懂题目意思。思路及代码知道意思之后，这道题就很简单了。一个，每次分三步来做，是每次都是新的统计后位里面，从前开始有多少个，用变量来保存，其中可能的值只有从开始检查，后八位中的前两位是否为，一共检查更新的值为

UTF-8 Validation

题目链接：https://leetcode.com/problems...

这道题关键是搞懂题目意思。

UTF-8

1 byte: characters from 0 to 127 == ASCII
2 bytes: characters from 127 to 2047
3 bytes: characters from 2048 to 65535
4 bytes: characters from 65536 to 1112064

The leading bits tell: the length of the bytes

1 byte: the 1st bit is 0

2 bytes:

1st byte: start with "110"

2nd byte: start with "10"

3 bytes:

1st byte: start with "1110"

2nd byte: start with "10"

3rd byte: start with "10"

4 bytes:

1st byte: start with "11110"

2nd byte: start with "10"

3rd byte: start with "10"

4th byte: start with "10"

思路及代码

知道意思之后，这道题就很简单了。
一个loop，每次分三步来做，loop invariant是每次data[i]都是first byte of 新的character

统计data[i]后8位里面，从前开始有多少个1，用变量ones来保存，其中ones可能的值只有0, 2, 3, 4

从 data[i+1] 开始检查，后八位中的前两位是否为"10"，一共检查ones - 1

更新i的值为 i + ones

public class Solution {
    public boolean validUtf8(int[] data) {
        /* 1. check how many "1"s = ones
         * 2. check (i + 1, i + ones - 1) for "10"
         * 3. update i = i + ones
         * valid ones: 0, 2, 3, 4
         */
        int i = 0;
        while(i < data.length) {
            // 1. find ones
            int ones = 0;
            while(((data[i] >> (7 - ones)) & 1) == 1) {
                ones++;
            }
            // invalid ones 
            if(ones == 1 || ones > 4) return false;
            // 2. check 1s
            i++;
            while(ones-- > 1) {
                if(i >= data.length || ((data[i] >> 6) & 3) != 2) return false;
                // 3. update i
                i++;
            }
        }
        
        return true;
    }
}

Advantage of UTF-8

implement Unicode: encode different symbols(Chinese...)

web pages are often coded in UTF-8, XML, JSON

only use binary representation: 0 and 1

endianness independent

Disadvantage of UTF-8

space: use more bytes, larger

time: calculate

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66554.html

[LintCode] UTF-8 Validation

Problem A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules: For 1-byte character, the first bit is a 0, followed by its unicode code.For n-bytes character, the first n...

tolerious 2019-08-19 10:57 评论0 收藏0
leetcode393. UTF-8 Validation

摘要：题目要求检验整数数组能否构成合法的编码的序列。剩余的字节必须以开头。而紧跟其后的字符必须格式为。综上所述单字节多字节字符的跟随字节两个字节的起始字节三个字节的起始字节四个字节的起始字节下面分别是这题的两种实现递归实现循环实现题目要求 A character in UTF8 can be from 1 to 4 bytes long, subjected to the followin...

Cruise_Chan 2019-08-16 15:07 评论0 收藏0
记录_使用JSR303规范进行数据校验

摘要：时间年月日星期三说明使用规范校验接口请求参数源码第一章理论简介背景介绍如今互联网项目都采用接口形式进行开发。该规范定义了一个元数据模型，默认的元数据来源是注解。时间：2017年11月08日星期三说明：使用JSR303规范校验http接口请求参数源码：https://github.com/zccodere/s... 第一章：理论简介 1-1 背景介绍如今互联网项目都采用HTTP接口...

187J3X1 2019-08-15 12:28 评论0 收藏0
Bean Validation完结篇：你必须关注的边边角角（约束级联、自定义约束、自定义校验器、国际

摘要：和上标注的约束都会被执行注意如果子类覆盖了父类的方法，那么子类和父类的约束都会被校验。每篇一句没有任何技术方案会是一种银弹，任何东西都是有利弊的相关阅读【小家Java】深入了解数据校验：Java Bean Validation 2.0（JSR303、JSR349、JSR380）Hibernate-Validation 6.x使用案例【小家Spring】Spring方法级别数据校...

niuxiaowei111 2019-08-19 10:17 评论0 收藏0
eclipse定制化配置调优、初始化配置指南、可以解决启动慢等问题

摘要：配置的参数打开根目录下的在最后面加上如下的参数测试环境位内存双核测试版本经测试，启动速度比默认配置有所提升，占用内存也较少其中这三行为启用方式，不能保证在不同环境下都是最优配置，可以替换为多核和大内存建议使配置eclipse的jvm参数打开eclipse根目录下的eclipse.ini在最后面加上如下的jvm参数 -Xms400m -Xmx1400m -XX:NewSize=128...

Warren 2019-08-14 15:16 评论0 收藏0