Friday, July 3, 2015

hackRand problem

Q:  检测一个2D数组  其 x,y坐标的k范围内是否存在重复


import java.util.*;

public class Main {
    public static void main(String args[] ) throws Exception {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if(n<=0){System.out.print("NO"); return;}
        String str  = sc.nextLine();
        // change str into line
        List<Integer[]> list = new LinkedList();

        int[][] Arr = new int[n][n];

        for(int i =0;i<n;i++) {
            String strArr[] = sc.nextLine().split("\\s+");
            for (int j = 0; j < strArr.length; j++)
                Arr[i][j] = Integer.parseInt(strArr[j]);
        }

        int k = sc.nextInt();
        int m = Arr[0].length;


        Map<Integer,Integer> map = new HashMap();

        //  each position as a center, and find it int the circle/ use k as radius
        for(int i =0;i<n;i++) {
            map.clear();
            // set-up the circle into the map
            for(int row=0; row < Math.min(n,i+k+1);row++){
                for(int col = 0;col<Math.min(n,k+1);col++){
                    if(row == i && col == 0)
                        continue;
                    int key = Arr[row][col];
                    addMap(map, key);
                }
            }
            // mvoe for each i-th position
            for (int j = 0; j < Arr[0].length; j++) {   // not, current i,j is not included
                int val = Arr[i][j];
                if(map.containsKey(val)){
                    System.out.println("YES");
                    return;
                }
                map.put(val,1);
                // remove most left column and add most left row
                if(j+ 1< m)
                    delMap(map,Arr[i][j+1]);
                if( j - k >=0 ){ // delete this 2k column
                    for(int row=Math.max(0,i-k); row < Math.min(n,i+k+1);row++){
                        delMap(map, Arr[row][j-k]);
                    }
                }
                if( j + k +1 < m ){ // add this 2k column
                    for(int row=Math.max(0,i-k); row < Math.min(n,i+k+1);row++){
                        addMap(map, Arr[row][j + k + 1]);
                    }
                }

            }
        }

        System.out.println("NO");
    }

    private static void addMap(Map<Integer,Integer> map, int val){
        int count = 0;
        if(map.containsKey(val))
            count = map.get(val);
        map.put(val,count+1);
    }
    private static void delMap(Map<Integer,Integer> map, int val){
        if(map.containsKey(val)) {
            int count = map.get(val);
            if(count==1){
                map.remove(val);
            }else
                map.put(val, count - 1);
        }
    }

}


No comments:

Post a Comment