LC388.文件的最长路径

原题链接
image.png

思路1：哈希表模拟

  • 哈希表<int, int> ump，key代表当前深度level，value从第0层到第level层深度的总长度。
  • 每个文件一定是衔接最近的上级目录，所以当前层次文件或者目录长度ump[level] = ump[level - 1] + cur_len。
  • 如果是文件，那么就进行比较max_len = max(max_len, ump[level]
  • 本质上是利用了哈希表的不重复性，可以保证上级目录长度一定是当前文件需要的那一个。

  • 如何去确定level和当前文件长度cur_len，不复杂，但是容易乱。在数组里面跑来跑去是我的短板，这种题目需要多练习。

    代码1：

    1. class Solution {
    2. public:
    3.   int lengthLongestPath(string input) {
    4.       // ump[i] = len 从第0层到第i层，累计的长度
    5.       unordered_map<int, int> ump;
    6.       vector<string> res;
    7.       int max_len = 0;
    8.       bool is_file = false;
    9.       for (int i = 0, ns = input.size(); i < ns; ) {
    10.           // 读掉前面的转义符
    11.           int k = i;
    12.           if (input[k] == '\n') {
    13.               k++;
    14.           }
    16.           int level = 0;
    17.           while (k < ns && input[k] == '\t') {
    18.               k++;
    19.               level += 1;
    20.           }
    22.           int cur_len = 0;
    23.           int rec = k;
    25.           // 读目录或者文件的长度class Solution {
    26. public:
    27.   int lengthLongestPath(string input) {
    28.       // ump[i] = len 从第0层到第i层，累计的长度
    29.       unordered_map<int, int> ump;
    30.       vector<string> res;
    31.       int max_len = 0;
    32.       bool is_file = false;
    33.       for (int i = 0, ns = input.size(); i < ns; ) {
    34.           // 读掉前面的转义符
    35.           int k = i;
    36.           if (input[k] == '\n') {
    37.               k++;
    38.           }
    40.           int level = 0;
    41.           while (k < ns && input[k] == '\t') {
    42.               k++;
    43.               level += 1;
    44.           }
    46.           int cur_len = 0;
    47.           int rec = k;
    49.           // 读目录或者文件的长度
    50.           is_file = false;
    51.           while (k < ns && input[k] != '\n') {
    52.               k++;
    53.               if (input[k] == '.') {
    54.                   is_file = true;
    55.               }
    56.               cur_len += 1;
    57.           }
    59.           ump[level] = ump[level - 1] + cur_len;
    60.           // cout << level << " " << input.substr(rec, cur_len) << endl;
    61.           if (is_file) {
    62.               max_len = max(max_len, ump[level] + level);
    63.           }
    65.           i = k;
    66.       }
    68.       return is_file ? max_len : 0;
    69.   }
    70. };
    71.           is_file = false;
    72.           while (k < ns && input[k] != '\n') {
    73.               k++;
    74.               if (input[k] == '.') {
    75.                   is_file = true;
    76.               }
    77.               cur_len += 1;
    78.           }
    80.           ump[level] = ump[level - 1] + cur_len;
    81.           // cout << level << " " << input.substr(rec, cur_len) << endl;
    82.           if (is_file) {
    83.               max_len = max(max_len, ump[level] + level);
    84.           }
    86.           i = k;
    87.       }
    89.       return is_file ? max_len : 0;
    90.   }
    91. };

    思路2： 栈模拟

  • 依然需要读取所有目录和文件的深度level和当前长度cur_len

  • 如果当前入栈文件或目录深度level大于栈顶level，那么直接入栈，否则，需要持续弹栈，直到level小于栈顶level

    代码2：

    1. class Solution {
    2. public:
    3.   int lengthLongestPath(string input) {
    4.       int ns = input.size();
    5.       stack<pair<int, int>> sta;
    6.       int max_len = 0;
    7.       bool is_file = false;
    8.       for (int i = 0; i < ns;) {
    9.           if (input[i] == '\n') {
    10.               i++;
    11.           }
    13.           int level = 0;
    14.           while (i < ns && input[i] == '\t') {
    15.               i++;
    16.               level += 1;
    17.           }
    19.           // 读取文件长度
    20.           int begin_pos = i;
    21.           int cur_len = 0;
    22.           is_file = false;
    23.           while (i < ns && input[i] != '\n') {
    24.               if (input[i] == '.') {
    25.                   is_file = true;
    26.               }
    27.               i++;
    28.               cur_len += 1;
    29.           }
    31.           while (!sta.empty() && level <= sta.top().first) {
    32.               sta.pop();
    33.           }
    35.           if (sta.empty() || level > sta.top().first) {
    36.               int prev_len = (sta.empty() ? 0: sta.top().second);
    37.               sta.push({level, cur_len + prev_len});
    38.               if (is_file) {
    39.                   max_len = max(max_len, cur_len + prev_len + level);
    40.               }
    41.           } 
    42.       }
    44.       return (is_file ? max_len : 0);
    45.   }
    46. };class Solution {
    47. public:
    48.   int lengthLongestPath(string input) {
    49.       int ns = input.size();
    50.       stack<pair<int, int>> sta;
    51.       int max_len = 0;
    52.       bool is_file = false;
    53.       for (int i = 0; i < ns;) {
    54.           if (input[i] == '\n') {
    55.               i++;
    56.           }
    58.           int level = 0;
    59.           while (i < ns && input[i] == '\t') {
    60.               i++;
    61.               level += 1;
    62.           }
    64.           // 读取文件长度
    65.           int begin_pos = i;
    66.           int cur_len = 0;
    67.           is_file = false;
    68.           while (i < ns && input[i] != '\n') {
    69.               if (input[i] == '.') {
    70.                   is_file = true;
    71.               }
    72.               i++;
    73.               cur_len += 1;
    74.           }
    76.           while (!sta.empty() && level <= sta.top().first) {
    77.               sta.pop();
    78.           }
    80.           if (sta.empty() || level > sta.top().first) {
    81.               int prev_len = (sta.empty() ? 0: sta.top().second);
    82.               sta.push({level, cur_len + prev_len});
    83.               if (is_file) {
    84.                   max_len = max(max_len, cur_len + prev_len + level);
    85.               }
    86.           } 
    87.       }
    89.       return (is_file ? max_len : 0);
    90.   }
    91. };