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

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        Trie t = new Trie();
        for(int i = 0; i < wordDict.Count; i++){
            t.InsertWord(wordDict[i]);
        }
        bool[] dp = new bool[s.Length + 1];
        dp[0] = true;
        for(int i = 1; i <= s.Length; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] == true && t.ContainsWord(s.Substring(j, i - j)) == true){
                    dp[i] = true;
                }
            }
        }
        return dp[s.Length];
    }
}

class Node {
    private Node[] child;
    private bool isEnd;
    public Node(){
        child = new Node[26];
        isEnd = false;
    }
    public bool IsEnd(){
        return isEnd;
    }
    public void SetEnd(bool val){
        isEnd = val;
    }
    public bool ContainsChar(char c){
        return child[c - 'a'] != null;
    }
    public Node GetChild(char c){
        return child[c - 'a'];
    }
    public void AddChar(char c){
        child[c - 'a'] = new Node();
    }
}

class Trie {
    private Node root;
    public Trie(){
        root = new Node();
    }
    public void InsertWord(string word){
        Node ptr = root;
        for(int i = 0; i < word.Length; i++){
            char curr = word[i];
            if(!ptr.ContainsChar(curr)){
                ptr.AddChar(curr);
            }
            ptr = ptr.GetChild(curr);
        }
        ptr.SetEnd(true);
    }
    public bool ContainsWord(string word){
        Node ptr = root;
        for(int i = 0; i < word.Length; i++){
            char curr = word[i];
            if(ptr.ContainsChar(curr)){
                ptr = ptr.GetChild(curr);
            }
            else{
                return false;
            }
        }
        return ptr.IsEnd();
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:

        @cache
        def get_trees(start_value, end_value):
            if start_value > end_value:
                return [None]
            if start_value == end_value:
                return [TreeNode(start_value)]
            
            trees = []
            for root_value in range(start_value, end_value + 1):
                left_trees = get_trees(start_value, root_value - 1)
                right_trees = get_trees(root_value + 1, end_value)

                for left_tree in left_trees:
                    for right_tree in right_trees:
                        trees.append(TreeNode(root_value, left_tree, right_tree))
            
            return trees
        
        return get_trees(1, n)

public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        return generate(1, n).ToList();
    }

    IEnumerable<TreeNode> generate(int from, int to)
    {
        if (from > to)
            yield return null;

        for (var i = from; i <= to; i++)
            foreach (var left in generate(from, i - 1))
                foreach (var right in generate(i + 1, to))
                    yield return new TreeNode(i, left, right);
    }
}

@cache
def solve(l, r):
    if l > r: return [None]
    return [TreeNode(i, lt, rt) for i in range(l, r+1) for lt in solve(l,i-1) for rt in solve(i+1,r)]


class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        return solve(1, n)

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        fn solve(l: i32, r: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            if l > r {
                return vec![None];
            }

            let mut res: Vec<Option<Rc<RefCell<TreeNode>>>> = Vec::new();
            (l..r + 1).for_each(|i| {
                let lefts = solve(l, i - 1);
                let rights = solve(i + 1, r);
                
                for left in lefts.iter() {
                    for right in rights.iter() {
                        let mut root = TreeNode::new(i);
                        root.left = left.clone();
                        root.right = right.clone();
                        res.push(Some(Rc::new(RefCell::new(root))));
                    }
                }
            });
            res
        }
        solve(1, n)
    }
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
type Key = [number, number]
function generateTrees(n: number): Array<TreeNode | null> {
    if (n === 1) return [new TreeNode(1)];
    const memo: Map<Key, Array<TreeNode | null>> = new Map();
    const generate = (start: number, end: number) => {
        const res: Array<TreeNode | null> = [];
        if (start > end) {
            res.push(null);
            return res;
        }
        if (memo.has([start, end])) {
            return memo.get([start, end])
        }
        for (let i = start; i <= end; i++) {
            const left = generate(start, i - 1);
            const right = generate(i + 1, end);
            for (const l of left) {
                for (const r of right) {
                    const node = new TreeNode(i, l, r);
                    res.push(node)
                }
            }
        }
        memo.set([start, end], res);
        return res;
    }
    return generate(1, n);
};

struct Solution {
    vector<TreeNode*> generateTrees(int n, int startId = 1) {
        if (n == 0) return vector<TreeNode*>{nullptr};
        vector<TreeNode*> res;
        for (int i = startId, endId = startId + n - 1; i <= endId; ++i)
            for (TreeNode* pLeft : generateTrees(i - startId, startId))
                for (TreeNode* pRite : generateTrees(endId - i, i + 1))
                    res.push_back(new TreeNode(i, pLeft, pRite));
        return res;
    }
};

struct Solution {
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<vector<TreeNode*>>> memo(n + 1);
        memo[0].resize(n + 1, vector<TreeNode*>{nullptr});
        for (int diag = 1; diag <= n; ++diag)
            for (int row = 1, col = diag - 1; row <= diag; ++row, --col) {
                memo[row].push_back(vector<TreeNode*>{});
                for (int i = 0; i < row; ++i)
                    for (TreeNode* pLeft : memo[i][col])
                        for (TreeNode* pRite : memo[row - 1 - i][col + 1 + i])
                            memo[row][col].push_back(new TreeNode(i + col + 1, pLeft, pRite));
            }
        return memo.back()[0];
    }
};

struct Solution {
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<vector<TreeNode*>>> memo(n + 1);
        memo[0].resize(n + 1, vector<TreeNode*>{nullptr});
        for (int row = 1; row <= n; ++row) {
            memo[row].resize(n - row + 1);
            for (int col = 0; col < n - row + 1; ++col)
                for (int i = 0; i < row; ++i)
                    for (TreeNode* pLeft : memo[i][col])
                        for (TreeNode* pRite : memo[row - i - 1][col + i + 1])
                            memo[row][col].push_back(new TreeNode(i + col + 1, pLeft, pRite));
        }
        return memo.back()[0];
    }
};

