leetcode393. 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 | 0xxxxxxx0000 0080-0000 07FF | 110xxxxx 10xxxxxx0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx0001 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.

檢驗整數數組能否構成合法的UTF8編碼的序列。UTF8的字節編碼規則如下:

  1. 每個UTF8字符包含1~4個字節
  2. 如果只包含1個字節,則該字節以0作為開頭,剩下的位隨意
  3. 如果包含兩個或兩個以上字節,則起始字節以n個1和1個0開頭,例如,如果該UTF8字符包含兩個字節,則第一個字節以110開頭,同理,三個字符的第一個字節以1110開頭。剩余的字節必須以10開頭。

思路和代碼

首先我們整理一下,每一種類型的UTF8字符包含什么樣的規格:

  1. 只包含一個字節,該字節格式為0xxxxxxx,則轉換為整數的話,該整數必須小于128(1000000)
  2. 包含多個字節,則頭字節格式為110xxxxx, 1110xxxx, 11110xxx。而緊跟其后的字符必須格式為10xxxxxx。

綜上所述:

  1. num<1000000: 單字節
  2. 10000000=<num<11000000: 多字節字符的跟隨字節
  3. 11000000<=num<11100000: 兩個字節的起始字節
  4. 11100000<=num<11110000: 三個字節的起始字節
  5. 11110000<=num<11111000: 四個字節的起始字節

下面分別是這題的兩種實現:

遞歸實現:

    private static final int ONE_BYTE = 128; //10000000private static final int FOLLOW_BYTE = 192; //11000000private static final int TWO_BYTE = 224; //11100000private static final int THREE_BYTE = 240;//11110000private static final int FOUR_BYTE = 248;//11111000public boolean validUtf8(int[] data) {return validUtf8(data, 0);}public boolean validUtf8(int[] data, int startAt) {if(startAt >= data.length) return true;int first = data[startAt];int followLength = 0;if(first < ONE_BYTE) {return validUtf8(data, startAt+1);}else if(first < FOLLOW_BYTE){return false;}else if(first <TWO_BYTE) {followLength = 2;}else if(first < THREE_BYTE) {followLength = 3;}else if(first < FOUR_BYTE) {followLength = 4;}else {return false;}if(startAt + followLength > data.length) return false; for(int i = 1 ; i<followLength ; i++) {int next = data[startAt + i];if(next < ONE_BYTE || next >= FOLLOW_BYTE) {return false;}}return validUtf8(data, startAt + followLength);}

循環實現:

    private static final int ONE_BYTE = 128; //10000000private static final int FOLLOW_BYTE = 192; //11000000private static final int TWO_BYTE = 224; //11100000private static final int THREE_BYTE = 240;//11110000private static final int FOUR_BYTE = 248;//11111000public boolean validUtf8(int[] data) {return validUtf8(data, 0);}public boolean validUtf8(int[] data, int startAt) {int followCount = 0;for(int num : data) {if(num < ONE_BYTE) {if(followCount != 0) {return false;}}else if(num < FOLLOW_BYTE) {if(followCount == 0) {return false;}followCount--;}else if(num < TWO_BYTE) {if(followCount != 0) {return false;}followCount = 1;}else if(num < THREE_BYTE) {if(followCount != 0) {return false;}followCount = 2;}else if(num < FOUR_BYTE) {if(followCount != 0) {return false;}followCount = 3;}else {return false;}}return followCount == 0;}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/536958.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/536958.shtml
英文地址,請注明出處:http://en.pswp.cn/news/536958.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Mybatis源碼閱讀(五 ):接口層——SqlSession

*************************************優雅的分割線 ********************************** 分享一波:程序員賺外快-必看的巔峰干貨 如果以上內容對你覺得有用,并想獲取更多的賺錢方式和免費的技術教程 請關注微信公眾號:HB荷包 一個能讓你學習技術和賺錢方法的公眾號,持續更…

插入公式_一個小工具,徹底幫你搞定在Markdown中插入公式的問題

在編輯Markdown文檔時&#xff0c;插入公式是一個挺麻煩的活兒。需要掌握LaTex語法。我自己看完語法后&#xff0c;直接放棄&#xff0c;這絕對是反人類的語法。&#xff08;好吧&#xff0c;是我不會用...&#xff09;但是&#xff0c;我相信你看了這篇文章后&#xff0c;絕對…

JavaScript數據結構與算法——字典

1.字典數據結構 在字典中&#xff0c;存儲的是【鍵&#xff0c;值】對&#xff0c;其中鍵名是用來查詢特定元素的。字典和集合很相似&#xff0c;集合以【值&#xff0c;值】的形式存儲&#xff0c;字典則是用【鍵&#xff0c;值】對的形式存儲。字典也稱作映射。 2.創建字典 f…

Mybatis源碼閱讀(一):Mybatis初始化1.2 —— 解析別名、插件、對象工廠、反射工具箱、環境

*************************************優雅的分割線 ********************************** 分享一波:程序員賺外快-必看的巔峰干貨 如果以上內容對你覺得有用,并想獲取更多的賺錢方式和免費的技術教程 請關注微信公眾號:HB荷包 一個能讓你學習技術和賺錢方法的公眾號,持續更…

中西方對時間的差異_中西方時間觀念差異 英文

The concept of time(時間觀念)①Inchina&#xff0c;words and phrases about time are very general. Forexample&#xff0c;ifyoudatewithsomeone,mostofChineseusedtoanswer: in the afternoon /at night/after a while and so on.Butinwestern,peoplehaveaverystrongconc…

Google 修改 Chrome API,防止隱身模式檢測

