71.简化路径

题目

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以'/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
  返回简化后得到的 规范路径 。

数据范围

• 1 <= path.length <= 3000
• path 由英文字母，数字，'.'，'/' 或 '_'组成。
• path 是一个有效的 Unix 风格绝对路径。

分析

用栈维护所有的路径，遇到".."就出栈，遇到"."就不动，其他入栈，注意点细节

代码

class Solution {
public:stack<string> stk;string simplifyPath(string path) {int j = path.size() - 1;while(path[j] == '/' && j > 0) j -- ;string tmp = "";int i = 0;while(path[i] == '/' && i < path.size()) i ++ ;path = path.substr(i, j - i + 1);for(i = 0; i < path.size(); i ++ ) {if(path[i] == '/') {print();int j = i;while(path[j] == '/' && j < path.size()) j ++ ;i = j - 1;if(tmp == ".." && !stk.size()) {tmp = "";continue;} else if(tmp == ".." && stk.size()) stk.pop();else if(tmp == ".") tmp = "";else stk.push(tmp);tmp = "";}else {tmp += path[i];}}if(tmp == ".." && stk.size() != 0) {stk.pop();} else if(tmp == ".." && stk.size() == 0) {return "/";} else if(tmp != ".") stk.push(tmp);vector<string> res;while(stk.size()) {res.push_back(stk.top());stk.pop();}reverse(res.begin(), res.end());string ans = "";for(auto k : res) {ans += "/" + k;}if(ans.size() == 0) return "/";return ans;}
};

---

86. 分隔链表

题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

数据范围

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

分析

用两个链表存小于x的数和大于等于x的数，最后合并

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* h1 = new ListNode(0);ListNode* h2 = new ListNode(0);auto tmph1 = h1, tmph2 = h2;ListNode* p1, *p2, *q;q = head;int cnt = 0;while(q != NULL) {cnt ++ ;if(q -> val < x) {tmph1 -> next = q;tmph1 = q;} else {tmph2 -> next = q;tmph2 = q;}q = q -> next;}tmph1 -> next = h2 -> next;tmph1 = h1;while(tmph1 != NULL && cnt) {cnt -- ;tmph1 = tmph1 -> next;}tmph1 -> next = NULL;return h1 -> next;}
};