今天在LeetCode刷每日一题,遇到了388. 文件的最长绝对路径的思路,这道题让我想到了系统的目录是栈结构,果然在题解中找到了栈的解法(暴力半天没出来,跑去看题解了QWQ)。 所以我就
今天在LeetCode刷每日一题,遇到了388. 文件的最长绝对路径的思路,这道题让我想到了系统的目录是栈结构,果然在题解中找到了栈的解法(暴力半天没出来,跑去看题解了QWQ)。
所以我就捎带复习了一下go语言中栈的实现,然后把这道题给理解一下
-
较为简单的实现(通过切片和内置函数)
func main() { // int类型的栈 stack := make([]int,10) // 压栈 eg.压入1 stack = append(stack,1) // 出栈 stack = stack(:len(stack)-1) }
-
看到网上一种。
使用list(双链表)的部分操作就可以达到stack操作的目的 转自 寇浩哲
stack := list.New() //初始化栈 ind := stack.Remove(stack.Front()).(int) //出栈 stack.PushFront(i) //入栈 fmt.Println(stack.Front().Value)
-
为什么要用栈呢?
因为题目的目录是层级关系,如果遍历到某个目录的最后也没找到文件,肯定要返回到上一级去找另一个目录 -
/t的多少就是当前目录的层级
-
其他操作在注释里很详细了,就不再赘述
func lengthLongestPath(input string) int { stack := []int{} l := len(input) ans := 0 for i := 0;i < l;i++ { index := 1 // 遇到/t遍历有几个/t 增加深度(一个/t相当于一级目录) for ;i < l&& input[i] == '\t';i++ { index++ } length := 0 isExt := 0 // 遍历当前目录长度 for ;i < l&& input[i] != '\n';i++{ if input[i] == '.' { isExt = 1 } length++ } // 如果当前深度小于栈里的目录级数,说明栈里的目录已经到底了,需要退栈 for index <= len(stack) { stack = stack[:len(stack)-1] } // 如果不是第一级目录,那么就要多算一个/的长度,同时要把上一级的长度加到length里 if len(stack) > 0{ length += stack[len(stack)-1] + 1 } //如果isExt == 1 说明已经找到文件,判断一下是不是最长的,如果不等于,把当前目录长度给压栈里,方便下一次加到length里 if isExt == 1{ ans = max(ans,length) }else { stack = append(stack,length) } } return ans } func max(a int,b int) int { if a > b { return a }else { return b } }