Exercise one

Posted on | In , | |
Words count in article: 2.4k | Reading time ≈ 15

1.（What a Simple Research）(30 Points)

Doctor Li is doing some research on Chinese ancient
music. Many Chinese ancient music has only five kinds of tones, which can be denoted by
‘C’,‘D’,‘E’,‘G’, and ‘A’. Given a piece of music score, Li wants to do some simple statistics.

Input

There are no more than 20 test cases.

In each test case:

The first line contains two integers n and m (2 <= n, m<=20), indicating that a piece of music
score is represented by an n*m matrix of tones. Only ‘C’,‘D’,‘E’,‘G’, and ‘A’ can appear in the
matrix.

Then the n*m matrix follows.
The input ends with a line of ‘0 0’.

Output

For each test case:
For each kind of tone shown in the matrix, calculate the appearing times of it, and print the
result in descending order according to the appearing times. If more than one kind of tones has
the same appearing times, print them in the lexicographical order.

1
2
3
4
5
6
7
8
9
10
11
12
13
Sample Input
4 5
AGCDE
AGDDE
DDDDD
EEEEE
2 4
GADC
CDEE
0 0
Sample Output
D 8 E 7 A 2 G 2 C 1
C 2 D 2 E 2 A 1 G 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.Scanner;
import java.io.*;

public class No1 {
    public static void main(String[] args){
    	class chrr{
    		char x;
    		int num;
    	}
        int a = 0, b = 0;
        String cc = null;
        int A = 0, C = 0, D = 0, E = 0, G = 0;
        Scanner scan = new Scanner(System.in);
        while(true)
        {
        	a = scan.nextInt();
            b = scan.nextInt();
        	if(a == 0 && b == 0)
        		break;
        	for(int i=0; i<5; i++)
        	{
        		A = C = D = E = G = 0;
        	}
        	
        	for(int i=0; i<a; i++)
        	{
        			cc = scan.next();
	        		char[] c = cc.toCharArray();
	        		for(int j=0; j<b; j++)
		        	{
	        			if(c[j] == 'A')
	        				A++;
	        			else if(c[j] == 'C')
	        				C++;
	        			else if(c[j] == 'D')
	        				D++;
	        			else if(c[j] == 'E')
	        				E++;
	        			else if(c[j] == 'G')
	        				G++;
	        		}
        	}
        	chrr allc[] = new chrr[5];
        	for(int i=0; i<5; i++)
        		allc[i] = new chrr();
        	allc[0].x = 'A'; allc[0].num = A;
        	allc[1].x = 'C'; allc[1].num = C;
        	allc[2].x = 'D'; allc[2].num = D;
        	allc[3].x = 'E'; allc[3].num = E;
        	allc[4].x = 'G'; allc[4].num = G;
        	
        	for(int i=0; i<4; i++)
        	{
        		for(int j=0; j<4-i; j++)
        		{
        			if(allc[j].num < allc[j+1].num)
        			{
        				chrr temp = allc[j];
        				allc[j] = allc[j+1];
        				allc[j+1] = temp;
        			}
        			else if(allc[j].num == allc[j+1].num)
        			{
        				if(allc[j].x > allc[j+1].x)
        				{
        					chrr temp = allc[j];
            				allc[j] = allc[j+1];
            				allc[j+1] = temp;
        				}
        			}
        		}
        	}
        	
        	for(int i=0; i<5; i++)
        	{
        		if(allc[i].num != 0)
        			System.out.print(allc[i].x + " " + allc[i].num + " ");
        	}
        	System.out.print("\n");
        }
        scan.close();
    }
}

2.（Reverse Words in a String）(30 Points)

Given a string, you need to write a program to
reverse the order of characters in each word within a sentence while still preserving whitespace
and initial word order.

1
2
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.Scanner;

public class No2 {
	public static void main(String[] args) {
		String str1 = null;
		Scanner scan = new Scanner(System.in);
		while(scan.hasNextLine()) 
		{
			str1 = scan.nextLine();
			char[] cstr1 = str1.toCharArray();
			int len = str1.length();
			char[] cstr2 = new char[len];
			
			int f1 = 0;
			int f2 = 0;
			int z = 0;
			
			for(int i=0; i<len; i++)
			{
				if(cstr1[i] == ' ')
				{
					cstr2[z++] = ' ';
					f1 = f2 = i+1;
				}
				else
				{
					for(int j=i; j<len; j++)
					{
						if(cstr1[j] == ' ')
						{
							f2 = j-1;
							i = j-1;
							break;
						}
						else if(j == len-1)
						{
							f2 = len-1;
							i = len;
							break;
						}
					}
					for(int j=f2; j>=f1; j--)
					{
						cstr2[z++] = cstr1[j];
					}
					
				}
			}
			
			String str2 = String.valueOf(cstr2);
			System.out.print(str2 + '\n');
		}
		scan.close();
	}
	
}

