365 day challenge leetcode 1000 questions - day 040 design jump table + avoid flooding + find the latest grouping with size M + color ball with reduced sales value

1206. Design jump table

Code implementation （ Look at the explanation ）

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--) {
    
            /*  Find No  i  The layer is smaller than and closest to  target  The elements of */
            while (curr->forward[i] && curr->forward[i]->val < target) {
    
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        /*  Detect whether the value of the current element is equal to  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--) {
    
            /*  Find No  i  The layer is smaller than and closest to  num  The elements of */
            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++) {
    
            /*  Right.  i  Update the status of the layer , Change the current element's  forward  Point to new node  */
            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--) {
    
            /*  Find No  i  The layer is smaller than and closest to  num  The elements of */
            while (curr->forward[i] && curr->forward[i]->val < num) {
    
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];
        /*  If the value does not exist, it returns  false */
        if (!curr || curr->val != num) {
    
            return false;
        }
        for (int i = 0; i < level; i++) {
    
            if (update[i]->forward[i] != curr) {
    
                break;
            }
            /*  Right.  i  Update the status of the layer , take  forward  Point to the next hop of the deleted node  */
            update[i]->forward[i] = curr->forward[i];
        }
        delete curr;
        /*  Update the current  level */
        while (level > 1 && head->forward[level - 1] == nullptr) {
    
            level--;
        }
        return true;
    }

    int randomLevel() {
    
        int lv = 1;
        /*  Random generation  lv */
        while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
    
            lv++;
        }
        return lv;
    }
};

---

1488. Avoid flooding

Code implementation （ Part depends on the solution ）

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. Find size is M The latest group of

Code implementation （ Look at the explanation ）

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. Color balls with reduced sales value

Code implementation （ Self solution ）

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;
    }
};

---