#medium
Задача: 508. Most Frequent Subtree Sum

Дано корень бинарного дерева, вернуть наиболее часто встречающуюся сумму поддерева. Если есть несколько таких значений, вернуть все значения с наибольшей частотой в любом порядке.

Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел).

Пример:

Input: root = [5,2,-3]
Output: [2,-3,4]

👨‍💻 Алгоритм:

1⃣Инициализация переменных
Инициализируйте переменные sumFreq для хранения частоты всех сумм поддеревьев. Инициализируйте maxFreq для хранения максимальной частоты. Создайте массив maxFreqSums для хранения всех сумм поддеревьев, частота которых равна максимальной.

2⃣Обход дерева и вычисление сумм
Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

3⃣Сборка результата
Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎 Решение:

class Solution {
    private HashMap<Integer, Integer> sumFreq = new HashMap<Integer, Integer>();
    private Integer maxFreq = 0;
    
    private int subtreeSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftSubtreeSum = subtreeSum(root.left);
        int rightSubtreeSum = subtreeSum(root.right);

        int currSum = root.val + leftSubtreeSum + rightSubtreeSum;
        
        sumFreq.put(currSum, sumFreq.getOrDefault(currSum, 0) + 1);
        maxFreq = Math.max(maxFreq, sumFreq.get(currSum));
        return currSum;
    }
    
    public int[] findFrequentTreeSum(TreeNode root) {
        subtreeSum(root);
        
        List<Integer> ansList = new ArrayList<Integer>(); 
        for (Map.Entry<Integer, Integer> mapElement : sumFreq.entrySet()) {
            Integer sum = mapElement.getKey();
            Integer freq = mapElement.getValue();
            
            if (freq == maxFreq) {
                ansList.add(sum);
            }
        }
        
        int maxFreqSums[] = new int[ansList.size()];
        for (int i = 0; i < ansList.size(); i++) {
            maxFreqSums[i] =  ansList.get(i).intValue();
        }
        
        return maxFreqSums;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 723. Candy Crush

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

👨‍💻 Алгоритм:

1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления.

2⃣Удалите отмеченные конфеты, установив их значение в 0.

3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления.

😎 Решение:

public class Solution {
    public int[][] candyCrush(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        boolean stable = false;

        while (!stable) {
            stable = true;
            boolean[][] crush = new boolean[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n - 2; j++) {
                    int v = Math.abs(board[i][j]);
                    if (v != 0 && v == Math.abs(board[i][j + 1]) && v == Math.abs(board[i][j + 2])) {
                        stable = false;
                        crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
                    }
                }
            }

            for (int i = 0; i < m - 2; i++) {
                for (int j = 0; j < n; j++) {
                    int v = Math.abs(board[i][j]);
                    if (v != 0 && v == Math.abs(board[i + 1][j]) && v == Math.abs(board[i + 2][j])) {
                        stable = false;
                        crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
                    }
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (crush[i][j]) {
                        board[i][j] = 0;
                    }
                }
            }

            for (int j = 0; j < n; j++) {
                int idx = m - 1;
                for (int i = m - 1; i >= 0; i--) {
                    if (board[i][j] != 0) {
                        board[idx][j] = board[i][j];
                        idx--;
                    }
                }
                for (int i = idx; i >= 0; i--) {
                    board[i][j] = 0;
                }
            }
        }

        return board;
    }
}

Ставь 👍 и забирай 📚 Базу знаний