第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;
    }
};

水壶问题

问题描述

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的z升水。

你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True

示例 2:
输入: x = 2, y = 6, z = 5
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/water-and-jug-problem

思路

满足题意需要有z=x+y;
如果z=ax+by（a，b均整），x与y最大公约数为g，那么z一定是g的整数倍，即z%g=0;
需要注意的是，g不能为0，所以，x==0&&y==0这一种情况需要特判。

题解

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x==0&&y==0) return z==x;
        return z%gcd(x,y)==0&&(x+y>=z);
    }
    int gcd(int x,int y){
        return y?gcd(y,x%y):x;
    }
};