y***n
发帖数: 1594 | 1 Given an array A (the array can be treated as a big number) and a number
n, find the biggest number that you can reach to via n swaps. A swap can
only happen in adjacent items. For example, given [1 3 4 2 5 7 9]
n=1, 3 1 4 2 5 7 9
n=2, 1 3 4 -> 1 4 3 -> 4 1 3
我写了一个，http://ideone.com/9c4Xcx 觉得不太好，求指导。。 | I*****x
发帖数: 84 | 2 d和e的输出有问题吧，不应该是413XXXX是应该输出431XXXX这样的么 | y***n
发帖数: 1594 | | l*********8
发帖数: 4642 | 4 必须要做n次swap吗？ 还是说最多n次swap
如果输入
[9, 8, 7, 6], n =3 答案是多少？
【在 y***n 的大作中提到】
: Given an array A (the array can be treated as a big number) and a number
: n, find the biggest number that you can reach to via n swaps. A swap can
: only happen in adjacent items. For example, given [1 3 4 2 5 7 9]
: n=1, 3 1 4 2 5 7 9
: n=2, 1 3 4 -> 1 4 3 -> 4 1 3
: 我写了一个，http://ideone.com/9c4Xcx 觉得不太好，求指导。。
| I*****x
发帖数: 84 | 5 我用python写了个swap程序，我测试了一下似乎能用，如果你懂python的话可以看看，
欢迎大家批评指正
def swap(numbers, swap_times):
current_position = 0
while current_position < len(numbers) and swap_times != 0:
max_pos = -1
max_val = numbers[current_position]
for i in range(1, swap_times+1):
if current_position + i < len(numbers) and numbers[current_
position + i] > max_val:
max_pos = current_position + i
max_val = numbers[current_position + i]
if max_pos > -1:
numbers.pop(max_pos)
numbers.insert(current_position,max_val)
swap_times -= max_pos-current_position
current_position += 1
return numbers
print swap([1,3,4,2,5,7,9], 1)
print swap([1,3,4,2,5,7,9], 2)
print swap([1,3,4,2,5,7,9], 3)
print swap([1,3,4,0,5,7,9], 3)
print swap([1,3,4,0,5,7,9], 4)
print swap([9,8,7,6,5,4,3], 4) | y***n
发帖数: 1594 | | l*********8
发帖数: 4642 | 7 写了一个，还没测呢。 可能有bug。 时间复杂度也不是最优的。
假设可以swap 0到n次。
void swapToMax(int * ary, int arySize, int n) {
if (n <= 0 || arySize < 2)
return;
int * pMax = max_element(ary, ary+min(n+1, arySize));
if (pMax > ary) {
int tmp = *pMax;
copy(ary, pMax, ary+1);
*ary = tmp;
}
swapToMax(ary+1, arySize-1, n-(pMax-ary));
}
【在 y***n 的大作中提到】
: Given an array A (the array can be treated as a big number) and a number
: n, find the biggest number that you can reach to via n swaps. A swap can
: only happen in adjacent items. For example, given [1 3 4 2 5 7 9]
: n=1, 3 1 4 2 5 7 9
: n=2, 1 3 4 -> 1 4 3 -> 4 1 3
: 我写了一个，http://ideone.com/9c4Xcx 觉得不太好，求指导。。
| m*****n
发帖数: 2152 | 8 没懂啊，find the biggest number that you can reach to via n swaps 是不是指经
过n swaps，最大数被换到数组头？
这个不是找n+1中的最大值，然后换到第一个吗？
【在 y***n 的大作中提到】
: Given an array A (the array can be treated as a big number) and a number
: n, find the biggest number that you can reach to via n swaps. A swap can
: only happen in adjacent items. For example, given [1 3 4 2 5 7 9]
: n=1, 3 1 4 2 5 7 9
: n=2, 1 3 4 -> 1 4 3 -> 4 1 3
: 我写了一个，http://ideone.com/9c4Xcx 觉得不太好，求指导。。
| l*********8
发帖数: 4642 | 9 n可能 >= array size
【在 m*****n 的大作中提到】
: 没懂啊，find the biggest number that you can reach to via n swaps 是不是指经
: 过n swaps，最大数被换到数组头？
: 这个不是找n+1中的最大值，然后换到第一个吗？
| m*****n
发帖数: 2152 | 10 从题意看，应该不会，但是编程做sanity check是有必要的。
【在 l*********8 的大作中提到】
: n可能 >= array size
| l*********8
发帖数: 4642 | 11 如果array是[1 2 3 4 5]
那么swap 9 次可以得： [54312]
10次可以得到： [54321]
n>=array size是完全有意义的
【在 m*****n 的大作中提到】
: 从题意看，应该不会，但是编程做sanity check是有必要的。
| z******g
发帖数: 271 | 12 如果不需要把次数用完的话，俺感觉可以用greedy
while(n > 0) {
Find the leftmost array position which is not filled
with optimal number, break if not found;
For each number on the right, calculate its distance
to the position;
Find the largest number with distance <= n, swap it to
the position and subtract n by distance;
} | m*****k
发帖数: 731 | 13 why each?, just need check the array idx within distance range n to the
leftmost array position which is not filled
with optimal number , |
|
