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

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] cache = new int[n][n];
        return helper(s, 0, n - 1, cache);
    }

    public int helper(String s, int start, int end, int[][] cache) {
        if (cache[start][end] != 0) return cache[start][end];
        if (start > end) return 0;
        if (start == end) return 1;

        if (s.charAt(start) == s.charAt(end)) {
            cache[start][end] = helper(s, start + 1, end - 1, cache) + 2;
        } else {
            cache[start][end] = Math.max(helper(s, start, end - 1, cache), helper(s, start + 1, end, cache));
        }

        return cache[start][end];
    }
}

class Solution {
public:
    int longestPalindromeSubseq(const string& s) {
        int n = s.size(), dp[n][n];
        memset(dp, 0, sizeof(dp));
        for(int i = n - 1; i >= 0; --i){
            dp[i][i] = 1;
            for(int j = i + 1; j < n; ++j){
                if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};

var maxValueOfCoins = function(piles, k) {
    let current = Array(k + 1).fill(0), next = Array(k + 1).fill(0);

    for (const pile of piles) {
        for (let i = 1; i <= k; i++) {
            let s = 0;
            for (let j = 1; j <= Math.min(i, pile.length); j++) {
                s += pile[j-1] ?? 0;
                next[i] = Math.max(next[i], s + current[i-j]);
            }
        }

        current = next.slice();
    }


    return current[k];
};

function maxValueOfCoins(piles: number[][], k: number): number {
    let dp = new Array(k + 1).fill(0);
    
    for (let i = 0; i < piles.length; ++i) {
        for (let j = k; j > 0; --j) {
            let sum = 0;
            for (let k = 1; k <= Math.min(j, piles[i].length); k++) {
                sum += piles[i][k - 1];
                dp[j] = Math.max(dp[j], dp[j-k] + sum);
            }
        }
    }
    return dp[k];
};

const mulmod = (a, b, m) => {
    if (a < b) {
        return mulmod(b, a, m);
    }
    let res = 0;
    while (b) {
        if (b&1) {
            res = (res + a) % m;
        }
        b >>= 1;
        a = (a << 1) % m;
    }
    return res;
}
var numWays = function(words, target) {
    const m = target.length, n = words[0].length;
    const g = Array.from(words[0].length, () => ({}));
    const MOD = 1e9+7;
    const memo = {};
    for (const w of words) {
        for (let i = 0; i < n; i++) {
            g[i] ??= {};
            g[i][w[i]] ??= 0;
            g[i][w[i]]++;
        }
    }
    const go = (i, j) => {
        if (i >= m || j >= n) {
            return 0;
        }
        if (memo[i]?.[j] === undefined) {
            memo[i] ??= {};
            memo[i][j] = (
                mulmod(g[j][target[i]] ?? 0, (i<m-1 ? go(i+1, j+1) : 1), MOD)
                + go(i, j+1)
            ) % MOD;
        }
        
        return memo[i][j];
    };
    return go(0, 0);
};

function numWays(words: string[], target: string): number {
        const n = target.length;
        const mod = 1e9 + 7, ans = Array(n+1).fill(0);
        ans[0] = 1;
        for (let i = 0; i < words[0].length; ++i) {
            const counts = Array(26).fill(0);
            for (const w of words)
                counts[w[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
            for (let j = n - 1; j >= 0; --j) {
                ans[j + 1] += res[j] * counts[target[j].charCodeAt(0) - 'a'.charCodeAt(0)] % mod;
            }
        }
        return ans[n] % mod;
};

function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
    const res = Array(candies.length).fill(false);
    const max = Math.max.apply(Math, candies);
    for (let i = 0; i < candies.length; i++) {
        res[i] = candies[i] + extraCandies >= max
    }
    return res;
}

var kidsWithCandies = function(candies, extraCandies) {

    const max = Math.max(...candies);

    return candies.map(it => it + extraCandies >= max);

};

return [True if num + extraCandies >= max(candies) else False for num in candies]

function mergeAlternately(word1: string, word2: string): string {
    let res = ''
    for (let i = 0; i < Math.max(word1.length, word2.length); i++) {
        res+= (word1[i] ?? '') + (word2[i] ?? '')
    }
    return res
};

var mergeAlternately = (word1, word2) => _.zip([...word1], [...word2]).flat(true).join('')

var longestZigZag = function(root) {
    let ans = 0;
    const go = node => {
        const t = [0, 0];
        if (node.left) {
            t[0] = go(node.left)[1] + 1;
        }
        if (node.right) {
            t[1] = go(node.right)[0] + 1;
        }
        ans = Math.max(ans, ...t);

        return t;
    };

    go(root);

    return ans;
};

class Solution {
  int ans = 0;
  public int longestZigZag(TreeNode root) {
    dfs(root);
    return ans;
  }

  int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] right = dfs(node.right);
    ans = Math.max(ans, right[0]);
    int[] left = dfs(node.left);
    ans = Math.max(ans, left[1]);
    return new int[]{left[1]+1, right[0]+1};
  }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int longestZigZag(TreeNode root) {
        Map<TreeNode, int[]> cache = new HashMap<>();
        dp(root, 0, cache);
        dp(root, 1, cache);   
        int max = 0; 
        for (TreeNode n : cache.keySet()){
            int[] x = cache.get(n);
            // System.out.println(n + " " + Arrays.toString(x));
            max = Math.max(max, x[0]);
            max = Math.max(max, x[1]);
        }

        return max - 1;
    }

    int dp(TreeNode root, int dir, Map<TreeNode, int[]> cache) {
        if (root == null) return 0;
        int[] x = cache.get(root);
        if (x != null && x[dir] > 0) {
            return x[dir];
        }

        int sum = 1;

        if (dir == 0) {
            sum += dp(root.left, 1, cache);
            dp(root.left, 0, cache);
            dp(root.right, 0, cache);
            dp(root.right, 1, cache);
        } else if (dir == 1) {
            sum += dp(root.right, 0, cache);
            dp(root.left, 0, cache);
            dp(root.left, 1, cache);
            dp(root.right, 1, cache);
        }

        cache.putIfAbsent(root, new int[2]);
        cache.get(root)[dir] = sum;
        return sum;
    }
}

class Solution {
public:
    int res =0;
    void Lsearch(TreeNode* root,int n){
        res=max(res,n);
        if(root->right) Rsearch(root->right,n+1);
        if(root->left) Lsearch(root->left,1);
        return;
    }
    void Rsearch(TreeNode* root,int n){
        res = max(res,n);
        if(root->left) Lsearch(root->left,n+1);
        if(root->right) Rsearch(root->right,1);
        return;
    }
    int longestZigZag(TreeNode* root) {
        if(!root->left&&!root->right) return 0;
        Lsearch(root,0);
        return res;
    }
};