解法) + 解题思路 + 技巧总结 201604"/>
CCF 路径解析 满分代码(两种解法) + 解题思路 + 技巧总结 201604
题目描述
解题思路
数据范围很小,只需要考虑暴力模拟实现
将不规范的路径规范化,就是需要使路径没有 ‘.’ 、没有多余的 ‘/’
(代码实现1是用workmore函数对读入的串先进行去除多余/,在workpoint函数里边将字符串根据/进行划分,边处理./…问题)
(代码实现2是在get函数里边将字符串根据/进行划分,边处理多余/问题, 用order函数处理./…问题)
路径的存储可以利用substr将用/分隔的部分存储到vector数组或者stack中(方便…操作的弹出)
路径分为绝对路径和相对路径
如果是绝对路径,就是根据给出的文件路径处理
如果是相对路径,需要在遍历时加上初始的当前目录,以便返回上一级
'.'表示当前目录,则不处理,跳过
'…'表示返回上一级,则将存储路径的vector数组进行popback()或者stack的pop()
其余的pushback() / push到路径数组后
最后将保存的路径输出就是答案
代码实现1
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <stack>using namespace std;stack <string> cur;stack <string> work(string str) //正规化路径
{stack <string> res;res.push("/");for (int i = 1; i < str.size(); i ++){int j = i;string t;while (j < str.size() && str[j] != '/') t += str[j ++];res.push(t);i = j;}return res;
}void workmore(string &str) //去除多余的/
{string t;for (int i = 0; i < str.size(); i ++){if (str[i] != '/' || i == 0) t += str[i];else if (i > 0 && str[i - 1] != '/') t += str[i];}str = t;
}void workpoint(stack <string> &res, string str)
{//cout << str;for (int i = 1; i < str.size(); i ++){int j = i;string t;while (j < str.size() && str[j] != '/') t += str[j ++];i = j;if (t == ".") continue;else if (t == ".."){if (res.size() > 1) res.pop();}else res.push(t);}
}void print(stack <string> t)
{if (t.size() == 1){cout << "/" << endl;return ;}vector <string> res;int cnt = 0;while (t.size() > 1){res.push_back(t.top());t.pop();cnt ++;}for (int i = cnt - 1; i >= 0; i --){cout << "/" << res[i];}cout << endl;
}int main()
{int n;cin >> n;string str;cin >> str;cur = work(str);getchar();while (n --){str = ""; //要想读取str等于空的情况,必须每次读取前清空strstack <string> res;getline(cin, str);if (str == "") //路径为空字符串{print(cur);continue;}workmore(str); //去除多余/if (str[0] == '/') //绝对路径{res.push("/");}else //相对路径,还是那个老毛病,题目中说的是不以/开头,但是不代表一定像样例一样以点开头,{ //当样例过不了的时候,一定再仔细看题,思考它的逻辑,肯定是某个方面理解错了,或者范围想小了//千万不要被样例所迷惑,其他测试样例可能还有很多情况res = cur;str.insert(0, "/"); //将相对路径前加一个/,和绝对路径统一格式,因为res里面已经保存了当前位置//所以也可以将当看成是绝对路径进行处理}workpoint(res, str); //去除内部点号print(res); //输出答案}return 0;
}
代码实现2
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;vector <string> get(string str) //将字符串以/为分隔存入vector数组中
{vector <string> res;for (int i = 0; i < str.size(); i ++){if (str[i] == '/') continue;int j = i + 1;while (j < str.size() && str[j] != '/') j ++;res.push_back(str.substr(i, j - i));i = j;}return res;
}void order(vector <string> cur, vector <string> path) //遍历给出的文件路径
{for (auto p : path){if (p == ".") continue; //表示当前目录,跳过不处理if (p == "..") //表示返回上一目录{if (cur.size()) //若当前目录不为空{cur.pop_back(); // 则返回上一目录,否则跳过不处理}}else{cur.push_back(p); // 如果是其他的,则遍历,假如当前目录}}if (cur.empty()) //如果遍历完,当前目录为空,只需要输出根目录{puts("/");return ;}for (auto s : cur) //如果路径不为空,则输出{cout << '/' << s;}cout << endl;return ;
}int main()
{int n;string str;cin >> n >> str;auto cur = get(str);vector <string> bn;getchar(); //使用getline前用了cin,需要用getchar过滤回车while (n --){vector <string> path;getline(cin, str); //由于cin无法读入空串,所以使用getline读入path = get(str);if (str.size() && str[0] == '/') order(bn, path); //遍历绝对路径else order(cur, path); //遍历相对路径}return 0;
}
技巧总结
- str.substr(i, j)可以从str下标为i的位置截取长度为j的字符串
- vector数组可以模拟栈,利用popback 和 pushback
- str.insert(i, “abc”)可以从str下标为i的位置插入字符串abc,记得此处只能插入字符串,要用双引号
更多推荐
CCF 路径解析 满分代码(两种解法) + 解题思路 + 技巧总结 201604
发布评论