Sunday, October 4, 2015

Zenefits: [OA] N-queens max threats

题目巨长输入格式是
1
2
就是说 第1行第1个是queen 第2行第2个是queen,并保证输入的数字不重复,这样可以得出一个结论:同一行 同一列不会出现2个queen。
题目要求是求出 对于每个Queen, 最大的威胁次数,威胁指只要一个queen所能移动的范围内有别的queen就算威胁 P.S.同一方向上有2个queen威胁你 只算最近的那个。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
由于同一行 同一列不会出现2个queen。(由于输入限制)所以只要考虑对角线 和逆对角线。
举个例子: 棋盘是:. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
100           ---- 1号 queen
010           ---- 2号 queen
001           ---- 3号 queen
1号和3号queen的受威胁次数都是1, 2号是2(被1和3) 所以答案是2

Code (Java):
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] queens = new int[n];
        
        for (int i = 0; i < n; i++) {
            queens[i] = scanner.nextInt();
        }
        
        int result = maxThreats(queens);
        
        System.out.println(result);
        
        scanner.close();
    }
    
    public static int maxThreats(int[] queens) {
        if (queens == null || queens.length <= 1) {
            return 0;
        }
        
        int n = queens.length;
        int max = 0;
        
        for (int row = 0; row < n; row++) {
            int curMaxThreats = 0;
            int col = queens[row] - 1;
            
            curMaxThreats = getNumThreats(row, col, queens);
            
            max = Math.max(max, curMaxThreats);
            if (max == 4) {
                return max;
            }
        }
        
        return max;
    }
    
    private static int getNumThreats(int row, int col, int[] queens) {
        int numThreats = 0;
        int n = queens.length;
        
        // up-left
        int i = row - 1;
        while (i >= 0 && (row - i != col - queens[i] + 1)) {
            i--;
        }
        
        if (i >= 0) {
            numThreats += 1;
        }
        
        // down-right
        i = row + 1;
        while (i < n && (i - row != queens[i] - 1 - col)) {
            i++;
        }
        
        if (i < n) {
            numThreats +=1;
        }
        
        // up-right
        i = row - 1;
        while (i >= 0 && (row - i != queens[i] - 1 - col)) {
            i--;
        }
        
        if (i >= 0) {
            numThreats += 1;
        }
        
        // Down-left
        i = row + 1;
        while (i < n && (i - row) != col - queens[i] + 1) {
            i++;
        }
        
        if (i < n) {
            numThreats += 1;
        }
        
        return numThreats;
    }
} 

1 comment: