設計類題目基本考察的是你對現實事物的抽象能力，一般會遇到一些類的設計、字符串切分、集合的使用（list、map、set、stack、deque）等，結束后我會更新一些關于這些集合的常見使用方法和場景。設計模式其實考察的相對較少的。

一、設計文件系統

你需要設計一個能提供下面兩個函數的文件系統：

create(path, value):?創建一個新的路徑，并盡可能將值 value 與路徑 path 關聯，然后返回?True。如果路徑已經存在或者路徑的父路徑不存在，則返回?False。
get(path):?返回與路徑關聯的值。如果路徑不存在，則返回?-1。
“路徑” 是由一個或多個符合下述格式的字符串連接起來形成的：在?/?后跟著一個或多個小寫英文字母。

例如?/leetcode?和?/leetcode/problems?都是有效的路徑，但空字符串和?/?不是有效的路徑。

輸入：?
["FileSystem","create","get"]
[[],["/a",1],["/a"]]
輸出：?
[null,true,1]
解釋：?
FileSystem fileSystem = new FileSystem();

fileSystem.create("/a", 1); // 返回 true
fileSystem.get("/a"); // 返回 1

分析：首先系統中有兩個實體：文件路徑和文件的值，由于文件路徑的唯一，我們可以考慮用hashmap這種數據結構來存儲path和value的鍵值對。

接下來需要考慮一件事情，針對/leetcode/problems這種我們究竟應該創建幾個路徑？一般我們是創建兩個/leetcode和/leetcode/problems，但是這里他有說明

如果父路徑不存在我們就不需要直接返回False，所以我們需要做的事，把輸入的路徑的父路徑一次遍歷一遍。那么設計就涉及到字符串的分割，java我們可以使用split方法來分割字符串，然后對每一個層次依次進行判斷是否存在。

