首页 > 专题系列 > Java解POJ > POJ 1468 Rectangles [解题报告] Java
2013
11-09

POJ 1468 Rectangles [解题报告] Java

Rectangles

问题描述 :

A specialist in VLSI design testing must decide if there are some components that cover each other for a given design. A component is represented as a rectangle. Assume that each rectangle is rectilinearly oriented (sides parallel to the x and y axis), so that the representation of a rectangle consists of its minimum and maximum x and y coordinates.

Write a program that counts the rectangles that are entirely covered by another rectangle.

输入:

The input contains the text description of several sets of rectangles. The specification of a set consists of the number of rectangles in the set and the list of rectangles given by the minimum and maximum x and y coordinates separated by white spaces, in the format:

nr_rectangles

xmin1 xmax1 ymin1 ymax1

xmin2 xmax2 ymin2 ymax2



xminn xmaxn yminn ymaxn

For each set,there will be less than 5000 rectangles.

输出:

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the number of rectangles that are covered).

样例输入:

3
100 101 100 101
0 3 0 101
20 40 10 400
4
10 20 10 20
10 20 10 20
10 20 10 20
10 20 10 20

样例输出:

0
4

解题代码:

//* @author  [email protected]
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=0,k=0;
        boolean band;
        int M[][]=new int[5000][4];
        while(scan.hasNext()){
            n=scan.nextInt();
            for(int i=0;i< n;i++){
                for(int j=0;j< 4;j++){
                    M[i][j]=scan.nextInt();
                }
            }
            k=0;
            for(int i=0;i< n;i++){
                band=false;
                for(int j=0;j< n;j++){
                    if(j!=i&&M[j][0]<=M[i][0]&&M[j][1]>=M[i][1]&&M[j][2]<=M[i][2]&&M[j][3]>=M[i][3]){
                        band=true;
                        break;
                    }
                }
                if(band)k++;
            }
            System.out.println(k);
        }
    }
}

  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  5. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。