题目:
Problem Statement
You are given a bidirectional cyclical queue which contains N elements. You need to extract several elements from this queue. You can do 3 kinds of operations with this queue:
Extract first element. After applying this operation, queue a1, ..., aK becomes a2, ..., aK.
Shift queue elements left. After applying this operation, queue a1, ..., aK becomes a2, ..., aK, a1.
Shift queue elements right. After applying this operation, queue a1, ..., aK becomes aK, a1, ..., aK-1.
You are given the initial number of elements in the queue N and a int[] indices which contains the initial (1-based) positions of wanted elements in the queue. Return the minimal number of left and right shifts you'll have to perform to extract the wanted elements in the given order.
Definition
Class:
BidirectionalQueue
Method:
extractElements
Parameters:
int, int[]
Returns:
int
Method signature:
int extractElements(int N, int[] indices)
(be sure your method is public)
Constraints
-
N will be between 1 and 50, inclusive.
-
indices will contain between 1 and N elements, inclusive.
-
Each element of indices will be between 1 and N, inclusive.
-
All elements of indices will be distinct.
Examples
0)
10
{1, 2, 3}
Returns: 0
The elements are extracted in the same order as they appear in the queue, so no shifts are required.
1)
10
{2, 9, 5}
Returns: 8
To extract the first wanted element, 1 left shift is required. After this the next wanted element will be 7th in a queue with 9 elements, so to extract it 3 right shifts are required. Finally, the last wanted element will be 5th in a queue with 8 elements, so either 4 left shifts or 4 right shifts are required.
2)
32
{27, 16, 30, 11, 6, 23}
Returns: 59
3)
10
{1, 6, 3, 2, 7, 9, 8, 4, 10, 5}
Returns: 14
题目意思大概为:有一个双向的有序队列(1-N), 可以做 出队 左移 右移操作. 给定一个数组, 要求在队列中找到数组里的每一个数字,并出队,计算最少的移动次数.
我的求解思路:
1.遍历给定的数组,假定当前要出队的数字是n.
2.使用Java的Queue队列来存储有序队列,将队头的数组与n对比, 不匹配就做出队入队操作:queue.add(queue.remove());(等于左移一次).
3.记录移动次数直至找到匹配的数字. 然后将该数字出队,重复操作2.
实现的代码:
import java.util.LinkedList;
import java.util.Queue;
public class BidirectionalQueue {
public static void main(String[] args) {
BidirectionalQueue bq = new BidirectionalQueue();
int N = 10;
int[] indices = {1, 6, 3, 2, 7, 9, 8, 4, 10, 5};
System.out.println(bq.extractElements(N, indices));
}
int extractElements(int N, int[] indices){
Queue<Integer> queue = new LinkedList<Integer>();
int num = 0;
int lenght = N;
for (int i = 1; i <= N; i++) {
queue.add(i);
}
//找出取出每个数要移动的距离
for (int i = 0; i < indices.length; i++) {
int move = 0;
while(indices[i] != queue.peek()){
move++;
queue.add(queue.remove());
}
queue.remove();
// System.out.println(queue);
move = Math.min(move, lenght-move);
// System.out.println(move);
num += move;
lenght--;
}
return num;
}
}
总结: Topcoder上高手的代理思路大致也是这样, 但是我花了将近1小时才搞定. so, 分数可想而知, 比起前几天算是有进步了, 有思路, 没效率. 看懂题目花了挺多时间, 对Java的基础操作还不熟练,Queue之前只是看过, 没用过, 学完数据结构后也没好好练习过. 继续努力吧, 天道酬勤!