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

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int n = words.size(), left = 0;
        vector<string> res;
        while (left < n) {
            int right = left + 1, len = words[left].size();
            // right - left is spaces needed
            while (right < n && len + right - left + words[right].size() <= maxWidth)
                len += words[right++].size();
            
            int nword = right - left, nspace = maxWidth - len;
            string line = words[left];
            if (nword == 1) // line has only one word
                line += string(nspace, ' ');
            else if (right == n){ // last line
                for (int i = left + 1; i < right; ++i)
                    line += " " + words[i];
                line += string(nspace - nword + 1, ' ');
            }else {
                int divisible = nspace / (nword - 1), residual = nspace % (nword - 1);
                for (int i = left + 1; i < right; ++i)
                    line += string(divisible + (residual > i - left - 1), ' ') + words[i];
            }
            left = right;
            res.emplace_back(line);
        }
        return res;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void pushTail(ListNode*& head, ListNode*& tail, ListNode* entry){
        if(head == nullptr)
            head = tail = entry;
        else{
            tail->next = entry;
            tail = tail->next;
        }
    }
    void mergeList(ListNode*& first, ListNode*& second){
        if(first == nullptr)
            first = second;
        else {
            ListNode* head = nullptr;
            ListNode* tail = nullptr;
            while(first && second){
                if(first->val < second->val){
                    pushTail(head, tail, first);
                    first = first->next;
                }
                else{
                    pushTail(head, tail, second);
                    second = second->next;
                }
            }
            if(first)
                pushTail(head, tail, first);
            else if(second)
                pushTail(head, tail, second);
            first = head;
        }
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0)
            return nullptr;
        ListNode* listMerged = lists[0];
        for(int i = 1; i < lists.size(); ++i)
            mergeList(listMerged, lists[i]);
        return listMerged;
    }
};

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n,m,g = len(s1),len(s2),len(s3)
        if n + m != g:
            return False
        dp = [True] + [False] * m

        for i in range(0,n+1):
            for j in range(0,m+1):
                if i > 0:
                    dp[j] &= s1[i-1] == s3[i+j-1]
                if j > 0:
                    dp[j] |= (s2[j-1] == s3[i+j-1] and dp[j-1])
        return dp[m]

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode list : lists) {
            if (list != null)  pq.add(list);
        }

        ListNode sentinel = new ListNode();
        ListNode cur= sentinel;

        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                pq.add(node.next);
            }
        }

public class Item
{
    public int S1 { get; set; } // s1id
    public int S2 { get; set; } // s2id
    public int S3 { get; set; } // s3id
}

public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        if(s3.Length != s1.Length + s2.Length) return false;

        Stack<Item> stack = new Stack<Item>();
        HashSet<string> savePoints = new HashSet<string>();
        int s1Length = s1.Length,
            s2Length = s2.Length,
            s3Length = s3.Length;
        bool s1Result, s2Result;
        Item current;
        string key;

        stack.Push(new Item {S1 = 0, S2 = 0, S3 = 0});

        while(stack.Count > 0) {
            current = stack.Pop();
            for(; current.S3 < s3.Length; current.S3++) {
                s1Result = current.S1 < s1Length ? s3[current.S3] == s1[current.S1] : false;
                s2Result = current.S2 < s2Length ? s3[current.S3] == s2[current.S2] : false;

                if(s1Result && s2Result) {
                    key = $"{current.S1}-{current.S2}-{current.S3}";
                    if(!savePoints.Contains(key)) {
                        stack.Push(new Item{S1 = current.S1, S2 = current.S2+1, S3 = current.S3+1});
                        savePoints.Add(key);
                    }
                    current.S1++;
                } else if(s1Result) {
                    current.S1++;
                } else if(s2Result) {
                    current.S2++;
                } else {
                    break;
                }
            }

            if(current.S1 >= s1Length && current.S2 >= s2Length && current.S3 >= s3Length) {
                return true;
            }
        }
      
        return false;
    }
}

using tuple3i = tuple<int, int, int>;

struct hash_tuple3i {
    size_t operator()(const tuple3i& t) const {
        size_t res = 0;
        for (auto h : {hash<int>{}(get<0>(t)), hash<int>{}(get<1>(t)), hash<int>{}(get<2>(t))})
            res ^= h + 0x9e3779b9 + (res<<6) + (res>>2);
        return res;
    }
};

class Solution {
    unordered_map<tuple3i, bool, hash_tuple3i> dp;
public:
    bool isInterleave(string_view s1, string_view s2, string_view s3) {
        // dp(L1, L2, L3) = s1[L1-1] == s3[L3-1] ? dp(L1 - 1, L2, L3 - 1) |
        //                  s2[L2] == s3[L3] ? dp(L1, L2 - 1, L3 - 1)
        //                  else false
        // dp(0, 0, 0) = true
        // dp(0, 0, L3) = dp(L1, 0, 0) = dp(0, L2, 0) = false
        const int L1 = s1.size();
        const int L2 = s2.size();
        const int L3 = s3.size();
        if (L1 == 0 && L2 == 0) return L3 == 0;
        if (L1 == 0 && L3 == 0) return L2 == 0;
        if (L2 == 0 && L3 == 0) return L1 == 0;
        const auto k = make_tuple(L1, L2, L3);
        const auto it = dp.find(k);
        if (it != end(dp)) return it->second;
        bool res = false;
        if (L3 > 0) {
            if (L1 > 0 && s1[L1 - 1] == s3[L3 - 1])
                res = isInterleave(s1.substr(0, L1 - 1), s2, s3.substr(0, L3 - 1));
            if (res == false && L2 > 0 && s2[L2 - 1] == s3[L3 - 1])
                res = isInterleave(s1, s2.substr(0, L2 - 1), s3.substr(0, L3 - 1));
        }
        return dp[k] = res;
    }
};

