Рекурсивный вызов функции


Постановка задачи

Дан список вещественных чисел и четырех операторов +, -, *, / с плоской предпочтения, найти максимальное значение путем вставки оператора между каждой парой последовательных чисел.

Например, дан массив [1, 12, -3], максимальное число 33 можно найти с помощью 1 - 12 * (-3), так как все операторы имеют плоские предпочтения, поэтому 1 - 12 * (-3) будет осуществляться слева направо, первая операция 1 - 12 со значением -11, а потом повторная операция -11 * (-3) = 33.

Общий вопрос интервью

Рекурсивная функция является наиболее распространенным пробный вопрос. Я практиковал снова и снова рекурсивные функции интервьюера и интервьюируемого с марта 2017 года до января. 2018 году более 150 пробных интервью, я узнал так много в решении проблем рекурсивной функции через так много сверстников.

Обычно рекурсивная функция может быть написана в течение 10 минут, после много практики, на мой взгляд. Я чуть ли не все возможные ошибки в эти практики, и тогда я начинаю узнать, где дисциплинировать себя и пройти через обряды, которые должны найти основание чехол и решить эту проблему только один раз, прежде чем индуктивный шаг.

Алгоритм был трудно для меня, чтобы выяснить, в анонимном пробное интервью на прошлой неделе, поскольку я никогда не работал на точно такой же алгоритм раньше. У меня рейтинг 2 из 4 с основной намек был дан мне. Рекурсивная функция должна возвращать максимальное и минимальное числа.

Вторая проблема заключается в том, чтобы разработать рекурсивную функцию. Например, тестовый случай [1, 12, -3] вычисляется по ошибке вроде следующего: 1 - (12 * (-3)) = 37 в своем кратком интервью, МОЕ рекурсивное решение нарушает ограничения плоский верх.

После пробных интервью

Я продолжал писать алгоритм после пробных интервью, и мне потребовалось еще 30 минут, но ответа 37 вместо 33. Я отменил заказ из входного массива, результат все равно неправильный. Поэтому я потратил более 30 минут, чтобы перепроектировать рекурсивные функции, вычислить результат с 33. Я узнаю одного алгоритма через анонимные интервью, и я очень благодарен, чтобы иметь возможность пройти процесс обучения. Этот алгоритм быстро становится мой любимый алгоритм в последние несколько дней, и алгоритм не был включен основных панельная дискуссия Leetcode.com до 29 января 2018 года.

Комментарий код