class FileSystem {HashMap<String,Integer> filePath;// 文件路徑//在構造函數來初始化這個FileSystempublic FileSystem() {filePath= new HashMap<>();filePath.put("",-1);}public boolean createPath(String path, int value) {if(path!="/"){String [] paths = path.split("/");String temp ="/";//判斷父路徑和路徑是否存在，不存在則返回falsefor (int i = 1; i <paths.length ; i++) {temp=temp+paths[i];if(!filePath.containsKey(temp)){return false;}}//若都存在，則路徑中filePath.put(path,value);return true;}else {return false;}}//獲取這個路徑下的文件值public int get(String path) {if (filePath.containsKey(path)){return filePath.get(path);}else {return -1;}}

二、設計內存文件系統

那我們再來個難的

設計一個內存文件系統，模擬以下功能：

ls： 以字符串的格式輸入一個路徑。如果它是一個文件的路徑，那么函數返回一個列表，僅包含這個文件的名字。如果它是一個文件夾的的路徑，那么返回該 文件夾內?的所有文件和子文件夾的名字。你的返回結果（包括文件和子文件夾）應該按字典序排列。

mkdir：輸入一個當前不存在的?文件夾路徑?，你需要根據路徑名創建一個新的文件夾。如果有上層文件夾路徑不存在，那么你也應該將它們全部創建。這個函數的返回類型為 void 。

addContentToFile： 輸入字符串形式的?文件路徑?和 文件內容?。如果文件不存在，你需要創建包含給定文件內容的文件。如果文件已經存在，那么你需要將給定的文件內容 追加?在原本內容的后面。這個函數的返回類型為 void 。

readContentFromFile： 輸入 文件路徑?，以字符串形式返回該文件的?內容?。

輸入:?
["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]
[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]

輸出:
[null,[],null,null,["a"],"hello"]

解釋:

注意:

你可以假定所有文件和文件夾的路徑都是絕對路徑，除非是根目錄?/?自身，其他路徑都是以?/?開頭且 不 以?/?結束。
你可以假定所有操作的參數都是有效的，即用戶不會獲取不存在文件的內容，或者獲取不存在文件夾和文件的列表。
你可以假定所有文件夾名字和文件名字都只包含小寫字母，且同一文件夾下不會有相同名字的文件夾或文件。

分析：還是先來分析一下。比上道題我們的文件系統多了些什么呢？多了個ls：返回該文件路徑下的所有文件夾或者文件；還有一個構造文件路徑的mkdir，這個看起來和我們剛剛的create有點類似，但是好像有點不一樣，我們需要根據路徑名創建一個新的文件夾。如果有上層文件夾路徑不存在，那么你也應該將它們全部創建。剛剛我們只是做了一個判斷，二這里需要判斷父路徑是否存在，并且創建它。根據mkdir，似乎我們還是可以用一個map來存儲它，路徑為key，文件夾或者文件為value。但是這里注意到和我們剛剛的不同，也就是我們的value，可能是一個文件夾和文件的混合體。想想我們好像沒有這樣的數據結構來表現它。那么很自然的我們想到我們需要創建抽象出來一個新的數據接口（或者是類）來幫助我們，這個數據結構里面包含了：一個文件夾集合和一個文件集合。

那么這里又存在一個問題？文件夾里面又可能還有文件和文件夾，所以這是個嵌套結構。好，到這里我們的基本數據結構就確定下來了。

class Dirs {HashMap<String,Dirs> dirs = new HashMap<>();// 路徑和文件夾映射HashMap<String,String> file = new HashMap<>();//路徑和文件值的映射}

繼續開始寫我們的mkdir

public void mkdir(String path) {Dir t = root; //從根目錄開始遍歷String[] paths = path.split("/");for (int i = 1; i <paths.length ; i++) {//層次遍歷，如果有一層不包含，則在當前目錄下創建一個目錄if(!t.dirs.containsKey(paths[i])){t.dirs.put(paths[i],new Dir());}t = t.dirs.get(paths[i]);}}

接下來是addContentToFile，這個比較簡單，就是往路徑下的文件夾放file

public void addContentToFile(String filePath, String content) {//一樣需要從根開始遍歷Dir t = root;String[] d = filePath.split("/");for (int i = 1; i < d.length - 1; i++) {t = t.dirs.get(d[i]); //拿到當前的上級目錄}t.files.put(d[d.length - 1], t.files.getOrDefault(d[d.length - 1], "") + content);}

ls這個就有點意思了，首先我們要分辨出它是文件還是文件夾，如果是文件夾還的再遍歷其下的所有文件夾和文件。其次還要按照字典序（是基于字母順序排列的單詞按字母順序排列的方法，剛開始看這個名詞估計一下就懵了）進行輸出。考慮到java中集合中的字符串已經有了排序的實現方法Collections.sort

public List<String> ls(String path) {Dir t = root;List<String> files =new ArrayList<>(); //最后返回的列表String [] d = path.split("/");for (int i = 1; i <d.length-1; i++) {t=t.dirs.get(d[i]);}//拿到了最上一級的目錄if (t.files.containsKey(d[d.length - 1])) {//有沒有包含名字相同的文件，如果沒有files.add(d[d.length - 1]);return files;} else {//有沒有有包含名字相同的文件夾t = t.dirs.get(d[d.length - 1]);}files.addAll(new ArrayList < > (t.dirs.keySet()));//如果是文件夾files.addAll(new ArrayList<>(t.files.keySet()));//如果是文件Collections.sort(files); //字典序列：return files;}

?三、設計瀏覽器歷史記錄

你有一個只支持單個標簽頁的 瀏覽器?，最開始你瀏覽的網頁是?homepage?，你可以訪問其他的網站?url?，也可以在瀏覽歷史中后退?steps?步或前進?steps?步。

請你實現?BrowserHistory 類：

BrowserHistory(string homepage)?，用?homepage?初始化瀏覽器類。
void visit(string url)?從當前頁跳轉訪問 url 對應的頁面??。執行此操作會把瀏覽歷史前進的記錄全部刪除。
string back(int steps)?在瀏覽歷史中后退?steps?步。如果你只能在瀏覽歷史中后退至多?x 步且?steps > x?，那么你只后退?x?步。請返回后退 至多 steps?步以后的?url?。
string forward(int steps)?在瀏覽歷史中前進?steps?步。如果你只能在瀏覽歷史中前進至多?x?步且?steps > x?，那么你只前進 x?步。請返回前進?至多?steps步以后的 url?。

輸入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
輸出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解釋：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com"); ? ? ? // 你原本在瀏覽 "leetcode.com" 。訪問 "google.com"
browserHistory.visit("facebook.com"); ? ? // 你原本在瀏覽 "google.com" 。訪問 "facebook.com"
browserHistory.visit("youtube.com"); ? ? ?// 你原本在瀏覽 "facebook.com" 。訪問 "youtube.com"
browserHistory.back(1); ? ? ? ? ? ? ? ? ? // 你原本在瀏覽 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1); ? ? ? ? ? ? ? ? ? // 你原本在瀏覽 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1); ? ? ? ? ? ? ? ?// 你原本在瀏覽 "google.com" ，前進到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com"); ? ? // 你原本在瀏覽 "facebook.com" 。 訪問 "linkedin.com"
browserHistory.forward(2); ? ? ? ? ? ? ? ?// 你原本在瀏覽 "linkedin.com" ，你無法前進任何步數。
browserHistory.back(2); ? ? ? ? ? ? ? ? ? // 你原本在瀏覽 "linkedin.com" ，后退兩步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7); ? ? ? ? ? ? ? ? ? // 你原本在瀏覽 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

分析：一看瀏覽器歷史記錄，我就想到了一個數據結構”棧“，我們可以用兩個棧來實現這個功能嗎？一個存我們訪問過的頁面（后退），一個存我們訪問過但是回退了的頁面（前進)。

public class BrowserHistory {//訪問過到頁面Deque<String> visited = new LinkedList<>();//我們訪問完之后，又回退的頁面；同時它的深度也是我們可以前進多少步Deque<String> backed = new LinkedList<>();public BrowserHistory(String homepage) {visited.push(homepage);}public void visit(String url) {visited.push(url);//我們注意到還有一個需求，就是執行這個操作到瀏覽器到前進記錄要全部清空，也就是我們到back棧記錄清空backed.clear();}public String back(int steps) {String url="";if(steps<visited.size()) {for (int i = 0; i <steps ; i++) {url = visited.pop();backed.push(url);}}else{for (int i = 0; i <visited.size() ; i++) {url = visited.pop();backed.push(url);}}return visited.getFirst();}public String forward(int steps) {String url="";if(steps<backed.size()) {for (int i = 0; i <steps ; i++) {url = backed.pop();visited.push(url);}}else{for (int i = 0; i <backed.size() ; i++) {url = backed.pop();visited.push(url);}}return visited.getFirst();}public static void main(String[] args) {BrowserHistory browserHistory = new BrowserHistory("leetcode.com");browserHistory.visit("google.com"); // 你原本在瀏覽 "leetcode.com" 。訪問 "google.com"browserHistory.visit("facebook.com"); // 你原本在瀏覽 "google.com" 。訪問 "facebook.com"browserHistory.visit("youtube.com"); // 你原本在瀏覽 "facebook.com" 。訪問 "youtube.com"System.out.println( browserHistory.back(1));// 你原本在瀏覽 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"System.out.println(browserHistory.back(1)); // 你原本在瀏覽 "facebook.com" ，后退到 "google.com" 并返回 "google.com"System.out.println(browserHistory.forward(1)); // 你原本在瀏覽 "google.com" ，前進到 "facebook.com" 并返回 "facebook.com"browserHistory.visit("linkedin.com"); // 你原本在瀏覽 "facebook.com" 。 訪問 "linkedin.com"System.out.println(browserHistory.forward(2)) ; // 你原本在瀏覽 "linkedin.com" ，你無法前進任何步數。System.out.println(browserHistory.back(2)); // 你原本在瀏覽 "linkedin.com" ，后退兩步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"System.out.println(browserHistory.back(7)); // 你原本在瀏覽 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"}}

還有一類的設計類題目會讓給你一些常見的數據結構讓你實現它，最常見的就是樹、隊列、鏈表等的特殊型號

四、設計前綴樹

Tire（發音類似 "try"）或者說 前綴樹 是一種樹形數據結構，用于高效地存儲和檢索字符串數據集中的鍵。這一數據結構有相當多的應用情景，例如自動補完和拼寫檢查。

請你實現 Trie 類：

Trie() 初始化前綴樹對象。
void insert(String word) 向前綴樹中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前綴樹中，返回 true（即，在檢索之前已經插入）；否則，返回 false 。
boolean startsWith(String prefix) 如果之前已經插入的字符串?word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。

輸入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出
[null, null, true, false, true, null, true]

解釋
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); ? // 返回 True
trie.search("app"); ? ? // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); ? ? // 返回 True

分析：要實現前綴樹，首先需要理解前綴樹，前綴樹還有一種叫法：字典樹

Trie又被稱為前綴樹、字典樹，所以當然是一棵樹。上面這棵Trie樹包含的字符串集合是{in, inn, int, tea, ten, to}。每個節點的編號是我們為了描述方便加上去的。樹中的每一條邊上都標識有一個字符。這些字符可以是任意一個字符集中的字符。比如對于都是小寫字母的字符串，字符集就是’a’-‘z’；對于都是數字的字符串，字符集就是’0’-‘9’；對于二進制字符串，字符集就是0和1。

?

比如上圖中3號節點對應的路徑0123上的字符串是inn，8號節點對應的路徑0568上的字符串是ten。終結點與集合中的字符串是一一對應的。

明白了概念，來看看我們需要什么？對于樹中每個節點包含以下字段：

1、指向子節點的指針數組 children。由于不包含重復，我們考慮用一個map來存儲，key為字母，value為子節點
2、布爾字段 isEnd，表示該節點是否為字符串的結點

結論有了，首先我們一個字典樹（必須有根節點），然后我們有一個子類節點（包含了節點是否結束和子節點）

代碼相對來說好理解：

//字典樹的java實現public class Trie {public class TrieNode {Map<Character, TrieNode> childdren;boolean wordEnd;public TrieNode() {childdren = new HashMap<Character, TrieNode>();wordEnd = false;}}private TrieNode root;public Trie() {root = new TrieNode();root.wordEnd = false;}public void insert(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) {Character c = new Character(word.charAt(i));if (!node.childdren.containsKey(c)) {node.childdren.put(c, new TrieNode());}node = node.childdren.get(c);}node.wordEnd = true;}public boolean search(String word) {TrieNode node = root;boolean found = true;for (int i = 0; i < word.length(); i++) {Character c = new Character(word.charAt(i));if (!node.childdren.containsKey(c)) {return false;}node = node.childdren.get(c);}return found && node.wordEnd;}public boolean startsWith(String prefix) {TrieNode node = root;boolean found = true;for (int i = 0; i < prefix.length(); i++) {Character c = new Character(prefix.charAt(i));if (!node.childdren.containsKey(c)) {return false;}node = node.childdren.get(c);}return found;}}}

?

?

?

?

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的力扣刷题心得（设计类题目）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。