lc 1943. 描述绘画结果

就是个差分数组,注意保存一下每个点的颜色即可

 

class Solution {
public:
    long long d[100010];
    vector<vector<long long > > ret;
    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
        memset(d, 0, sizeof(d));
        int cnt = 0;
        set<string> s[100010];
        vector<long long > t;
        int length = segments.size();
        int low = 100010;
        for(int i = 0; i < length; i++)
        {
            d[segments[i][0]] += segments[i][2];
            d[segments[i][1]] -= segments[i][2];
            low = min(low, segments[i][0]);
            s[segments[i][0]].insert(to_string(segments[i][2]));
            s[segments[i][1]].insert(to_string(segments[i][2]));
        }
        int p = low;
        long long color = d[1], k = d[low];



        for(int i = low + 1; i <= 100000; i++)
        {
            t.clear();
            if(k + d[i] == k)
            {
                if(s[i].size() == 0 || (s[p].size() != 0 && s[i] == s[p]))
                    k += d[i];
                else
                {
                    if(k == 0) continue;
                    t.push_back(p);
                    t.push_back(i);
                    t.push_back(k);
                    ret.push_back(t);
                    
                    k += d[i];
                    p = i;
                }
            }
            else
            {
                    if(k != 0)
                    {
                       t.push_back(p);
                        t.push_back(i);
                        t.push_back(k);
                        ret.push_back(t);
                    }
                    k += d[i];
                    p = i;
            }
        }
        return ret;
    }
};

 

上一篇:平面最近点对


下一篇:2021-11-10 micropython 的 tm1638记录 附带DHT11读显实例