class Solution {
    enum class Tribool : uint8_t { NoValue = 0, True, False };
    Tribool dp[101][101][201]{};
public:
    bool isInterleave(string_view s1, string_view s2, string_view s3) {
        // dp(L1, L2, L3) = s1[L1-1] == s3[L3-1] ? dp(L1 - 1, L2, L3 - 1) |
        //                  s2[L2] == s3[L3] ? dp(L1, L2 - 1, L3 - 1)
        //                  else false
        // dp(0, 0, 0) = true
        // dp(0, 0, L3) = dp(L1, 0, 0) = dp(0, L2, 0) = false
        const int L1 = s1.size();
        const int L2 = s2.size();
        const int L3 = s3.size();
        if (L1 == 0 && L2 == 0) return L3 == 0;
        if (L1 == 0 && L3 == 0) return L2 == 0;
        if (L2 == 0 && L3 == 0) return L1 == 0;
        auto& dpValue = dp[L1][L2][L3];
        if (dpValue != Tribool::NoValue) return dpValue == Tribool::True;
        bool res = false;
        if (L3 > 0) {
            if (L1 > 0 && s1[L1 - 1] == s3[L3 - 1])
                res = isInterleave(s1.substr(0, L1 - 1), s2, s3.substr(0, L3 - 1));
            if (res == false && L2 > 0 && s2[L2 - 1] == s3[L3 - 1])
                res = isInterleave(s1, s2.substr(0, L2 - 1), s3.substr(0, L3 - 1));
        }
        dpValue = res ? Tribool::True : Tribool::False;
        return res;
    }
};

class Solution {
    enum class Tribool : uint8_t { NoValue = 0, True, False } dp[101][101][201]{};
public:
    bool isInterleave(string_view s1, string_view s2, string_view s3) {
        if (s1.empty() && s2.empty() && s3.empty()) return true;
        auto& dpValue = dp[s1.size()][s2.size()][s3.size()];
        if (dpValue != Tribool::NoValue) return dpValue == Tribool::True;
        bool res = !s3.empty() && (
            !s1.empty() && s1[0] == s3[0] && isInterleave(s1.substr(1), s2, s3.substr(1)) ||
            !s2.empty() && s2[0] == s3[0] && isInterleave(s1, s2.substr(1), s3.substr(1))
        );
        dpValue = res ? Tribool::True : Tribool::False;
        return res;
    }
};

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(begin(pairs), end(pairs));
        int result = 1;
        vector<int> chains(pairs.size(), 1);
        for(int i = 1; i < pairs.size(); ++i){
            for(int j = 0; j < i; ++j){
                if(pairs[i][0] > pairs[j][0] && pairs[i][1] > pairs[j][1] && pairs[i][0] > pairs[j][1])
                    chains[i] = chains[j] + 1;
            }
            result = max(result, chains[i]);
        }
        return result;
    }
};

var findLongestChain = function(pairs) {
    const ans = {};
    const pbe = _.groupBy(pairs, '1');
    for (let i = -1000; i <= 1000; i++) {
        ans[i] = ans[i-1] ?? 0;
        for (const [s] of (pbe[i] ?? [])) {
            ans[i] = Math.max(ans[i], (ans[s-1] ?? 0) + 1);
        }
    }
    return ans[1000];
};

function fullJustify(words: string[], maxWidth: number): string[] {
    let i =0;
    let concatWordsLen = 0;
    const concatArray=[];
    const wordsLen = words.length;
    const result:string[]= [];

    while(i<wordsLen){
 
        if ((concatWordsLen + words[i].length + concatArray.length) <= maxWidth){
            concatArray.push(words[i]);
            concatWordsLen += words[i].length;
            i++;
        }
        else {

            const justifiedWord = genJustifiedWord(concatArray,maxWidth-concatWordsLen);
            result.push(justifiedWord + ' '.repeat(maxWidth - justifiedWord.length))
            concatArray.splice(0,concatArray.length);
            concatWordsLen=0;
        }

    }

    const lastElement = concatArray.reduce((acc,ele,index)=> (acc+ ele + (index === concatArray.length -1 ? '':' ')) ,'');
    result.push(lastElement+' '.repeat(maxWidth - lastElement.length))

    return result;
};

function genJustifiedWord(words:string[], remaining:number):string{
    const numberOfWords = words.length;
    let remainingSpace = remaining

    const justifiedWord = words.reverse().reduce((acc,word,index)=>{
        let numberOfSpace = numberOfWords-index > 0 ? Math.floor(remainingSpace/(numberOfWords-index)):0;

        if (index === 0) numberOfSpace=0
        else remainingSpace-=numberOfSpace

        return word+ ' '.repeat(numberOfSpace)+ acc
    },'')

    return justifiedWord;
}

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [&](vector<int> &p1, vector<int> &p2) { return p1[1] < p2[1]; });
        int n = pairs.size();
        vector<int> dp(n, 0);
        dp[0] = 1;
        auto end = pairs.begin();
        for (int i = 1; i < n; i++) {
            int j = lower_bound(pairs.begin(), ++end, pairs[i][0], [&](const vector<int> &p, int v) { return p[1] < v; }) - pairs.begin();
            dp[i] = max(dp[i - 1], j ? dp[j - 1] + 1 : 1);
        }
        return dp[n - 1];
    }
};