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

function findNumberOfLIS(nums: number[]): number {
    let maxL = 0, ans = 0;
    const n = nums.length;
    const l = new Array(n).fill(1), c = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (l[j] > l[i] - 1) {
                    l[i] = l[j] + 1;
                    c[i] = 0;
                }

                if (l[j] + 1 === l[i]) {
                    c[i] += c[j]
                }
            }
        }
    }
    maxL = Math.max(...l);
    for (let i = 0; i < n; i++) {
        if (l[i] === maxL) ans+= c[i];
    }
    return ans;
};

class Solution {
public:
    double dp[25][25][101];
    int dx[8] = {1,2,1,2,-1,-2,-1,-2};
    int dy[8] = {2,1,-2,-1,2,1,-2,-1};
    bool belong(int n, int r, int c){
        return (r >= 0 && r < n && c >= 0 && c < n);
    }
    double calc(int n, int k, int r, int c){
        if (!belong(n,r,c)) return 0;
        if (k == 0){
            if (belong(n,r,c)) return 1;
            else return 0;
        }
        if (dp[r][c][k] != -1) return dp[r][c][k];
        double ret = 0;
        for (int i = 0; i < 8; i++){
            int x = r + dx[i], y = c + dy[i];
            ret += calc(n,k-1,x,y) * 0.125;
        }
        return dp[r][c][k] = ret;
    }
    double knightProbability(int n, int k, int r, int c) {
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int t = 0; t <= k; t++){
                    dp[i][j][t] = -1;
                }
            }
        }
        return calc(n,k,r,c);
    }
};

class Solution:
    def knightProbability(self, n: int, k: int, start_row: int, start_column: int) -> float:
        probability = [[0] * n for _ in range(n)]
        probability[start_row][start_column] = 1

        dirs = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]

        for step in range(k):
            new_probability = [[0] * n for _ in range(n)]
            for row in range(n):
                for col in range(n):
                    for row_dir, col_dir in dirs:
                        next_row, next_col = row + row_dir, col + col_dir
                        if 0 > next_row or 0 > next_col or next_row >= n or next_col >= n:
                            continue
                        new_probability[next_row][next_col] += probability[row][col] / 8
        
            probability = new_probability
        
        result = 0
        for row in range(n):
            for col in range(n):   
                result += probability[row][col]

        return result

var knightProbability = function(n, m, row, column) {
    const moves = [
        [1, 2], [1, -2], [-1, 2], [-1, -2],
        [2, 1], [2, -1], [-2, 1], [-2, -1],
    ];
    const memo = [];
    const go = (i, j, k) => memo[k * n * n + i * n + j] ??= (() => {
        if (k === 0) {
            return 1;
        }
        let res = 0;
        for (const [ii, jj] of moves.map(it => [it[0] + i, it[1] + j])) {
            if (ii >= 0 && ii < n && jj >= 0 && jj < n) {
                res += 1 / 8 * go(ii, jj, k - 1);
            }
        }
        return res;
    })();
    return go(row, column, m);
};

class Solution {
   public:
    double knightProbability(int n, int k, int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n) return 0.0;
        if (k == 0) return 1.0;
        if (memo[r * 26 * 101 + c * 101 + k]) return memo[r * 26 * 101 + c * 101 + k];
        double total = 0;
        for (int i = 0; i < 8; ++i) total += knightProbability(n, k - 1, r + dx[i], c + dy[i]);
        return memo[r * 26 * 101 + c * 101 + k] = total / 8;
    }
   private:
    double memo[26 * 26 * 101];
    int dx[8] = {1, 2, 1, 2, -1, -2, -1, -2};
    int dy[8] = {2, 1, -2, -1, 2, 1, -2, -1};
};

class Solution:

    @cache
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []

        if n == 1:
            return [TreeNode()]

        trees = []
       
        for left_nodes in range(1, n, 2):
            right_nodes = n - 1 - left_nodes
           
            left_trees = self.allPossibleFBT(left_nodes)
            right_trees = self.allPossibleFBT(right_nodes)

            for left_tree in left_trees:
                for right_tree in right_trees:
                    root = TreeNode(0, left_tree, right_tree)
                    trees.append(root)
       
        return trees

var allPossibleFBT = _.memoize(function(n) {
    if (n % 2 === 0) {
        return [];
    }
    if (n === 1) {
        return [new TreeNode(0)];
    }
    let ans = [];
    for (let l = 1; n - l - 1 > 0; l += 2) {
        for (const left of allPossibleFBT(l)) {
            for (const right of allPossibleFBT(n - l - 1)) {
                ans.push(new TreeNode(0, left, right));
            }
        }
    }
    return ans;
});

/**
 * 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)
 *     }
 * }
 */

function allPossibleFBT(n: number): Array<TreeNode | null> {
    if (n % 2 === 0) return [];
    const dp: TreeNode[][] = [];
    for (let i = 0; i <= n; i++) {
        dp.push([]);
    }
    dp[1].push(new TreeNode(0));
    for (let i = 3; i <= n; i = i + 2) {
        for (let j = 1; j <= i - 2; j = j + 2) {
            const k = i - 1 - j;
            for (const l of dp[j]) {
                for (const r of dp[k]) {
                    dp[i].push(new TreeNode(0, l, r))
                }
            }
        }
    }
    return dp[n];
};

class Solution {
  List<List<TreeNode>> dp = new ArrayList<>(20);
  public List<TreeNode> allPossibleFBT(int n) {
    if (n%2 == 0) return List.of();
    for (int i = 0; i++ <= n;) {
      dp.add(null);
    }
    dp.set(1, List.of(new TreeNode()));
    return build(n);
  }

  List<TreeNode> build(int n) {
    if (dp.get(n) != null) {
      return dp.get(n);
    }
    List<TreeNode> list = new ArrayList<>();
    for (int i = 1; i < n; i += 2) {
      for (TreeNode l: build(i)) {
        for (TreeNode r: build(n-i-1)) {
          list.add(new TreeNode(0, l, r));
        }
      }
    }
    dp.set(n, list);
    return list;
  }
}

@cache
def POW(x, n):
    if n == 0: return 1
    y = POW(x, n // 2)
    y = y * y
    if n & 1: y = y * x
    return y

class Solution:
    def myPow(self, x: float, n: int) -> float:
        neg = n < 0
        if neg: n = -n
        ans = POW(x, n)
        if neg: ans = 1/ans
        return ans

function myPow(x: number, n: number): number {
    const pow = (c: number, e: number) => {
        if (e === 0) return 1;
        if (e < 0) return 1/pow(c, -1 * e);
        if (e % 2 === 1) return c * pow(c * c, (e-1) /2);
        else return pow(c * c, e/2);
    }
    return pow(x, n);
};

class Solution {
public:
    double myPow(double x, int n) {
        return pow(x,n);
    }
};

myPow=(x,n)=>x**n;

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0 : return 1.0
        if n == 1 : return x
        if n < 0 : return 1/ self.myPow(x , -n)
        k = self.myPow(x , n // 2)
        if n % 2 == 0: return k * k
        return k * k * x

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0)
            return 0;
        if(x == 1 || n == 0)
            return 1;
       
        double res = 1.0;
        if(n < 0) {
            x = 1.0 / x;
            res = x;
            n = -(1 + n); // void integer overflow
        }
       
        while(n > 0){
            if(n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
       
        return res;
    }
};