每日题目-1.6：每日一题+49+50

1. 每日一题71. 简化路径

题目

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

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

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

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

示例 1：

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

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

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

输入：path = "/a/./b/../../c/"
输出："/c"
 

提示：

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

思路

模拟。
s一开始结尾若没有'/'要加一个。
用name存储目录名称。
分三种情况，一是普通目录，直接加到ans结尾并加上'/'。二是name为".."，这时先删去'/'，再删去上一级目录，一和二都要清空name。三是为"."或为空，此时直接清空name并continue。
最后要删除结尾多余的'/'即可得到答案。

复杂度

整个字符串之遍历一次且删除时删除的是字符串的子集，因此总的空间时间复杂度为o(n)。

代码

class Solution {
public:
    string simplifyPath(string s) {
        int n = s.size();
        string ans, name;
        if(s[n - 1] != '/') s += '/', n++;
        for(int i = 0; i < n; i++){
            if(ans.empty()) ans += s[i];
            else if(s[i] != '/') name += s[i];
            else{
                // 返回上一级
                if(name == ".."){
                    if(ans.size() > 1){
                        // string也可以pop
                        // 先除去'/'
                        ans.pop_back();
                        // 除去上一级的路径
                        while(ans.back() != '/') ans.pop_back();
                    }
                    name = "";
                }
                // 位置不变或者有重复'/'的情况
                else if(name == "." || name.empty()){
                    name = "";
                    continue;
                }
                else{
                    ans += name;
                    ans += '/';
                    name = "";
                }
            }
        }
        if(ans.size() > 1 && ans.back() == '/') ans.pop_back();
        return ans;
    }
};

2. 49. 字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

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

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]
 

提示：

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路

遍历并对每个元素的每个字符排序成为排好序的字符串，开个>型的哈希表，将排好序的字符串作为哈希表的第一映射。
各个字符异形词排序后的字符串是相同的，因此直接插入对应的vector当中即可。
还要提高速率的方法时本来插入时需要将整个字符串copy过去，但使用move之后只需要把字符串的首地址赋值过去，可以减少一次拷贝操作，提高效率。

代码

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        vector> ans;
        if(strs.empty()) return ans;
        unordered_map> ma;
        for(int i = 0; i < strs.size(); i++){
            string s = strs[i];
            sort(s.begin(), s.end());
            // 直接拷贝
            // ma[s].push_back(strs[i]);

            // 本来需要将整个字符串copy过去，使用move之后只需要把字符串的首地址赋值过去，可以减少一次拷贝操作，提高效率
            ma[s].push_back(move(strs[i]));
        }
        for(auto& i: ma){
            // 直接拷贝
            // ans.push_back(i.second);
            
            ans.push_back(move(i.second));
        }
        return ans;
    }
};

3. 50. Pow(x, n)

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2^-2 = 1/2^2 = 1/4 = 0.25

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4

思路

快速幂+特判负数最大的情况。

代码

class Solution {
public:
    double myPow(double x, int nn) {
        if(x == 1 || nn == 0) return 1;
        typedef long long ll;
        double ans = 1;
        // 负数取到2^-31时防止溢出转成long long
        ll n = abs(ll(nn));
        while(n){
            if(n & 1) ans *= x;
            x *= x;
            n >>= 1;
        }
        if(nn < 0) return 1 / ans;
        return ans;
    }
};