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

class Solution {
    fun search(nums: IntArray, target: Int): Boolean {
        val n = nums.size
        var lo = 0
        var hi = n - 1
        while (lo <= hi) {
            val mid = lo + (hi - lo) / 2
            if (nums[mid] == target) return true

            // lo <= mid
            // -- target < lo     -> lo = mid + 1
            // -- target > mid    -> lo = mid + 1
            // lo <= target < mid -> hi = mid - 1
            // lo > mid
            // -- target < mid    -> hi = mid - 1
            // -- target >= lo    -> hi = mid - 1
            // mid < target < lo  -> lo = mid + 1
            if (nums[lo] == nums[mid]) {
                lo++
                continue
            }
            if (nums[lo] <= nums[mid] && (target < nums[lo] || target > nums[mid]) || target < nums[lo] && target > nums[mid]) {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
        return false
    }
}

public class Solution {
    private int result = 0;
    private int[] coins;
    public int Change(int amount, int[] coins) {
         this.coins = coins;
         NumFlips(0, amount);
         return result;
    }

    private void NumFlips(int index, int amount)
    {
        if(amount == 0) {
            this.result ++;
            return;
        }

        if(amount < 0 || index >= coins.Length)
            return;

        NumFlips(index, amount - coins[index]);
        NumFlips(index + 1, amount);
    }
}

public class Solution {
    private int[] coins;
    public int Change(int amount, int[] coins) {
         this.coins = coins;
         var dp = new int[coins.Length + 1, amount + 1];
         for(int i = 0; i<= coins.Length; i++)
         {
             for(int j = 0; j <= amount; j++)
             {
                 dp[i,j] = -1;
             }
         }
         return NumFlips(0, amount, dp);
    }

    private int NumFlips(int index, int amount, int[,] dp)
    {
        if(amount == 0) {
            return 1;
        }

        if(amount < 0 || index >= coins.Length)
            return 0;

        if(dp[index, amount] == -1)
        {
            dp[index, amount] = NumFlips(index, amount - coins[index], dp) + NumFlips(index + 1, amount, dp);
        }

        return dp[index,amount];
    }
}

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

var change = function(amount, coins) {
    let now = [1, ...Array(amount).fill(0)];
    for (const c of coins) {
        for (let i = 0; i <= amount; i++) {
            now[i] += i - c >= 0 ? now[i-c] : 0;
        }
    }
    return now[amount];
};

func change(amount int, coins []int) int {
    dp := make([]int,amount+1)
    dp[0] = 1
    
    for _,coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i-coin]
        }
    }
    
    return dp[amount]
}

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
}

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val dp = IntArray(amount + 1)
        dp[0] = 1

        for (coin in coins) {
            for (k in coin..amount) {
                dp[k] += dp[k - coin]
            }
        }

        return dp[amount]
    }
}

public class Solution {
    Dictionary<(int, int), int> memo = new ();

    public int Change(int amount, int[] coins) {
        return exchange(amount, coins, coins.Length - 1);
    }

    int exchange(int amount, int[] coins, int index)
    {
        if (amount < 0 || index < 0)
            return 0;
        if (amount == 0)
            return 1;
        if (!memo.ContainsKey((amount, index)))
        {
            int take = exchange(amount-coins[index], coins, index);
            int notTake = exchange(amount, coins, index-1);
            memo[(amount, index)] = take + notTake;
        }
        return memo[(amount, index)];
    }
}

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector dp(n, vector<int>(amount, -1));
        function<int(int, int)> solve = [&](int i, int s){
            if (s == amount) return 1;
            if (i == n || s > amount) return 0;
            if (dp[i][s] != -1) return dp[i][s];

            return dp[i][s] = solve(i, s + coins[i]) + solve(i + 1, s);
        };
        return solve(0, 0);
    }
};

var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length,
          n = obstacleGrid[0].length;
    let ans = obstacleGrid.map(r => r.map(() => 0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                continue;
            }
            if (!i && !j) {
                ans[i][j] = 1;
            } else {
                if (i > 0) {
                    ans[i][j] += ans[i-1][j];
                }
                if (j > 0) {
                    ans[i][j] += ans[i][j-1];
                }
            }
        }
    }
    
    return ans[m-1][n-1];
};