算法题汇总：其二

整数转罗马数字

个人提交

提交内容

class Solution
{
public:
    string result;
    string intToRoman(int num)
    {
        int n, i = 0;
        while (num)
        {
            n = num % 10;
            num /= 10;

            temp(i, n);
            i++;
        }
        reverse(result.begin(), result.end());
        return result;
    }

private:
    unordered_map<int, string> map{
        {1, "I"},
        {5, "V"},
        {10, "X"},
        {50, "L"},
        {100, "C"},
        {500, "D"},
        {1000, "M"},
    };

    int times(int index)
    {
        int temp = 1;
        for (int i = 0; i < index; i++)
            temp *= 10;
        return temp;
    }

    void temp(int i, int n)
    {
        if (n <= 3)
            for (int j = 0; j < n; j++)
                result.append(map[times(i)]);
        else if (n == 4)
            result.append(map[5 * times(i)]).append(map[times(i)]);
        else if (n > 4 && n < 9)
        {

            for (int j = 0; j < n - 5; j++)
                result.append(map[times(i)]);
            result.append(map[5 * times(i)]);
        }
        else
            result.append(map[times(i + 1)]).append(map[times(i)]);
    }
};

调试用

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    Solution solution;
    cin >> n;
    cout << solution.intToRoman(n) << endl;
    return 0;
}

思路

• 将罗马数字转化成数字比较简单，那么反过来呢？前者需要考虑是否存在前面数字相减的问题，而后者只需要逐位读取数据，然后进行对应就好。
• 在public部分的函数，主要用于获取每一位的数据及其位数；后面的temp函数则是将获取的数据和位数与unordered_map中的罗马字符进行对应；times用于乘上位数。
• 由于数据从个位开始处理，字符串中最低位也依此压入了最先的位置，需要在reverse()后才是正常的语序。
• temp是最复杂的部分。用于对不同的数据压入不同的罗马字符。具有重复字符时，该函数会进行循环压入，在遇到4字头或9字头时，会进行特殊处理。
• 但可以看到，该方法需要多次进行循环和函数调用，效率并不高，仅击败了16%的人。

题解

以下来源于力扣官方题解

模拟法

可以利用贪心算法的思想，通过选择最大的符号值来进行操作。为了表示一个给定的整数$num$，我们寻找不超过$num$的最大符号值，将$num$减去该符号值，然后继续寻找不超过$num$的最大符号值，将该符号拼接在上一个找到的符号之后，循环直至$num$为 0。最后得到的字符串即为$num$的罗马数字表示。

const pair<int, string> valueSymbols[] = {
    {1000, "M"},
    {900,  "CM"},
    {500,  "D"},
    {400,  "CD"},
    {100,  "C"},
    {90,   "XC"},
    {50,   "L"},
    {40,   "XL"},
    {10,   "X"},
    {9,    "IX"},
    {5,    "V"},
    {4,    "IV"},
    {1,    "I"},
};
class Solution {
public:
    string intToRoman(int num) {
        string roman;
        for (const auto &[value, symbol] : valueSymbols) {
            while (num >= value) {
                num -= value;
                roman += symbol;
            }
            if (num == 0) {
                break;
            }
        }
        return roman;
    }
};

硬编码法

与我的思路相似，也是观察到只需要处理每一位数字的特点。但其直接暴力匹配。

const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[]      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

class Solution {
public:
    string intToRoman(int num) {
        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }
};

简化路径

个人提交

提交内容

class Solution
{
public:
    string simplifyPath(string path)
    {
        string temp, result = "/";
        for (auto it = path.begin() + 1; it != path.end(); ++it)
        {
            if (*it != '/')
                temp.push_back(*it);
            else
            {
                name.push(temp);
                temp.clear();
            }
        }
        name.push(temp);
        while (!name.empty())
        {
            temp = name.top();
            if (temp == "" || temp == ".")
                name.pop();
            else if (temp == "..")
            {
                while (!name.empty() && name.top() == "..")
                {
                    name.pop();
                    del++;
                }
                for (; del > 0 && !name.empty(); del--)
                {
                    if (name.top() == "" || name.top() == ".")
                    {
                        del++;
                        name.pop();
                    }else if(name.top() == ".."){
                        del += 2;
                        name.pop();
                    }
                    else
                    name.pop();
                }
            }
            else
            {
                s.push(temp);
                name.pop();
            }
        }
        while (!s.empty())
        {
            result.append(s.top() + "/");
            s.pop();
        }
        if (result.size() != 1)
            result.pop_back();
        return result;
    }

private:
    stack<string> name;
    stack<string> s;
    int del = 0;
};

调试用

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    Solution solution;
    cin >> s;
    cout << solution.simplifyPath(s) << endl;
    return 0;
}

思路

• 该代码是经过多次报错后，多次修改所成的样子，整体非常繁杂。
• 首先，通过迭代器，将字符串中的名字逐一弹进栈中。迭代器逐字符迭代，当遇到/时，将temp中的内容弹进去。否则将迭代器所指的字符弹进temp中。最后达到去除/的效果。
• 接着逐一弹出，过滤需要简化的字符，名字保存到另一个栈s中（如果直接放进字符串会让目录反过来）。
  1. ""和"."直接弹出。
  2. 名字和"..."保留。
  3. ".."的处理比较复杂，出的错也最多：另立一个计数器进行循环，计数器一直计算".."的个数，并向上弹出数据。对于第一种数据计数器不变（即后面再+1）；第二种数据计数器-1（不做处理）；第三种数据计数器+1（后面+2）。
• 一切操作都建立在栈不为空的情况，一旦栈为空，处理提前结束。
• 最后将s栈中的数据弹进字符串中，同时加入/。
• 最后的时间复杂度为$O(n)$，击败了50%的人。

题解

来源为力扣官方题解。
思路大差不差。但官方先利用自己写的split()函数将字符串拆成vector进行操作 （Java都不用自己写）。而这个split函数有许多可以玩味的地方。

class Solution {
public:
    string simplifyPath(string path) {
        auto split = [](const string& s, char delim) -> vector<string> {
            vector<string> ans;
            string cur;
            for (char ch: s) {
                if (ch == delim) {
                    ans.push_back(move(cur));
                    cur.clear();
                }
                else {
                    cur += ch;
                }
            }
            ans.push_back(move(cur));
            return ans;
        };

        vector<string> names = split(path, '/');
        vector<string> stack;
        for (string& name: names) {
            if (name == "..") {
                if (!stack.empty()) {
                    stack.pop_back();
                }
            }
            else if (!name.empty() && name != ".") {
                stack.push_back(move(name));
            }
        }
        string ans;
        if (stack.empty()) {
            ans = "/";
        }
        else {
            for (string& name: stack) {
                ans += "/" + move(name);
            }
        }
        return ans;
    }
};