LouYu – 第 10 页 – 娄禹的个人博客

LeetCode #71：Simplify Path(简化路径)

在 *nix 操作系统中，系统对当前目录的管理就是通过栈来实现的，本问题就是对这一过程的模拟。思路是先将 path 串根据 “/” 分割，再对分割出来的子串根据 “.” “..” 等规则进行操作。由于 C++ 的 string 没有原生的 split 函数，这里采用 stringstream 对象和 getline() 巧妙实现了这一功能。

LeetCode #347：Top K Frequent Elements(前K个高频元素)

本题的思路不难，先用 map 统计各个元素出现的频率，再用小顶堆（或大顶堆）找出频率前 k 的元素。在实现的过程中会涉及到对 C++ map、priority_queue、pair 等 STL 库的用法，之前对这块知识有些遗忘，特此记录。

LeetCode #150：Evaluate Reverse Polish Notation(后缀表达式求值)

逆波兰式，更为人所知的名字是 “后缀表达式”。所谓后缀就是指运算算符写在操作数后面，我们平时习惯的 “中缀表达式” 是将运算符写在两个操作数之间。由于计算机内部就是采用后缀表达式的算法来计算表达式的值，所以实现此算法有着很高的现实意义。

LeetCode #459：Repeated Substring Pattern(重复的子字符串)

本题依然是使用 KMP 算法中 next 数组（最长相等前后缀）来解决。设字符串长度为 n，根据 next 数组的定义，next[i] 记录的是字符串 s[0…n-1] 的子串 s[0…i] 最长相同前后缀的长度。根据这个定义，字符串 s 的最长相等前后缀的长度为 next[n – 1]。