Программирование всегда связано с решением различных задач. Я подготовил список из шести различных заданий и отсортировал их по сложности решения. Первая — самая простая, шестая — самая сложная. Сможете разобраться со всеми?

В конце статьи я также разместил решения, выполненные на языке 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;
}

Читайте также:

Перевод статьи Daan: Do You Know How to Solve These Programming Problems?

Предыдущая статьяКак работает случайный лес?
Следующая статьяПишем интерфейсы командной строки в Python как профи