摘要:記錄長度法復雜度時間空間思路本題難點在于如何在合并后的字符串中,區分出原來的每一個子串。這里我采取的編碼方式,是將每個子串的長度先賦在前面,然后用一個隔開長度和子串本身。這樣我們先讀出長度,就知道該讀取多少個字符作為子串了。
Encode and Decode Strings
記錄長度法 復雜度Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function:
string encode(vectorstrs) { // ... your code return encoded_string; }
Machine 2 (receiver) has the function:
vectordecode(string s) { //... your code return strs; } So Machine 1 does:
string encoded_string = encode(strs);
and Machine 2 does:
vectorstrs2 = decode(encoded_string);
strs2 in Machine 2 should be the same as strs in Machine 1.Implement the encode and decode methods.
Note: The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters. Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless. Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.
時間 O(N) 空間 O(1)
思路本題難點在于如何在合并后的字符串中,區分出原來的每一個子串。這里我采取的編碼方式,是將每個子串的長度先賦在前面,然后用一個#隔開長度和子串本身。這樣我們先讀出長度,就知道該讀取多少個字符作為子串了。
注意為了簡化代碼,這里使用了indexOf和substring這兩個屬于String的API,實際上復雜度和遍歷是一樣的。
代碼public class Codec { // Encodes a list of strings to a single string. public String encode(Liststrs) { StringBuilder output = new StringBuilder(); for(String str : strs){ // 對于每個子串,先把其長度放在前面,用#隔開 output.append(String.valueOf(str.length())+"#"); // 再把子串本身放在后面 output.append(str); } return output.toString(); } // Decodes a single string to a list of strings. public List decode(String s) { List res = new LinkedList (); int start = 0; while(start < s.length()){ // 找到從start開始的第一個#,這個#前面是長度 int idx = s.indexOf("#", start); int size = Integer.parseInt(s.substring(start, idx)); // 根據這個長度截取子串 res.add(s.substring(idx + 1, idx + size + 1)); // 更新start為子串后面一個位置 start = idx + size + 1; } return res; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64585.html
摘要:值得注意的是,有的編碼方案不一定能表示某些信息,這時編碼就會失敗,比如就不能用來表示中文。數組的每一項是一個字節,用來表示。所以對于字符串來說,其長度等于編碼后字節的長度。所以,讓來編碼解碼中文,就超出了其能力范圍。 在人機交互之字符編碼 一文中對字符編碼進行了詳細的討論,并通過一些簡單的小程序驗證了我們對于字符編碼的認識。但僅了解這篇文章的內容,并不能幫我們在日常編程中躲過一些字符編...
摘要:我可以明確告訴你這不是,但它可以用解釋器運行。這種黑魔法,還要從說起。提案者設想使用一種特殊的文件首注釋,用于指定代碼的編碼。暴露了一個函數,用于注冊自定義編碼。所謂的黑魔法其實并不神秘,照貓畫虎定義好相應的接口即可。 首發于我的博客,轉載請注明出處 寫在前面 本文為科普文 本文中的例子在 Ubuntu 14.04 / Python 2.7.11 下運行成功,Python 3+ 的接...
摘要:需求問題需要對序列化以后的對象中的在中進行存取由于聲稱只支持作為暴露出來的最基本的數據類型形式的存取所以需要在存取前后將與互相轉換發現從出來的跟之前的不一樣即使強制指定了一致的編碼解碼方式結果仍不符合預期猜測嘗試懷疑是系統的默認編碼方式與解 需求&問題 需要對序列化以后的對象 (java中的byte[]) 在redis中進行存取由于redis聲稱只支持String(作為redis暴露出...
摘要:,,等屬于不同的字符集,轉換編碼就是在它們中的任意兩者間進行。一般個人用的電腦上控制臺基本上都是編碼的,但運維的機器上基本全是,中文的時候就會有酸爽的問題。 總結總結,本文僅適用于python2.x 默認編碼與開頭聲明 首先是開頭的地方聲明編碼 # coding: utf8 這個東西的用處是聲明文件編碼為utf8(要寫在前兩行內),不然文件里如果有中文,比如 a = 美麗 b = u美...
閱讀 3448·2023-04-26 00:39
閱讀 4039·2021-09-22 10:02
閱讀 2532·2021-08-09 13:46
閱讀 1098·2019-08-29 18:40
閱讀 1444·2019-08-29 18:33
閱讀 773·2019-08-29 17:14
閱讀 1513·2019-08-29 12:40
閱讀 2970·2019-08-28 18:07