给定一个浮点数列表,以及四个操作符+、-、*和/,通过在每一对连续的数字之间插入运算符来找到最大值。例如,给定数组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#编程语言编写。请分享你的建议,帮助我改进解决方案。
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 };
}
}
}
发布于 2018-01-30 16:41:13
GetMaxNumber
中的应用
做得很好,考虑狡猾/边缘情况的输入。然而..。
您提供的规范没有说明如何处理空列表或空列表。这是一个设计决策。如果您不能做出设计决策,那么您应该尽可能清楚地记录这样一个事实,即在达到任何一个条件时,都会暴力地抛出一个ArgumentException。返回一个空列表几乎是毫无帮助的,因为这可能是。
我可以想象只有两件事是“正确的”行为:返回零(有意义的输出);或抛出(强烈拒绝输入)。
GetMaxNumber
返回多个数字visit
意味着什么firstKNumbers
确实是误导的:可能是"currentMaxMin“还是其他什么?参数文档的帮助甚至更小:什么是K?我该怎么处理呢?应用递归解决方案意味着什么?!number2
不是很有意义,rhs
可能更好,甚至rightHandSide/Operand
maxMin
数组成为自定义(不可变)数据类型,特别是考虑到您将它作为公共API的一部分返回。目前,您正在显式地记录它们是哪一种(这很好),但是数组的功能要比一对强得多,而且您不需要(也不使用)任何这种功能。thing.Max
比thing[0]
清晰得多。GetMaxNumberHelper
是公开的,有什么好的理由吗?在不理解代码的情况下,任何参数都是不明显的,而且它没有任何保护子句:将其隐藏起来。length
从未在GetMaxNumberHelper
中使用过IReadOnlyList<double>
传递给这个API会让我感到更舒服:您没有理由修改,也没有修改它,所以请给消费者选项,并向他们保证您不会破坏他们的数据。(您甚至可以对其进行重新排列,以获得一个IEnumerable<double>
,只需付出一点努力)发布于 2018-07-05 16:33:31
这是一种算法评审,而不是代码评审,因此应该进入注释空间。然而,它太长,不能发表评论。
问题描述说,这些操作是从左到右执行的,因此,在分析位置N的参数操作之前,应该先对0到N1位置上的数字进行所有可能的操作分析,因此总的大纲如下:
partialResult(numbers, N)
{
return partialResult(numbers, N-1) plus/minus/times/divided numbers[N];
}
当我们乘或除以负的number[N]
,最大和最小交换,所以我们需要一个部分的结果包含可能的最大值和最小值的子问题。这可以通过返回双倍结构或仅仅通过传递两个引用参数来实现:
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();
}
当然,我们需要识别和处理一个基本案件!一个大小写是一个数字,它本身就是它的最大值和最小值:
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();
}
最后,我们可以使用我们的助手:
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而获得学分。
发布于 2019-05-26 15:17:45
GetMaxNumber
:既然要计算表达式,就叫它EvaluateMaximum
。GetMaxNumberHelper
:-helper是一个可接受的类名,但不是方法名称。使用过载的EvaluateMaximum
代替。visit
:这是访问者模式中方法的名称。不要将它用作变量名。使用number
代替。maxMin
:这是一个充满矛盾的名字。使用span
或interval
代替。number2
:不必要的后缀。使用number
代替。numbers.Length == 0
:我更喜欢!numbers.Any()
。calculateFourOperations
:不要用camelcase方法的名称。CalculateFourOperations
如果numbers
是null
,则不符合规范,因此抛出一个ArgumentNullException
。如果它没有元素,我会选择返回对new[] { double.NaN, double.NaN }
。您正在让调用方知道无法对其输入执行评估。
如果(数字为== null \ numbers.Length numbers.Length == 0) {返回新的double[] { };}
if (numbers == null)
throw new ArgumentNullException(nameof(numbers));
if (!numbers.Any())
{
return new [] { double.NaN, double.NaN };
}
我也缺少溢出,并除以您表达式中的零处理。
var除法= maxMin0 / number2;// <-如果number2为0怎么办?
使用startIndex
并对其进行增量,对我来说更像是一种代码味道。与其说是递归,不如说是隐藏的循环。
公共静态double[] GetMaxNumberHelper(double[] numbers,int startIndex,..) { // .startIndex +1}
您可以指定表达式(加法、减法、乘法、除法)作为单独的方法。然后,CalculateFourOperations
可以在其输入上调用这些表达式。其优势有两方面:
私有静态double[] calculateFourOperations(double[] maxMin,double number2) { var加法= maxMin0 + number2;var addition2 = maxMin1 + number2;// .}
我提出了一个评估这些表达式的替代解决方案。我的步骤是自下而上的。
一个新的结构Span
存储Min
和Max
值对。这样,我们就可以避免对这些对的double[]
。
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子句位于外部函数内时的堆栈跟踪。
private static double EvaluateExpression(Func<double> expression)
{
return (new Func<double>(() =>
{
try
{
return expression();
}
catch
{
return double.NaN;
}
}
))();
}
现在,我们可以根据输入和下一个数字计算所有表达式。
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());
}
下一步是在当前Min
和Max
的两个分支上执行评估。Queue
是这类操作的理想集合。然后,我们根据两个分支计算新的current
。
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
。
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;
}
[TestMethod]
public void RunTestcase()
{
var input = new double[] { 1, 12, -3 };
Assert.AreEqual(33, EvaluateMaximum(input));
}
https://codereview.stackexchange.com/questions/186306
复制相似问题