首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >递归函数挑战

递归函数挑战
EN

Code Review用户
提问于 2018-01-30 05:23:48
回答 3查看 688关注 0票数 6

问题陈述

给定一个浮点数列表,以及四个操作符+、-、*和/,通过在每一对连续的数字之间插入运算符来找到最大值。例如,给定数组1、12、-3,可以使用1-12* (-3)找到最大值33,因为所有运算符都有平面偏好,所以1-12* (-3)将从左到右处理,第一个操作为值为-11的1-12,然后第二个操作为-11 * (-3) = 33。

常见面试问题

递归函数是最常见的模拟面试问题。从2017年3月到2018年1月,我一次又一次地练习递归函数作为面试官和面试者--超过150次模拟面试。在递归函数的问题解决中,我通过这么多同伴学到了很多东西。

在我看来,递归函数通常可以在经过大量练习后10分钟内完成。在这些练习中,我几乎犯了所有可能的错误,然后我开始学习在哪里约束自己,并进行一些仪式,即在归纳步骤之前只找到基本案例并解决问题一次。

在上周的匿名模拟采访中,这个算法让我很难弄清楚,因为我以前从未使用过完全相同的算法。自从给了我重大提示后,我得到了2比4的评分。递归函数应该设计为返回最大值和最小数。

第二个问题是递归函数的设计顺序。例如,在模拟面试中,测试用例1、12、-3是错误计算的:1- (12 * (-3)) = 37,我的递归解决方案打破了平面优先级的约束。

模拟采访后的

模拟面试后,我继续写算法,花了我30分钟的时间,但答案是37而不是33分钟。我颠倒了输入数组的顺序,结果仍然是错误的。所以我花了30多分钟重新设计递归函数,用33来计算结果。我通过匿名面试学到了一种算法,我真的很感激有机会通过这个学习过程。在过去的几天里,这个算法很快成为我最喜欢的算法,直到2018年1月29日,该算法还没有在Leetcode.com上包含主要的讨论面板。

代码评审

代码用C#编程语言编写。请分享你的建议,帮助我改进解决方案。

代码语言:javascript
运行
复制
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 };
        }
    }
}
EN

回答 3

Code Review用户

回答已采纳

发布于 2018-01-30 16:41:13

保护子句在GetMaxNumber

中的应用

做得很好,考虑狡猾/边缘情况的输入。然而..。

您提供的规范没有说明如何处理空列表或空列表。这是一个设计决策。如果您不能做出设计决策,那么您应该尽可能清楚地记录这样一个事实,即在达到任何一个条件时,都会暴力地抛出一个ArgumentException。返回一个空列表几乎是毫无帮助的,因为这可能是。

我可以想象只有两件事是“正确的”行为:返回零(有意义的输出);或抛出(强烈拒绝输入)。

命名

  • GetMaxNumber返回多个数字
  • 不知道变量名visit意味着什么
  • firstKNumbers确实是误导的:可能是"currentMaxMin“还是其他什么?参数文档的帮助甚至更小:什么是K?我该怎么处理呢?应用递归解决方案意味着什么?!
  • number2不是很有意义,rhs可能更好,甚至rightHandSide/Operand

Misc

  • 我将使maxMin数组成为自定义(不可变)数据类型,特别是考虑到您将它作为公共API的一部分返回。目前,您正在显式地记录它们是哪一种(这很好),但是数组的功能要比一对强得多,而且您不需要(也不使用)任何这种功能。thing.Maxthing[0]清晰得多。
  • 规范没有提到返回最小数目的问题(既然规范不是特别清楚)
  • 为什么GetMaxNumberHelper是公开的,有什么好的理由吗?在不理解代码的情况下,任何参数都是不明显的,而且它没有任何保护子句:将其隐藏起来。
  • 如果有人决定将数千个数字输入其中,我倾向于迭代(而不是递归)实现,但这可能并不是很重要。
  • length从未在GetMaxNumberHelper中使用过
  • 将一个IReadOnlyList<double>传递给这个API会让我感到更舒服:您没有理由修改,也没有修改它,所以请给消费者选项,并向他们保证您不会破坏他们的数据。(您甚至可以对其进行重新排列,以获得一个IEnumerable<double>,只需付出一点努力)