3. (Maximum Submatrix）(40 Points)

Given an n*n matrix composed of 0 or 1, determine the
top left corner position and the order of the maximum submatrix in which all of element are 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input:
5
1 1 0 1 0
1 0 1 0 1
0 1 1 1 0
0 1 0 0 0
0 1 0 0 1
Output: position: (2,1), order: 3*1
Input:
3
1 0 1
0 1 1
1 0 1
output: position: (0,2), order: 3*1
Input:
4
1 1 1 0
0 1 1 0
1 0 1 1
0 1 1 1
output: position: (0, 2), order: 4*1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.*;

public class No3 {
	public static void main(String[] args)
	{
		int n = 0;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		char [][]mat = new char[n][];
		for(int i=0; i<n; i++)
		{
			mat[i] = new char[n];
		}
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				int rem = scan.nextInt();
				mat[i][j] = (char)('0' + rem);
			}
		}
		Solution ret = new Solution();
		ret.maximalRectangle(mat);
		int xx = ret.getx();
		int yy = ret.gety();
		int mxx = ret.getxx();
		int myy = ret.getyy();
		System.out.println("position: (" + xx + "," +yy +"), order: " + mxx + "*" + myy);
		scan.close();
	}
}

class Solution {
	int x;
	int y;
	int maxx;
	int maxy;
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int columnCount = matrix.length,rowCount = matrix[0].length,max=0;
        int[] count = new int[rowCount];
        for(int i=0;i<columnCount;i++){
            for(int j=0;j<rowCount;j++)
                if (matrix[i][j] == '1') 
                    count[j]++;
                else 
                    count[j]=0;
            for(int j=0;j<rowCount;j++){
                int currentCount = count[j];
                while(currentCount>0){
                    int columnNumber=1;
                    int idxx = 0;
                    int flag = 0;
                    for(int idx=j+1;idx<count.length;idx++)
                        if(currentCount <= count[idx])
                            columnNumber++;
                        else
                        {
                        	idxx = idx;
                        	flag = 1;
                            break;
                        }
                    if(flag == 0)
                    	idxx = count.length;
                    max = Math.max(max,columnNumber*currentCount);
                    if(max == columnNumber*currentCount)
                    {
                    	x = i-currentCount+1;
                    	y = idxx-columnNumber;
                    	maxx = currentCount;
	                    maxy = columnNumber;
                    }
	                currentCount--;
                }
            }
        }
        return max;
    }
    public int getx() {
    	return x;
    }
    public int gety() {
    	return y;
    }
    public int getxx() {
    	return maxx;
    }
    public int getyy() {
    	return maxy;
    }
}

4. Chess

implement a simple chess game

Rules of Chess

Project implementation:

The following is the provided code framework:

1

Experiment

implement all the class methods under the chessmen folder. Note that the chessman classes inherit from a abstract base class Chessman in cn/edu/sysu/jood/core/Chessman.java

For each chessman, you need to complete three functions, which are listed as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
Can chessman move?

@param to destination
@return true if can move
*/
public abstract boolean canGo(Position to);

/*
get path to destination.
if
@param to destination
@return point of path
*/
public abstract List<Position> path(Position to);

/*
Get status of chessman

@return 
*/
public abstract Status status();

  • canGo: Can chessman move? For example, the queen at 1d(row 1, column d)wants to move to 4f, as 4f is not on the diagonal对角线 direction, thus canGo should return false.

  • Path: A list of points that is he path from current position to the target position. For example, the queen at 1d wants to move to 5h, thus the Path function should return 2e 3f 4g.

  • status: Return the status of the chessmen (e.g, King, Queen, Knight…..)

Caution:

Only the simple rules are required, the rules related to chessboard are for later experiment. For example, a rook can move any number of squares along a rank or file but cannot leap over other pieces, in which “move any number of squares along a rank or file “ is simple rule, and”cannot leap over other pieces” is chessboard rule.

Rules:

  • King: The king moves one square in any direction.
  • Queen: The queen moves any number of squares in any direction.
  • Rook: A rook can move any number of squares along a rank or file.
  • Bishop: A bishop can move any number of squares diagonally.
  • Knight: A knight moves to any of the closest squares that are not on the sane rank, file, or diagonal.(Thus the move forms an “L”-shape: two squares vertically and one square horizontally, or two squares horizontally and one square vertically.)
  • Pawn: A pawn can move forward to the unoccupied square immediately in front of it on the sanme file.

