393. UTF-8 Validation

public class Solution {
    public bool ValidUtf8(int[] data) {
        int nBytes = 0;
        foreach (int num in data) {
            string binRep = Convert.ToString(num, 2).PadLeft(8, '0').Substring(0, 8);
            if (nBytes == 0) {
                foreach (char bit in binRep) {
                    if (bit == '0') break;
                    nBytes++;
                }
                if (nBytes == 0) continue;
                if (nBytes == 1 || nBytes > 4) return false;
            } else {
                if (!(binRep[0] == '1' && binRep[1] == '0')) return false;
            }
            nBytes--;
        }
        return nBytes == 0;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool ValidUtf8(vector<int>& data) {
        int nBytes = 0;
        foreach (int num in data) {
            string binRep = Convert.ToString(num, 2).PadLeft(8, '0').Substring(0, 8);
            if (nBytes == 0) {
                foreach (char bit in binRep) {
                    if (bit == '0') break;
                    nBytes++;
                }
                if (nBytes == 0) continue;
                if (nBytes == 1 || nBytes > 4) return false;
            } else {
                if (!(binRep[0] == '1' && binRep[1] == '0')) return false;
            }
            nBytes--;
        }
        return nBytes == 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.validUtf8(new int[]{197, 130, 1})); // true
        System.out.println(solution.validUtf8(new int[]{235, 140, 4})); // false
    }
}

class Solution {
    public boolean validUtf8(int[] data) {
        int nBytes =

var validUtf8 = function(data) {
    let nBytes = 0;
    for (let num of data) {
        let binRep = num.toString(2).padStart(8, '0').slice(-8);
        if (nBytes === 0) {
            for (let bit of binRep) {
                if (bit === '0') break;
                nBytes++;
            }
            if (nBytes === 0) continue;
            if (nBytes === 1 || nBytes > 4) return false;
        } else {
            if (!(binRep[0] === '1' && binRep[1] === '0')) return false;
        }
        nBytes--;
    }
    return nBytes === 0;
};

class Solution:
    def validUtf8(self, data):
        n_bytes = 0

        for num in data:
            bin_rep = format(num, '#010b')[-8:]

            if n_bytes == 0:
                for bit in bin_rep:
                    if bit == '0': break
                    n_bytes += 1

                if n_bytes == 0:
                    continue

                if n_bytes == 1 or n_bytes > 4:
                    return False
            else:
                if not (bin_rep[0] == '1' and bin_rep[1] == '0'):
                    return False

            n_bytes -= 1

        return n_bytes == 0

package main

import (
    "fmt"
)

func validUtf8(data []int) bool {
    nBytes := 0
    for _, num := range data {
        binRep := fmt.Sprintf("%08b", num)[-8:]
        if nBytes == 0 {
            for _, bit := range binRep {
                if bit == '0' {
                    break
                }
                nBytes++
            }
            if nBytes == 0 {
                continue
            }
            if nBytes == 1 || nBytes > 4 {
                return false
            }
        } else {
            if !(binRep[0] == '1' && binRep[1] == '0') {
                return false
            }
        }
        nBytes--
    }
    return nBytes == 0
}

func main() {
    data1 := []int{197, 130, 1}
    data2 := []int{235, 140, 4}
    fmt.Println(validUtf8(data1)) // true
    fmt.Println(validUtf8(data2)) // false
}

Algorithm

Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep.

Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа.

Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий.

Теперь давайте перейдем к реализации этого алгоритма.

😎