票数 9
EN

Code Review用户

发布于 2018-07-05 16:33:31

这是一种算法评审,而不是代码评审,因此应该进入注释空间。然而,它太长,不能发表评论。

问题描述说,这些操作是从左到右执行的,因此,在分析位置N的参数操作之前,应该先对0到N1位置上的数字进行所有可能的操作分析,因此总的大纲如下:

代码语言:javascript
运行
复制
    partialResult(numbers, N)
    {
        return partialResult(numbers, N-1) plus/minus/times/divided numbers[N];
    }

当我们乘或除以负的number[N],最大和最小交换,所以我们需要一个部分的结果包含可能的最大值和最小值的子问题。这可以通过返回双倍结构或仅仅通过传递两个引用参数来实现:

代码语言:javascript
运行
复制
    void calcPartialResult(double[] numbers, int N, double& minResult, double& maxResult)
    {
        calcPartialResult(numbers, N-1, minResult, maxResult);

        double[] newResults = {
            minResult plus/minus/times/divided numbers[N],
            maxResult plus/minus/times/divided numbers[N] };

        minResult = newResults.Min();
        maxResult = newResults.Max();
    }

当然,我们需要识别和处理一个基本案件!一个大小写是一个数字,它本身就是它的最大值和最小值:

代码语言:javascript
运行
复制
    void calcPartialResult(double[] numbers, int N, double& minResult, double& maxResult)
    {
        if(N == 0) {
            minResult = maxResult = numbers[0];
            return;
        }

        calcPartialResult(numbers, N-1, minResult, maxResult);

        double[] newResults = {
            minResult plus/minus/times/divided numbers[N],
            maxResult plus/minus/times/divided numbers[N] };

        minResult = newResults.Min();
        maxResult = newResults.Max();
    }

最后,我们可以使用我们的助手:

代码语言:javascript
运行
复制
    double GetMaxNumber(double[] numbers)
    {
        if(numbers == null || numbers.Length == 0)
            throw ArgumentException;

        double minResult, maxResult;
        calcPartialResult(numbers, numbers.Length-1, minResult, maxResult);

        return max(minResult, maxResult);
    }

@VisualMelon因抛出ArgumentException而获得学分。

票数 5
EN

Code Review用户

发布于 2019-05-26 15:17:45

命名约定

  • GetMaxNumber:既然要计算表达式,就叫它EvaluateMaximum
  • GetMaxNumberHelper:-helper是一个可接受的类名,但不是方法名称。使用过载的EvaluateMaximum代替。
  • visit:这是访问者模式中方法的名称。不要将它用作变量名。使用number代替。
  • maxMin:这是一个充满矛盾的名字。使用spaninterval代替。
  • number2:不必要的后缀。使用number代替。
  • numbers.Length == 0:我更喜欢!numbers.Any()
  • calculateFourOperations:不要用camelcase方法的名称。CalculateFourOperations

保护条件

如果numbersnull,则不符合规范,因此抛出一个ArgumentNullException。如果它没有元素,我会选择返回对new[] { double.NaN, double.NaN }。您正在让调用方知道无法对其输入执行评估。

如果(数字为== null \ numbers.Length numbers.Length == 0) {返回新的double[] { };}

代码语言:javascript
运行
复制
if (numbers == null)
    throw new ArgumentNullException(nameof(numbers));
if (!numbers.Any())
{
    return new [] { double.NaN, double.NaN };
}

我也缺少溢出,并除以您表达式中的零处理。

var除法= maxMin0 / number2;// <-如果number2为0怎么办?

Recursion

