×

Loading...

I wrote the code in C# (replaced leading spaces to dots to keep indentation).

benbenli (大岭)
本文发表在 rolia.net/zh 相约加拿大网上社区枫下论坛
I used only basic language elements and it should straightforward to convert to Java or C or C++ or any similar language. I also appended the output of the code. I believe this is the optimal code: space O(N) and time O(N^3) Hope it helps

using System;
using System.Text;

namespace ArithmeticSeriesQuiz
{
....class Program
....{
........static void Main(string[] args)
........{
............Resolve(new int[] { 3, 8, 4, 5, 6, 2, 2 });
............Resolve(new int[] { -1, -5, 1, 3 });
............Resolve(new int[] { -10, -20, -10, -10 });
........}

........public static void Resolve(int[] values)
........{
............Console.WriteLine("Question series: {0}", ASeries.ArrayToString(values));
............int[] resultSeries;
............int length = ASeries.Longest(values, out resultSeries);
............Console.WriteLine("Returns: {0}", length);
............Console.WriteLine("Result series: {0}", ASeries.ArrayToString(resultSeries));
............Console.WriteLine();
........}
....}

....public class ASeries
....{
........public static int Longest(int[] values, out int[] longestSeries)
........{
............int lengthOfLongestSeries = 0;
............longestSeries = null;

............if (values != null && values.Length > 0)
............{
................// Sort
................for (int i = 0; i < values.Length; ++i)
................{
....................for (int j = i + 1; j < values.Length; ++j)
....................{
........................if (values[i] > values[j])
........................{
............................int temp = values[i];
............................values[i] = values[j];
............................values[j] = temp;
........................}
....................}
................}

................int[] workingSeries = new int[values.Length];

................for (int firstElementIndex = 0; firstElementIndex < values.Length; ++firstElementIndex)
................{
....................workingSeries[0] = values[firstElementIndex];

....................for (int secondElementIndex = firstElementIndex + 1; secondElementIndex < values.Length; ++secondElementIndex)
....................{
........................workingSeries[1] = values[secondElementIndex];
........................int lengthOfWorkingSeries = 2;

........................int delta = values[secondElementIndex] - values[firstElementIndex];
........................int nextElementValue = values[secondElementIndex] + delta;

........................for (int nextAvailableElementIndex = secondElementIndex + 1; nextAvailableElementIndex < values.Length; ++nextAvailableElementIndex)
........................{
............................if (values[nextAvailableElementIndex] > nextElementValue)
............................{
................................break; // next value of the arithmetic series is not in the array. this series can not be longer
............................}

............................if (values[nextAvailableElementIndex] == nextElementValue)
............................{
................................// found the next value of the arithmetic series, save it
................................workingSeries[lengthOfWorkingSeries++] = values[nextAvailableElementIndex];
................................nextElementValue = values[nextAvailableElementIndex] + delta;
............................}
........................}


........................if (lengthOfWorkingSeries > lengthOfLongestSeries)
........................{
............................lengthOfLongestSeries = lengthOfWorkingSeries;
............................longestSeries = new int[lengthOfLongestSeries];
............................for (int i = 0; i < lengthOfLongestSeries; ++i)
............................{
................................longestSeries[i] = workingSeries[i];
............................}
........................}

....................}
................}
............}

............return lengthOfLongestSeries;
........}

........public static string ArrayToString(int[] values)
........{
............StringBuilder buffer = new StringBuilder();
............buffer.Append("[ ");

............if (values != null && values.Length > 0)
............{
................for (int i = 0; i < values.Length; ++i)
................{
....................buffer.Append(values[i]);
....................buffer.Append(", ");
................}

................buffer.Length -= 2; // remove the last delimeter
............}
............buffer.Append(" ]");

............return buffer.ToString();
........}
....}
}



// Output
Question series: [ 3, 8, 4, 5, 6, 2, 2 ]
Returns: 5
Result series: [ 2, 3, 4, 5, 6 ]

Question series: [ -1, -5, 1, 3 ]
Returns: 3
Result series: [ -5, -1, 3 ]

Question series: [ -10, -20, -10, -10 ]
Returns: 3
Result series: [ -10, -10, -10 ]
更多精彩文章及讨论,请光临枫下论坛. 网址: rolia.net/zh
(#9937690@0)
2016-2-10 -05:00
Reply
Page address has been copied.
To share, click to copy page address.
Share Online by QR Code

Back To Topic: 一道面试题,大家给出出主意哈,我一点头绪都没有

Back To Forum: HOME枫下论坛枫下论坛主坛工作学习学科技术