簡化路徑的思路探討與原始碼
簡化路徑的題目如下圖，該題屬于堆疊和字串型別的題目，主要考察對于堆疊本身的理解和字串遍歷技巧的使用，本文的題目作者想到2種方法，分別是雙端佇列方法和堆疊方法，其中雙端佇列方法使用Java進行撰寫，而堆疊方法使用Python進行撰寫，當然這可能不是最優的解法，還希望各位大佬給出更快的演算法，
本人認為該題目可以使用雙端佇列方法，首先初始化一個雙端佇列，并且將輸入的字串根據“斜杠”分割轉化為陣列，然后開始遍歷陣列，并且判斷當前元素是否為慷訓者點，如果是就不操作；否則就判斷當前元素是否為".."，如果是就繼續判斷雙端佇列是否不為空，如果滿足就洗掉雙端佇列最后一個元素，否則就把元素添加到雙端佇列的尾部，遍歷結束后，開始遍歷雙端佇列，遍歷取出佇列頭部的元素后拼接“斜杠”得到結果字串，并且最后回傳結果，那么按照這個思路我們的Java代碼如下：
#噴火龍與水箭龜
class Solution {
public String simplifyPath(String path) {
Deque<String> doubleList = new LinkedList<>();
String[] arr = path.split("/");
for(int jr = 0; jr < arr.length; jr++){
String word = arr[jr];
if(word.equals("") || word.equals(".")){
continue;
}else if (word.equals("..")){
if(! doubleList.isEmpty()){
doubleList.pollLast();
}
}else{
doubleList.offer(word);
}
}
StringBuilder resFinal = new StringBuilder("/");
while(! doubleList.isEmpty()){
resFinal.append(doubleList.poll());
if(! doubleList.isEmpty()){
resFinal.append("/");
}
}
if(resFinal.toString().equals("")){
return "/";
}else{
return resFinal.toString();
}
}
}
顯然，我們看到雙端佇列的效果不錯，同時還可以使用堆疊方法進行處理，首先初始化一個串列作為堆疊，把字串按照“斜杠”進行分割得到陣列，然后開始遍歷陣列，如果堆疊不是空并且當前元素等于"..“那就把堆疊頂元素拋出，否則判斷元素是否屬于”.."如果是則插入到堆疊內，最后將堆疊轉化為以“斜杠”分割的字串并回傳結果，所以按照這個思路就可以解決，下面是Python代碼部分：
#噴火龍與水箭龜
class Solution:
def simplifyPath(self, path):
stackList = []
arr = path.split('/')
for jr in arr:
if stackList and jr == '..':
stackList.pop()
elif jr not in " ..":
stackList.append(jr)
resFinal = '/' + '/'.join(stackList)
return resFinal
從結果來說Java版本的雙端佇列方法的效率不錯，而Python版本的堆疊方法的速度也不錯，但應該是有更多的方法可以進一步提速的，希望朋友們能夠多多指教，非常感謝，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/333608.html
標籤：其他
下一篇：2021-10-22刷題總結