本文发表在 rolia.net 枫下论坛我从网上找的了这道题的思路。下面是我的java code
是从下面这个链接的思路里，改写的。
http://codercareer.blogspot.ca/2014/03/no-53-longest-arithmetic-sequence.html
import java.io.Console;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ASeries {
public int longest(int[] values) {
// sort the array
Arrays.sort(values);
Map<Integer, List<Pair>> hashTable = buildHashTable(values);
return analyze(hashTable, values.length);
}
/*
for an array {3, 8, 4, 5, 6, 2, 2}, group the pars like this
differenece 0: (2,2)
difference 1: (2,3), (3,4), (4,5),(5,6)
so we need a hash table to store the information, the key is the difference.
the value is the indexes of the pairs(not values)
*/
private Map<Integer, List<Pair>> buildHashTable(int[] values) {
Map<Integer, List<Pair>> hashTable = new HashMap<Integer, List<Pair>>();
for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {
Pair pair = new Pair();
pair.setFirst(i);
pair.setSecond(j);
int diff = values[j] - values[i];
if (hashTable.containsKey(diff)) {
hashTable.get(diff).add(pair);
} else {
List<Pair> newValue = new ArrayList<Pair>();
newValue.add(pair);
hashTable.put(diff, newValue);
}
}
}
return hashTable;
}
/*
in this method, we need to get the length of the pairs with each difference.
A list of pairs with difference k is got given a key k in the hash table.
If an element A[i] is mth element is an arithmetic sequence with a common difference k, and there is a pair (A[i], A[j]) (j>i) in the list of pairs,
the element A[j] should be the m+1th elemement in the arithmetic sequence.
*/
private int analyze(Map<Integer, List<Pair>> hashTable, int lengthOfNumbers) {
int maxLength = 0;
for (int key : hashTable.keySet()) {
int[] lengths = new int[lengthOfNumbers];
for (int i = 0; i < lengthOfNumbers; i++) {
lengths[i] = 1;
}
for (Pair pair : hashTable.get(key)) {
lengths[pair.getSecond()] = lengths[pair.getFirst()] + 1;
}
for (int length : lengths) {
if (length > maxLength) {
maxLength = length;
}
}
}
return maxLength;
}
private static void test(String testName, int[] numbers, int expected) {
ASeries as = new ASeries();
if (as.longest(numbers) == expected) {
System.out.println(String.format("%s passed.", testName));
} else {
System.out.println(String.format("%s failed.", testName));
}
}
private static void test1() {
int[] numbers = {3, 8, 4, 5, 6, 2, 2};
int expected = 5;
test("test1", numbers, expected);
}
private static void test2() {
int[] numbers = {-1, -5, 1, 3};
int expected = 3;
test("test2", numbers, expected);
}
private static void test3() {
int[] numbers = {-10, -20, -10, -10};
int expected = 3;
test("test3", numbers, expected);
}
public static void main(String[] args) {
test1();
test2();
test3();
}
}
class Pair {
private int first;
private int second;
public int getFirst() {
return first;
}
public void setFirst(int first) {
this.first = first;
}
public int getSecond() {
return second;
}
public void setSecond(int second) {
this.second = second;
}
}
不知道哪里有这样的活动，让我们这些在多伦多的IT猥琐男，每月聚一下，大家交流，交流啊？哪位大侠有这样振臂一呼的能力？更多精彩文章及讨论，请光临枫下论坛 rolia.net
是从下面这个链接的思路里，改写的。
http://codercareer.blogspot.ca/2014/03/no-53-longest-arithmetic-sequence.html
import java.io.Console;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ASeries {
public int longest(int[] values) {
// sort the array
Arrays.sort(values);
Map<Integer, List<Pair>> hashTable = buildHashTable(values);
return analyze(hashTable, values.length);
}
/*
for an array {3, 8, 4, 5, 6, 2, 2}, group the pars like this
differenece 0: (2,2)
difference 1: (2,3), (3,4), (4,5),(5,6)
so we need a hash table to store the information, the key is the difference.
the value is the indexes of the pairs(not values)
*/
private Map<Integer, List<Pair>> buildHashTable(int[] values) {
Map<Integer, List<Pair>> hashTable = new HashMap<Integer, List<Pair>>();
for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {
Pair pair = new Pair();
pair.setFirst(i);
pair.setSecond(j);
int diff = values[j] - values[i];
if (hashTable.containsKey(diff)) {
hashTable.get(diff).add(pair);
} else {
List<Pair> newValue = new ArrayList<Pair>();
newValue.add(pair);
hashTable.put(diff, newValue);
}
}
}
return hashTable;
}
/*
in this method, we need to get the length of the pairs with each difference.
A list of pairs with difference k is got given a key k in the hash table.
If an element A[i] is mth element is an arithmetic sequence with a common difference k, and there is a pair (A[i], A[j]) (j>i) in the list of pairs,
the element A[j] should be the m+1th elemement in the arithmetic sequence.
*/
private int analyze(Map<Integer, List<Pair>> hashTable, int lengthOfNumbers) {
int maxLength = 0;
for (int key : hashTable.keySet()) {
int[] lengths = new int[lengthOfNumbers];
for (int i = 0; i < lengthOfNumbers; i++) {
lengths[i] = 1;
}
for (Pair pair : hashTable.get(key)) {
lengths[pair.getSecond()] = lengths[pair.getFirst()] + 1;
}
for (int length : lengths) {
if (length > maxLength) {
maxLength = length;
}
}
}
return maxLength;
}
private static void test(String testName, int[] numbers, int expected) {
ASeries as = new ASeries();
if (as.longest(numbers) == expected) {
System.out.println(String.format("%s passed.", testName));
} else {
System.out.println(String.format("%s failed.", testName));
}
}
private static void test1() {
int[] numbers = {3, 8, 4, 5, 6, 2, 2};
int expected = 5;
test("test1", numbers, expected);
}
private static void test2() {
int[] numbers = {-1, -5, 1, 3};
int expected = 3;
test("test2", numbers, expected);
}
private static void test3() {
int[] numbers = {-10, -20, -10, -10};
int expected = 3;
test("test3", numbers, expected);
}
public static void main(String[] args) {
test1();
test2();
test3();
}
}
class Pair {
private int first;
private int second;
public int getFirst() {
return first;
}
public void setFirst(int first) {
this.first = first;
}
public int getSecond() {
return second;
}
public void setSecond(int second) {
this.second = second;
}
}
不知道哪里有这样的活动，让我们这些在多伦多的IT猥琐男，每月聚一下，大家交流，交流啊？哪位大侠有这样振臂一呼的能力？更多精彩文章及讨论，请光临枫下论坛 rolia.net