Buttercola: Zenefits: [OA] N-queens max threats

Buttercola: Zenefits: [OA] N-queens max threats
就是说 第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

    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;

    }

http://www.1point3acres.com/bbs/thread-131978-1-1.html
棋盘上放queen 已经保证同一行或者同一列不会出现2个queen，求出对于每个Queen最大的威胁次数威胁指只要一个queen所能移动的范围（对于这道题就是对角线）内有别的queen就算威胁。

1.         int maxThreats(int[] a) {
2.         int len = a.length;. Waral 鍗氬鏈夋洿澶氭枃绔�,
3.         if (len == 0) return 0;
4.         int[] threat = new int[len]; // max threats for queen in each row
5.         Map<Integer, Integer> diag1 = new HashMap();. 1point 3acres 璁哄潧
6.         Map<Integer, Integer> diag2 = new HashMap();
7.         for (int i = 0; i < len; i++){
8.             int col = a[i] - 1;.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
9.             if (diag1.containsKey(i - col)){
10.                 threat[i]++;
11.                 threat[diag1.get(i - col)]++;
12.             }
13.             diag1.put(i - col, i); 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
14.             if (diag2.containsKey(i + col)){
15.                 threat[i]++;. Waral 鍗氬鏈夋洿澶氭枃绔�,
16.                 threat[diag2.get(i + col)]++;
17.             }
18.             diag2.put(i + col, i);.1point3acres缃�
19.         }
20.         int maxThreat = 0;
21.         for (int i = 0; i < len; i++){
22.             maxThreat = Math.max(maxThreat, threat[i]);
23.         }.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
24.         return maxThreat;
25.     }

Read full article from Buttercola: Zenefits: [OA] N-queens max threats