LeetCode71

题目

71. 简化路径 

思路

说实话 最开始没看懂题目什么意思，去看了题解根据“遇到..弹出栈顶元素” 思想写出代码，使用栈来装目录名称，最后所有元素出栈时与文件路径顺序是相反的；因此考虑使用双端队列来实现栈，最后从另一端取出元素，就可以得到与文件路径一致的顺序；

代码

public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        // 按/分割目录所在路径
        String[] subString = path.split("/");
        for(int i = 0; i < subString.length; i ++){
            if(subString[i].equals("") || subString[i].equals(".")){
                // 空字符串
                continue;
            }
            if(subString[i].equals("..")){
                // ..且栈不为空时 弹出栈顶元素
                if(!stack.isEmpty()){
                    stack.pollLast();
                }
            }
            else{
                stack.offerLast(subString[i]);
            }
        }
        StringBuilder re = new StringBuilder();
        if(stack.isEmpty()){
            // 为空 只返回根目录
            re.append("/");
        }else{
            while(!stack.isEmpty()){
                re.append("/");
                // 从另一端取出元素 先进去的目录先出来 保持顺序
                re.append(stack.pollFirst());
            }
        }
        return re.toString();
    }

 Tips：双端队列yyds 可以用来实现栈、队列。

题目

 102. 二叉树的层序遍历

思路

 树的广度优先遍历都可以用两个队列+两层循环进行解决；

代码

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> re = new ArrayList<>();
        // 使用两个队列来实现
        if(root == null){
            return re;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> tempNodeList = new ArrayList<>();
            Queue<TreeNode> tempQueue = new LinkedList<>();
            // 遍历其子节点
            TreeNode tempNode = queue.poll();
            while(tempNode != null){
                // 加入这一层节点的值
                tempNodeList.add(tempNode.val);
                if(tempNode.left != null){
                    tempQueue.add(tempNode.left);
                }
                if(tempNode.right != null){
                    tempQueue.add(tempNode.right);
                }
                tempNode = queue.poll();
            }
            // 更新每一层节点的val
            re.add(tempNodeList);
            queue = tempQueue;
        }
        return re;
    }