# 算法

## 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 }

## 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]);
}
}```

## 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
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”

## My code

```package tc.srm.srm236;

import java.util.ArrayList;

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++) {
}
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"};
list = new String []{"a","b","c","d","e"};
list = new String [] {"alpha","beta","gamma","delta","epsilon"};
list = new String [] {"a","b"};
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"};