23.04.17 Today’s Leetcode

1621. Number of Sets of K Non-Overlapping Line Segments

DP Approach, But failed

def numberOfSets(self, n: int, k: int) -> int:
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(2, n + 1):
            dp[i][i - 1] = 1
        
        for i in range(2, n + 1):
            for j in range(i - 1, 0, -1):
                dp[i][j - 1] = dp[i][j] + (j)
        # for i in
        print(dp)
        return dp[n][k] % (10**9 + 7)

Mathmatical Approach

class Solution:
    def numberOfSets(self, n, k):
        res = 1
        for i in range(1, k * 2 + 1):
            res *= n + k - i
            res //= i
        return res % (10**9 + 7)

739. Daily Temperatures (medium)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack, ans = [], [0] * len(temperatures) 
        for i, temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temp:
                cur = stack.pop()
                ans[cur] = i - cur
            stack.append(i)
        
        return ans

1431. Kids With the Greatest Number of Candies (easy)

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_value = max(candies)
        res = [False] * len(candies)
        for index, candy in enumerate(candies):
            if candy + extraCandies >= max_value:
                res[index] = True
        return res