3 логические задачи по программированию

1. Задача о Комбинациях:

Предположим, у вас есть массив целых чисел и число K. Требуется найти все уникальные комбинации чисел из массива, сумма которых равна K. Каждое число можно использовать только один раз в комбинации.

Пример:

Вход: массив [2, 3, 5, 7], K = 8
Выход: [[2, 3, 3], [5, 3], [2, 2, 2, 2]]

Эта задача проверяет навыки работы с массивами, рекурсивные функции и умение эффективно управлять потоком выполнения программы.

2. Задача о Матрицах:

Дана квадратная матрица. Напишите программу, которая поворачивает матрицу на 90 градусов по часовой стрелке.

Пример:

Вход:
1 2 3
4 5 6
7 8 9

Выход:
7 4 1
8 5 2
9 6 3

Эта задача проверяет умение манипулировать матрицами и использовать индексы массивов для доступа к элементам.

3. Задача о Деревьях:

Реализуйте функцию для проверки сбалансированности двоичного дерева поиска. Сбалансированное дерево - это дерево, в котором высота поддеревьев различается не более чем на единицу.

Пример:

Вход:
   1
  / \
 2   3
    / \
   4   5

Выход: True (сбалансированное дерево)

Вход:
   1
  / 
 2   
  \
   3

Выход: False (несбалансированное дерево)

Эта задача проверяет знание структур данных, таких как деревья, и умение рекурсивно обходить их.

Решение этих задач требует не только знания языка программирования, но и умения разрабатывать эффективные и логичные алгоритмы. Эти задачи часто встречаются на собеседованиях и могут помочь выявить кандидатов с сильными навыками программирования.

Ответы к задачам

1. Задача о Комбинациях:

def find_combinations(nums, K):
	result = []

	def backtrack(start, target, path):
		if target == 0:
			result.append(path)
			return
		for i in range(start, len(nums)):
			if i > start and nums[i] == nums[i - 1]:
				continue
			if nums[i] > target:
				break
			backtrack(i + 1, target - nums[i], path + [nums[i]])

	nums.sort()
	backtrack(0, K, [])
	return result

# Пример использования:
arr = [2, 3, 5, 7]
K = 8
print(find_combinations(arr, K))

2. Задача о Матрицах:

def rotate_matrix(matrix):
	n = len(matrix)

	# Транспонирование матрицы
	for i in range(n):
		for j in range(i, n):
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

	# Реверс строк матрицы
	for i in range(n):
		matrix[i].reverse()

# Пример использования:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_matrix(matrix)
print(matrix)

3. Задача о Деревьях:

class TreeNode:
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

def is_balanced(root):
	def height(node):
		if not node:
			return 0
		left_height = height(node.left)
		right_height = height(node.right)

		if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
			return -1

		return 1 + max(left_height, right_height)

	return height(root) != -1

# Пример использования:
root_balanced = TreeNode(1)
root_balanced.left = TreeNode(2)
root_balanced.right = TreeNode(3)
root_balanced.right.left = TreeNode(4)
root_balanced.right.right = TreeNode(5)

print(is_balanced(root_balanced)) # True

root_unbalanced = TreeNode(1)
root_unbalanced.left = TreeNode(2)
root_unbalanced.left.left = TreeNode(3)

print(is_balanced(root_unbalanced)) # False

Эти ответы предоставляют рабочие решения для каждой из предложенных задач.