Currently browsing category

算法

TopCoder SRM 208 TallPeople

Problem Statement

Link to original problem statement

A group of people stand before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. You will be given a String[] people containing the height of each person. Elements of people correspond to rows in the rectangle. Each element contains a space-delimited list of integers representing the heights of the people in that row. Your job is to return 2 specific heights in a int[]. The first is computed by finding the shortest person in each row, and then finding the tallest person among them (the “tallest-of-the-shortest”). The second is computed by finding the tallest person in each column, and then finding the shortest person among them (the “shortest-of-the-tallest”).

Definition
Class: TallPeople
Method: getPeople
Parameters: String[]
Returns: int[]
Method signature: int[] getPeople(String[] people)

Constraints
– people will contain between 2 and 50 elements inclusive.
– Each element of people will contain between 3 and 50 characters inclusive.
– Each element of people will be a single space-delimited list of positive integers such that:
1) Each positive integer is between 1 and 1000 inclusive with no extra leading zeros.
2) Each element contains the same number of integers.
3) Each element contains at least 2 positive integers.
4) Each element does not contain leading or trailing whitespace.

Examples
0)
{“9 2 3”,
“4 8 7”}
Returns: { 4, 7 }
The heights 2 and 4 are the shortest from the rows, so 4 is the taller of the two. The heights 9, 8, and 7 are the tallest from the columns, so 7 is the shortest of the 3.

1)
{“1 2”,
“4 5”,
“3 6”}
Returns: { 4, 4 }

2)
{“1 1”,
“1 1”}
Returns: { 1, 1 }

Analysis

还是个很简单的问题。。木有任何技术含量,先建立二维数组,把int从string里弄出来,然后去找每一排的最大最小值之类的。

My code

package tc.srm.srm208;

public class TallPeople {
	public static int[] getPeople(String[] people){
		// x = row size, y = column size
		int x = people.length, y = 1;
		// Use people0 to find the column size
		char [] people0 = people[0].toCharArray();
		for (int i = 0; i < people0.length; i++) {
			if (people0[i] == ' ') {
				y++;
			}
		}
		int [][] matrix = new int [x][y];
		// Fill the matrix with parsed int
		for (int i = 0; i < x; i++) {
			int current = 0;
			int nextSpace;
			for (int j = 0; j < y; j++) {
				nextSpace = people[i].indexOf(' ', current);
				if (nextSpace == -1) {
					nextSpace = people[i].length();
				}
				matrix[i][j] = Integer.parseInt(people[i].substring
                                               (current, nextSpace));
				current = nextSpace + 1;
			}
		}
		// Find tall in short
		int shortt, tallInShort = 0;
		for (int i = 0; i < x; i++) {
			shortt = 1001;
			for (int j = 0; j < y; j++) {
				if (matrix[i][j] < shortt) {
					shortt = matrix[i][j];
				}
			}
			if (shortt > tallInShort) {
				tallInShort = shortt;
			}
		}
		// Find short in short
		int tall, shortInTall = 1001;
		for (int j = 0; j < y; j++) {
			tall = 0;
			for (int i = 0; i < x; i++) {
				if (matrix[i][j] > tall) {
					tall = matrix[i][j];
				}
			}
			if (tall < shortInTall) {
				shortInTall = tall;
			}
		}
		int [] rtn = {tallInShort, shortInTall};
		return rtn;
	}

	public static void main(String[] args) {
		String [] people;
		people = new String [] {"9 2 3", "4 8 7"};
		System.out.println(getPeople(people)[0] + "  " + getPeople(people)[1]);
		people = new String [] {"1 2", "4 5", "3 6"};
		System.out.println(getPeople(people)[0] + "  " + getPeople(people)[1]);
		people = new String [] {"1 1", "1 1"};
		System.out.println(getPeople(people)[0] + "  " + getPeople(people)[1]);
	}
}

Complexity

空间复杂度是O(mn),m,n代表行数和列数。因为想要按行或者按列遍历,最方便的方法就是弄个二维数组了,直接通过下标读取了。 如果想做的更好当然也可以,但是要牺牲不少时间,考虑到这里数字都不大,所以无所谓了。

时间复杂度也是O(mn), 确切的说O(n + mn + mn + nm + c),因为填充数组,和先按行在按列,先按列在按行各对整个数组遍历了一次。这个应该没有特别能提升的空间了吧,起码不会比O(mn)更小我觉得,不过就我这水平肯定也弄不出来更小的。。。

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步搞定。