2019年8月

分隔链表

问题描述

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

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

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list

思路

借助了两个vector。

  • 若是链表为空：直接返回nullptr即可。
  • 链表不为空：遍历链表的过程中，将节点值小于x的存到一个vector中，将值大于等于x的存到一个vector中。
  • 利用两个vector生成两个链表。

  • 根据不同情况将两个链表拼接起来。

    小于x的链表为空，那么返回大于x链表的头节点即可
    大于等于x的链表为空，那么返回小于x链表的头节点即可
    两个都不空，将大于等于x的链表拼接到小于x的链表的后面
    两个链表都为空，即链表为空，在最开始特判过了。

题解

class Solution {
public:
    vector<int> tmp1;
    vector<int> tmp2;
    ListNode *head1;
    ListNode *head2;
    ListNode *ret;
    ListNode *buildList(vector<int> vec, ListNode *&node) {
        int n = vec.size();
        ListNode *p = nullptr;
        for (int i = 0; i < n; i++) {
            if (p == nullptr) {
                p = new ListNode(vec[i]);
                node = p;
            } else {
                p->next = new ListNode(vec[i]);
                p = p->next;
            }
        }
        return node;
    }

    ListNode *partition(ListNode *head, int x) {
        if (head == nullptr)
            return nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            if (cur->val < x) tmp1.push_back(cur->val);
            else tmp2.push_back(cur->val);
            cur = cur->next;
        }
        int n1=tmp1.size();
        int n2 =tmp2.size();
        if(n1!=0) head1=buildList(tmp1,head1);
        if(n2!=0) head2=buildList(tmp2,head2);
        if(n1==0&&n2!=0) ret = head2;
        else if(n2==0&&n1!=0) ret =  head1;
        else {
            ListNode *tail=head1;
            while (tail->next!= nullptr){
                tail=tail->next;
            }
            tail->next=head2;
            ret = head1;
        }
        return ret;
    }
};

第k个排列

问题描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。

示例 1:
输入: n = 3, k = 3
输出: "213"

示例 2:
输入: n = 4, k = 9
输出: "2314"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-sequence

思路

逆康托展开
详细见 https://blog.csdn.net/wbin233/article/details/72998375，我感觉讲的挺详细的。

题解

class Solution {
public:
    vector<char> ch={'1','2','3','4','5','6','7','8','9'};
    vector<int> FAC={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
    string getPermutation(int n, int k) {
        string ret;
        k=k-1;//排名第k名，所以有k-1个排序比它小的
        for(k;n--;k%=FAC[n]){
            const int i=k/FAC[n];
            ret+=ch[i];
            ch.erase(ch.begin()+i);去除下标为i的元素。
        }
        return ret;
    }
};

简化路径

问题描述

\# 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：
输入："/a/./b/../../c/"
输出："/c"

示例 5：
输入："/a/../../b/../c//.//"
输出："/c"

示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplify-path

思路

基本思路是用栈来实现。返回值是ret，ret最开始为"/"

  • 单词之间是通过“/“来隔开的。
  • 如果两个”/“之间是".",那么continu；如果是“..",如果栈不为空的话，弹出顶端元素。如果是正常的字母组合，那么将压入栈中。
    此处应该注意，路径的最后不是以“/”结尾，所以应该在遍历结束后，单独进行判断
  • 最后，我用两个栈实现了双端队列，来将栈中的内容存储到ret中

题解

class Solution {
public:
    string simplifyPath(string path) {
        string ret="/";
        stack<string> stack1;
        string tmp = "";
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == '/') {
                if (tmp.size() == 0) {
                    continue;
                } else if (tmp == ".") {
                    tmp="";
                    continue;
                } else if (tmp == "..") {
                    tmp="";
                    if (!stack1.empty()) {
                        stack1.pop();
                    } else continue;
                } else{
                    stack1.push(tmp);
                    tmp="";
                }
            } else{
                tmp+=path[i];
            }
        }
        if(tmp==".."){
            if(!stack1.empty()) stack1.pop();
        } else if(tmp!="."&&tmp.size()!=0){
            stack1.push(tmp);
        }
        stack<string> stack2;
        while (!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        int flag=1;
        if(!stack2.empty()) flag=0;
        while (!stack2.empty()){
            ret+=stack2.top();
            stack2.pop();
            ret+="/";
        }
        if(flag==0) ret=ret.substr(0,ret.size()-1);
        return ret;
    }
};
  1. 1
  2. 2
  3. 3