C++实现LeetCode(71.简化路径)

[LeetCode] 71.Simplify Path 简化路径

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

  • Did you consider the case where path = "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".

这道题让简化给定的路径,光根据题目中给的那一个例子还真不太好总结出规律,应该再加上两个例子 path = "/a/./b/../c/", => "/a/c"和path = "/a/./b/c/", => "/a/b/c", 这样我们就可以知道中间是"."的情况直接去掉,是".."时删掉它上面挨着的一个路径,而下面的边界条件给的一些情况中可以得知,如果是空的话返回"/",如果有多个"/"只保留一个。那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串,把它们分别提取出来一一处理即可,代码如下:

C++ 解法一:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> v;
        int i = 0;
        while (i < path.size()) {
            while (path[i] == '/' && i < path.size()) ++i;
            if (i == path.size()) break;
            int start = i;
            while (path[i] != '/' && i < path.size()) ++i;
            int end = i - 1;
            string s = path.substr(start, end - start + 1);
            if (s == "..") {
                if (!v.empty()) v.pop_back();
            } else if (s != ".") {
                v.push_back(s);
            }
        }
        if (v.empty()) return "/";
        string res;
        for (int i = 0; i < v.size(); ++i) {
            res += '/' + v[i];
        }
        return res;
    }
};

还有一种解法是利用了C语言中的函数strtok来分隔字符串,但是需要把string和char*类型相互转换,转换方法请猛戳这里。除了这块不同,其余的思想和上面那种解法相同,代码如下:

C 解法一:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> v;
        char *cstr = new char[path.length() + 1];
        strcpy(cstr, path.c_str());
        char *pch = strtok(cstr, "/");
        while (pch != NULL) {
            string p = string(pch);
            if (p == "..") {
                if (!v.empty()) v.pop_back();
            } else if (p != ".") {
                v.push_back(p);
            }
            pch = strtok(NULL, "/");
        }
        if (v.empty()) return "/";
        string res;
        for (int i = 0; i < v.size(); ++i) {
            res += '/' + v[i];
        }
        return res;
    }
};

C++中也有专门处理字符串的机制,我们可以使用stringstream来分隔字符串,然后对每一段分别处理,思路和上面的方法相似,参见代码如下:

C++ 解法二:

class Solution {
public:
    string simplifyPath(string path) {
        string res, t;
        stringstream ss(path);
        vector<string> v;
        while (getline(ss, t, '/')) {
            if (t == "" || t == ".") continue;
            if (t == ".." && !v.empty()) v.pop_back();
            else if (t != "..") v.push_back(t);
        }
        for (string s : v) res += "/" + s;
        return res.empty() ? "/" : res;
    }
};

Java 解法二:

public class Solution {
    public String simplifyPath(String path) {
        Stack<String> s = new Stack<>();
        String[] p = path.split("/");
        for (String t : p) {
            if (!s.isEmpty() && t.equals("..")) {
                s.pop();
            } else if (!t.equals(".") && !t.equals("") && !t.equals("..")) {
                s.push(t);
            }
        }
        List<String> list = new ArrayList(s);
        return "/" + String.join("/", list);
    }
}

到此这篇关于C++实现LeetCode(71.简化路径)的文章就介绍到这了,更多相关C++实现简化路径内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(62.不同的路径)

    [LeetCode] 62. Unique Paths 不同的路径 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner

  • C++实现LeetCode(67.二进制数相加)

    [LeetCode] 67. Add Binary 二进制数相加 Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: &q

  • C++实现LeetCode(189.旋转数组)

    [LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate

  • C++实现LeetCode(63.不同的路径之二)

    [LeetCode] 63. Unique Paths II 不同的路径之二 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right c

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • C++实现LeetCode(64.最小路径和)

    [LeetCode] 64. Minimum Path Sum 最小路径和 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in t

  • C++实现LeetCode(66.加一运算)

    [LeetCode] 66. Plus One 加一运算 Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the a

  • C++实现LeetCode(70.爬楼梯问题)

    [LeetCode] 70. Climbing Stairs 爬楼梯问题 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Examp

  • C++实现LeetCode(71.简化路径)

    [LeetCode] 71.Simplify Path 简化路径 Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" click to show corner cases. Corner Cases

  • C++实现LeetCode(113.二叉树路径之和之二)

    [LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22,  5 / \ 4   8 /      / \ 11  13  4 /  \         / \ 7  

  • Go Java算法之简化路径实例详解

    目录 简化路径 方法一:栈(Java) 方法二:标准库(Go) 简化路径 给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径. 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身:此外,两个点 (..) 表示将目录切换到上一级(指向父目录):两者都可以是复杂相对路径的组成部分. 任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' . 对于此问题,任何其他格式的点(例如,'...')均被视为文件/

  • vue.js项目中实用的小技巧汇总

    前言 Vue.js 是一套构建用户界面的 渐进式框架.与其他重量级框架不同的是,Vue 采用自底向上增量开发的设计.Vue 的核心库只关注视图层,并且非常容易学习,非常容易与其它库或已有项目整合.另一方面,Vue 完全有能力驱动采用单文件组件和 Vue 生态系统支持的库开发的复杂单页应用. # 在Vue 项目中引入Bootstrap 有时在vue项目中会根据需求引入Bootstrap,而Bootstrap又是依赖于jQuery的,在使用npm安装时,可能会出现一系列的错误 1.安装jQuery

  • Vue基础学习之项目整合及优化

    前言 使用 webpack 构建过 Vue 项目的同学应该知道 alias 的作用,我们可以使用它将复杂的文件路径定义成一个变量来访问.在不使用 alias 的项目中,我们引入文件的时候通常会去计算被引入文件对于引入它的文件的相对路径,比如像这样 import HelloWorld from '../../../../HelloWorld.vue' 一旦相对层次结构较深,我们就很难去定位所引入文件的具体位置,其实这并不是我们应该操心的地方,完全可以交给 webpack 来进行处理.在原生的 we

  • create-react-app开发常用配置教程

    目录 引言 设置代理 模块热替换(HMR) css局部化 支持装饰器写法 打包后路径问题导致页面空白 配置简化路径 按需引用antd-mobile(antd同) 打包构建分析 生产环境去掉map文件 配置less 配置不同环境变量 引言 注: 如未找到配置文件请使用npm run eject弹出配置文件 当前对应版本react 16.2 设置代理 在开发中往往是跨域请求的,配置一下请求代理可以解决这个问题 // package.json 文件 "proxy": "http:/

  • C++实现LeetCode(112.二叉树的路径和)

    [LeetCode] 112. Path Sum 二叉树的路径和 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below bi

随机推荐