thảo luận Leetcode mỗi ngày

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<unordered_set<int>> steps(n);
        steps[0].insert(1);
        unordered_map<int, int> m;
        vector<int> minStep(n, 1);
        for (int i = 0; i < n - 1; ++i) {
            m[stones[i]] = i; // map stone to index
            minStep[i] = stones[i + 1] - stones[i]; // min steps required at i 
        }
        for (int i = 0; i < n - 1; ++i){
            for (int k : steps[i]){
                if (k + stones[i] == stones.back()) return true;
                if (m.count(k + stones[i])){
                    int idx = m[k + stones[i]];
                    for (int j = max(k - 1, minStep[idx]); j <= k + 1; ++j)
                        steps[idx].insert(j);
                }
            }
        }
        return false;
    }
};

class Solution {
public:
    ListNode** reverseBetween(ListNode*& head, int left, int right) {
        ListNode* nodeRight = head;
        ListNode** ppl = &head;
        ListNode** ppr = &nodeRight;
        int idx = 1;
        for(ListNode* curr = head; curr != nullptr; curr = curr->next){
            if(idx < left){
                ppl = &((*ppl)->next);
                nodeRight = nodeRight->next;
            }
            else if(idx > left && idx <= right){
                (*ppr)->next = curr->next;
                curr->next = *ppl;
                *ppl = curr;
                curr = *ppr;
            }
            else if(idx > right)
                break;
            idx++;
        }
        return ppr;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        int left = 1;
        int right = 1;
        if(k != 1){
            ListNode* iter = head;
            ListNode** entry = &head;
            while(iter != nullptr){
                if(right - left + 1 == k){
                    iter = iter->next;
                    entry = reverseBetween(*entry, 1, k);
                    entry = entry ? &((*entry)->next) : nullptr;
                    left = right + 1;
                }
                else
                    iter = iter->next;
                right++;
            }
        }
        return head;
    }
};

class MyStack {
    constructor() {
        this.q = new Queue();
    }
    push(x) {
        const q2 = new Queue();
        while (!this.q.isEmpty()) {
            q2.enqueue(this.q.dequeue());
        }
        
        this.q.enqueue(x);
        while (!q2.isEmpty()) {
            this.q.enqueue(q2.dequeue());
        }
    }
    pop() {
        return this.q.dequeue();
    }
    top() {
        return this.q.front();
    }
    empty() {
        return this.q.isEmpty();
    }
}

function canCross(stones: number[]): boolean {
    //for each el in stones, assign number of units needed to next stone = foreach existing unit current stones has
    // stepdp[stones.last] = result
    const stonesLen = stones.length;
    const stonedp = (new Array(stonesLen).fill(undefined))
    let result = false;
    stonedp[0]=[0]

    stones.forEach((currentStone, index) => {
        if (!stonedp[index]) return;
        if (index === stonesLen - 1) result= true;
        stonedp[index].forEach((prevStone) => {
            for (let i = index + 1; i < stonesLen && stones[i] - currentStone <= currentStone- stones[prevStone] + 1; i++) {
                const nextStone = stones[i];
                if (Math.abs(nextStone-2*currentStone+ stones[prevStone]) > 1) continue;
                if (!stonedp[i]) stonedp[i]=[index];
                else if(!stonedp[i].includes(index)) stonedp[i].push(index);
            }
        });

        stonedp[index]=undefined
    });

    return result;
}