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

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        def beautifulSubsetsOfArithmeticSequence(sequence):
            n = len(sequence)
            dp = n * [0]
            for i in range(n):
                prev2 = dp[i - 2] if i - 2 >= 0 else 1
                prev1 = dp[i - 1] if i - 1 >= 0 else 1
                take = ((1 << counter[sequence[i]]) - 1) * prev2
                notTake = prev1
                dp[i] = take + notTake
            return dp[n - 1]
        
        counter = Counter(nums)
        ans = 1
        for num in counter:
            if num - k not in counter: #num is the start of an arithmetic sequence
                sequence = []
                while num in counter:
                    sequence.append(num)
                    num += k
                ans *= beautifulSubsetsOfArithmeticSequence(sequence)
        return ans - 1 # "- 1" is to eliminate the empty set from the count

class Solution {
public:
    bool isBeauty(vector<int> &vIn, int num, int k)
    {
        for(auto &it: vIn) if(abs(it-num) == k) return false;
        return true;
    }
    void bt(vector<int>&vCur, vector<int>& nums, int idx, int k, int &re)
    {
        while(idx<nums.size())
        {
            if(isBeauty(vCur,nums[idx],k))
            {
                vCur.push_back(nums[idx]);
                ++re; ++idx;
                bt(vCur,nums,idx,k,re);
                vCur.pop_back();
            }
            else  ++idx;
        }
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        int re = 0;
        vector<int> vCur;
        bt(vCur,nums,0,k,re);
        return re;
    }
};

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        
        def isBeautiful(arr, value):
            for el in arr:
                if abs(el - value) == k:
                    return False
            return True
        
        self.result = 0
        n = len(nums)
        def backtracking(i, arr):
            if i == n:
                return
            
            if isBeautiful(arr, nums[i]):
                self.result += 1
                arr.append(nums[i])
                backtracking(i + 1, arr)
                arr.pop()

            backtracking(i+1, arr)

        backtracking(0, [])     
        
        return self.result

public class Solution {
    public bool IsBeautifulSubset(List<int> nums)
    {
        for(int i = 0; i<nums.Count-1; i++)
        {
            for(int j = i+1; j<nums.Count; j++)
            {
                if(Math.Abs(nums[i] - nums[j]) == p)
                {
                    return false;
                }
            }
        }
        return true;
    }

    public void CountBeautifulSubsets(int[] nums, List<int> temp, int index)
    {
        for(int i = index; i<nums.Length; i++)
        {
            temp.Add(nums[i]);
            if(IsBeautifulSubset(temp))
            {
                result++;
            }
            CountBeautifulSubsets(nums, temp, i+1);
            temp.RemoveAt(temp.Count - 1);
        }
    }

    public static int p = 0;
    public static int result = 0;

    public int BeautifulSubsets(int[] nums, int k) {
        p = k;
        result = 0;
        Array.Sort(nums);
        List<int> temp = new List<int>();
        CountBeautifulSubsets(nums, temp, 0);
        return result;
    }
}

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        capacity = defaultdict(int)
        totalPoint = 0
        for l in letters:
            capacity[l] += 1
            totalPoint += score[ord(l) - ord('a')]

        def validWord(word):
            freq = defaultdict(int)
            for char in word:
                freq[char] += 1
                if freq[char] > capacity[char]:
                    return False

            return True

        def calculatePoint():
            remaining = 0
            for key, value in capacity.items():
                remaining += score[ord(key) - ord('a')]*value

            return totalPoint - remaining

        n = len(words)
        ans = 0
        def backtrack(index):
            if index == n:
                nonlocal ans
                ans = max(ans, calculatePoint())
                return False

            if validWord(words[index]):
                for char in words[index]:
                    capacity[char] -= 1

                backtrack(index + 1)
                for char in words[index]:
                    capacity[char] += 1

            backtrack(index + 1)

        backtrack(0)
        return ans