当前位置 : 主页 > 编程语言 > 其它开发 >

栈在go语言中实现,及解决388.文件的最长绝对路径的思路

来源:互联网 收集:自由互联 发布时间:2022-05-30
今天在LeetCode刷每日一题,遇到了388. 文件的最长绝对路径的思路,这道题让我想到了系统的目录是栈结构,果然在题解中找到了栈的解法(暴力半天没出来,跑去看题解了QWQ)。 所以我就

今天在LeetCode刷每日一题,遇到了388. 文件的最长绝对路径的思路,这道题让我想到了系统的目录是栈结构,果然在题解中找到了栈的解法(暴力半天没出来,跑去看题解了QWQ)。
所以我就捎带复习了一下go语言中栈的实现,然后把这道题给理解一下

go语言栈的实现
  1. 较为简单的实现(通过切片和内置函数)

     func main() {
       // int类型的栈
       stack := make([]int,10)
       // 压栈 eg.压入1
       stack = append(stack,1)
       // 出栈
       stack = stack(:len(stack)-1)
     }
    
  2. 看到网上一种。

    使用list(双链表)的部分操作就可以达到stack操作的目的 转自 寇浩哲

       stack := list.New() //初始化栈
       ind := stack.Remove(stack.Front()).(int) //出栈
       stack.PushFront(i) //入栈
       fmt.Println(stack.Front().Value)
    
388. 文件的最长绝对路径的思路 题解
  1. 为什么要用栈呢?
    因为题目的目录是层级关系,如果遍历到某个目录的最后也没找到文件,肯定要返回到上一级去找另一个目录

  2. /t的多少就是当前目录的层级

  3. 其他操作在注释里很详细了,就不再赘述

     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
         }
     }
【文章原创作者:美国服务器 https://www.68idc.cn处的文章,转载请说明出处】
上一篇:【理论积累】如何度过试用期【第一版】
下一篇:没有了
网友评论