О чем урок
Основная цель урока — познакомить тебя с техникой «непересекающиеся окна», которая позволяет решать множество задач одним и тем же способом. Это поможет тебе не ошибаться на собеседованиях и писать решения с первого раза! А также ты:
- Решишь задачу с собеседования в крупную технологическую компанию (BigTech).
- Научишься решать задачи на тему «непересекающиеся окна» с первого раза.
- Узнаешь, как мыслит интервьюер на собеседовании.
Пример задачи с собеседования
Представь, что ты на собеседовании в компании своей мечты. Ты заходишь на видеозвонок и знакомишься с интервьюером. Он сообщает, что тебе нужно решить две алгоритмические задачи за 60 минут, и озвучивает условие первой задачи…
Условие
Дан отсортированный по возрастанию массив уникальных чисел nums. Нужно объединить подряд идущие числа по следующим правилам:
"x->y", если есть непрерывная последовательность, увеличивающаяся на 1, отxдоy"x", если соседние элементы отличаются более чем на 1
Пример
Ввод: nums = [1,2,3,4,5,8,10,15,16,20] Вывод: ["1->5","8","10","15->16","20"]
В чём сложность задачи
На первый взгляд задача несложная, но без знания определённых паттернов можно написать код, в котором трудно разобраться, хотя он и будет работать:
using System;
using System.Collections.Generic;
public class Solution
{
public static List<string> SummaryRanges(List<int> nums)
{
List<string> result = new List<string>();
int start = 0;
while (start < nums.Count)
{
int end = start;
// Найти диапазон последовательных чисел
while (end + 1 < nums.Count && nums[end] + 1 == nums[end + 1])
{
end++;
}
// Добавить результат в список
if (nums[start] == nums[end])
{
result.Add(nums[start].ToString());
}
else
{
result.Add($"{nums[start]}->{nums[end]}");
}
// Переместить старт на следующий элемент после текущего диапазона
start = end + 1;
}
return result;
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> summaryRanges(vector<int>& nums) {
vector<string> result;
if (nums.empty()) return result;
int start = 0, end = 0;
while (start < nums.size() && end < nums.size()) {
if (end + 1 < nums.size() && nums[end] + 1 == nums[end + 1]) {
end += 1;
} else {
if (nums[start] == nums[end]) {
result.push_back(to_string(nums[start]));
} else {
result.push_back(to_string(nums[start]) + "->" + to_string(nums[end]));
}
end += 1;
start = end;
}
}
return result;
}package main
import (
"strconv"
)
func summaryRanges(nums []int) []string {
var result []string
if len(nums) == 0 {
return result
}
start, end := 0, 0
for start < len(nums) && end < len(nums) {
if end+1 < len(nums) && nums[end]+1 == nums[end+1] {
end += 1
} else {
if nums[start] == nums[end] {
result = append(result, strconv.Itoa(nums[start]))
} else {
rangeStr := strconv.Itoa(nums[start]) + "->" + strconv.Itoa(nums[end])
result = append(result, rangeStr)
}
end += 1
start = end
}
}
return result
}import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> summaryRanges(List<Integer> nums) {
List<String> result = new ArrayList<>();
if (nums.isEmpty()) return result;
int start = 0, end = 0;
while (start < nums.size() && end < nums.size()) {
if (end + 1 < nums.size() && nums.get(end) + 1 == nums.get(end + 1)) {
end += 1;
} else {
if (nums.get(start).equals(nums.get(end))) {
result.add(String.valueOf(nums.get(start)));
} else {
result.add(nums.get(start) + "->" + nums.get(end));
}
end += 1;
start = end;
}
}
return result;
}
}def summaryRanges(nums: List[int]) -> List[str]:
result = []
start, end = 0, 0
while start < len(nums) and end < len(nums):
if (end + 1) < len(nums) and nums[end] + 1 == nums[end + 1]:
end += 1
else:
if nums[start] == nums[end]:
result.append(str(nums[start]))
else:
result.append(f"{nums[start]}->{nums[end]}")
end += 1
start = end
return resultfunction summaryRanges(nums) {
const result = [];
let start = 0, end = 0;
while (start < nums.length && end < nums.length) {
if (end + 1 < nums.length && nums[end] + 1 === nums[end + 1]) {
end += 1;
} else {
if (nums[start] === nums[end]) {
result.push(nums[start].toString());
} else {
result.push(`${nums[start]}->${nums[end]}`);
}
end += 1;
start = end;
}
}
return result;
}На собеседовании оценивается не только правильность решения, но и чистота кода, а также умение объяснить своё решение. Приятно, когда твои решения выглядят аккуратно и понятно.
Как решать задачу
Заметим, что последовательности чисел можно представить как «окна», и когда одно окно заканчивается, начинается другое. Это ключевое свойство мы и будем использовать.
Алгоритм решения:
- Заводим два указателя
- Двигаем правый указатель
- Когда движение правого указателя невозможно, добавляем в результат:
"{nums[l]}->{nums[r]}", еслиl != r"{nums[l]}", еслиl == r
- Сдвигаем указатели:
- Повторяем шаги 2–4, пока
lне выйдет за границы массива
using System;
using System.Collections.Generic;
public class Solution
{
public static List<string> SummaryRanges(List<int> nums)
{
int l = 0;
int r = 0;
List<string> result = new List<string>();
while (l < nums.Count)
{
while (r + 1 < nums.Count && nums[r] + 1 == nums[r + 1])
{
r++;
}
if (l != r)
{
result.Add($"{nums[l]}->{nums[r]}");
}
else
{
result.Add($"{nums[l]}");
}
l = r + 1;
r = r + 1;
}
return result;
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> summaryRanges(vector<int>& nums) {
int l = 0;
int r = 0;
vector<string> result;
while (l < nums.size()) {
while (r + 1 < nums.size() && nums[r] + 1 == nums[r + 1]) {
r += 1;
}
if (l != r) {
result.push_back(to_string(nums[l]) + "->" + to_string(nums[r]));
} else {
result.push_back(to_string(nums[l]));
}
l = r + 1;
r = r + 1;
}
return result;
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> summaryRanges(vector<int>& nums) {
int l = 0;
int r = 0;
vector<string> result;
while (l < nums.size()) {
while (r + 1 < nums.size() && nums[r] + 1 == nums[r + 1]) {
r += 1;
}
if (l != r) {
result.push_back(to_string(nums[l]) + "->" + to_string(nums[r]));
} else {
result.push_back(to_string(nums[l]));
}
l = r + 1;
r = r + 1;
}
return result;
}package main
import (
"strconv"
)
func summaryRanges(nums []int) []string {
l := 0
r := 0
var result []string
for l < len(nums) {
for r+1 < len(nums) && nums[r]+1 == nums[r+1] {
r += 1
}
if l != r {
rangeStr := strconv.Itoa(nums[l]) + "->" + strconv.Itoa(nums[r])
result = append(result, rangeStr)
} else {
result = append(result, strconv.Itoa(nums[l]))
}
l = r + 1
r = r + 1
}
return result
}from typing import List
def summaryRanges(nums: List[int]) -> List[str]:
l = 0
r = 0
result = []
while l < len(nums):
while r + 1 < len(nums) and nums[r] + 1 == nums[r + 1]:
r += 1
if l != r:
result.append(f"{nums[l]}->{nums[r]}")
else:
result.append(f"{nums[l]}")
l = r + 1
r = r + 1
return resultfunction summaryRanges(nums) {
let l = 0;
let r = 0;
const result = [];
while (l < nums.length) {
while (r + 1 < nums.length && nums[r] + 1 === nums[r + 1]) {
r += 1;
}
if (l !== r) {
result.push(`${nums[l]}->${nums[r]}`);
} else {
result.push(`${nums[l]}`);
}
l = r + 1;
r = r + 1;
}
return result;
}Паттерн «Непересекающиеся окна»
Мы использовали паттерн, который применим к целому классу задач. Теперь вместо запоминания решений для каждой задачи, ты можешь использовать этот универсальный подход. А вот и общий шаблон с использованием этого паттерна:
using System;
using System.Collections.Generic;
public class Solution
{
/**
* @param nums - вектор целых чисел
* @return ReturnType - замените ReturnType на фактический тип возвращаемого значения
*/
public static List<ReturnType> SomeFunction(int[] nums)
{
int l = 0;
int r = 0;
// Замените ReturnType на фактический тип элементов
List<ReturnType> result = new List<int>();
while (l < nums.Length)
{
while (r + 1 < nums.Length && условие_продолжения_окна)
{
r += 1;
}
// Обработка текущего окна и обновление результата
// ...
// Сдвиг указателей для следующего окна
l = r + 1;
r = r + 1;
}
return result;
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
/**
* @param nums - вектор целых чисел
* @return ReturnType - замените ReturnType на фактический тип возвращаемого значения
*/
vector<ReturnType> someFunction(const vector<int>& nums) { // Замените ReturnType на нужный тип
int l = 0;
int r = 0;
vector<ReturnType> result; // Замените ReturnType на фактический тип элементов
while (l < nums.size()) {
while (r + 1 < nums.size() && условие_продолжения_окна) {
r += 1;
}
// Обработка текущего окна и обновление результата
// ...
// Сдвиг указателей для следующего окна
l = r + 1;
r = r + 1;
}
return result;
}package main
import (
// Импортируйте другие необходимые пакеты
)
// Замените ReturnType на фактический тип возвращаемого значения
func someFunction(nums []int) []ReturnType { // Замените ReturnType на нужный тип
l := 0
r := 0
var result []ReturnType // Замените ReturnType на фактический тип элементов
for l < len(nums) {
for r+1 < len(nums) && условие_продолжения_окна {
r += 1
}
// Обработка текущего окна и обновление результата
// ...
// Сдвиг указателей для следующего окна
l = r + 1
r = r + 1
}
return result // Замените на соответствующее значение
}import java.util.ArrayList;
import java.util.List;
public class SomeFunctionSolution {
/**
* @param nums - список целых чисел
* @return ReturnType - замените ReturnType на фактический тип возвращаемого значения
*/
public List<ReturnType> someFunction(List<Integer> nums) { // Замените ReturnType на нужный тип
int l = 0;
int r = 0;
List<ReturnType> result = new ArrayList<>(); // Замените ReturnType на фактический тип элементов
while (l < nums.size()) {
while (r + 1 < nums.size() && условие_продолжения_окна) {
r += 1;
}
// Обработка текущего окна и обновление результата
// ...
// Сдвиг указателей для следующего окна
l = r + 1;
r = r + 1;
}
return null; // Замените на `result` или соответствующее значение
}
}from typing import List
def someFunction(nums: List[int]) -> ReturnType:
l = 0
r = 0
result = []
while l < len(nums):
while r + 1 < len(nums) and условие_продолжения_окна:
r += 1
# Обработка текущего окна и обновление результата
# ...
# Сдвиг указателей для следующего окна
l = r + 1
r = r + 1
return resultfunction someFunction(nums) {
let l = 0;
let r = 0;
const result = [];
while (l < nums.length) {
while (r + 1 < nums.length && условие_продолжения_окна) {
r += 1;
}
// Обработка текущего окна и обновление результата
// ...
// Сдвиг указателей для следующего окна
l = r + 1;
r = r + 1;
}
return result;
}В этом шаблоне тебе нужно определить условие продолжения окна и как обновлять результат на каждом шаге.
В некоторых задачах шаблон может казаться избыточным и не во всех задачах мы получим самое красивое решение, но тут цель в другом: получить решение, которое работает с первого раза и не запоминать каждый раз новую задачу, а иметь универсальный ключ!
Всегда ли решение паттерном оптимальное?
Рассмотрим задачу: дан массив nums из нулей и единиц, нужно найти длину самой длинной последовательности из подряд идущих единиц. Например, для nums = [1,1,0,0,1,1,1,0] ответ — 3.
Можно использовать тот же паттерн «непересекающихся окон», но иногда есть более простые решения. Например:
using System;
using System.Collections.Generic;
public class Solution
{
public static int LongestConsecutiveOnes(int[] nums)
{
int maxCount = 0; // Максимальное количество подряд идущих единиц
int count = 0; // Текущее количество подряд идущих единиц
foreach (int num in nums)
{
if (num == 1)
{
count++;
// Обновляем максимальное значение при необходимости
maxCount = Math.Max(maxCount, count);
}
else
{
// Сбрасываем счетчик, если встречается 0
count = 0;
}
}
return maxCount;
}
}#include <iostream>
#include <vector>
#include <algorithm> // Для std::max
using namespace std;
/**
* Находит длину самой длинной последовательности единиц в массиве.
*
* @param nums - Вектор целых чисел, содержащий 0 и 1.
* @return int - Максимальное количество подряд идущих единиц.
*/
int longestConsecutiveOnes(const vector<int>& nums) {
int maxCount = 0; // Максимальное количество подряд идущих единиц
int count = 0; // Текущее количество подряд идущих единиц
for (int num : nums) {
if (num == 1) {
count += 1;
// Обновляем максимальное значение при необходимости
maxCount = max(maxCount, count);
} else {
count = 0; // Сбрасываем счетчик, если встречается 0
}
}
return maxCount;
}package main
import (
)
/**
* Находит длину самой длинной последовательности единиц в массиве.
*/
/**
* longestConsecutiveOnes находит длину самой длинной последовательности единиц в срезе.
*
* @param nums - Срез целых чисел, содержащий 0 и 1.
* @return int - Максимальное количество подряд идущих единиц.
*/
func longestConsecutiveOnes(nums []int) int {
maxCount := 0 // Максимальное количество подряд идущих единиц
count := 0 // Текущее количество подряд идущих единиц
for _, num := range nums {
if num == 1 {
count += 1
if count > maxCount {
// Обновляем максимальное значение при необходимости
maxCount = count
}
} else {
count = 0 // Сбрасываем счетчик, если встречается 0
}
}
return maxCount
}import java.util.Arrays;
import java.util.List;
/**
* Находит длину самой длинной последовательности единиц в массиве.
*/
class LongestConsecutiveOnes {
/**
* Находит длину самой длинной последовательности единиц в массиве.
*
* @param nums - Массив целых чисел, содержащий 0 и 1.
* @return int - Максимальное количество подряд идущих единиц.
*/
public int longestConsecutiveOnes(int[] nums) {
int maxCount = 0; // Максимальное количество подряд идущих единиц
int count = 0; // Текущее количество подряд идущих единиц
for (int num : nums) {
if (num == 1) {
count += 1;
// Обновляем максимальное значение при необходимости
maxCount = Math.max(maxCount, count);
} else {
count = 0; // Сбрасываем счетчик, если встречается 0
}
}
return maxCount;
}
}def longest_consecutive_ones(nums: List[int]) -> int:
max_count = 0 # Максимальное количество подряд идущих единиц
count = 0 # Текущее количество подряд идущих единиц
for num in nums:
if num == 1:
count += 1
# Обновляем максимальное значение при необходимости
max_count = max(max_count, count)
else:
count = 0 # Сбрасываем счетчик, если встречается 0
return max_count/**
* Находит длину самой длинной последовательности единиц в массиве.
*
* @param {number[]} nums - Массив целых чисел, содержащий 0 и 1.
* @return {number} - Максимальное количество подряд идущих единиц.
*/
function longestConsecutiveOnes(nums) {
let maxCount = 0; // Максимальное количество подряд идущих единиц
let count = 0; // Текущее количество подряд идущих единиц
for (let num of nums) {
if (num === 1) {
count += 1;
if (count > maxCount) {
// Обновляем максимальное значение при необходимости
maxCount = count;
}
} else {
count = 0; // Сбрасываем счетчик, если встречается 0
}
}
return maxCount;
}Решение выше выглядит более простым, чем то, которое мы получим, следуя паттерну:
using System;
using System.Collections.Generic;
public class Solution
{
public static int LongestConsecutiveOnes(List<int> nums)
{
int l = 0;
int r = 0;
int result = 0;
while (l < nums.Count)
{
while (r + 1 < nums.Count && nums[r] == nums[r + 1])
{
r += 1;
}
if (nums[r] == 1)
{
result = Math.Max(result, r - l + 1);
}
l = r + 1;
r = r + 1;
}
return result;
}
}#include <iostream>
#include <vector>
using namespace std;
int longestConsecutiveOnes(const vector<int>& nums) {
int l = 0;
int r = 0;
int result = 0;
while (l < nums.size()) {
while (r + 1 < nums.size() && nums[r] == nums[r + 1]) {
r += 1;
}
if (nums[r] == 1) {
result = max(result, r - l + 1);
}
l = r + 1;
r = r + 1;
}
return result;
}func longestConsecutiveOnes(nums []int) int {
l, r, result := 0, 0, 0
for l < len(nums) {
for r+1 < len(nums) && nums[r] == nums[r+1] {
r++
}
if nums[r] == 1 {
if r-l+1 > result {
result = r - l + 1
}
}
l = r + 1
r = r + 1
}
return result
}import java.util.List;
public class Solution {
public static int longestConsecutiveOnes(List<Integer> nums) {
int l = 0;
int r = 0;
int result = 0;
while (l < nums.size()) {
while (r + 1 < nums.size() && nums.get(r).equals(nums.get(r + 1))) {
r++;
}
if (nums.get(r).equals(1)) {
result = Math.max(result, r - l + 1);
}
l = r + 1;
r = r + 1;
}
return result;
}
}def longest_consecutive_cnes(nums: List[int]) -> int:
l = 0
r = 0
result = 0
while l < len(nums):
while r + 1 < len(nums) and nums[r] == nums[r + 1]:
r += 1
if nums[r] == 1:
result = max(result, r - l + 1)
l = r + 1
r = r + 1function longestConsecutiveOnes(nums) {
let l = 0;
let r = 0;
let result = 0;
while (l < nums.length) {
while (r + 1 < nums.length && nums[r] === nums[r + 1]) {
r++;
}
if (nums[r] === 1) {
result = Math.max(result, r - l + 1);
}
l = r + 1;
r = r + 1;
}
return result;
}В паттерне так же есть сложность додуматься до идеи: не нужно пропускать как-то специально нули, а можно тоже объединить их в окно. Главное, при обновлении ответа учесть, что нужно обновлять окна только из подряд идущих единиц, а нули игнорировать
Важно отметить, что оба решения оптимальны и оба интервьюер примет на собеседовании! Не стоит путать красоту кода и оптимальность решения. Если код красивый, но не оптимальный, то к следующей задачке тебя не допустят, а вот если наоборот, то все ОК, ведь главное – рабочее решение, а красота уже потом.
Итог
Моя цель — дать тебе инструмент для решения множества задач, а не только одной. Хотя важно рассматривать разные варианты решений, универсальные паттерны помогут тебе быстрее находить ответы. Тренируйся применять их, но всегда выбирай решение, которое считаешь лучшим для себя!
Бонус: мир глазами интервьюера
Знаешь ли ты, что интервьюеры часто имеют перед собой эталонное решение? Особенно если они дают эту задачу впервые.
Чтобы интервьюер был уверен в твоём решении и не тратил время на его проверку, важно чётко объяснять свои мысли. Например:
"Я использую технику плавающего окна. Завожу два указателя l и r, изначально указывающие на первый элемент. Пока следующий элемент последовательный (nums[r] + 1 == nums[r + 1]), сдвигаю r. Затем добавляю диапазон в результат. Сдвигаю l и r на r + 1 и повторяю, пока l не выйдет за границы массива. Моё решение имеет временную сложность O(n), так как каждый элемент обрабатывается один раз. Дополнительная память — O(1) для хранения результата."
Объяснять ход решения задачи и оценивать решение по времени и памяти является хорошей практикой перед написанием кода, поэтому важно уметь кратко формулировать идею решения задачи!
Что дальше?
А теперь, время закрепить все полученные знания на задачах!