Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCode40-я статья, давайте посмотрим на 71 вопрос Simplify Path в LeetCode, китайское название — упрощенный путь.
Сложность этого вопроса средняя, а проходной балл около 1/3.Это также вопрос с большим количеством голосов и несколькими похвалами.Всего 737 лайков и 1703 возражения. Честно говоря, я не считаю несправедливым противодействовать этому, я сначала продам его, а о том, почему его растоптали, я подробно расскажу позже.
смысл названия
Вопросу будет дана строка, представляющаяUnix-системаПуть к файлу ниже, этот путь будет содержать некоторые вычисления пути, требующие от нас возврата упрощенного результата.
Используйте / для разделения папок в системах Unix, например /home/download/file.txt. В этом пути поддерживаются простые операции, такие как .текущая папка. Поэтому, если наш текущий терминал находится в папке загрузки и мы хотим получить доступ к файлу file.txt, мы можем использовать относительный путь ./file.txt. В дополнение к этому, .. операции также включены. ..ВыражатьПапка над текущей папкой.
Например, если мы находимся в папке загрузки, при запуске cd.. мы вернемся на верхний уровень папки загрузки, которая является домашней папкой. Мы можем использовать .. и ., встроенные в путь к файлу. Например, /home/download/../download/file.txt также является допустимым.Поскольку мы вставляем .. в середине, он вернется на верхний уровень загрузки, который является домашним, а затем войдет в загрузку. Хотя это трудоемко, это законно. Используйте столько, сколько хотите.. Вернитесь на верхний уровень и перемещайтесь туда и обратно.
То, что мы возвращаем, этоУпрощенный вариант путиТо есть: /home/download/file.txt
Рассмотрим несколько случаев:
Input: "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name.Input: "/../" Output: "/" Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Input: "/a/../../b/../c//.//" Output: "/c"
отвечать
Этот вопрос на самом делешуточные вопросы, но это гораздо менее сложно, чем вопросы моделирования, которые мы задавали ранее. Идея этого вопроса вполне очевидна, из-за операций .. и . нам нужно записать путь доступа, и отбросить предыдущую папку, когда .. перемещается вверх.
Например, a/b/../b/d/e
Мы используем после b.. обратно к a, затем снова возвращаемся к b. очевидно здесьb появляется дважды в пути из-за .., что избыточно. Нам нужно отбросить b, когда .. вернуться на верхний уровень. Для операции ., поскольку она представляет текущий путь, она не влияет на ответ, мы можем просто игнорировать ее существование.
После понимания этой идеи реализация очень проста, нам нужно толькоСегментируйте строку в соответствии с /. Кроме .. и .. в каждом абзаце указано имя папки.Мы используем список для хранения папок, которые проходят сверху вниз.Когда ..встречается, последний добавленный элемент отбрасывается. Наконец, используйте / соедините их вместе, единственное, что нужно отметить, это то, что когда мы достигли верхнего уровня, если мы продолжим выполнение.. Он не сообщит об ошибке, но останется на месте. Так что нам нужно специально судить об этой ситуации, и кроме этого почти нет никакой трудности.
class Solution:
def simplifyPath(self, path: str) -> str:
folders = []
# 按照/分割
fs = path.split("/")
for f in fs:
# .直接跳过即可，不会影响结果
if f == '.':
continue
# 如果是..需要判断是否在顶层
# 不在顶层的话抛弃掉最后插入的文件夹
if f == '..':
if len(folders) > 0:
folders.pop()
elif f != '':
folders.append(f)
return '/' + '/'.join(folders)
Код очень простой, всего около 10 строк.
Суммировать
На этом часть о решении закончена.
Вернемся к вопросу в заголовке, почему я так себя чувствую? Это потому, что я задавал этот вопрос дважды, и в последний раз, когда я это делал, я использовал C++. так какСтроковый тип С++ не поддерживает разделение, поэтому мне нужно выполнить раздельную обработку самостоятельно. Весь процесс расчета намного сложнее, я поставил код AC C++, и все узнают его на ощупь, это не размерность.
class Solution {
public:
vector<string> split(string & path) {
vector<string> vt;
string cur = "";
// 遍历所有字符
for (int i = 0; i < path.length(); i++) {
// 如果是/ 说明需要把之前的内容放入vector
if (path[i] == '/') {
// 如果是空或者是.就跳过，因为.没有意义
if (cur != "" && cur != ".") {
vt.push_back(cur);
}
cur = "";
}else cur = cur + path[i];
}
// 要注意最后遗留的字符串
if (cur != "" && cur != ".") vt.push_back(cur);
return vt;
}
string simplifyPath(string path) {
vector<string> dirs = split(path);
string ret = "";
// 存储文件的结构
vector<string> paths;
for (string str : dirs) {
// 如果是.. 则返回上级
if (str == "..") {
if (paths.size() > 0) {
paths.pop_back();
}
// 否则则填入vector，表示合法
}else paths.push_back(str);
}
for (string str : paths) ret = ret + "/" + str;
if (ret == "") return "/";
return ret;
}
};
Я говорю это не для того, чтобы разглагольствовать о том, насколько отсталым является C++, или чтобы доказать, насколько мощным является Python. Естественно, что разные языки имеют разное происхождение и разные сильные стороны. Основная проблема в том, чтоНе должно быть такой огромной разницы из-за особенностей самого языка, если такая проблема возникнет в обычной игре, на нее точно будут лихорадочно жаловаться.
Например, в Java существует класс больших целых чисел BigInter, который можно использовать вместо высокоточной арифметики для обработки больших целых чисел за пределами диапазона int64. Если есть очень сложная задача с большими целыми числами, игроки, использующие Java, используют BigInter (Python, как правило, не допускается в соревнованиях по алгоритмам), и они могут легко выполнить AC с помощью трех или двух строк кода, в то время как игрокам на C++ нужны сотни строк кода. для достижения высокой точности расчетов, что явно несправедливо. Поэтому в конкурсе acm спрашивающий постарается избежать этой огромной разницы в языковых характеристиках, что, вероятно, является причиной того, что этот вопрос был взломан.
Эта статья здесь, если вам нравится эта статья, если вы можете, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.