使用startIndex并对其进行增量,对我来说更像是一种代码味道。与其说是递归,不如说是隐藏的循环。

公共静态double[] GetMaxNumberHelper(double[] numbers,int startIndex,..) { // .startIndex +1}

表达式

您可以指定表达式(加法、减法、乘法、除法)作为单独的方法。然后,CalculateFourOperations可以在其输入上调用这些表达式。其优势有两方面:

  • 多次重用现有表达式
  • 溢出,除以零,可以对单个表达式执行检查。

私有静态double[] calculateFourOperations(double[] maxMin,double number2) { var加法= maxMin0 + number2;var addition2 = maxMin1 + number2;// .}

提出的解决方案

我提出了一个评估这些表达式的替代解决方案。我的步骤是自下而上的。

一个新的结构Span存储MinMax值对。这样,我们就可以避免对这些对的double[]

代码语言:javascript
运行
复制
 public struct Span
 {
      public double Min { get; }
      public double Max { get; }
      public Span(double min, double max)
      {
          Min = min;
          Max = max;
      }
      public static Span NaN => new Span(double.NaN, double.NaN);
      public static Span Zero => new Span(0d, 0d);
      // .. hashcode, equals, tostring ..
 }

计算表达式时,句柄溢出,除以零。当这些错误发生时,我决定使用double.NaN。稍后,我将忽略这些值,并与其他值一起继续流。这是一个设计决策。我使用的系统税是一个生平 (在javascript世界中是众所周知的)。这有助于在try-catch子句位于外部函数内时的堆栈跟踪。

代码语言:javascript
运行
复制
  private static double EvaluateExpression(Func<double> expression)
  {
        return (new Func<double>(() =>
        {
            try
            {
                return expression();
            }
            catch
            {
                return double.NaN;
            }
        }
        ))();
  }

现在,我们可以根据输入和下一个数字计算所有表达式。

代码语言:javascript
运行
复制
private static Span EvaluateSpan(double current, double number)
{
      var evaluations = new Func<double>[] {
            () => current + number,
            () => current - number,
            () => current * number,
            () => current / number
      }.Select(e => EvaluateExpression(e)).Where(n => !double.IsNaN(n));
      return new Span(evaluations.Min(), evaluations.Max());
}

下一步是在当前MinMax的两个分支上执行评估。Queue是这类操作的理想集合。然后,我们根据两个分支计算新的current

代码语言:javascript
运行
复制
private static Span EvaluateSpan(Span current, Queue<double> numbers)
{
     if (!numbers.Any())
         return current;
     var number = numbers.Dequeue();
     var s1 = EvaluateSpan(current.Min, number);
     var s2 = EvaluateSpan(current.Max, number);
     current = new Span(Math.Min(s1.Min, s2.Min), Math.Max(s1.Max, s2.Max));
     return EvaluateSpan(current, numbers);
}

我们所有的助手方法都已经创建了。公共API包含一个获取调用方Span的方法和两个重载:一个用于Max,另一个用于Min

代码语言:javascript
运行
复制
public static Span EvaluateSpan(IEnumerable<double> numbers)
{
      if (numbers == null)
          throw new ArgumentNullException(nameof(numbers));
      var queue = new Queue<double>(numbers);
      if (!queue.Any())
          return Span.NaN;
      var number = queue.Dequeue();
      var current = new Span(number, number);
      return EvaluateSpan(current, queue);
}

public static double EvaluateMaximum(IEnumerable<double> numbers)
{
      return EvaluateSpan(numbers).Max;
}

public static double EvaluateMinimum(IEnumerable<double> numbers)
{
      return EvaluateSpan(numbers).Min;
}

测试场景

代码语言:javascript
运行
复制
 [TestMethod]
 public void RunTestcase()
 {
      var input = new double[] { 1, 12, -3 };

      Assert.AreEqual(33, EvaluateMaximum(input));
 }
票数 4
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/186306

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档