Sort Food | tech::interview

Sort Food | tech::interview

输入一个字符串，它包含的是『食物-重量』对。解析之，按食物重量降序排序输出List. (重量一致可放在一起）
特别情况：

1. 当食物后面跟的也是食物，表明前面的食物是默认重量，比如5.
   在例子1中：crab后面直接跟了hotdog，那么crab的重量是5
2. 在例子4中，2.0表示的是食物，这个食物的名字就叫2.0 因为它前面已经完成了
   一个食物-重量对（pizza, 500），但是当数字直接出现在食物后，它就一定是重量，
   比如例子2，3中的1，500都是重量。

注意：输入字符串前后可能有若干冗余空格，食物/重量之间也可能有冗余空格，请忽略所有冗余空格。
4个例子（默认重量 = 5）：

1 2 3 4

sort_food("crab hotdog 9.0 chicken 9.2", 5); sort_food(" pizza 1 hotdog 2.0", 5); sort_food("pizza 500 hotdog 2.0 ", 5); sort_food(" pizza 500 2.0 ", 5);

输出：

chicken hotdog crab
hotdog pizza
pizza hotdog
pizza 2.0

注意double在map里作为key比较，要手写一个compare类，不然会有精度问题。

void sort_food(const string& food_list, double def_weight) {

    struct comp {

        bool operator()( double a, double b ) const {

            return (abs(a - b) > 1e-5) && (a > b);

        }

    };

    map<double, vector<string>, comp> food;

    

    string last_food;

    for(int begin = -1, i = 0; i <= food_list.length(); ++i) {

        char c = food_list[i];

        if(begin == -1 && (c != ' ' && c != '\0')) {

            begin = i;

        } else if (begin != -1 && (c == ' ' || c == '\0')) {

            auto word = food_list.substr(begin, i - begin);

            if(last_food.empty()) {

                last_food = word;

            } else {

                double weight = atof(word.c_str());

                if(weight > 1e-5) { // valid weight

                    food[weight].push_back(last_food);

                    last_food.clear();

                } else { // food

                    food[def_weight].push_back(last_food);

                    last_food = word;

                }

            }

            begin = -1;

        }

    }

    if(!last_food.empty()) food[def_weight].push_back(last_food);

    

    for(auto& p : food)

        for(auto &s : p.second) cout << s << " ";    

    cout << endl;

}

Read full article from Sort Food | tech::interview