TopCoder SRM 236 BusinessTasks

最近在看TopCoder网站上的算法的教程,从最简单的看起,发现不练不行,所以找到教程中提到的最简单的例子开始做,练练手。

Link to original Problem Statement

Problem Statement

A busy businessman has a number of equally important tasks which he must accomplish. To decide which of the tasks to perform first, he performs the following operation.

He writes down all his tasks in the form of a circular list, so the first task is adjacent to the last task. He then thinks of a positive number. This number is the random seed, which he calls n. Starting with the first task, he moves clockwise (from element 1 in the list to element 2 in the list and so on), counting from 1 to n. When his count reaches n, he removes that task from the list and starts counting from the next available task. He repeats this procedure until one task remains. It is this last task that he chooses to execute.

Given a String[] list representing the tasks and an int n, return the task which the businessman chooses to execute.

Definition
Class: BusinessTasks
Method: getTask
Parameters: String[], int
Returns: String
Method signature: String getTask(String[] list, int n)

Constraints
– list will contain between 2 and 50 elements inclusive.
– Each element in list will contain between 1 and 50 characters inclusive.
– Each element in list will contain only characters ‘a’-‘z’.
– n will be between 1 and 10000000 inclusive.

Examples

0)
{“a”,”b”,”c”,”d”}
2
Returns: “a”
We start counting from a. So a is 1, b is 2. We remove b, so list is now {a,c,d}. We continue from c. So c is 1, d is 2. We remove d, so list is now {a,c}. We continue from a. So a is 1, c is 2. We remove c, and now we are left with the last task a.

1)
{“a”,”b”,”c”,”d”,”e”}
3
Returns: “d”
We start counting from a. So a is 1, b is 2, c is 3. We remove c, now list = {a,b,d,e}. We continue from d. So d is 1, e is 2, a is 3. We remove a, now list = {b,d,e}. We continue from b. So b is 1, d is 2, e is 3. We remove e, now list = {b,d}. We continue from b. So b is 1, d is 2 and finally b is 3. We remove b, and now we are left with just one task d.

2)
{“alpha”,”beta”,”gamma”,”delta”,”epsilon”}
1
Returns: “epsilon”

3)
{“a”,”b”}
1000
Returns: “a”

4)
{“a”,”b”,”c”,”d”,”e”,”f”,”g”,”h”,”i”,”j”,”k”,”l”,”m”,”n”,”o”,”p”,”q”,”r”,”s”,”t”,”u”,”v”,”w”,”x”,”y”,”z”}
17
Returns: “n”

5)
{“zlqamum”,”yjsrpybmq”,”tjllfea”,”fxjqzznvg”,”nvhekxr”,”am”,”skmazcey”,”piklp”,”olcqvhg”,”dnpo”,”bhcfc”,
“y”,”h”,”fj”,”bjeoaxglt”,”oafduixsz”,”kmtbaxu”,”qgcxjbfx”,”my”,”mlhy”,”bt”,”bo”,”q”}
9000000
Returns: “fxjqzznvg”

Analysis

问题我就不翻译了。 算是个很简单的问题,简单暴力解决。

My code

package tc.srm.srm236;

import java.util.ArrayList;

public class BusinessTasks {

	public static String getTask(String[] list, int n){
		// Use the arraylist to quickly locate and delete n-th element
		ArrayList<Integer> listArray = new ArrayList<Integer>();
		// Fill it with int instead of original string to save space
		for (int i = 0; i < list.length; i++) {
			listArray.add(i);
		}
		int len = listArray.size();
		int current = 0;
		while (len != 1) {
			// Add n - 1 to the target place and modulo len to get the position
			current = (current + n - 1) % len;
			listArray.remove(current);
			len = listArray.size();
		}
		return list[listArray.get(0)];
	}

	public static void main(String[] args) {
		String [] list;
		list = new String [] {"a","b","c","d"};
		System.out.println(getTask(list, 2));
		list = new String []{"a","b","c","d","e"};
		System.out.println(getTask(list, 3));
		list = new String [] {"alpha","beta","gamma","delta","epsilon"};
		System.out.println(getTask(list, 1));
		list = new String [] {"a","b"};
		System.out.println(getTask(list, 1000));
		list = new String [] {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t",
			"u","v","w","x","y","z"};
		System.out.println(getTask(list, 17));
		list = new String [] {"zlqamum","yjsrpybmq","tjllfea","fxjqzznvg","nvhekxr","am","skmazcey","piklp",
			"olcqvhg","dnpo","bhcfc","y","h","fj","bjeoaxglt","oafduixsz","kmtbaxu",
			"qgcxjbfx","my","mlhy","bt","bo","q"};
		System.out.println(getTask(list, 9000000));
	}
}

Complexity

空间复杂度是O(n),和输入list的长度有关,有没有可能更小呢?应该很难,因为想想,总是需要记录哪些元素没有被删除,而记录这个一定需要跟删除元素数量呈线性的空间,所以应该不容易在减小了。这里使用了ArrayList来储存这个数组因为String []是没法删除某个固定位置的,也就是说一次删除需要O(n)的操作,那么如果直接在上面处理,复杂度就变成O(n2)了。所以用了可以快速删除的ArrayList,好像就相当于C++的Vector。

时间复杂度也是O(n),一共n个元素,一次删除一个,自然需要n步搞定。

发表评论

电子邮件地址不会被公开。