開發四年只會寫業務代碼&#xff0c;分布式高并發都不會還做程序員&#xff1f; 在使用 Chrome 瀏覽網頁時&#xff0c;某些網站會使用某種方法來確定訪問者是否處于隱身模式&#xff0c;這是一種隱私泄漏行為。Google 目前正在考慮修改 Chrome 的相關 API&#xff0c;來杜絕…

Mybatis源碼閱讀(一):Mybatis初始化1.1 解析properties、settings

*************************************優雅的分割線 ********************************** 分享一波:程序員賺外快-必看的巔峰干貨 如果以上內容對你覺得有用,并想獲取更多的賺錢方式和免費的技術教程 請關注微信公眾號:HB荷包 一個能讓你學習技術和賺錢方法的公眾號,持續更…

亞馬遜推薦python_使用python查找amazon類別

我想得到amazon的類別&#xff0c;我計劃廢棄不用API。我已經取消了http://www.amazon.com&#xff0c;我已經在Shop By Department下拉列表中抓取了所有的類別和子類別&#xff0c;我創建了一個web服務來完成這項工作&#xff0c;代碼就在這里route(/hello)def hello():textli…

JavaScript異步基礎

唯一比不知道代碼為什么崩潰更可怕的事情是&#xff0c;不知道為什么一開始它是工作的&#xff01;在 ECMA 規范的最近幾次版本里不斷有新成員加入&#xff0c;尤其在處理異步的問題上&#xff0c;更是不斷推陳出新。然而&#xff0c;我們在享受便利的同時&#xff0c;也應該了…

Flutter、ReactNative、uniapp對比

*************************************優雅的分割線 ********************************** 分享一波:程序員賺外快-必看的巔峰干貨 如果以上內容對你覺得有用,并想獲取更多的賺錢方式和免費的技術教程 請關注微信公眾號:HB荷包 一個能讓你學習技術和賺錢方法的公眾號,持續更…

JavaScript數組方法

一、基本類型和引用類型 數值、字符串、布爾值、undefined、null可以直接寫出來&#xff0c;比較簡單的數據稱為基本類型&#xff0c;在比較的時候&#xff0c;是直接按值比較。對象、函數、數組復雜的數據是引用類型&#xff0c;在比較的時候&#xff0c;是按照地址比較。cons…

nodejs mysql模塊_NodeJs使用Mysql模塊實現事務處理

依賴模塊&#xff1a;1. mysql&#xff1a;https://github.com/felixge/node-mysqlnpm install mysql --save2. async&#xff1a;https://github.com/caolan/asyncnpm install async --save(ps: async模塊可換成其它Promise模塊如bluebird、q等)因為Node.js的mysql模塊本身對于…

計數排序vs基數排序vs桶排序

從計數排序說起 計數排序是一種非基于元素比較的排序算法&#xff0c;而是將待排序數組元素轉化為計數數組的索引值&#xff0c;從而間接使待排序數組具有順序性。 計數排序的實現一般有兩種形式&#xff1a;基于輔助數組和基于桶排序。 基于輔助數組 整個過程包含三個數組&…

多線程中ThreadLocal的使用

*************************************優雅的分割線 ********************************** 分享一波:程序員賺外快-必看的巔峰干貨 如果以上內容對你覺得有用,并想獲取更多的賺錢方式和免費的技術教程 請關注微信公眾號:HB荷包 一個能讓你學習技術和賺錢方法的公眾號,持續更…

mysql 查看所有表的引擎_MySQL查看數據庫、表的占用空間大小以及某個庫中所有表的引擎類型...

本文章來給大家介紹一些常用的MySQL查看數據庫、表的占用空間大小sql命令吧&#xff0c;希望此教程 對各位同學會有所幫助。查看各庫的大小代碼如下復制代碼SELECT SUM(DATA_LENGTH)SUM(INDEX_LENGTH) FROM information_schema.tables WHERE TABLE_SCHEMAdatabase_name;結果是以…

Fusion組件庫是如何支持多語言能力的

隨著國際化發展&#xff0c;多語言的需求越來越常見&#xff0c;單一的語言已經遠不能滿足需求了。作為一個組件庫&#xff0c;支持多語言也是基本能力。 多語言功能的本質其實是文本的替換&#xff0c;一個詞匯“OK”&#xff0c;在英文語境下是“OK”&#xff0c;日語語境下是…

mysql 存儲過程 replace_mysql replace存儲過程

{"moduleinfo":{"card_count":[{"count_phone":1,"count":1}],"search_count":[{"count_phone":4,"count":4}]},"card":[{"des":"阿里云數據庫專家保駕護航&#xff0c;為用戶…

注解版poi操作工具

*************************************優雅的分割線 ********************************** 分享一波:程序員賺外快-必看的巔峰干貨 如果以上內容對你覺得有用,并想獲取更多的賺錢方式和免費的技術教程 請關注微信公眾號:HB荷包 一個能讓你學習技術和賺錢方法的公眾號,持續更…

Kali Linux 2019.1 發布,Metasploit 更新到 5.0 版本

百度智能云 云生態狂歡季 熱門云產品1折起>>> Kali Linux 2019.1 發布了&#xff0c;Kali 前身 BackTrack&#xff0c;它是一個基于 Debian 的 Linux 發行版&#xff0c;主要用于信息安全行業&#xff0c;其包含了一系列安全、滲透測試和取證工具。此版本 Linux 內核…

peewee mysql_scrapy中利用peewee插入Mysql

前兩天老大布置一個任務&#xff0c;說爬下來的數據要存入數據庫中&#xff0c;丟給我一個peewee&#xff0c;說用這個。當時的我兩眼一抹黑&#xff0c;這是個什么東西呀&#xff0c;我知道scrapy的數據存入數據庫是在pipelines中進行設置但是peewee是什么東西呢。經過兩天不懈…