/**
 * 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 List<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }

    public List<TreeNode> helper(int left, int right){
        List<TreeNode> ans = new ArrayList<>();
        if(left == right){
            ans.add(new TreeNode(left));
            return ans;
        }
        if(left > right){
            ans.add(null);
            return ans;
        }
        for(int i = left; i <= right; i++){
            for(TreeNode leftNode : helper(left, i - 1)){
                for(TreeNode rightNode : helper(i + 1, right)){
                    ans.add(new TreeNode(i, leftNode, rightNode));
                }
            }
        }
        return ans;
    }
}

const MOD = 1e9 + 7
func numMusicPlaylists(n int, goal int, k int) int {
    dp := make([][]int,goal+1)
    for i := 0; i <= goal; i++{
        dp[i] = make([]int,n+1)
    }
    dp[0][0] = 1
    for i := 1; i <= goal; i++{
        for j := 1; j <= n; j++{
            dp[i][j] = (dp[i][j] + dp[i-1][j-1]*(n-j+1))%MOD;
            if j > k{
                dp[i][j] = (dp[i][j] + dp[i-1][j]*(j-k))%MOD;
            }
        }
    }
    return dp[goal][n];
}

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        MOD = int(1e9) + 7
        dp = [0 for _ in range(n + 1)]

        dp[k + 1] = 1
        for num in range(n, n - k - 1, -1):
            dp[k + 1] *= num
            dp[k + 1] %= MOD
        
        for nums in range(k + 2, goal + 1):
            limit_diff_nums = min(n, nums)
            for diff_nums in range(limit_diff_nums, k, -1):
                
                dp[diff_nums] = dp[diff_nums] * (diff_nums - k) + dp[diff_nums - 1] * (n - diff_nums + 1)
                dp[diff_nums] %= MOD

        return dp[n]

function numMusicPlaylists(n: number, goal: number, k: number): number {
    const m = 1e9 + 7;
    const dp = Array(goal + 1).fill(0).map(e => Array(n + 1).fill(-1));
    // with i is the playlist's length and j is the number of unique songs
    const generate = (i: number, j: number) => {
        // base case
        if (i === 0 && j === 0) return 1;
        if (i === 0 || j === 0) return 0;

        // has already been calculated
        if (dp[i][j] !== -1) return dp[i][j];

        // in case of adding a new song
        dp[i][j] = generate(i - 1, j - 1) * (n - j + 1) % m;

        // in case of replaying an old song
        if (j > k) {
            dp[i][j] += generate(i - 1, j) * (j - k) % m;
            dp[i][j] %= m;
        }
        return dp[i][j]
    }
    return generate(goal, n);
};

MOD = int(1e9+7)
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        dp = [[0 for _ in range(n + 1)] for _ in range(goal + 1)]
        dp[0][0] = 1
        for i in range(1, goal + 1):
            for j in range(1, min(i, n) + 1):
                dp[i][j] = ((n-j+1)*dp[i-1][j-1] + max(0,j-k)*dp[i-1][j]) % MOD
        return dp[-1][-1]

function searchMatrix(matrix: number[][], target: number): boolean {
    const row = matrix.length, col = matrix[0].length;
    let left = 0, right = row * col - 1;
    while (left <= right) {
        const mid = (left + right) >> 1;
        if (matrix[Math.floor(mid / col)][mid % col] == target) {
            return true;
        }
        if (matrix[Math.floor(mid / col)][mid % col] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
};

struct Solution {
    bool searchMatrix(const vector<vector<int>>& mat, int target) {
        if (auto rowIt = upper_bound(begin(mat), end(mat), target,
                         [](int val, const auto& row){ return val < row[0]; }); rowIt-- != begin(mat))
            if (auto it = lower_bound(begin(*rowIt), end(*rowIt), target); it != end(*rowIt))
                return *it == target;
        return false;
    }
};

var searchMatrix = function(matrix, target) {
    const m = matrix.length,
          n = matrix[0].length;
    if (target < matrix[0][0] || target > matrix[m-1][n-1]) {
        return false;
    }
    const findRowIdx = (l, r, v) => {
        while (l<r) {
            const m = (l+r)>>1;
            if (v >= matrix[m][0]) {
                l = m+1;
            } else {
                r = m;
            }
        }
        
        return l-1;
    };
    const findColIdx = (l, r, c, v) => {
        while (l<r) {
            const m = (l+r)>>1;
            if (v >= matrix[c][m]) {
                l = m+1;
            } else {
                r = m;
            }
        }
        
        return l-1;
    }
    const row = findRowIdx(0, m, target);
    const col = findColIdx(0, n, row, target);
    
    return matrix[row][col] === target;
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int l = 0, r = m * n - 1;
        while (l <= r) {
           int mid = l + (r - l) / 2;
           int x = mid / n;
           int y = mid % n;

           if (matrix[x][y] == target) return true;
           else if (matrix[x][y] < target) l = mid + 1;
           else r = mid - 1;
        }

        return false;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> ft;
        int n = matrix.size();
        for(int i = 0; i < n; i++){
            ft.push_back(matrix[i][0]);
        }
        int id = upper_bound(ft.begin(),ft.end(),target) - ft.begin() - 1;
        if (id < 0 || id >= n) return false;
        auto pt = lower_bound(matrix[id].begin(),matrix[id].end(),target);
        if (pt == matrix[id].end()) return false;
        return *pt == target;
    }
};