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

public class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> patternCount = new HashMap<>();

        for (int[] row : matrix) {
            StringBuilder pattern = new StringBuilder();
            for (int cell : row) {
                pattern.append(cell ^ row[0]);
            }
            String key = pattern.toString();
            patternCount.put(key, patternCount.getOrDefault(key, 0) + 1);
        }

        int maxRows = 0;
        for (int count : patternCount.values()) {
            maxRows = Math.max(maxRows, count);
        }

        return maxRows;
    }
}

public class Solution
{
    public int MaxEqualRowsAfterFlips(int[][] matrix)
    {
        Dictionary<string, int> dict = new();
        int m = matrix.Length;
        int n = matrix[0].Length;

        int result = 0;
        for (int i = 0; i < m; i++)
        {
            StringBuilder sb = new();
            int xor = matrix[i][0];
            for (int j = 0; j < n; j++)
            {
                int bit = matrix[i][j] ^ xor;
                sb.Append(bit == 1 ? '1' : '0');
            }
            string str = sb.ToString();
            dict.TryGetValue(str, out int count);
            dict[str] = count + 1;
            result = Math.Max(result, count + 1);
        }

        return result;
    }
}

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        auto countOf = unordered_map<vector<bool>, int>();
        for (const auto& row : matrix) {
            bool toBool[2]; toBool[row[0]] = false; toBool[1 - row[0]] = true;
            auto boolRow = vector<bool>(); boolRow.reserve(row.size());
            for (const auto elem : row) boolRow.emplace_back(toBool[elem]);
            countOf[boolRow]++;
        }
        auto m = 0;
        for (const auto& rowCount : countOf) {
            if (m < rowCount.second) m = rowCount.second;
        }
        return m;
    }
};

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        prefixSum = [0]*n
        for i in range(1, n):
            if nums[i]%2 != nums[i - 1]%2:
                prefixSum[i] = 1 + prefixSum[i - 1]
            else:
                prefixSum[i] = prefixSum[i - 1]

        ans = []
        for left, right in queries:
            if prefixSum[right] - prefixSum[left] == right - left:
                ans.append(True)
            else:
                ans.append(False)

        return ans

class TrieNode {
    Map<Integer, TrieNode> next;
    boolean isEnd;
    int counter;

    public TrieNode() {
        next = new HashMap<>();
        isEnd = false;
        counter = 0;
    }

    public TrieNode addNode(int nextIndex) {
        TrieNode nextNode = next.get(nextIndex);
        if (nextNode == null) {
            nextNode = new TrieNode();
            next.put(nextIndex, nextNode);
        }
        return nextNode;
    }

    public int setEnd(){
        isEnd = true;
        counter++;

        return counter;
    }
}
class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        TrieNode root = new TrieNode();
        int maximumEndNode = 0;
        int fullyRow = 0;
        for (int r = 0; r < matrix.length; r++) {
            TrieNode zeroIdx = root;
            TrieNode oneIdx = root;
            for (int c = 0; c < matrix[0].length; c++) {
                if (matrix[r][c] == 0) {
                    zeroIdx = zeroIdx.addNode(c);
                } else {
                    oneIdx = oneIdx.addNode(c);
                }
            }

            maximumEndNode = Math.max(
                Math.max(
                    zeroIdx.setEnd(),
                    oneIdx.setEnd()
                ),
                maximumEndNode
            );

            if (root == zeroIdx) fullyRow++;
            if (root == oneIdx) fullyRow++;
        }

        return Math.max(
            maximumEndNode,
            fullyRow
        );
    }
}

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        def bs(arr, target, i, j):
            l, r = i, j
            while l < r:
                m =  l + (r - l) // 2
                if arr[m] >= target:
                    r = m
                else:
                    l = m  + 1
            return l

        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)

        def check(word):
            curr_index_in_s = -1
            for l in word:
                if not d[l] or letter_to_curr_index[l] >= len(d[l]):
                    return False
                idx = bs(d[l], curr_index_in_s, letter_to_curr_index[l], len(d[l]) - 1)
                if d[l][idx] <= curr_index_in_s:
                    return False
                curr_index_in_s = d[l][idx]
                letter_to_curr_index[l] = idx + 1
            return True
             
        res = 0
        for word in words:
            letter_to_curr_index = defaultdict(int)
            if check(word):
               res += 1

        return res

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)

        def check(word, curr_index_in_s=0):
            for l in word:
                idx = bisect_left(d[l], curr_index_in_s)
                if idx == len(d[l]):
                    return False
                curr_index_in_s = d[l][idx] + 1
            return True

        return sum(check(word) for word in words)

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Map<Character, TreeSet<Integer>> charFinding = new HashMap<>();
        for (char c =  'a'; c <= 'z'; c++) {
            charFinding.put(c, new TreeSet<>());
            charFinding.get(c).add(1_000_000);
        }

        for (int i = 0; i < s.length(); i++) {
            charFinding.get(s.charAt(i)).add(i);
        }

        int counter = 0;
        for (String word : words) {
            int prevIndex = -1;
            boolean isSubSequence = true;
            for (int i = 0; i < word.length(); i++) {
                Integer finding = null;
                if (i == 0) {
                    finding = charFinding.get(word.charAt(i)).first();
                } else {
                    finding = charFinding.get(word.charAt(i)).higher(prevIndex);
                }
                
                if (finding == 1_000_000) {
                    finding = null;
                }

                if (finding == null) {
                    isSubSequence = false;
                    break;
                }
                prevIndex = finding;
            }

            if (isSubSequence) {
                counter++;
            }
        }

        return counter;
    }
}

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        count1 = defaultdict(int)
        count2 = defaultdict(int)
        n = len(nums1)
        m = len(nums2)
        for i in range(max(n, m)):
            if i < n:
                count1[nums1[i]] +=1

            if i < m:
                count2[nums2[i]] += 1

        ans = 0
        for key, value in count1.items():
            if key % k != 0:
                continue
            
            key//=k
            for i in range(1, int(sqrt(key)) + 1):
                if key%i != 0:
                    continue

                ans += value * count2[i]
                if i != key//i:
                    ans += value * count2[key//i]
        return ans

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m = len(box)
        n = len(box[0])

        for i in range(m):
            p1 = n - 1
            for j in range(n - 1, -1, -1):
                if box[i][j] == '*':
                    p1 = j - 1
                    continue

                if box[i][j] == '#':
                    box[i][j], box[i][p1] = box[i][p1], box[i][j]
                    p1 -= 1
        
        grid = [['' for _ in range(m)] for _ in range(n)]
        for i in range(n):
            for j in range(m - 1, -1, -1):
                grid[i][m - 1 - j] = box[j][i]

        return grid