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

class Solution {
public:
    int maxSatisfaction(vector<int>& s) {
        sort(begin(s), end(s));
        int sum = accumulate(begin(s), end(s), 0);
        int n = s.size(), res = 0;
        for(int i = 0; i < n; ++i) res += (i + 1) * s[i];
        for(int i = 0; i < n && sum < 0; ++i){
            res -= sum;
            sum -= s[i];
        }
        return res;
    }
};

/**
 * @param {number[]} satisfaction
 * @return {number}
 */
var maxSatisfaction = function(satisfaction) {
    satisfaction.sort((u, v) => v - u);
    let sum = 0, t = 0;
    for (const s of satisfaction) {
        if (sum + t + s < sum) {
            break;
        }
        sum += t += s;
    }

    return sum;
};

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n = len(satisfaction)
       
        suffix = 0
        res = 0
       
        for idx in range(n-1, -1, -1):
            if suffix + satisfaction[idx] <= 0:
                break
       
            suffix += satisfaction[idx]
            res += suffix
           
        return res

function isScramble(s1: string, s2: string): boolean {
    if (s1 === s2) return true;
    const c1 = s1.split('');
    const c2 = s2.split('');
    c1.sort();
    c2.sort();
    if (c1.join('') !== c2.join('')) return false;
    for (let i = 1; i < s1.length; i++) {
        if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) return true;
        if (isScramble(s1.substring(0, i), s2.substring(s2.length - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length - i))) return true;
    }
    return false;

};

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2) or Counter(s1) != Counter(s2):
            return False
        
        @cache
        def dfs(s1, s2):
            if s1 == s2 or s1 == s2[::-1]:
                return True
            c1 = Counter()
            c2 = Counter()
            
            s2_r = s2[::-1]
            c2_r = Counter()
            for i in range(0, len(s1) - 1):
                c1[s1[i]] += 1
                c2[s2[i]] += 1
                c2_r[s2_r[i]] +=1
                if c1 == c2 and dfs(s1[:i+1], s2[:i+1]) and dfs(s1[i+1:], s2[i+1:]):
                    return True
                if c1 == c2_r and dfs(s1[:i+1], s2_r[:i+1]) and dfs(s1[i+1:], s2_r[i+1:]):
                    return True
        return dfs(s1,s2)

class Solution {
    unordered_map<int, bool> dp;

    bool dfs(const string& s1, const string& s2, int id1, int id2, int len) {
        if (len == 1) {
            return true;
        } else if (len == 0) {
            return false;
        }

        int key = id1*900 + id2*30 + len;
        if (dp.count(key)) return dp[key];


        vector<int> d1(26, 0), d2(26, 0), d3(26, 0);
            
        for (int i = 0; i < len - 1; ++i) {
            int a1 = s1[id1 + i] - 'a', a2 = s2[id2 + i] - 'a', a3 = s2[id2 + len - i - 1] - 'a';

            d1[a1]++;
            d2[a2]++;
            d3[a3]++;

            bool same12 = true;
            for (int i = 0; i < 26 && same12; ++i) {
                if (d1[i] != d2[i])
                    same12 = false;
            }

            bool same13 = true;
            for (int i = 0; i < 26 && same13; ++i) {
                if (d1[i] != d3[i])
                    same13 = false;
            }

            if (same12) {
                if (dfs(s1, s2, id1, id2, i + 1) && dfs(s1, s2, id1 + i + 1, id2 + i + 1, len - i - 1)) {
                    dp[key] = true;
                    return true;
                }
            }

            if (same13) {
                if (dfs(s1, s2, id1, id2 + len - i - 1, i + 1) && dfs(s1, s2, id1 + i + 1, id2, len - i - 1)) {
                    dp[key] = true;
                    return true;
                }
            }
            
        }

        dp[key] = false;
        return false;
    }

public:
    bool isScramble(string s1, string s2) {
        vector<int> d(26, 0);
        for (auto c: s1)
            d[c - 'a']++;
        for (auto c: s2)
            d[c - 'a']--;

        for (auto n: d) if (n != 0) return false;
        return dfs(s1, s2, 0, 0, s1.size());
    }
};

class Solution {
    Map<String, Set<String>> cache = new HashMap<>();
    Map<String, Set<String>> cache2 = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
      
        if (cache.getOrDefault(s1, new HashSet<>()).contains(s2)) return true;
        if (cache2.getOrDefault(s1, new HashSet<>()).contains(s2)) return false;

        if (cache.getOrDefault(s2, new HashSet<>()).contains(s1)) return true;
        if (cache2.getOrDefault(s1, new HashSet<>()).contains(s2)) return false;


        if (s1.equals(s2)) return true;
        if (s1.length() != s2.length()) return false;
      
        int[] map1 = new int[26];
        int cnt = 0;
        for (int i = 0; i < s1.length(); i++){
            map1[s1.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s2.length(); i++){
            map1[s2.charAt(i) - 'a']--;
            if (map1[s2.charAt(i) - 'a'] < 0) return false;
        }

        for (int i = 1; i < s1.length(); i++) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i))
                && isScramble(s1.substring(i), s2.substring(i))) {
                cache.putIfAbsent(s1, new HashSet<>());
                cache.get(s1).add(s2);
                cache.putIfAbsent(s2, new HashSet<>());
                cache.get(s2).add(s1);
                return true;
            }
          
            if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
                && isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) {
                cache.putIfAbsent(s1, new HashSet<>());
                cache.get(s1).add(s2);
                cache.putIfAbsent(s2, new HashSet<>());
                cache.get(s2).add(s1);
                return true;
            }
        }

        cache2.putIfAbsent(s1, new HashSet<>());
        cache2.get(s1).add(s2);
        cache2.putIfAbsent(s2, new HashSet<>());
        cache2.get(s2).add(s1);
      
        return false;
    }
}

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */

const memo = {};

var isScramble = function(s1, s2) {
  const n = s1.length;

  if (n === 1) {
    return s1 === s2;
  }
 
  if (memo[s1+s2] !== undefined) {
    return memo[s1+s2];
  }
 
  let ans = false;
  for (let i = 1; i < n; i++) {
    if (
      isScramble(s1.slice(0, i), s2.slice(0, i)) && isScramble(s1.slice(i), s2.slice(i))
      || isScramble(s1.slice(0, i), s2.slice(n-i)) && isScramble(s1.slice(i), s2.slice(0, n-i))
    ) {
      ans = true;
      break;
    }
  }

  memo[s1+s2] = memo[s2+s1] = ans;

  return ans;
};

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        r = len(pizza)
        c = len(pizza[0])
        mod = int(1e9 + 7)
        @cache
        def dfs(x: int, y: int, k: int) -> int:
            if k == 1:
                return 1 if any(["A" in row[y:] for row in pizza[x:]]) else 0
            if x >= r or y >= c:
                return 0
            
            prev_row_has_apple = False
            ret = 0
            for i in range(x, r):
                if prev_row_has_apple or "A" in pizza[i][y:]:
                    prev_row_has_apple = True
                    ret += dfs(i+1, y, k-1)

            prev_col_has_apple = False
            for j in range(y, c):
                if prev_col_has_apple or "A" in [row[j] for row in pizza[x:]]:
                    prev_col_has_apple = True
                    ret += dfs(x, j+1, k-1)
            return ret%mod
        return dfs(0,0,k)