date: 2020/01/29

基本概念


"122买卖股票的最佳时机II(简单)


860柠檬水找零(简单)

https://leetcode-cn.com/problems/lemonade-change

一次遍历,按收银分三类决策:空间O(1)时间O(n)


455分发饼干(简单)

https://leetcode-cn.com/problems/assign-cookies

排序+一次遍历:空间O(1)或O(n),时间O(nlogn + klogk)

int findContentChildren(vector<int>& g, vector<int>& s) {
    if(g.size() == 0 || s.size() == 0)
        return 0;

    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    
    int content = 0, s_idx = -1;
    for(int i = 0; i < g.size(); i++){
        do{
            if((++s_idx) >= s.size())
                return content;
        }while(s[s_idx] < g[i]);
        content++;
    }
    return content;
}


874模拟行走机器人(简单)

https://leetcode-cn.com/problems/walking-robot-simulation

// 自定义pair<int, int>的哈希函数
struct pair_hash {
    inline size_t operator()(const pair<int,int>& p) const {
        return p.first * 100 + p.second;
    }
};

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
    // 初始化
    int dx[4] = {0, 1, 0, -1};  // 北、东、南、西
    int dy[4] = {1, 0, -1, 0};  // 北、东、南、西
    int direction = 0;          // 北、东、南、西
    int x = 0, y = 0;   // 当前坐标
    max_dist = 0;       // 最大欧式距离
    // 障碍物数组转成集合
    unordered_set<pair<int, int>, pair_hash> obs_set;  // set内置pair的哈希函数,但unordered_set没有
    for(int i = 0; i < obstacles.size(); i++)
        obs_set.insert(make_pair(obstacles[i][0], obstacles[i][1]));
    // 开始模拟
    for(int i = 0; i < commands.size(); i++){
        if(commands[i] == -2){          // 左转
            direction = (direction + 3) % 4;
        }else if(commands[i] == -1){    // 右转
            direction = (direction + 1) % 4;
        }else{  // 前进
            // 逐步试探前进
            for(int j = 0; j < commands[i]; j++){
                // 试探
                int nx = x + dx[direction];
                int ny = y + dy[direction];
                if(obs_set.find(make_pair(nx, ny)) != obs_set.end())
                    break;
                // 应用
                x = nx;
                y = ny;
            }
            max_dist = max(max_dist, x * x + y * y);
        }
    }
    return max_dist;
}


406根据身高重建队列(中等)

https://leetcode-cn.com/problems/queue-reconstruction-by-height

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    /* // vector随机插值,省内存,速度慢
        if(people.size() <= 1)
            return people;

        sort(people.begin(), people.end(), [](vector<int> &a, vector<int> &b){
            return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
        });

        vector<vector<int> > ans;
        int last_h = 0;
        for(auto p: people){
            if(p[0] <= last_h)
                ans.insert(ans.begin() + p[1], p);
            else
                ans.push_back(p);
            last_h = p[0];
        }
        return ans;
        */

    // list随机插值,最后再转存vector作为答案,速度快,内存占用高
    if(people.size() <= 1)
        return people;

    sort(people.begin(), people.end(), [](vector<int> &a, vector<int> &b){
        return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });

    int last_h = 0;
    list<vector<int> > ans;
    for(auto p: people){
        if(p[0] <= last_h){
            // list不允许对迭代器做类似it+=2的操作
            list<vector<int> >::iterator it = ans.begin();
            for(int i = 0; i < p[1]; i++)
                it++;
            ans.insert(it, p);
        }else
            ans.push_back(p);
        last_h = p[0];
    }

    vector<vector<int> > ans_vec;
    for(auto a: ans)
        ans_vec.push_back(a);
    return ans_vec;
}