Java | LeetCode
Задача: 1424. Diagonal Traverse II
Сложность: medium
Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.
Пример:
Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
👨💻 Алгоритм:
1⃣Инициализируйте очередь с (0, 0) и список ответов ans.
2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.
3⃣Верните ans.
😎 Решение:
class Solution {
public int[] findDiagonalOrder(List<List<Integer>> nums) {
Queue<Pair<Integer, Integer>> queue = new LinkedList();
queue.offer(new Pair(0, 0));
List<Integer> ans = new ArrayList();
while (!queue.isEmpty()) {
Pair<Integer, Integer> p = queue.poll();
int row = p.getKey();
int col = p.getValue();
ans.add(nums.get(row).get(col));
if (col == 0 && row + 1 < nums.size()) {
queue.offer(new Pair(row + 1, col));
}
if (col + 1 < nums.get(row).size()) {
queue.offer(new Pair(row, col + 1));
}
}
int[] result = new int[ans.size()];
int i = 0;
for (int num : ans) {
result[i] = num;
i++;
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 480 ·