Код написан на языке программирования C#. Пожалуйста, поделитесь своими советами, помогите мне улучшить решение.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FindMaximumNumber
{
    /*
    Keyword:
    Given a list of float number, and 
    four operator: +, -, *, / arithmetic opeators, 
    insert an operator between each consecutive pair of numbers    
    Ask you to solve the problem:
    Find maximimum value -> greedy algorithm    
    Constraints:
    equal precedence order - 1 + 2 * 3 = 1 + 6 = 7 - No
                             1 + 2 * 3 = 3 * 3 = 9 - Yes
    evaluation order is from left to right 
    -> scan the float number from left to right 

    Major hint: 
    1, 12, -3, maximum number is 1 - 12 * (-3) = 33
         [1, 12]    
       /  /  \    \
     -11 13  1/12 12  -> Design the recursive with a problem 
                         include maximum and minimum value.
    */
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase();
        }        

        public static void RunTestcase()
        {
            var input = new double[] { 1, 12, -3 };

            var result = GetMaxNumber(input);
            Debug.Assert(result[0] == 33);
        }
        /// <summary>
        /// First number in the return array is the maximum value and
        /// the second one is the minimum value.  
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static double[] GetMaxNumber(double[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return new double[] { };
            }

            return GetMaxNumberHelper(numbers, 1, new double[] { numbers[0], numbers[0] });
        }

        /// <summary>
        /// Recursive function is designed to fit for flat precedence, 
        /// in other words, the calculation is processed from left to right
        /// instead of right to left. 
        /// [1, 12, -3] will be handled 1 [+,-,*,/] 12 first, and then
        /// max/min [+,-,*,/] -3
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="startIndex"></param>
        /// <param name="firstKNumbers">process first K numbers first
        ///  and then apply recursive solution</param>
        /// <returns></returns>
        public static double[] GetMaxNumberHelper(double[] numbers, int startIndex, double[] firstKNumbers)
        {
            if (startIndex >= numbers.Length)
            {
                return firstKNumbers;
            }

            var length = numbers.Length;

            var visit = numbers[startIndex];

            var fourOperations = calculateFourOperations(firstKNumbers, visit);

            var current = new double[] { fourOperations.Max(), fourOperations.Min() };

            return GetMaxNumberHelper(numbers, startIndex + 1, current);
        }

        /// <summary>
        /// calculate using four operators +, -, *, /
        /// </summary>
        /// <param name="maxMin"></param>
        /// <param name="number2"></param>
        /// <returns></returns>
        private static double[] calculateFourOperations(double[] maxMin, double number2)
        {
            var addition  = maxMin[0] + number2;
            var addition2 = maxMin[1] + number2;

            var subtraction  = maxMin[0] - number2;
            var subtraction2 = maxMin[1] - number2;

            var multiplication  = maxMin[0] * number2;
            var multiplication2 = maxMin[1] * number2;

            var division  = maxMin[0] / number2;
            var division2 = maxMin[1] / number2;

            return new double[] { addition, addition2, subtraction, subtraction2, multiplication, multiplication2, division, division2 };
        }
    }
}


Комментарии
1 ответ

Охранник П. В GetMaxNumber

Молодец, учитывая изворотливые/края-дело ввода. Однако...

Спец вам предоставлять ничего не говорит о том, что делать с null или пустой список. Это дизайнерское решение. Если вы не можете сделать дизайнерское решение, то вы должны документировать то, что вы упустили его максимально четко, яростно бросая исключение ArgumentException, если хотя бы одно условие не будет достигнуто. Возвращается пустой список-это примерно так же бесполезно, как это может быть.

Есть только 2 вещи, которые я мог представить себе "правильное" поведение: возвращает ноль (осмысленного вывода); или бросить (яростно отвергают вход).

Именования


  • GetMaxNumber возвращает более одного номера

  • понятия не имею, что имя переменной visit это предназначается, чтобы вызвать

  • firstKNumbers это действительно вводит в заблуждение: возможно, "currentMaxMin" или что-то? В документации параметр еще менее полезные: Что такое к? как мне их обработать? что это означает применять рекурсивное решение?!

  • number2 не очень содержательно, rhs может быть лучше, или даже rightHandSide/Operand

Смешанная


  • Я хотел бы сделать maxMin массив пользовательского (неизменяемых) данных-тип, особенно учитывая, что вы возвращаете его как часть общественного API. В настоящее время вы явно документировать, в какую сторону вокруг их (что хорошо), но массив является значительно более мощным, чем просто пара, и вам не нужно (и не используют) ее. thing.Max гораздо яснее, чем thing[0].

  • В спецификации ничего не говорится о возвращении минимальное количество (конечно спец не особо понятно)

  • Есть ли хорошая причина, почему GetMaxNumberHelper является общедоступной? Это не очевидно, что любые рассуждения без понимания кода и это не имеет никакого защитные предложения: спрячьте его подальше.

  • Я был бы склонен реализовать этот итерационно (а не рекурсивно), если кто-то решит накормить тысячи чисел, но это наверное не очень важно.

  • length никогда не используется в GetMaxNumberHelper

  • Я бы чувствовать себя более комфортно проезжает IReadOnlyList<double> для этого API: у вас нет причин, чтобы изменять и не изменять его, так что дайте потребителю варианты и убедить их, что вы не собираетесь калечить свои данные. (Вы могли бы даже изменить его взять IEnumerable<double> С немного усилий)

5
ответ дан 30 января 2018 в 04:01 Источник Поделиться