Massive Algorithms: LeetCode 393

LeetCode 393 - UTF-8 Validation

https://leetcode.com/problems/utf-8-validation/

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-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.

Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

X. http://www.cnblogs.com/grandyang/p/5847597.html

这道题考察我们UTF-8编码，这种互联网所采用的通用的编码格式的产生是为了解决ASCII只能表示英文字符的局限性，和统一Unicode的实现方式。下面这段摘自维基百科UTF-8编码：

对于UTF-8编码中的任意字节B，如果B的第一位为0，则B独立的表示一个字符(ASCII码)；
如果B的第一位为1，第二位为0，则B为一个多字节字符中的一个字节(非ASCII字符)；
如果B的前两位为1，第三位为0，则B为两个字节表示的字符中的第一个字节；
如果B的前三位为1，第四位为0，则B为三个字节表示的字符中的第一个字节；
如果B的前四位为1，第五位为0，则B为四个字节表示的字符中的第一个字节；
因此，对UTF-8编码中的任意字节，根据第一位，可判断是否为ASCII字符；根据前二位，可判断该字节是否为一个字符编码的第一个字节；根据前四位（如果前两位均为1），可确定该字节为字符编码的第一个字节，并且可判断对应的字符由几个字节表示；根据前五位（如果前四位为1），可判断编码是否有错误或数据传输过程中是否有错误。

那么根据上面的描述，我们可以先来判断第一位，如果是0的话，则说明是ASCII码，我们直接跳过，判断方法是只要比二进制数10000000小的数第一位肯定是0，然后我们来处理第一位是1的情况，由于第一位的1只是个标识符，后面连续跟的1的个数才是表示后面的字节的个数，我们可以统一从第一位开始连续1的个数，然后减去1就是后面的字节的个数，我想的办法是如果该数字大于等于128，则表示第一位是1，然后减去128，如果得到的数大于等于64，则表示第二位是1，依次类推就可以得到连续的个数，我们要注意10000000这个数是不合法的，遇到了直接返回false。我们得到了cnt的个数，只要验证后面的字节是否是以10开头的数即可，验证方法也很简单，只要这个数在10000000 ~ 10111111范围之间，则一定是10开头的，

https://leetcode.com/problems/utf-8-validation/discuss/87464/Bit-Manipulation-Java-6ms

public boolean validUtf8(int[] data) {
 if(data==null || data.length==0) return false;
 boolean isValid = true;
 for(int i=0;i<data.length;i++) {
  if(data[i]>255) return false; // 1 after 8th digit, 100000000
  int numberOfBytes = 0;
  if((data[i] & 128) == 0) { // 0xxxxxxx, 1 byte, 128(10000000)
   numberOfBytes = 1;
  } else if((data[i] & 224) == 192) { // 110xxxxx, 2 bytes, 224(11100000), 192(11000000)
   numberOfBytes = 2;
  } else if((data[i] & 240) == 224) { // 1110xxxx, 3 bytes, 240(11110000), 224(11100000)
   numberOfBytes = 3;
  } else if((data[i] & 248) == 240) { // 11110xxx, 4 bytes, 248(11111000), 240(11110000)
   numberOfBytes = 4;
  } else {
   return false;
  }
  for(int j=1;j<numberOfBytes;j++) { // check that the next n bytes start with 10xxxxxx
   if(i+j>=data.length) return false;
   if((data[i+j] & 192) != 128) return false; // 192(11000000), 128(10000000)
  }
  i=i+numberOfBytes-1;
 }
 return isValid;
}

    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for (int d : data) {
            if (cnt == 0) {
                if ((d >> 5) == 0b110) cnt = 1;
                else if ((d >> 4) == 0b1110) cnt = 2;
                else if ((d >> 3) == 0b11110) cnt = 3;
                else if (d >> 7) return false;
            } else {
                if ((d >> 6) != 0b10) return false;
                --cnt;
            }
        }
        return cnt == 0;
    }

