Программирование всегда связано с решением различных задач. Я подготовил список из шести различных заданий и отсортировал их по сложности решения. Первая — самая простая, шестая — самая сложная. Сможете разобраться со всеми?
В конце статьи я также разместил решения, выполненные на языке PHP. Вы же можете выбрать для этого другой язык.
1. Плюс минус
Давайте начнем с относительно простой задачи, взятой с HackerRank. Ее можно назвать разминочной.
Дан массив целых чисел. Вычислите дроби его элементов, являющихся положительными, отрицательными и нулевыми. Выведите на печать десятичное значение каждой дроби в новой строке. Имейте в виду, что это задача с высокой степенью точности. Примеры масштабированы до шести знаков после точки, поэтому диапазон допустимых ошибок составляет до 10^-4 . Например, дан массив arr=[1, 1, 0.-1, -1]. В нем пять элементов, два из которых положительные, два отрицательные и 1 равен нулю. Их отношения будут следующими 2/5 = 0.400000, 2/5 = 0.400000 и 1/5 = 0.200000. На печати они должны выглядеть так: см. скриншот.
2. Сумма двух
Эта задача, взятая с LeetCode, считается простой.
Дан массив целых чисел, верните индексы двух чисел, сумма которых будет соответствовать целевому значению. Имейте в виду, что каждый набор исходных данных имеет только одно решение, при этом нельзя использовать один элемент дважды.
3. Самое большое палиндромное произведение
Это еще одна простая задача, которую я взял с Project Euler. На данный момент она уже решена более чем 455 000 людьми:
Палиндромное число читается одинаково в обе стороны. Самое большое палиндромное произведение, полученное из двух двухзначных чисел — это 9009=91*99. Найдите самый большой палиндром, который можно получить из произведения двух трехзначных чисел.
4. Различные значения
Следующая задача взята с Project Euler. Она уже несколько сложнее предыдущей и решена только 100 000 пользователями.
Рассмотрите все целочисленные комбинации a^b при условии, что 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5. Если затем их расположить по порядку, удалив все повторения, то мы получим следующую последовательность из 15 различных значений. Сколько таких различных значений содержится в последовательности, полученной согласно условию 2 ≤ a ≤ 100 и 2 ≤ b ≤ 100?
5. Постоянная Капрекара
Поздравляю тех, кто дошел до этого этапа! Настало время приступить к по-настоящему серьезной задаче, которая была предоставлена Coderbyte.
Пусть функция KaprekarsConstant(num) получает для передачи параметр num — четырехзначное число с как минимум двумя различными цифрами. Программа должна производить с этим числом следующие действия: упорядочивать его цифры по возрастанию и убыванию (добавляя нули для получения четырехзначного числа), а затем вычитать меньшее число из большего. Далее она должна повторять предыдущий шаг. Выполнение этого процесса всегда в итоге будет приводить вас к результату 6174 (7641–1467=6174). Программа также должна возвращать количество повторов, потребовавшихся для достижения этого значения. Например, если num равен 3524, программа должна вернуть 3, вот её три шага:
(1) 5432–2345 = 3087 (2) 8730–0387 = 8352 (3) 8532–2358 = 6174
6. Поменять местами узлы в парах
Это труднейшая задача, которая была предоставлена LeetCode. Хоть она и считается средней по сложности, для меня она оказалась гораздо труднее постоянной Капрекара. Для ее решения вам потребуется знать принцип работы связанных списков.
Давайте не будем слишком углубляться в детали и взглянем на саму задачу:
Дан связанный список. Поменяйте местами смежные узлы и верните их головной элемент. Изменять можно только узлы, но не их значения.
Решения
1. Плюс минус
Решение здесь очень простое:
<?php
function getFractionals($numbers) {
$length = count($numbers);
$results = [
'positive' => 0,
'negative' => 0,
'zero' => 0,
];
for ($i = 0; $i < $length; $i++) {
if ($numbers[$i] < 0) {
$results['negative'] += 1;
} else if ($numbers[$i] > 0) {
$results['positive'] += 1;
} else {
$results['zero'] += 1;
}
}
return [
$results['positive'] / $length,
$results['negative'] / $length,
$results['zero'] / $length
];
}
print_r(getFractionals([1, 1, 0, -1, -1])); // [0.4, 0.4, 0.2]
print_r(getFractionals([-4, 3, -9, 0, 4, 1])); // [0.5, 0.3333, 0.16667]
2. Сумма двух
Хоть эта задача и является несколько сложнее, у вас вряд ли возникнут трудности с ее решением. Я использовал простой подход брутфорс.
<?php
function twoSum($numbers, $target) {
for ($i = 0; $i < count($numbers); $i++) {
for ($j = $i + 1; $j < count($numbers); $j++) {
if ($numbers[$j] + $numbers[$i] === $target) {
return [$i, $j];
}
}
}
}
print_r(twoSum([2, 7, 11, 15], 9)); // [0, 1]
print_r(twoSum([2, 7, 11, 15], 17)); // [0, 3]
3. Самое большое палиндромное произведение
Решение, которое я применил, имеет дополнительное преимущество в том, что с его помощью можно вычислить самый большой палиндром произведения двух чисел.
Я также добавил стоп-условия, чтобы избежать лишних повторений.
<?php
function isPalindrome($number)
{
return (string) $number === strrev((string) $number);
}
function getBiggestPalindrome($digits)
{
$start = pow(10, $digits) - 1;
$max = 0;
for ($i = $start; $i > 0; $i--)
{
if ($i * $start <= $max)
{
break;
}
for ($j = $start; $j > 0; $j--)
{
$product = $i * $j;
if ($product < $max)
{
break;
}
if ($product > $max && isPalindrome($product))
{
$max = $product;
}
}
}
return $max;
}
echo getBiggestPalindrome(2); // 9009
echo getBiggestPalindrome(3); // 906609, which is 993 * 913
4. Различные значения
Эту задачу я решил снова путем брутфорса.
Добавьте каждый результат в массив, а затем удалите из него повторы. Последним шагом станет сортировка массива.
function distinctPowers($min, $max) {
$numbers = [];
for ($i = $min; $i <= $max; $i++) {
for ($j = $min; $j <= $max; $j++) {
$numbers[] = pow($i, $j);
}
}
$unique_numbers = array_unique($numbers);
sort($unique_numbers);
return $unique_numbers;
}
echo print_r(distinctPowers(2, 5), 1); // [4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125]
echo print_r(count(distinctPowers(2, 100)), 1); // 9183 различных выражений
5. Постоянная Капрекара
Эта задача уже несколько сложнее. Она первая в списке, требующая для своего решения рекурсию.
function KaprekarsConstant($number, $numberOfIterations = 1) {
$number = (string) $number;
if (strlen($number) < 4) {
for ($i = strlen($number); $i < 4; $i++) {
$number .= '0';
}
}
$asc = str_split($number);
$desc = $asc;
rsort($desc);
sort($asc);
$asc_number = (int) implode($asc, '');
$desc_number = (int) implode($desc, '');
$difference = abs($asc_number - $desc_number);
if ($difference !== 6174) {
return KaprekarsConstant($difference, $numberOfIterations + 1);
}
return $numberOfIterations;
}
echo KaprekarsConstant(2111); // 5
echo KaprekarsConstant(9831); // 7
Скриншот прохождения всех тестовых кейсов.
6. Поменять местами узлы в парах
Для решения этой задачи мне потребовалось немало времени. Трюк в том, чтобы передать переменные посредством ссылок, а не значений.
function swapPairs($head) {
$current = &$head;
while (!is_null($current->next)) {
$nextValue = $current->next->val;
$temp = &$current;
$temp->next->val = $temp->val;
$temp->val = $nextValue;
$current = &$current->next->next;
}
return $head;
}
Специально для сайта ITWORLD.UZ. Новость взята с сайта NOP::Nuances of programming