class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int len = data.size();
        vector<string> s(len);
        for (int i = 0; i < len; ++ i ) {
            // 将每个转换为字符串编码
            for (int j = 7; j >= 0; -- j ) {
                int x = (data[i] >> j) & 1;
                s[i] += char('0' + x);
            }
            // cout << s[i] << endl;
        }
        // 接下来去判断。
        bool flag = true;
        int op = 0;
        int i = 0;
        while (i < len) {
            op = calc(s[i]);
            // cout << i << " " << op << endl;
            if (op == 5) {
                // 说明计算错误
                flag = false;
                break;
            } else {
                // 去判断是否成立
                if (op == 1) {
                    ++ i;
                }
                else if (op == 2) {
                    if (i + 1 < len && s[i + 1][0] == '1' && s[i + 1][1] == '0') {
                        i += 2;
                    } else {
                        flag = false;
                        break;
                    }
                } else if (op == 3) {
                    if (i + 2 < len && s[i + 1][0] == '1' && s[i + 1][1] == '0' && s[i + 2][0] == '1' && s[i + 2][1] == '0') {
                        i += 3;
                    } else {
                        flag = false;
                        break;
                    }
                } else {
                    if (i + 3 < len && s[i + 1][0] == '1' && s[i + 1][1] == '0' && s[i + 2][0] == '1' && s[i + 2][1] == '0' && s[i + 3][0] == '1' && s[i + 3][1] == '0') {
                        i += 4;
                    } else {
                        flag = false;
                        break;
                    }
                }
            }
        }
        return flag;
    }
    int calc(string s) {
        if (s[0] == '0') {
            return 1;
        } else if (s[0] == '1' && s[1] == '1' && s[2] == '0') {
            return 2;
        } else if (s[0] == '1' && s[1] == '1' && s[2] == '1' && s[3] == '0') {
            return 3;
        } else if (s[0] == '1' && s[1] == '1' && s[2] == '1' && s[3] == '1' && s[4] == '0') {
            return 4;
        } else {
            return 5;
        }
    }
};