#hard
Задача: 741. Cherry Pickup

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

public class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][] dp = new int[n][n][2 * n - 1];
        for (int[][] layer : dp) {
            for (int[] row : layer) {
                Arrays.fill(row, Integer.MIN_VALUE);
            }
        }
        dp[0][0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            for (int i1 = Math.max(0, k - n + 1); i1 <= Math.min(n - 1, k); i1++) {
                for (int i2 = Math.max(0, k - n + 1); i2 <= Math.min(n - 1, k); i2++) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1) {
                        int maxCherries = Integer.MIN_VALUE;
                        if (i1 > 0 && i2 > 0) maxCherries = Math.max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]);
                        if (i1 > 0) maxCherries = Math.max(maxCherries, dp[i1 - 1][i2][k - 1]);
                        if (i2 > 0) maxCherries = Math.max(maxCherries, dp[i1][i2 - 1][k - 1]);
                        maxCherries = Math.max(maxCherries, dp[i1][i2][k - 1]);
                        if (maxCherries != Integer.MIN_VALUE) {
                            dp[i1][i2][k] = maxCherries + grid[i1][j1];
                            if (i1 != i2) dp[i1][i2][k] += grid[i2][j2];
                        }
                    }
                }
            }
        }
        
        return Math.max(0, dp[n - 1][n - 1][2 * (n - 1)]);
    }
}

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

#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

public class WordFilter {
    private Map<String, Integer> prefixSuffixMap = new HashMap<>();
    
    public WordFilter(String[] words) {
        for (int index = 0; index < words.length; index++) {
            String word = words[index];
            int length = word.length();
            for (int prefixLength = 1; prefixLength <= length; prefixLength++) {
                for (int suffixLength = 1; suffixLength <= length; suffixLength++) {
                    String prefix = word.substring(0, prefixLength);
                    String suffix = word.substring(length - suffixLength);
                    String key = prefix + "#" + suffix;
                    prefixSuffixMap.put(key, index);
                }
            }
        }
    }
    
    public int f(String pref, String suff) {
        String key = pref + "#" + suff;
        return prefixSuffixMap.getOrDefault(key, -1);
    }
}

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