LeetCode #393 UTF-8 Validation. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
문제 해석만 해두고 연휴 마지막날 밤에 잠깐이면 되겠지 해서 붙잡고 정신차리고 보니까 2시간 반걸림..
처리과정이랑 골격까지는 술술되더니 마지막에 예외케이스들 수정하는데 정신줄 놓고 막해버림, 성능 최악~
Worst performance ever~
LeetCode #393
Q.
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.
UTF8 문자는 1~ 4 바이트 long 타입이고, 다음과 같은 룰을 따른다.
1 바이트 캐릭터는, 첫번째 비트가 0 이고, 다음에 유니코드 코드가 온다.
n 바이트 캐릭터는, 첫번째 n 개의 비트가 전부 1 이고, n+1 번째의 bit 는 0 이다. 이 후 n-1 개의 바이트는 맨 앞의 bit 두개가 10으로 시작한다.
This is how the UTF-8 encoding would work: UTF-8 인코딩이 어떻게 동작하는지를 보자
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
**1바이트 문자는 0 부터 시작하고 나머지는 유니코드
**n바이트 문자는 n개의 1부터 시작후 0이 한개 붙고, 나머지 byte 들의 시작 bit 두개가 10 으로 시작한다.
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
데이터를 나타내는 정수의 배열을 입력받고, utf-8 인코딩이 유효한지 확인해서 반환해라
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.
인풋은 정수의 배열이다. 데이터를 저장하기 위해서 최소한 중요한 8비트의 정수는 있다. 8비트 정수는 1바이트의 데이터를 나타낸다.
e.g.
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.
Process
// Process
//1. Input data vector
//2. Iterate from begin to the end
// 2.1. Convert decimal int to binary string
//3. Iterate from begin to the end
// 3.1. Get count of "1" in the head byte (UTF form)
// 3.2. Iterate from i to i + count
// 3.2.1. Check if front number is '1' and '0'
//4. Return isValid or not
// 처리과정
//1. 데이터 벡터 입력받는다.
//2. 데이터 시작부터 끝까지 반복한다.
// 2.1. 데이터를 binary로 변환한다.
//3. 데이터 시작부터 끝까지 반복한다.
// 3.1. utf 맨 앞 형식에 맞는지 확인해서 맞으면
// 3.1.1. 몇자인지 나온만큼 반복한다.
// 3.1.1.1. 앞자가 10 인지 확인한다.
//4. 결과 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
#include <vector>
#include <iostream>
#include <string>
using namespace std;
// 처리과정
//1. 데이터 벡터 입력받는다.
//2. 데이터 시작부터 끝까지 반복한다.
// 2.1. 데이터를 binary로 변환한다.
//3. 데이터 시작부터 끝까지 반복한다.
// 3.1. utf 맨 앞 형식에 맞는지 확인해서 맞으면
// 3.1.1. 몇자인지 나온만큼 반복한다.
// 3.1.1.1. 앞자가 10 인지 확인한다.
//4. 결과 반환한다.
class Solution {
private:
bool isDone = false;
public:
bool validUtf8(vector<int>& data) {
bool isValid = true;
vector<string> convertedData;
string convertedString;
//convert decimal integer to binary string
for (int i = 0; i < data.size(); ++i)
{
convertedString = convert2Binary(data[i]);
convertedData.push_back(convertedString);
}
int validByteCount;
for (int i = 0; i < convertedData.size() && isValid; ++i)
{
//cout << "binary : " << convertedData[i] << " ";
//count number of 1 of the head byte
validByteCount = checkFirstByte(convertedData[i]);
if (validByteCount > 1)
{
//cout << "validByteCount : " << validByteCount << " ";
int j = i + 1;
//cout << "j : " << j << " " << "convertedDataSize : " << convertedData.size() << " ";
if ((validByteCount - 1) > (convertedData.size() - j))
{
//cout << (validByteCount - 1) << " > " << (convertedData.size() - j);
isValid = false;
}
//cout << isValid;
while (--validByteCount > 0 && isValid)
{
if (j > convertedData.size() - 1 || !checkSequenceByte(convertedData[j]))
isValid = false;
++j;
}
i = --j;
//cout << " i : " << i << endl;
}
else if (validByteCount != 0)
{
isValid = false;
}
}
return isValid;
}
private:
string convert2Binary(int& integer) {
string binaryString = "";
if (integer < 256)
{
if (integer >= 128)
{
integer -= 128; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 64)
{
integer -= 64; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 32)
{
integer -= 32; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 16)
{
integer -= 16; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 8)
{
integer -= 8; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 4)
{
integer -= 4; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 2)
{
integer -= 2; binaryString += "1";
}
else
{
binaryString += "0";
}
if (integer >= 1)
{
integer -= 1; binaryString += "1";
}
else
{
binaryString += "0";
}
}
else
{
return 0;
}
return binaryString;
}
/*
* get the count of 1 in the byte string
*/
int checkFirstByte(const string& binaryString) {
int validByteLength = 0;
if (binaryString[0] == '0')
return 0;
else if (binaryString[0] != '1')
return -1;
for (int i = 1; i < 5; ++i)
{
if (binaryString[i] == '1')
{
if (binaryString[i - 1] == '1')
++validByteLength;
else
return -1;
if (i == 3 && binaryString[i+1] != '0')
return -1;
}
else if (binaryString[i] == '0')
{
if (binaryString[i - 1] != '1')
return -1;
else
return ++validByteLength;
}
}
return validByteLength;
}
bool checkSequenceByte(string& binaryString) {
if (binaryString[0] != '1' || binaryString[1] != '0')
return false;
return true;
}
};
int main(int args, char *argv[]) {
//vector<int> data = { 240,162,138,147,145 }; // 0
//vector<int> data = { 145 }; // 0
//vector<int> data = { 230, 136, 145 }; // 1
//vector<int> data = { 10 }; // 1
vector<int> data = { 248,130,130,130 }; // 0
Solution sln;
bool answer = sln.validUtf8(data);
std::cout << endl << "answer : " << answer << endl;
}
Something else you might like...?
2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)
2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)
2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법