There is a straight roads with 'n' number of milestones. You are given an
array with the distance between all the pairs of milestones in some random
order. Find the position of milestones.
Example:
Consider a road with 4 milestones(a,b,c,d) :
a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d
Distance between a and b = 3
Distance between a and c = 8
Distance between a and d = 10
Distance between b and c = 5
Distance between b and d = 7
Distance between c and d = 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3,5,2 or 2,5,3
m*********2 发帖数: 701
2
so, N is known when you run the program?
first step is obvious to sort it, and get the first and last position.
2) break the distance down to 2 segments so that
10 = segment1 + segment2 （any pair of segments will do)
3) repeat 2
an
random
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
g**e 发帖数: 6127
3
既然数组是随机的，怎么保证最后所有点的位置？比如你这例子，为什么不能输出5,3,
2?
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
s_1_1
s_2_1 s_2_2
s_3_1 s_3_2 s_3_3
...
s_t_1 s_t_2 s_t_3 s_t_t
t = n - 1 (n is the number of point)
s(i,j) means the sum of lj to li (li is the what we want to output)
e.g. s(2,4) = l2+l3+l4
so, s(i,i) = li
rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
s(t,1) = longest length
Use dfs and edge cut to fill the matrix, then output s(i,i) i=1 to t
for the sample:
7, 10, 5, 2, 8, 3
?
? ?
10 ? ?
1) try 8 in s(3,2)
?
? ?
10 8 ?
-> (based on rule1)
2
? ?
10 8 ?
1-1) try 7 in s(2,1)
2
7 ?
10 8 ?
-> (based on rule1, 10-7=3, 7-2=5)
2
7 5
10 8 3
1-2) try 5 in s(2,1),skip since 10-5 is not in the list
1-3) try 3 in s(2,1),skip since 3-2 is not in the list
2) try 7 in s(3,2)
...
the lots of edges will be cut, so it will not be slow.
if it is a math question for n=4,
s_2_2 = sum(all) - s_3_1 * 3
in our sample, s_2_2 = 35 - 10 * 3 = 5
s_3_2 could only be 7 or 8, considering the matrix is symmetric,
let s_3_2 = 8, then s_1_1 = 10 - 8 = 2, s_2_1 = 5 + 2 = 7, s_3_3 = 8 - 5
=3
2
7 5
10 8 3
【在 g***s 的大作中提到】 : s_1_1 : s_2_1 s_2_2 : s_3_1 s_3_2 s_3_3 : ... : s_t_1 s_t_2 s_t_3 s_t_t : t = n - 1 (n is the number of point) : s(i,j) means the sum of lj to li (li is the what we want to output) : e.g. s(2,4) = l2+l3+l4 : so, s(i,i) = li : rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
【在 g***s 的大作中提到】 : s_1_1 : s_2_1 s_2_2 : s_3_1 s_3_2 s_3_3 : ... : s_t_1 s_t_2 s_t_3 s_t_t : t = n - 1 (n is the number of point) : s(i,j) means the sum of lj to li (li is the what we want to output) : e.g. s(2,4) = l2+l3+l4 : so, s(i,i) = li : rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
r*******y 发帖数: 1081
15
sort firstly?
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
public class FindSegments {
public static void main(String args[]) throws InterruptedException {
// List segs = Arrays.asList(new Integer[]{2, 3, 5, 7,
8, 10});
List segs = Arrays.asList(new Integer[]
{2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,2
6,28,
29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56});
long startTime = System.currentTimeMillis();
findSegs(segs);
System.out.printf("Total running time : %d ms",
System.currentTimeMillis() - startTime);
}
private static void findSegs(List segs) {
int t = getN(segs.size())-1;
Collections.sort(segs, Collections.
i**********e 发帖数: 1145
20
My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A = {3,8,2,6,5,3}
Answer:
3 3 2
2 3 3
A = {7,10,16,9,3,6,2,8,5,14}
Answer:
2 5 3 6
6 3 5 2
A = {4,1,6,1,2,4,2,2,3,3}
Answer:
2 1 1 2
A = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5}
Answer:
1 1 2 2 3 3
3 3 2 2 1 1
#include
#include
#include
using namespace std;
typedef hash_map Hash;
typedef Hash::const_iterator HashIter;
// Decrement the key's value by one in the hash table.
// Key's value reaches 0 implies that the number is already
// selected (no longer available), so remove it from the table.
void decrementByOne(Hash &hash, int key) {
assert(hash[key] > 0);
hash[key]--;
if (hash[key] == 0)
hash.erase(key);
}
// Generates all combinations that will be used as the next combinations.
bool generatePartialSolution(int last, const vector &inCombinations, vector &outCombinations, Hash &hash) {
assert(outCombinations.empty());
int n = inCombinations.size();
for (int i = 0; i < n; i++) {
int sumPair = last + inCombinations[i];
if (hash[sumPair] == 0)
return false;
outCombinations.push_back(sumPair);
decrementByOne(hash, sumPair);
}
return true;
}
void solve(const Hash &hash, const vector &combinations, vector solution) {
// No more numbers to pick from, a new solution exists.
if (hash.empty()) {
int n = solution.size();
for (int i = 0; i < n; i++)
cout << solution[i] << " ";
cout << endl;
return;
}
for (HashIter iter = hash.begin(); iter != hash.end(); ++iter) {
int num = iter->first;
Hash hashCopy = hash;
solution.push_back(num);
decrementByOne(hashCopy, num);
vector nextCombinations;
if (generatePartialSolution(num, combinations, nextCombinations, hashCopy)) {
nextCombinations.push_back(num);
solve(hashCopy, nextCombinations, solution);
}
solution.pop_back();
}
}
void solve(int A[], int n) {
Hash hash;
for (int i = 0; i < n; i++) {
hash[A[i]]++;
}
solve(hash, vector(), vector());
}
int main() {
int A[] = {7,10,5,2,8,3};
//int A[] = {1,1,1,2,3,2};
//int A[] = {3,8,2,6,5,3};
//int A[] = {7,10,16,9,3,6,2,8,5,14};
//int A[] = {4,1,6,1,2,4,2,2,3,3};
//int A[] = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5};
/*int A[] = {2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,26,28,29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56};*/
int n = sizeof(A)/sizeof(int);
solve(A, n);
return 0;
}
一些常见面试题的答案与总结 - http://www.ihas1337code.com
【在 i**********e 的大作中提到】 : My code found two valid answers for the following input in about 3 secs ( : obviously not as good as grass, but the algorithm is easier to code). : Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23 : 24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 } : Answer: : 2 7 2 4 8 8 8 10 7 : 7 10 8 8 8 4 2 7 2 : grass, can you explain whether your code generates the solution {7 10 8 8 8 : 4 2 7 2} ? : Test cases:
t******g 发帖数: 252
22
From the length of the array n, we can get the number of the milestones i.
And the i-1 smallest numbers should be the distances between the consecutive
milestones. The rest of the numbers are derived.
t******g 发帖数: 252
23
O(nlgn)
consecutive
【在 t******g 的大作中提到】 : From the length of the array n, we can get the number of the milestones i. : And the i-1 smallest numbers should be the distances between the consecutive : milestones. The rest of the numbers are derived.
g**e 发帖数: 6127
24
wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a
milestone.
consecutive
【在 t******g 的大作中提到】 : From the length of the array n, we can get the number of the milestones i. : And the i-1 smallest numbers should be the distances between the consecutive : milestones. The rest of the numbers are derived.
t******g 发帖数: 252
25
You're right.
【在 g**e 的大作中提到】 : wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a : milestone. : : consecutive
g**********y 发帖数: 14569
26
写了个简化版的：
public class Gloomyturkey implements IMilestone {
private int N;
private int M;
private int[] sequence;
private int[] answer;
private HashMap map;
private boolean[] used;
private int[] sum;
private boolean found;
public int[] findMilestones(int[] segs) {
M = segs.length;
sum = segs;
calcN();
initMap(segs);
used = new boolean[M];
found = false;
sequence = new int[N];
answer = new int[N];
assign(0, M-1);
assign(1, M-2);
dfs(2);
return found? answer : new int[0];
}
private void assign(int index, int from) {
sequence[index] = sum[from];
used[from] = true;
if (index > 0) answer[index-1] = sequence[index-1] - sequence[index];
if (index == N-1) answer[N-1] = sequence[N-1];
}
private void backtrack(int from) {
used[from] = false;
}
private void dfs(int len) {
if (len == N) return;
for (int i=M-3; i>=0; i--) {
if (used[i]) continue;
assign(len, i);
if (validate(len+1)) {
if (len+1 == N) found = true;
dfs(len+1);
if (found) break;
}
backtrack(i);
}
}
private boolean validate(int len) {
int size = len==N? len : len-1;
HashMap partial = new HashMap();
for (int i=1; i<=size; i++) {
for (int j=0; j<=size-i; j++) {
int S = 0;
for (int k=j; k
S += answer[k];
}
int count = partial.get(S)!=null? partial.get(S) :
map.get(S)==null? 0 : map.get(S);
if (count == 0) return false;
partial.put(S, count-1);
}
}
return true;
}
private void calcN() {
N = (int) ((Math.sqrt(1 + 8*M) - 1) / 2 + 0.5);
}
private void initMap(int[] segs) {
map = new HashMap();
for (int seg : segs) {
if (map.get(seg) == null) {
map.put(seg, 0);
}
map.put(seg, map.get(seg)+1);
}
}
}
我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
的多了点，好在都是数。
time ./milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
real 1m5.827s
user 1m5.776s
sys 0m0.028s
假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
prev_pos之和。
基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
以及逐个累加prev_pos里milestone所得到的路程，都在a里，则认为该a[i]可以作为新
的milestone，进行递归。
#! /usr/bin/env python
import sys
DEBUG=1
def milestone(a, total, prev_pos):
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
#print total
return prev_pos + [total]
a.sort()
if a[0] == total:
#print a[0]
return prev_pos + [total]
prev_v = 0
for i in range(len(a) - 1):
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
aa = a[:]
aa.remove(a[i]) # remove first: to avoid b == a[i]
b = total - a[i]
if b in aa: # here use aa!
is_cand = 1
aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 - j]
# reverse
if c in aa:
aa.remove(c)
continue
is_cand = 0
break
if is_cand:
#print a[i]
tmp_pos = milestone(aa, b, prev_pos + [a[i]])
if len(tmp_pos) > 0:
return tmp_pos
return []
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 18,
20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38, 39, 40, 41, 45,
47, 47, 49, 54, 56]
a = [2,4,4,5,5,6,6,6,8,8, 9,9,9,11,11,11,12,13,13,13, 13,13,13,14,16,16,17,
17,17,17, 18,19,19,20,22,22,22,22,22,23, 25,25,26,26,26,26,27,27,28,28, 28,
29,31,33,35,35,36,36,37,38, 38,38,39,39,39,40,41,42,42,43, 44,45,45,46,48,48
,49,50,51,51, 51,51,53,53,55,55,57,58,59,59, 61,63,64,64,64,64,64,64,64,65,
66,68,70,71,72,73,73,75,76,77, 77,77,77,80,81,81,81,83,84,86, 86,86,89,90,90
,90,91,92,92,94, 97,99,99,100,101,102,103,103,103,106, 107,108,109,109,111,
112,112,114,115,116, 117,117,119,120,122,123,123,125,128,128, 128,128,129,
130,132,134,134,136,137,139, 140,141,141,145,145,145,147,150,150,151, 152,
154,156,156,158,162,163,167,169,173]
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])
【在 g***s 的大作中提到】 : s_1_1 : s_2_1 s_2_2 : s_3_1 s_3_2 s_3_3 : ... : s_t_1 s_t_2 s_t_3 s_t_t : t = n - 1 (n is the number of point) : s(i,j) means the sum of lj to li (li is the what we want to output) : e.g. s(2,4) = l2+l3+l4 : so, s(i,i) = li : rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
s*****y 发帖数: 897
37
是算最长那个 66秒吗？
【在 h*****t 的大作中提到】 : 我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用 : 的多了点，好在都是数。 : time ./milestone_pos.py : [4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6] : real 1m5.827s : user 1m5.776s : sys 0m0.028s : 假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去 : prev_pos之和。 : 基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
h*****t 发帖数: 40
38
是的，那个ultimate的
【在 s*****y 的大作中提到】 : 是算最长那个 66秒吗？
g***s 发帖数: 3811
39
再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
算出答案是26s，全部扫描完是32s。
Answer: (running time from start : 26396ms)
4 13 5 4 13 6 8 12 16 9 13 13 13 16
9 2 6 5 6
4
Total running time : 32052 ms, count of dfs=100342
h*****t 发帖数: 40
40
我的优化后是33秒，CPU是C2D T8100. 递归的次数是58539.
D:\download>d:\Python27\python.exe milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
cnt 58539
time 33.2269999981
Mod:
@@ -1,10 +1,15 @@
#! /usr/bin/env python
import sys
+import time
#DEBUG=1
DEBUG=0
+global cnt
+cnt = 0
def milestone(a, total, prev_pos):
+ global cnt
+ cnt += 1
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
@@ -16,17 +21,21 @@
#print a[0]
return prev_pos + [total]
prev_v = 0
- for i in range(len(a) - 1):
+ for i in range(len(a) - 1): # can safely disgard the last
one as b must exist.
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
- aa = a[:]
- aa.remove(a[i]) # remove first: to avoid b ==
a[i]
+ #aa = a[:]
+ #aa.remove(a[i]) # remove first: to
avoid b == a[i]
+ #if b in aa: # here use aa!
b = total - a[i]
- if b in aa: # here use aa!
+ if (b != a[i] and b in a) or (b == a[i] and i < len(a)
- 1 and a[i+1] == a[i]):
is_cand = 1
- aa.remove(b)
+ aa = a[:]
+ aa.remove(a[i])
+ if b != a[i]:
+ aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 -
j] # reverse
@@ -42,6 +51,7 @@
return tmp_pos
return []
+start_time=time.time()
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16,
17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38,
39, 40, 41, 45, 47, 47, 49, 54, 56]
@@ -49,3 +59,6 @@
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])
+print "cnt", cnt
+end_time=time.time()
+print "time", end_time - start_time
16
【在 g***s 的大作中提到】 : 再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右） : 算出答案是26s，全部扫描完是32s。 : Answer: (running time from start : 26396ms) : 4 13 5 4 13 6 8 12 16 9 13 13 13 16 : 9 2 6 5 6 : 4 : Total running time : 32052 ms, count of dfs=100342
Run the ultimate example around 400 ms
here is my code
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167,
4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
14, 26, 42, 51, 64, 77, 90, 106, 115, 117, 123, 128, 8, 20, 36, 45, 58,
71, 84, 100, 109, 111, 117, 122, 12, 28, 37, 50, 63, 76, 92, 101, 103,
109, 114, 16, 25, 38, 51, 64, 80, 89, 91, 97, 102, 9, 22, 35, 48, 64,
73, 75, 81, 86, 13, 26, 39, 55, 64, 66, 72, 77, 13, 26, 42, 51, 53, 59,
64, 13, 29, 38, 40, 46, 51, 16, 25, 27, 33, 38, 9, 11, 17, 22, 2, 8, 13,
6, 11, 5,
406 ms
Recursion count 77985
[4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167]
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
, 9, 13, 13, 13, 16, 9, 2, 6, 5,
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FindMilestones {
private static int recurCount = 0;
/**
* @param args
*/
public static void main(String[] args) {
int[] points = generatePoints ();
print(points);
int[] dists = generateDists(points);
print(dists);
long start = System.currentTimeMillis();
List founded = findMilestones(dists);
long end = System.currentTimeMillis();
System.out.println((end-start)+" ms");
System.out.println("Recursion count "+recurCount);
Collections.sort(founded);
System.out.println(founded);
System.out.print(founded.get(0)+", ");
for (int i = 1; i < founded.size(); i++){
System.out.print(founded.get(i)-founded.get(i-
1));
System.out.print(", ");
}
System.out.println("");
}
private static List findMilestones(int[] dists){
int L = dists.length;
int N = (int)((1+Math.sqrt(1+8*L))/2);
Arrays.sort(dists);
List founded = new ArrayList ();
int max = dists[dists.length-1];
int[] map = new int[max+1];
for (int i = 0; i < map.length; i++){
map[i] = 0;
}
for (int i = 0; i < dists.length; i++){
map[dists[i]]++;
}
int cur = dists.length-1;
search (founded, dists, N, cur, map);
return founded;
}
private static boolean search (List founded, int[]
sortedDists, int N, int cur, int[] map){
recurCount++;
if (founded.size() == N-1){
return true;
}
//Optimize the lower bound of the index for the next
search nodes
int nextMax = sortedDists[cur];
int delta = 0;
if (founded.size() >=2){
delta = founded.get(0) -
founded.get(founded.size()-1);
}
int minPossible = nextMax-delta;
int lb = 0;
if (minPossible > 0){
lb = Arrays.binarySearch(sortedDists,
minPossible);
if (lb < 0){
lb = -1*lb;
}
}
int remaining = N-founded.size();
lb = Math.max(remaining*(remaining-1)/2-1, lb-1);
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}
private static boolean isCandidate (List founded, int
cand, int[] map){
boolean isCan = true;
if (map[cand] == 0){
return false;
}
for (int val : founded){
int diff = val-cand;
if (map[diff] == 0){
isCan = false;
break;
}
}
return isCan;
}
private static int[] generatePoints (){
//int[] diffs = {2, 3, 5, 7, 8, 10};
int[] diffs = {4,13,5,4,13, 6, 8, 12, 16,9, 13, 13, 13,
16, 9, 2, 6, 5};//{2, 7, 2, 4, 8, 8, 8, 10, 7};
print(diffs);
int[] points = new int[diffs.length+1];
points[0] = 0;
for (int i = 1; i < points.length; i++){
points[i] = points[i-1]+diffs[i-1];
}
return points;
}
private static int[] generateDists (int[] points){
int N = points.length;
int[] dists = new int[N*(N-1)/2];
int k = 0;
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++){
dists[k++] = points[j] - points[i];
}
}
return dists;
}
private static void print (int[] arry){
for (int i = 0; i < arry.length; i++){
System.out.print(arry[i]+", ");
}
System.out.println("");
}
}
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
This one is harder! Still running after 12 minutes...
Now got the results:
time ./milestone_pos.py
[8, 4, 2, 2, 2, 2, 10, 7, 1, 6, 9, 2, 4, 3, 7, 5, 10, 10]
cnt 1227534
time 859.453764915
real 14m19.570s
user 14m19.070s
sys 0m0.280s
主要是Bravethinker的code, 改动很小：
1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
2. founded不用ArrayList, 改成数组，速度更快。
3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
紧要，不怎么影响速度。
public class BraveThinker implements IMilestone {
private int dfsCount = 0;
public int[] findMilestones(int[] dists) {
long t0 = System.currentTimeMillis();
dfsCount = 0;
int L = dists.length;
int N = (int) ((Math.sqrt(1 + 8 * L) - 1) / 2);
int[] founded = new int[N+1];
int max = dists[dists.length - 1];
int[] map = new int[max + 1];
for (int i = 0; i < map.length; i++) {
map[i] = 0;
}
for (int i = 0; i < dists.length; i++) {
map[dists[i]]++;
}
int cur = dists.length - 1;
search(founded, 0, dists, N, cur, map);
int[] solution = new int[N];
for (int i=0; i
solution[i] = founded[i] - founded[i+1];
}
long t1 = System.currentTimeMillis();
System.out.println("DFS count = " + dfsCount + ", takes " + (t1-t0)
+ "ms.");
return solution;
}
private boolean search(int[] founded, int len, int[] dists,
int N, int cur, int[] map) {
dfsCount++;
if (len == N) return true;
// Optimize the lower bound of the index for the next search nodes
int nextMax = dists[cur];
int delta = 0;
if (len >= 2) {
delta = founded[0] - founded[len-1];
}
int minPossible = nextMax - delta;
int lb = 0;
if (minPossible > 0) {
lb = Math.abs(Arrays.binarySearch(dists, minPossible));
}
int remaining = N - len;
lb = Math.max(remaining * (remaining + 1) / 2 - 1, lb - 1);
for (int i = cur; i >= lb; i--) {
int candidate = dists[i];
while (i>=lb && candidate==dists[i-1]) i--;
if (isCandidate(founded, len, candidate, map)) {
founded[len] = candidate;
if (search(founded, len+1, dists, N, i - 1, map)) {
return true;
}
map[candidate]++;
for (int j=0; j
map[founded[j] - candidate]++;
}
}
}
return false;
}
private boolean isCandidate(int[] founded, int len, int candidate
, int[] map) {
if (map[candidate] == 0) return false;
map[candidate]--;
for (int i=0; i
if (map[founded[i]-candidate] == 0) { // revert
map[candidate]++;
for (int j=0; j
map[founded[j]-candidate]++;
}
return false;
}
else {
map[founded[i]-candidate]--;
}
}
return true;
}
}
【在 s*****y 的大作中提到】 : can you share your optimization?
//The mini possible candidate would be the max of the
following 2 cases
//(1) The sum of the least remaining-2 intervals in the
map
//(2) or the remaining*(remaining-1)/2 -th smallest
value in the map
int order = remaining*(remaining-1)/2-1;
int minDist = -1; //The calculate order-th value int the
remaining map
int prevValid = 0;
int count = 0;
int minPossible = 0; //The sum of the least remaining-2
intervals in the map
for (int i = 0; i < map.length; i++){
if (order <= 0){
minDist = prevValid;
break;
}
if (map[i] > 0){
prevValid = i;
if (count < remaining-1){
minPossible += map[i]*i;
count += map[i];
if (count > remaining-1){
minPossible -= (count-
remaining+1)*i;
}
}
}
order -= map[i];
}
minDist = Math.max(minDist, minPossible);
int lb0 = Math.abs(Arrays.binarySearch(sortedDists,
minDist))-1;
int lb = Math.max(lb0, 0);
int prevVal = -1;
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (can == prevVal){
prevVal = can;
continue;
}
prevVal = can;
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}
【在 g**********y 的大作中提到】 : 主要是Bravethinker的code, 改动很小： : 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。 : 2. founded不用ArrayList, 改成数组，速度更快。 : 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关 : 紧要，不怎么影响速度。 : public class BraveThinker implements IMilestone { : private int dfsCount = 0; : public int[] findMilestones(int[] dists) { : long t0 = System.currentTimeMillis(); :
有没有人同意题目说给的是 all the pairs of milestones 意思是
如果是 4 milestones的，那排序后的输入肯定是下面序列？
|<-- a -->|<-- b -->|<-- c -->|
a b c a+b b+c a+b+c
如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
g**********y 发帖数: 14569
56
不是，你看前面例子就知道。
【在 c*******n 的大作中提到】 : 有没有人同意题目说给的是 all the pairs of milestones 意思是 : 如果是 4 milestones的，那排序后的输入肯定是下面序列？ : |<-- a -->|<-- b -->|<-- c -->| : a b c a+b b+c a+b+c : 如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
c*******n 发帖数: 63
57
我看LZ的就符合..
其他牛人给的是更通用的解法，那些太难了
I just wanna make my life easier
【在 g**********y 的大作中提到】 : 不是，你看前面例子就知道。
g**********y 发帖数: 14569
58
我们都希望life有个easy button, 但是没有 :)
【在 c*******n 的大作中提到】 : : 我看LZ的就符合.. : 其他牛人给的是更通用的解法，那些太难了 : I just wanna make my life easier
c*******n 发帖数: 63
59
好吧，我希望题目中的all the pairs可以理解成这个easy button
不知道你是怎么理解的，莫非是 only some of pairs of milestone are given?
不过不管怎么说，严格要求自己还是没有错的
哦，对
我举的4个milestones的例子还有可能是
a b a+b c b+c a+b+c 可能c > a+b
不过肯定有个规律是 a+b+c肯定是最大的一个（升序排序序列的最后一个），其他的不
能保证顺序。
另外，和为a+b+c的最长子序列一定是 a, b ,c
如果是这样，就转成我说的那个求“指定和”找“最长子序列”的问题
【在 g**********y 的大作中提到】 : all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么 : 歧义。 : 问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
C*******l 发帖数: 1198
63
印象中LSAT有很多类似题目，不过是靠人自己分析的。
觉得这条可以计算出来，不用尝试的。
f******3 发帖数: 534
64
i have an idea，not sure if it is correct:
1.先找到最小的2个，假设是a和b.
2.remove ab, a+b from the array
3. find the next smallest left in the array - c, which must be a stone to stone distance.
4. remove a+c, b+c, a+b+c from the array if the array contain those values.
5 find the next smallest value left in the array, repeat the process from 4,
until the value you got a+b+c+d+e...adds up to the biggest value in the
array.
h*********3 发帖数: 111
65
There is a straight roads with 'n' number of milestones. You are given an
array with the distance between all the pairs of milestones in some random
order. Find the position of milestones.
Example:
Consider a road with 4 milestones(a,b,c,d) :
a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d
Distance between a and b = 3
Distance between a and c = 8
Distance between a and d = 10
Distance between b and c = 5
Distance between b and d = 7
Distance between c and d = 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3,5,2 or 2,5,3
m*********2 发帖数: 701
66
so, N is known when you run the program?
first step is obvious to sort it, and get the first and last position.
2) break the distance down to 2 segments so that
10 = segment1 + segment2 （any pair of segments will do)
3) repeat 2
an
random
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
g**e 发帖数: 6127
67
既然数组是随机的，怎么保证最后所有点的位置？比如你这例子，为什么不能输出5,3,
2?
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
s_1_1
s_2_1 s_2_2
s_3_1 s_3_2 s_3_3
...
s_t_1 s_t_2 s_t_3 s_t_t
t = n - 1 (n is the number of point)
s(i,j) means the sum of lj to li (li is the what we want to output)
e.g. s(2,4) = l2+l3+l4
so, s(i,i) = li
rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
s(t,1) = longest length
Use dfs and edge cut to fill the matrix, then output s(i,i) i=1 to t
for the sample:
7, 10, 5, 2, 8, 3
?
? ?
10 ? ?
1) try 8 in s(3,2)
?
? ?
10 8 ?
-> (based on rule1)
2
? ?
10 8 ?
1-1) try 7 in s(2,1)
2
7 ?
10 8 ?
-> (based on rule1, 10-7=3, 7-2=5)
2
7 5
10 8 3
1-2) try 5 in s(2,1),skip since 10-5 is not in the list
1-3) try 3 in s(2,1),skip since 3-2 is not in the list
2) try 7 in s(3,2)
...
the lots of edges will be cut, so it will not be slow.
g***s 发帖数: 3811
75
if it is a math question for n=4,
s_2_2 = sum(all) - s_3_1 * 3
in our sample, s_2_2 = 35 - 10 * 3 = 5
s_3_2 could only be 7 or 8, considering the matrix is symmetric,
let s_3_2 = 8, then s_1_1 = 10 - 8 = 2, s_2_1 = 5 + 2 = 7, s_3_3 = 8 - 5
=3
2
7 5
10 8 3
【在 g***s 的大作中提到】 : s_1_1 : s_2_1 s_2_2 : s_3_1 s_3_2 s_3_3 : ... : s_t_1 s_t_2 s_t_3 s_t_t : t = n - 1 (n is the number of point) : s(i,j) means the sum of lj to li (li is the what we want to output) : e.g. s(2,4) = l2+l3+l4 : so, s(i,i) = li : rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
【在 g***s 的大作中提到】 : s_1_1 : s_2_1 s_2_2 : s_3_1 s_3_2 s_3_3 : ... : s_t_1 s_t_2 s_t_3 s_t_t : t = n - 1 (n is the number of point) : s(i,j) means the sum of lj to li (li is the what we want to output) : e.g. s(2,4) = l2+l3+l4 : so, s(i,i) = li : rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
r*******y 发帖数: 1081
79
sort firstly?
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
public class FindSegments {
public static void main(String args[]) throws InterruptedException {
// List segs = Arrays.asList(new Integer[]{2, 3, 5, 7,
8, 10});
List segs = Arrays.asList(new Integer[]
{2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,2
6,28,
29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56});
long startTime = System.currentTimeMillis();
findSegs(segs);
System.out.printf("Total running time : %d ms",
System.currentTimeMillis() - startTime);
}
private static void findSegs(List segs) {
int t = getN(segs.size())-1;
Collections.sort(segs, Collections.
i**********e 发帖数: 1145
84
My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A = {3,8,2,6,5,3}
Answer:
3 3 2
2 3 3
A = {7,10,16,9,3,6,2,8,5,14}
Answer:
2 5 3 6
6 3 5 2
A = {4,1,6,1,2,4,2,2,3,3}
Answer:
2 1 1 2
A = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5}
Answer:
1 1 2 2 3 3
3 3 2 2 1 1
#include
#include
#include
using namespace std;
typedef hash_map Hash;
typedef Hash::const_iterator HashIter;
// Decrement the key's value by one in the hash table.
// Key's value reaches 0 implies that the number is already
// selected (no longer available), so remove it from the table.
void decrementByOne(Hash &hash, int key) {
assert(hash[key] > 0);
hash[key]--;
if (hash[key] == 0)
hash.erase(key);
}
// Generates all combinations that will be used as the next combinations.
bool generatePartialSolution(int last, const vector &inCombinations, vector &outCombinations, Hash &hash) {
assert(outCombinations.empty());
int n = inCombinations.size();
for (int i = 0; i < n; i++) {
int sumPair = last + inCombinations[i];
if (hash[sumPair] == 0)
return false;
outCombinations.push_back(sumPair);
decrementByOne(hash, sumPair);
}
return true;
}
void solve(const Hash &hash, const vector &combinations, vector solution) {
// No more numbers to pick from, a new solution exists.
if (hash.empty()) {
int n = solution.size();
for (int i = 0; i < n; i++)
cout << solution[i] << " ";
cout << endl;
return;
}
for (HashIter iter = hash.begin(); iter != hash.end(); ++iter) {
int num = iter->first;
Hash hashCopy = hash;
solution.push_back(num);
decrementByOne(hashCopy, num);
vector nextCombinations;
if (generatePartialSolution(num, combinations, nextCombinations, hashCopy)) {
nextCombinations.push_back(num);
solve(hashCopy, nextCombinations, solution);
}
solution.pop_back();
}
}
void solve(int A[], int n) {
Hash hash;
for (int i = 0; i < n; i++) {
hash[A[i]]++;
}
solve(hash, vector(), vector());
}
int main() {
int A[] = {7,10,5,2,8,3};
//int A[] = {1,1,1,2,3,2};
//int A[] = {3,8,2,6,5,3};
//int A[] = {7,10,16,9,3,6,2,8,5,14};
//int A[] = {4,1,6,1,2,4,2,2,3,3};
//int A[] = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5};
/*int A[] = {2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,26,28,29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56};*/
int n = sizeof(A)/sizeof(int);
solve(A, n);
return 0;
}
一些常见面试题的答案与总结 - http://www.ihas1337code.com
【在 i**********e 的大作中提到】 : My code found two valid answers for the following input in about 3 secs ( : obviously not as good as grass, but the algorithm is easier to code). : Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23 : 24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 } : Answer: : 2 7 2 4 8 8 8 10 7 : 7 10 8 8 8 4 2 7 2 : grass, can you explain whether your code generates the solution {7 10 8 8 8 : 4 2 7 2} ? : Test cases:
t******g 发帖数: 252
86
From the length of the array n, we can get the number of the milestones i.
And the i-1 smallest numbers should be the distances between the consecutive
milestones. The rest of the numbers are derived.
t******g 发帖数: 252
87
O(nlgn)
consecutive
【在 t******g 的大作中提到】 : From the length of the array n, we can get the number of the milestones i. : And the i-1 smallest numbers should be the distances between the consecutive : milestones. The rest of the numbers are derived.
g**e 发帖数: 6127
88
wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a
milestone.
consecutive
【在 t******g 的大作中提到】 : From the length of the array n, we can get the number of the milestones i. : And the i-1 smallest numbers should be the distances between the consecutive : milestones. The rest of the numbers are derived.
t******g 发帖数: 252
89
You're right.
【在 g**e 的大作中提到】 : wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a : milestone. : : consecutive
g**********y 发帖数: 14569
90
写了个简化版的：
public class Gloomyturkey implements IMilestone {
private int N;
private int M;
private int[] sequence;
private int[] answer;
private HashMap map;
private boolean[] used;
private int[] sum;
private boolean found;
public int[] findMilestones(int[] segs) {
M = segs.length;
sum = segs;
calcN();
initMap(segs);
used = new boolean[M];
found = false;
sequence = new int[N];
answer = new int[N];
assign(0, M-1);
assign(1, M-2);
dfs(2);
return found? answer : new int[0];
}
private void assign(int index, int from) {
sequence[index] = sum[from];
used[from] = true;
if (index > 0) answer[index-1] = sequence[index-1] - sequence[index];
if (index == N-1) answer[N-1] = sequence[N-1];
}
private void backtrack(int from) {
used[from] = false;
}
private void dfs(int len) {
if (len == N) return;
for (int i=M-3; i>=0; i--) {
if (used[i]) continue;
assign(len, i);
if (validate(len+1)) {
if (len+1 == N) found = true;
dfs(len+1);
if (found) break;
}
backtrack(i);
}
}
private boolean validate(int len) {
int size = len==N? len : len-1;
HashMap partial = new HashMap();
for (int i=1; i<=size; i++) {
for (int j=0; j<=size-i; j++) {
int S = 0;
for (int k=j; k
S += answer[k];
}
int count = partial.get(S)!=null? partial.get(S) :
map.get(S)==null? 0 : map.get(S);
if (count == 0) return false;
partial.put(S, count-1);
}
}
return true;
}
private void calcN() {
N = (int) ((Math.sqrt(1 + 8*M) - 1) / 2 + 0.5);
}
private void initMap(int[] segs) {
map = new HashMap();
for (int seg : segs) {
if (map.get(seg) == null) {
map.put(seg, 0);
}
map.put(seg, map.get(seg)+1);
}
}
}
我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
的多了点，好在都是数。
time ./milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
real 1m5.827s
user 1m5.776s
sys 0m0.028s
假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
prev_pos之和。
基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
以及逐个累加prev_pos里milestone所得到的路程，都在a里，则认为该a[i]可以作为新
的milestone，进行递归。
#! /usr/bin/env python
import sys
DEBUG=1
def milestone(a, total, prev_pos):
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
#print total
return prev_pos + [total]
a.sort()
if a[0] == total:
#print a[0]
return prev_pos + [total]
prev_v = 0
for i in range(len(a) - 1):
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
aa = a[:]
aa.remove(a[i]) # remove first: to avoid b == a[i]
b = total - a[i]
if b in aa: # here use aa!
is_cand = 1
aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 - j]
# reverse
if c in aa:
aa.remove(c)
continue
is_cand = 0
break
if is_cand:
#print a[i]
tmp_pos = milestone(aa, b, prev_pos + [a[i]])
if len(tmp_pos) > 0:
return tmp_pos
return []
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 18,
20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38, 39, 40, 41, 45,
47, 47, 49, 54, 56]
a = [2,4,4,5,5,6,6,6,8,8, 9,9,9,11,11,11,12,13,13,13, 13,13,13,14,16,16,17,
17,17,17, 18,19,19,20,22,22,22,22,22,23, 25,25,26,26,26,26,27,27,28,28, 28,
29,31,33,35,35,36,36,37,38, 38,38,39,39,39,40,41,42,42,43, 44,45,45,46,48,48
,49,50,51,51, 51,51,53,53,55,55,57,58,59,59, 61,63,64,64,64,64,64,64,64,65,
66,68,70,71,72,73,73,75,76,77, 77,77,77,80,81,81,81,83,84,86, 86,86,89,90,90
,90,91,92,92,94, 97,99,99,100,101,102,103,103,103,106, 107,108,109,109,111,
112,112,114,115,116, 117,117,119,120,122,123,123,125,128,128, 128,128,129,
130,132,134,134,136,137,139, 140,141,141,145,145,145,147,150,150,151, 152,
154,156,156,158,162,163,167,169,173]
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])
【在 g***s 的大作中提到】 : s_1_1 : s_2_1 s_2_2 : s_3_1 s_3_2 s_3_3 : ... : s_t_1 s_t_2 s_t_3 s_t_t : t = n - 1 (n is the number of point) : s(i,j) means the sum of lj to li (li is the what we want to output) : e.g. s(2,4) = l2+l3+l4 : so, s(i,i) = li : rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
【在 h*****t 的大作中提到】 : 我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用 : 的多了点，好在都是数。 : time ./milestone_pos.py : [4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6] : real 1m5.827s : user 1m5.776s : sys 0m0.028s : 假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去 : prev_pos之和。 : 基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
h*****t 发帖数: 40
102
是的，那个ultimate的
【在 s*****y 的大作中提到】 : 是算最长那个 66秒吗？
g***s 发帖数: 3811
103
再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
算出答案是26s，全部扫描完是32s。
Answer: (running time from start : 26396ms)
4 13 5 4 13 6 8 12 16 9 13 13 13 16
9 2 6 5 6
4
Total running time : 32052 ms, count of dfs=100342
h*****t 发帖数: 40
104
我的优化后是33秒，CPU是C2D T8100. 递归的次数是58539.
D:\download>d:\Python27\python.exe milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
cnt 58539
time 33.2269999981
Mod:
@@ -1,10 +1,15 @@
#! /usr/bin/env python
import sys
+import time
#DEBUG=1
DEBUG=0
+global cnt
+cnt = 0
def milestone(a, total, prev_pos):
+ global cnt
+ cnt += 1
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
@@ -16,17 +21,21 @@
#print a[0]
return prev_pos + [total]
prev_v = 0
- for i in range(len(a) - 1):
+ for i in range(len(a) - 1): # can safely disgard the last
one as b must exist.
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
- aa = a[:]
- aa.remove(a[i]) # remove first: to avoid b ==
a[i]
+ #aa = a[:]
+ #aa.remove(a[i]) # remove first: to
avoid b == a[i]
+ #if b in aa: # here use aa!
b = total - a[i]
- if b in aa: # here use aa!
+ if (b != a[i] and b in a) or (b == a[i] and i < len(a)
- 1 and a[i+1] == a[i]):
is_cand = 1
- aa.remove(b)
+ aa = a[:]
+ aa.remove(a[i])
+ if b != a[i]:
+ aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 -
j] # reverse
@@ -42,6 +51,7 @@
return tmp_pos
return []
+start_time=time.time()
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16,
17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38,
39, 40, 41, 45, 47, 47, 49, 54, 56]
@@ -49,3 +59,6 @@
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])
+print "cnt", cnt
+end_time=time.time()
+print "time", end_time - start_time
16
【在 g***s 的大作中提到】 : 再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右） : 算出答案是26s，全部扫描完是32s。 : Answer: (running time from start : 26396ms) : 4 13 5 4 13 6 8 12 16 9 13 13 13 16 : 9 2 6 5 6 : 4 : Total running time : 32052 ms, count of dfs=100342
b**********r 发帖数: 91
105
Run the ultimate example around 400 ms
here is my code
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167,
4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
14, 26, 42, 51, 64, 77, 90, 106, 115, 117, 123, 128, 8, 20, 36, 45, 58,
71, 84, 100, 109, 111, 117, 122, 12, 28, 37, 50, 63, 76, 92, 101, 103,
109, 114, 16, 25, 38, 51, 64, 80, 89, 91, 97, 102, 9, 22, 35, 48, 64,
73, 75, 81, 86, 13, 26, 39, 55, 64, 66, 72, 77, 13, 26, 42, 51, 53, 59,
64, 13, 29, 38, 40, 46, 51, 16, 25, 27, 33, 38, 9, 11, 17, 22, 2, 8, 13,
6, 11, 5,
406 ms
Recursion count 77985
[4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167]
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
, 9, 13, 13, 13, 16, 9, 2, 6, 5,
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FindMilestones {
private static int recurCount = 0;
/**
* @param args
*/
public static void main(String[] args) {
int[] points = generatePoints ();
print(points);
int[] dists = generateDists(points);
print(dists);
long start = System.currentTimeMillis();
List founded = findMilestones(dists);
long end = System.currentTimeMillis();
System.out.println((end-start)+" ms");
System.out.println("Recursion count "+recurCount);
Collections.sort(founded);
System.out.println(founded);
System.out.print(founded.get(0)+", ");
for (int i = 1; i < founded.size(); i++){
System.out.print(founded.get(i)-founded.get(i-
1));
System.out.print(", ");
}
System.out.println("");
}
private static List findMilestones(int[] dists){
int L = dists.length;
int N = (int)((1+Math.sqrt(1+8*L))/2);
Arrays.sort(dists);
List founded = new ArrayList ();
int max = dists[dists.length-1];
int[] map = new int[max+1];
for (int i = 0; i < map.length; i++){
map[i] = 0;
}
for (int i = 0; i < dists.length; i++){
map[dists[i]]++;
}
int cur = dists.length-1;
search (founded, dists, N, cur, map);
return founded;
}
private static boolean search (List founded, int[]
sortedDists, int N, int cur, int[] map){
recurCount++;
if (founded.size() == N-1){
return true;
}
//Optimize the lower bound of the index for the next
search nodes
int nextMax = sortedDists[cur];
int delta = 0;
if (founded.size() >=2){
delta = founded.get(0) -
founded.get(founded.size()-1);
}
int minPossible = nextMax-delta;
int lb = 0;
if (minPossible > 0){
lb = Arrays.binarySearch(sortedDists,
minPossible);
if (lb < 0){
lb = -1*lb;
}
}
int remaining = N-founded.size();
lb = Math.max(remaining*(remaining-1)/2-1, lb-1);
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}
private static boolean isCandidate (List founded, int
cand, int[] map){
boolean isCan = true;
if (map[cand] == 0){
return false;
}
for (int val : founded){
int diff = val-cand;
if (map[diff] == 0){
isCan = false;
break;
}
}
return isCan;
}
private static int[] generatePoints (){
//int[] diffs = {2, 3, 5, 7, 8, 10};
int[] diffs = {4,13,5,4,13, 6, 8, 12, 16,9, 13, 13, 13,
16, 9, 2, 6, 5};//{2, 7, 2, 4, 8, 8, 8, 10, 7};
print(diffs);
int[] points = new int[diffs.length+1];
points[0] = 0;
for (int i = 1; i < points.length; i++){
points[i] = points[i-1]+diffs[i-1];
}
return points;
}
private static int[] generateDists (int[] points){
int N = points.length;
int[] dists = new int[N*(N-1)/2];
int k = 0;
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++){
dists[k++] = points[j] - points[i];
}
}
return dists;
}
private static void print (int[] arry){
for (int i = 0; i < arry.length; i++){
System.out.print(arry[i]+", ");
}
System.out.println("");
}
}
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
This one is harder! Still running after 12 minutes...
Now got the results:
time ./milestone_pos.py
[8, 4, 2, 2, 2, 2, 10, 7, 1, 6, 9, 2, 4, 3, 7, 5, 10, 10]
cnt 1227534
time 859.453764915
real 14m19.570s
user 14m19.070s
sys 0m0.280s
主要是Bravethinker的code, 改动很小：
1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
2. founded不用ArrayList, 改成数组，速度更快。
3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
紧要，不怎么影响速度。
public class BraveThinker implements IMilestone {
private int dfsCount = 0;
public int[] findMilestones(int[] dists) {
long t0 = System.currentTimeMillis();
dfsCount = 0;
int L = dists.length;
int N = (int) ((Math.sqrt(1 + 8 * L) - 1) / 2);
int[] founded = new int[N+1];
int max = dists[dists.length - 1];
int[] map = new int[max + 1];
for (int i = 0; i < map.length; i++) {
map[i] = 0;
}
for (int i = 0; i < dists.length; i++) {
map[dists[i]]++;
}
int cur = dists.length - 1;
search(founded, 0, dists, N, cur, map);
int[] solution = new int[N];
for (int i=0; i
solution[i] = founded[i] - founded[i+1];
}
long t1 = System.currentTimeMillis();
System.out.println("DFS count = " + dfsCount + ", takes " + (t1-t0)
+ "ms.");
return solution;
}
private boolean search(int[] founded, int len, int[] dists,
int N, int cur, int[] map) {
dfsCount++;
if (len == N) return true;
// Optimize the lower bound of the index for the next search nodes
int nextMax = dists[cur];
int delta = 0;
if (len >= 2) {
delta = founded[0] - founded[len-1];
}
int minPossible = nextMax - delta;
int lb = 0;
if (minPossible > 0) {
lb = Math.abs(Arrays.binarySearch(dists, minPossible));
}
int remaining = N - len;
lb = Math.max(remaining * (remaining + 1) / 2 - 1, lb - 1);
for (int i = cur; i >= lb; i--) {
int candidate = dists[i];
while (i>=lb && candidate==dists[i-1]) i--;
if (isCandidate(founded, len, candidate, map)) {
founded[len] = candidate;
if (search(founded, len+1, dists, N, i - 1, map)) {
return true;
}
map[candidate]++;
for (int j=0; j
map[founded[j] - candidate]++;
}
}
}
return false;
}
private boolean isCandidate(int[] founded, int len, int candidate
, int[] map) {
if (map[candidate] == 0) return false;
map[candidate]--;
for (int i=0; i
if (map[founded[i]-candidate] == 0) { // revert
map[candidate]++;
for (int j=0; j
map[founded[j]-candidate]++;
}
return false;
}
else {
map[founded[i]-candidate]--;
}
}
return true;
}
}
【在 s*****y 的大作中提到】 : can you share your optimization?
s*****y 发帖数: 897
115
赞，我今晚也要try try。
【在 g**********y 的大作中提到】 : 主要是Bravethinker的code, 改动很小： : 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。 : 2. founded不用ArrayList, 改成数组，速度更快。 : 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关 : 紧要，不怎么影响速度。 : public class BraveThinker implements IMilestone { : private int dfsCount = 0; : public int[] findMilestones(int[] dists) { : long t0 = System.currentTimeMillis(); :
//The mini possible candidate would be the max of the
following 2 cases
//(1) The sum of the least remaining-2 intervals in the
map
//(2) or the remaining*(remaining-1)/2 -th smallest
value in the map
int order = remaining*(remaining-1)/2-1;
int minDist = -1; //The calculate order-th value int the
remaining map
int prevValid = 0;
int count = 0;
int minPossible = 0; //The sum of the least remaining-2
intervals in the map
for (int i = 0; i < map.length; i++){
if (order <= 0){
minDist = prevValid;
break;
}
if (map[i] > 0){
prevValid = i;
if (count < remaining-1){
minPossible += map[i]*i;
count += map[i];
if (count > remaining-1){
minPossible -= (count-
remaining+1)*i;
}
}
}
order -= map[i];
}
minDist = Math.max(minDist, minPossible);
int lb0 = Math.abs(Arrays.binarySearch(sortedDists,
minDist))-1;
int lb = Math.max(lb0, 0);
int prevVal = -1;
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (can == prevVal){
prevVal = can;
continue;
}
prevVal = can;
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}
【在 g**********y 的大作中提到】 : 主要是Bravethinker的code, 改动很小： : 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。 : 2. founded不用ArrayList, 改成数组，速度更快。 : 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关 : 紧要，不怎么影响速度。 : public class BraveThinker implements IMilestone { : private int dfsCount = 0; : public int[] findMilestones(int[] dists) { : long t0 = System.currentTimeMillis(); :
有没有人同意题目说给的是 all the pairs of milestones 意思是
如果是 4 milestones的，那排序后的输入肯定是下面序列？
|<-- a -->|<-- b -->|<-- c -->|
a b c a+b b+c a+b+c
如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
g**********y 发帖数: 14569
120
不是，你看前面例子就知道。
【在 c*******n 的大作中提到】 : 有没有人同意题目说给的是 all the pairs of milestones 意思是 : 如果是 4 milestones的，那排序后的输入肯定是下面序列？ : |<-- a -->|<-- b -->|<-- c -->| : a b c a+b b+c a+b+c : 如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么
歧义。
问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。
【在 c*******n 的大作中提到】 : : 好吧，我希望题目中的all the pairs可以理解成这个easy button : 不知道你是怎么理解的，莫非是 only some of pairs of milestone are given? : 不过不管怎么说，严格要求自己还是没有错的
c*******n 发帖数: 63
125
哦，对
我举的4个milestones的例子还有可能是
a b a+b c b+c a+b+c 可能c > a+b
不过肯定有个规律是 a+b+c肯定是最大的一个（升序排序序列的最后一个），其他的不
能保证顺序。
另外，和为a+b+c的最长子序列一定是 a, b ,c
如果是这样，就转成我说的那个求“指定和”找“最长子序列”的问题
【在 g**********y 的大作中提到】 : all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么 : 歧义。 : 问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
C*******l 发帖数: 1198
127
印象中LSAT有很多类似题目，不过是靠人自己分析的。
觉得这条可以计算出来，不用尝试的。
f******3 发帖数: 534
128
i have an idea，not sure if it is correct:
1.先找到最小的2个，假设是a和b.
2.remove ab, a+b from the array
3. find the next smallest left in the array - c, which must be a stone to stone distance.
4. remove a+c, b+c, a+b+c from the array if the array contain those values.
5 find the next smallest value left in the array, repeat the process from 4,
until the value you got a+b+c+d+e...adds up to the biggest value in the
array.
【在 h*********3 的大作中提到】 : There is a straight roads with 'n' number of milestones. You are given an : array with the distance between all the pairs of milestones in some random : order. Find the position of milestones. : Example: : Consider a road with 4 milestones(a,b,c,d) : : a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d : Distance between a and b = 3 : Distance between a and c = 8 : Distance between a and d = 10 : Distance between b and c = 5
