Упражнения на Java: найдите максимальное число внутри числа в окне
Java Basic: упражнение 174 с решением
Напишите программу на Java, чтобы найти максимальное число внутри числа в окне (размер k) при каждом перемещении в заданном массиве целых чисел с повторяющимися числами. Переместить окно с начала массива.
{| 1, 2, 3 |, 4, 5, 6, 7, 8, 8} -> Максимум возврата 3
{1, | 2, 3, 4 |, 5, 6, 7, 8, 8} -> Максимум возврата 4
{1, 2, | 3, 4, 5 |, 6, 7, 8, 8} -> Максимум возврата 5
{1, 2, 3, | 4, 5, 6 |, 7, 8, 8} -> Максимум возврата 6
{1, 2, 3, 4, | 5, 6, 7 |, 8, 8} -> Максимум возврата 7
{1, 2, 3, 4, 5, | 6, 7, 8 |, 8} -> Максимум возврата 8
{1, 2, 3, 4, 5, 6, | 7, 8, 8 |} -> Максимум возврата 8
Массив результатов {3, 4, 5, 6, 7, 8, 8}
Пример решения:
Java-код:
import java.util.*;
import java.util.Arrays;
import java.util.LinkedList;
public class Solution {
public static void main(String[] args) {
int[] main_array = {1, 2, 3, 4, 5, 6, 7, 8, 8};
int k = 3;
System.out.println("\nOriginal array: "+Arrays.toString(main_array));
System.out.println("\nValue of k: "+k);
System.out.println("\nResult: ");
ArrayList result = max_slide_window(main_array,k);
for (int i = 0; i < result.size(); i++) {
System.out.println(result.get(i));
}
}
public static ArrayList max_slide_window(int[] main_array, int k) {
ArrayList rst_arra = new ArrayList();
if (main_array == null || main_array.length == 0 || k < 0) {
return rst_arra;
}
Deque deque_num = new LinkedList();
for (int i = 0; i < k; i++) {
while (!deque_num.isEmpty() && main_array[deque_num.peekLast()] <= main_array[i]) {
deque_num.pollLast();
}
deque_num.offerLast(i);
}
for (int i = k; i < main_array.length; i++) {
rst_arra.add(main_array[deque_num.peekFirst()]);
if (!deque_num.isEmpty() && deque_num.peekFirst() <= i - k) {
deque_num.pollFirst();
}
while (!deque_num.isEmpty() && main_array[deque_num.peekLast()] <= main_array[i]) {
deque_num.pollLast();
}
deque_num.offerLast(i);
}
rst_arra.add(main_array[deque_num.peekFirst()]);
return rst_arra;
}
}
Пример вывода:
Исходный массив: [1, 2, 3, 4, 5, 6, 7, 8, 8] Значение к: 3 Результат: 3 4 5 6 7 8 8
Блок - схема:
Редактор кода Java:
Компания: Zenefits Google Amazon
Внесите свой код и комментарии через Disqus.
Предыдущий: Напишите программу на Java, чтобы найти медиану числа внутри окна (размер k) при каждом перемещении в заданном массиве целых чисел с повторяющимися числами. Переместить окно с начала массива.
Далее: Напишите Java-программу для удаления указанного узла в середине односвязного списка.
Каков уровень сложности этого упражнения?
Новый контент: Composer: менеджер зависимостей для PHP , R программирования