2022-10-21-安贤量化-1h-量化工程师

正式入职的也需要先实习3个月，可以不用考虑了

力扣周赛内推的

实现一个python里的字典

1.要求

• 定义 SlashDict class，当key中包含斜杠(/)时，把相应的元素视作递归的字典把key按/分割后逐级查询
• 该 class 需至少支持 dict的get，pop方法以及插入操作。(如用python作答，该class 行为需要尽可能接近系统内置dict)
• dict插入key时若包含/，则逐级创建字典并插入相应的key/value
  ·定义deep keys()方法，返回的 key所对应的value 如包含dict，则递归获取它的key直到到最后一级，中间各级的key用/连接

2.示例

>>> sd = SlashDict({'a': {'b': {'c': {'x': 1. 'y': 2}},'d': 3},'e

>>> sd['a/b/c']
SlashDict({'x': 1, 'y': 2})>>> sd['a/b/d']
3
>>> sd['a/b/k']
KeyError: Dict under key 'a/b' does not have key 'k'
>>> sd.pop('a/b/c/y')
2
>>> sd['e/f/g'] = 5>>> sd
SlashDict({'a': {'b': {'c': {'x': 1}},'d': 3},'e': {'f':{'g': 5}}
>>> list(sd.deep_keys(())
['a/b/c/x','a/b/d', 'e/f/g']

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <exception>
#include <functional>
class SlashDict
{
    std::map<std::string, SlashDict> dic;
    int value;
public:
    SlashDict():value(-1){}

    int getValue(){return value;}

    void insert(std::string s, int v)
    {
        SlashDict *sd = this;
        int i = 0, j = 0;
        for (i = 0, j = 0; j <= s.length(); j++)
        {
            if (s[j] == '/' || j == s.length())
            {
                if (i == j)
                { // 连续 /
                    i = j + 1;
                    continue;
                }
                std::string k = s.substr(i, j - i);
                sd = &sd->dic[k];
                sd->value=-1;
                i = j + 1;
            }
        }
        sd->value = v;
    }

    SlashDict get(std::string s)
    {
        SlashDict *sd = this;
        int i = 0, j = 0;
        try
        {
            for (i = 0, j = 0; j <= s.length(); j++)
            {
                if (s[j] == '/' || j == s.length())
                {
                    if (i == j)
                    { // 连续 /
                        i = j + 1;
                        continue;
                    }
                    std::string k = s.substr(i, j - i);
                    if (sd->dic.count(k))
                    {
                        sd = &sd->dic[k];
                    }
                    else
                    {
                        throw std::exception();
                    }
                    i = j + 1;
                }
            }
        }
        catch (std::exception &e)
        {
            std::cout << "KeyError: Dict under key '" << s.substr(0, i-1) << "' does not have key 'k'" << std::endl;
        }
        return *sd;
    }

    SlashDict pop(std::string s)
    {
        SlashDict *sd = this;
        SlashDict res;
        int i = 0, j = 0;
        for (i = 0, j = 0; j <= s.length(); j++)
        {
            if (s[j] == '/' || j == s.length())
            {
                if (i == j)
                { // 连续 /
                    i = j + 1;
                    continue;
                }
                std::string k = s.substr(i, j - i);
                if (sd->dic.count(k))
                {
                    if (j == s.length())
                    {
                        res = sd->dic[k];
                        sd->dic.erase(k);
                    }
                    else
                        sd = &sd->dic[k]; // 可记录每个sd，dic.size()==0时可回溯
                }
                i = j + 1;
            }
        }
        return res;
    }

    std::vector<std::string> deep_keys()
    {
        std::vector<std::string> vlist;
        std::string path;
        std::function<void(SlashDict * psd, std::string)> dfs = [&](SlashDict *psd, std::string path)
        {
            if (psd->value != -1)
            {
                vlist.push_back(path); // std::to_string(psd->value)
            }
            for (auto &[k, sd] : psd->dic)
            {
                dfs(&sd, path + k + "/");
            }
        };
        dfs(this, path);
        return vlist;
    }
};

int main()
{
    SlashDict sd;
    sd.insert("a/b/c/x", 1);
    sd.insert("a/b/c/y", 2);
    sd.insert("a/b/d", 3);
    sd.insert("e/f", 4);

    SlashDict sd2 = sd.get("a/b/c/x");
    std::cout << sd2.getValue() << "\n";
    sd2 = sd.get("a/b/d");
    std::cout << sd2.getValue() << "\n";

    sd2 = sd.get("a/b/k");

    std::cout<<"pop a/b/c/y\n";
    sd.pop("a/b/c/y");
    sd2 = sd.get("a/b/c/y");

    sd.insert("e/f/g",5);
    std::vector<std::string> list=sd.deep_keys();
    for(auto&s:list)
        std::cout<<s<<"\n";
    return 0;
}