Skip to main content

393. UTF-8 Validation | leetcode solution

393UTF-8 Validation

 Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

  1. For a 1-byte character, the first bit is a 0, followed by its Unicode code.
  2. For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

     Number of Bytes   |        UTF-8 Octet Sequence
                       |              (binary)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x denotes a bit in the binary form of a byte that may be either 0 or 1.

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:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
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.

 

Constraints:

  • 1 <= data.length <= 2 * 104
  • 0 <= data[i] <= 255


solution:

class Solution {
public:
    int count_bits(int data)
    {   
        if(data == 255)
            return 8;
        int count = 0;
        int i =7;
        while(data & (1 <<i))
        {
             count++;
             i--;
        }
       return count;
    }
    bool validUtf8(vector<int>& data) {
        
        vector<int>bits;
        for(int i =0 ; i < data.size() ; i++)
        {
            bits.push_back(count_bits(data[i]));
            
        }
        for(int i =0 ; i < data.size() ; i++)
        {   
            if(bits[i] == 1  || bits[i] > 4)
                return false;
            else
            if(bits[i] == 0 )
                continue;
            else
                if(data.size() == 1)
                    return false;
            else
            {   
                int t = i;
                int x = bits[i]-1;
                while(x--)
                {
                      t++;
                    if(bits[t] != 1)
                        return false;
                     
                }
                i = t ;
            }
         
          }
         return true;
    }
       
};


Comments

Popular posts from this blog

[PDF DOWNLOAD] AKTU Quantum series data structure b.tech 2nd year download

  All AKTU Quantums are available here. Get your hands on AKTU Quantums and boost your grades in AKTU semester exams. You can either search them category wise or can use the search bar or can manually search on this page. Download aktu second year quantum pdf data structures  download  data structures quantum aktu download aktu data structures quantum click here to download  write in comment section if you want quantum of any other subject.

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...