http://blog.csdn.net/mebiuw/article/details/52445248
而解题的核心在于：
1、按照规则，识别byte应该有几位
2、如果是2-4bytes的数据，继续检查后面的数据是否10开头再返回1，而是1byte则直接返回
public boolean validUtf8(int[] data) { int n = data.length; int skip = 0b10000000; int check = 0; for (int i = 0; i < data.length; i++) { if (check > 0) { if ((data[i] & skip) == skip) check--; else return false; } else { check = getHeadType(data[i]); if (check < 0) return false; } } return check == 0; } /** * 检查*/ public int getHeadType(int num) { if ((num & 0b11110000) == 0b11110000) return 3; if ((num & 0b11100000) == 0b11100000) return 2; if ((num & 0b11000000) == 0b11000000) return 1; if ((num & 0b10000000) == 0b10000000) return -1; //error return 0; }

http://bookshadow.com/weblog/2016/09/04/leetcode-utf-8-validation/
def validUtf8(self, data): """ :type data: List[int] :rtype: bool """ masks = [0x0, 0x80, 0xE0, 0xF0, 0xF8] bits = [0x0, 0x0, 0xC0, 0xE0, 0xF0] while data: for x in (4, 3, 2, 1, 0): if data[0] & masks[x] == bits[x]: break if x == 0 or len(data) < x: return False for y in range(1, x): if data[y] & 0xC0 != 0x80: return False data = data[x:] return True

X. Recursion
http://www.voidcn.com/article/p-ndzzhlyb-kv.html

 public static boolean validUtf8(int[] data) {
  validUtf8(data, 0);
 }
 public static boolean validUtf8(int[] data, int start) {
  if (start == data.length) return true;
  int byteLen = data[start] >> 4;
  if (byteLen <= 7) return validUtf8(data, start + 1);//以0开头的
  if (byteLen == 12 || byteLen == 13) byteLen = 2;//数据格式为110x
  else if (byteLen == 14) byteLen = 3;//以1110开头的
  else if (byteLen == 15) byteLen = 4;//以1111开头的
  else return false;//数据格式为10xx的
  if (byteLen + start > data.length) return false;
  for (int i = 1; i < byteLen; i++) {
   if (data[start + i] > 0xbf || data[start + i] < 0x80) //二进制是否 begin with 10
    return false;
  }
  return validUtf8(data, start + byteLen);
 }

http://www.cnblogs.com/grandyang/p/5847597.html

    bool validUtf8(vector<int>& data) {
        for (int i = 0; i < data.size(); ++i) {
            if (data[i] < 0b10000000) {
                continue;
            } else {
                int cnt = 0, val = data[i];
                for (int j = 7; j >= 1; --j) {
                    if (val >= pow(2, j)) ++cnt;
                    else break;
                    val -= pow(2, j);
                }
                if (cnt == 1) return false;
                for (int j = i + 1; j < i + cnt; ++j) {
                    if (data[j] > 0b10111111 || data[j] < 0b10000000) return false;
                } 
                i += cnt - 1;
            }
        }
        return true;
    }

public boolean validUtf8(int[] data) {

// Number of bytes in the current UTF-8 character

int numberOfBytesToProcess = 0;

// For each integer in the data array.

for (int i = 0; i < data.length; i++) {

// Get the binary representation. We only need the least significant 8 bits

// for any given number.

String binRep = Integer.toBinaryString(data[i]);

binRep = binRep.length() >= 8 ? binRep.substring(binRep.length() - 8)

: "00000000".substring(binRep.length() % 8) + binRep;

// If this is the case then we are to start processing a new UTF-8 character.

if (numberOfBytesToProcess == 0) {

// Get the number of 1s in the beginning of the string.

for (int j = 0; j < binRep.length(); j++) {

if (binRep.charAt(j) == '0') {

break;

}

numberOfBytesToProcess += 1;

}

// 1 byte characters

if (numberOfBytesToProcess == 0) {

continue;

}

// Invalid scenarios according to the rules of the problem.

if (numberOfBytesToProcess > 4 || numberOfBytesToProcess == 1) {

return false;

}

} else {

// Else, we are processing integers which represent bytes which are a part of

// a UTF-8 character. So, they must adhere to the pattern `10xxxxxx`.

if (!(binRep.charAt(0) == '1' && binRep.charAt(1) == '0')) {

return false;

}

// We reduce the number of bytes to process by 1 after each integer.

numberOfBytesToProcess -= 1;

}

// This is for the case where we might not have the complete data for

// a particular UTF-8 character.

return numberOfBytesToProcess == 0;

}

Approach 2: Bit Manipulation

public boolean validUtf8(int[] data) {

// Number of bytes in the current UTF-8 character

int numberOfBytesToProcess = 0;

// Masks to check two most significant bits in a byte.

int mask1 = 1 << 7;

int mask2 = 1 << 6;

// For each integer in the data array.

for (int i = 0; i < data.length; i++) {

// If this is the case then we are to start processing a new UTF-8 character.

if (numberOfBytesToProcess == 0) {

int mask = 1 << 7;

while ((mask & data[i]) != 0) {

numberOfBytesToProcess += 1;

mask = mask >> 1;

}

// 1 byte characters

if (numberOfBytesToProcess == 0) {

continue;

}

// Invalid scenarios according to the rules of the problem.

if (numberOfBytesToProcess > 4 || numberOfBytesToProcess == 1) {

return false;

}

} else {

// data[i] should have most significant bit set and

// second most significant bit unset. So, we use the two masks

// to make sure this is the case.

if (!((data[i] & mask1) != 0 && (mask2 & data[i]) == 0)) {

return false;

}

// We reduce the number of bytes to process by 1 after each integer.

numberOfBytesToProcess -= 1;

}

// This is for the case where we might not have the complete data for

// a particular UTF-8 character.

return numberOfBytesToProcess == 0;

}

LeetCode 393 - UTF-8 Validation

Labels

Popular Posts