分隔链表

问题描述

给定一个链表和一个特定值 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;
    }
};

字母异位词分组

问题描述

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

说明:
所有输入均为小写字母。
不考虑答案输出的顺序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/group-anagrams

思路

使用map映射

  • 如果单词是异位词,那么他们本身对sort排序后,应该相同的。
  • 所以,异位词会在同一个k的映射下(不知道这种表述对不对,大概是这个意思...)

    `map<string, vector<string>> table`
    比如,eat排序后为aet,tea排序后也为aet,所以,aet对应eat,aet也对应tea。
    
  • 将结果存到vector<vector<string>> ret即可。

题解

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        vector<vector<string>> ret;
        map<string, vector<string>> table;
        for (const string &str : strs) {
            string buf = str;
            sort(buf.begin(), buf.end());
            table[buf].push_back(str);
        }
        for (const auto &each : table) {
            ret.push_back(each.second);
        }
        return ret;
    }
};

给单链表加一

问题描述

你可以假设这个整数除了 0 本身,没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:
输入: [1,2,3]
输出: [1,2,4]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/plus-one-linked-list

思路

从链表的最后一个节点开始,找到第一个不为9的位置

  • 如果整个链表都为9,那么将原链表的节点的值都置为0,并在链表前加一个值为1的节点。
  • 如果链表存在不为9的节点,该节点前边的节点值不变,该节点的值+1,该节点后边的值置为0。

题解

class Solution {
public:
    ListNode *plusOne(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        int location = -1;
        for (int i = vec.size() - 1; i >= 0; i--) {
            if (vec[i] != 9) {
                location = i;
                break;
            }
        }
        if (location == -1) {
            ListNode *tmphead = new ListNode(1);
            ListNode *tmp = head;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
            tmphead->next = head;
            head = tmphead;
        } else {
            ListNode *tmp = head;
            int count = 0;
            while (count <location) {
                tmp = tmp->next;
                count++;
            }
            tmp->val = tmp->val + 1;
            tmp = tmp->next;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
        }

        return head;
    }
};