Judgement

We will use the Junit framework to test each class of chessmen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//Bishop.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

import java.util.ArrayList;

public class Bishop extends Chessman {

	@Override
    public boolean canGo(Position to) {
		int to_row = to.row;
        int to_column = to.col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        int row = Math.abs(to_row-on_row);
        int col = Math.abs(to_column-on_column);
        if(col == row)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Bishop;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
		List<Position> ret = new ArrayList<Position>();
		int row_d = to.row-getPosition().row;
        int col_d = to.col-getPosition().col;
        int abs_row = Math.abs(row_d);
        int row_f = row_d / abs_row;
        int col_f = col_d / abs_row;
        for(int i = 1; i < abs_row; i++)
        	ret.add(new Position(getPosition().row+i*row_f,getPosition().col+i*col_f));
        return ret;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//King.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class King extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int abs_row = Math.abs(to.row-getPosition().row);
        int abs_col = Math.abs(to.col-getPosition().col);
        if (abs_row<2 && abs_col<2)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.King;
        return ret;
    }

	@Override
	public List<Position> path(Position to) {
		List<Position> ret=new ArrayList<Position>();
//		Position e = to;
//		ret.add(e);
		return ret;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//Knight.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Knight extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int sum = 0;
        int to_row = to.row;
        int to_column = to.col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        sum = (to_row - on_row)*(to_row - on_row) + (to_column - on_column)*(to_column - on_column);
        if(sum == 5)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Knight;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
		List<Position> ret = new ArrayList<Position>();
//		Position e = to;
//		ret.add(e);
		return ret;
	}    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//Pawn.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Pawn extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int to_row = to.row;
        int to_column = to.col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        if((on_column == to_column) && ((to_row-on_row) == 1))
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Pawn;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
		List<Position> ret = new ArrayList<Position>();
//		Position e = to;
//		ret.add(e);
		return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//Queen.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Queen extends Chessman {
    @Override
    public boolean canGo(Position to) {
    	int abs_row = Math.abs(to.row-getPosition().row);
        int abs_col = Math.abs(to.col-getPosition().col);
        if (abs_row == abs_col || abs_row==0 || abs_col==0)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Queen;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
    	List<Position> ret=new ArrayList<Position>();
    	int row_d = to.row-getPosition().row;
        int col_d = to.col-getPosition().col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        
        if(row_d == 0 || col_d == 0)
        {
        	if(row_d == 0)
            {
            	int num = Math.abs(col_d);
            	col_d = col_d / num;
            	for(int i = 1; i < num; i++)
            		ret.add(new Position(on_row,on_column+i*col_d));
            }
            else
            {
            	int num = Math.abs(row_d);
            	row_d = row_d / num;
            	for(int i = 1; i < num; i++)
            		ret.add(new Position(on_row+i*row_d,on_column));
            }
        }
        else
        {
        	int num=Math.abs(row_d);
            row_d = row_d / num;
            col_d = col_d / num;
            for(int i = 1; i < num; i++)
            	ret.add(new Position(on_row+i*row_d,on_column+i*col_d));
        }
        return ret;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//Rook.java
package cn.edu.sysu.jood.core.chessmen;

import java.util.ArrayList;
import java.util.List;

import cn.edu.sysu.jood.core.Chessman;
import cn.edu.sysu.jood.core.Position;
import cn.edu.sysu.jood.core.Chessman.Status;

public class Rook extends Chessman {

    @Override
    public boolean canGo(Position to) {
    	int row = to.row-getPosition().row;
        int col = to.col-getPosition().col;
        if (row == 0 || col == 0)
        	return true;
        else
        	return false;
    }

    @Override
    public Status status() {
    	Status ret = Status.Rook;
        return ret;
    }

    @Override
    public List<Position> path(Position to) {
    	List<Position> ret=new ArrayList<Position>();
    	int row_d = to.row-getPosition().row;
        int col_d = to.col-getPosition().col;
        int on_row = getPosition().row;
        int on_column = getPosition().col;
        if(row_d == 0)
        {
        	int num = Math.abs(col_d);
        	col_d = col_d / num;
        	for(int i = 1; i < num; i++)
        		ret.add(new Position(on_row,on_column+i*col_d));
        }
        else
        {
        	int num = Math.abs(row_d);
        	row_d = row_d / num;
        	for(int i = 1; i < num; i++)
        		ret.add(new Position(on_row+i*row_d,on_column));
        }
        return ret;
	}
}
Donate? comment?