365天挑战LeetCode1000题——Day 040 设计跳表 + 避免洪水泛滥 + 查找大小为 M 的最新分组 + 销售价值减少的颜色球

1206. 设计跳表

代码实现（看题解）

constexpr int MAX_LEVEL = 32;
constexpr double P_FACTOR = 0.25;

struct SkiplistNode {
    
    int val;
    vector<SkiplistNode *> forward;
    SkiplistNode(int _val, int _maxLevel = MAX_LEVEL) : val(_val), forward(_maxLevel, nullptr) {
    
        
    }
};

class Skiplist {
    
private:
    SkiplistNode * head;
    int level;
    mt19937 gen{
    random_device{
    }()};
    uniform_real_distribution<double> dis;

public:
    Skiplist(): head(new SkiplistNode(-1)), level(0), dis(0, 1) {
    

    }

    bool search(int target) {
    
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
    
            /* 找到第 i 层小于且最接近 target 的元素*/
            while (curr->forward[i] && curr->forward[i]->val < target) {
    
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        /* 检测当前元素的值是否等于 target */
        if (curr && curr->val == target) {
    
            return true;
        } 
        return false;
    }

    void add(int num) {
    
        vector<SkiplistNode *> update(MAX_LEVEL, head);
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
    
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr->forward[i] && curr->forward[i]->val < num) {
    
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        int lv = randomLevel();
        level = max(level, lv);
        SkiplistNode *newNode = new SkiplistNode(num, lv);
        for (int i = 0; i < lv; i++) {
    
            /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }

    bool erase(int num) {
    
        vector<SkiplistNode *> update(MAX_LEVEL, nullptr);
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
    
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr->forward[i] && curr->forward[i]->val < num) {
    
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];
        /* 如果值不存在则返回 false */
        if (!curr || curr->val != num) {
    
            return false;
        }
        for (int i = 0; i < level; i++) {
    
            if (update[i]->forward[i] != curr) {
    
                break;
            }
            /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
            update[i]->forward[i] = curr->forward[i];
        }
        delete curr;
        /* 更新当前的 level */
        while (level > 1 && head->forward[level - 1] == nullptr) {
    
            level--;
        }
        return true;
    }

    int randomLevel() {
    
        int lv = 1;
        /* 随机生成 lv */
        while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
    
            lv++;
        }
        return lv;
    }
};

---

1488. 避免洪水泛滥

代码实现（部分看题解）

class Solution {
    
public:
    vector<int> avoidFlood(vector<int>& rains) {
    
        const int n = rains.size();
        
        vector<int> ans(n, 1);
        set<int> sunny;
        map<int, int> full;

        for (int i = 0; i < n; i++) {
    
            if (rains[i] == 0) {
    
                sunny.emplace(i);
                continue;
            }
            if (full.count(rains[i])) {
    
                auto it = sunny.lower_bound(full[rains[i]]);
                if (it == sunny.end()) return {
    };
                ans[*it] = rains[i];
                sunny.erase(it);
            }
            full[rains[i]] = i;
            ans[i] = -1;
        }
        return ans;
    }
};

---

1562. 查找大小为 M 的最新分组

代码实现（看题解）

int link[100001] = {
    0};

class Solution {
    
public:
    int findLatestStep(vector<int>& arr, int m) {
    
        int cnt = 0;
        memset(link, -1, sizeof(link));
        int anw = -1;
        for(int i = 0; i < arr.size(); i++) {
    
            int pos = arr[i] - 1;
            link[pos] = pos;
            int L = pos, R = pos;
            if(0 < pos && link[pos-1] != -1) {
    
                if(pos-1 - link[pos-1] + 1 == m) {
    
                    cnt--;
                }
                L = link[pos-1];
            }
            if(pos+1 < arr.size() && link[pos+1] != -1) {
    
                if(link[pos+1] - (pos+1) + 1 == m) {
    
                    cnt--;
                }
                R = link[pos+1];
            }
            
            link[L] = R;
            link[R] = L;
            
            if(R-L+1 == m) {
    
                cnt++;
            }
            if(cnt > 0) {
    
                anw = i+1;
            }
        }
        return anw;
    }
};

---

1648. 销售价值减少的颜色球

代码实现（自解）

class Solution {
    
private:
    const int V = 1000000007;
public:
    int maxProfit(vector<int>& inventory, int orders) {
    
        if (inventory.size() == 1) {
    
            return (long long)
            (2 * inventory[0] - orders + 1) % V * orders % V / 2;
        }
        sort(inventory.begin(), inventory.end(), greater<int>());
        inventory.push_back(0);
        const int n = inventory.size();
        long long sum = 0, nextRound = 0, ans = 0;
        for (int i = 0; i < n - 1; i++) {
    
            nextRound = inventory[i] - inventory[i + 1];
            if (sum + nextRound * (i + 1) >= orders) {
    
                int j = i + 1;
                long long r1 = (orders - sum) / j;
                ans = ans + (i + 1)
                * (2 * inventory[i] - r1 + 1) * r1 / 2;
                long long r2 = (orders - sum) % j;
                ans = ans + (long long) r2 * (inventory[i] - r1);
                // cout << "r1 = " << r1 << " r2 = " << r2 << endl;
                //cout << "ans = " << ans << endl;
                return ans % V;
            }
            ans = ans + (long long) (i + 1) *
            (inventory[i] + inventory[i + 1] + 1) * nextRound / 2;
            sum += (i + 1) * nextRound;
            //cout << "ans = " << ans << " sum = " << sum << endl;
        }

        return -1;
    }
};

---