Це 10 найбільш часто запитуваних задач з масивами DSA на співбесідах:
1. Знайти максимальну суму підмасиву (Алгоритм Кадана)
Задача: Дано масив цілих чисел, потрібно знайти підмасив, сума елементів якого найбільша.
Вхід:
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Рішення:
def maxSubArray(nums):
max_sum = float('-inf')
current_sum = 0
for num in nums:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
Вихід:
maxSubArray(nums) # Вихід: 6
# Пояснення: Підмасив [4, -1, 2, 1] має максимальну суму 6.
2. Знайти відсутнє число
Задача: Дано масив розміру n, що містить числа від 0 до n, знайти відсутнє число.
Вхід:
nums = [3, 0, 1]
Рішення:
def missingNumber(nums):
n = len(nums)
total_sum = n * (n + 1) // 2
return total_sum - sum(nums)
Вихід:
missingNumber(nums) # Вихід: 2
# Пояснення: Числа від 0 до 3: [0, 1, 2, 3]. Відсутнє число — 2.
3. Два числа на суму
Задача: Знайти два числа в масиві, сума яких дорівнює заданій цілі.
Вхід:
nums = [2, 7, 11, 15]
target = 9
Рішення:
def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
diff = target - num
if diff in hashmap:
return [hashmap[diff], i]
hashmap[num] = i
Вихід:
twoSum(nums, target) # Вихід: [0, 1]
# Пояснення: nums[0] + nums[1] = 2 + 7 = 9.
4. Сортування масиву з 0, 1 та 2 (Проблема Голландського національного прапора)
Задача: Відсортувати масив, що містить тільки 0, 1 і 2, не використовуючи додаткової пам'яті.
Вхід:
nums = [2, 0, 2, 1, 1, 0]
Рішення:
def sortColors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
Вихід:
sortColors(nums) # nums стає [0, 0, 1, 1, 2, 2]
5. Знайти повторюване число
Задача: Дано масив з n + 1 цілих чисел, де кожне число знаходиться між 1 і n, знайти повторюване число.
Вхід:
nums = [3, 1, 3, 4, 2]
Рішення:
def findDuplicate(nums):
slow, fast = nums[0], nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Вихід:
findDuplicate(nums) # Вихід: 3
# Пояснення: 3 — це повторюване число в масиві.
6. Злиття двох відсортованих масивів
Задача: Об'єднати два відсортовані масиви в один відсортований масив без використання додаткової пам'яті.
Вхід:
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
Рішення:
def merge(nums1, m, nums2, n):
i, j, k = m - 1, n - 1, m + n - 1
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
Вихід:
merge(nums1, m, nums2, n) # nums1 стає [1, 2, 2, 3, 5, 6]
7. Знайти елемент більшості
Задача: Знайти елемент, який з'являється більше ніж n/2 разів у масиві.
Вхід:
nums = [3, 2, 3]
Рішення:
def majorityElement(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
Вихід:
majorityElement(nums) # Вихід: 3
# Пояснення: 3 з'являється більше ніж n/2 разів (n=3).
8.
Найкращий час для покупки та продажу акцій
Задача: Знайти максимальний прибуток, який можна отримати, купуючи і продаючи акцію один раз.
Вхід:
prices = [7, 1, 5, 3, 6, 4]
Рішення:
def maxProfit(prices):
min_price, max_profit = float('inf'), 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
Вихід:
maxProfit(prices) # Вихід: 5
# Пояснення: Купити за ціною 1 і продати за ціною 6 (6 - 1 = 5).
9. Знайти перетин двох масивів
Задача: Повернути спільні елементи між двома масивами.
Вхід:
nums1 = [4, 9, 5]
nums2 = [9, 4, 9, 8, 4]
Рішення:
def intersection(nums1, nums2):
return list(set(nums1) & set(nums2))
Вихід:
intersection(nums1, nums2) # Вихід: [9, 4]
# Пояснення: Спільні елементи — це 9 та 4.
10. Знайти найдовшу послідовність підрядкових чисел
Задача: Знайти довжину найдовшої послідовності підрядкових цілих чисел в не відсортованому масиві.
Вхід:
nums = [100, 4, 200, 1, 3, 2]
Рішення:
def longestConsecutive(nums):
num_set = set(nums)
longest_streak = 0
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_streak = 1
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak
Вихід:
longestConsecutive(nums) # Вихід: 4
# Пояснення: Найдовша послідовність — це [1, 2, 3, 4].
Перекладено з: [10 Most Frequently Asked Array Questions](https://medium.com/@alensabu12xtz/10-most-frequently-asked-array-questions-781a88ec0c89)