LeetCode(12) -- 463, 475

P463. Island Perimeter (Easy)

用一个二维数组代表一张地图，1代表陆地，0代表水域。只有一个岛，求它的周长。

我的思路

遍历整个数组，如果是1，就检查它的四个方向，如果是0，周长就加1。

从第一行开始，首先找到第一个1。然后以这个1为起点，用DFS算法遍历所有连通的陆地部分.

讨论区

public class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null) return 0;
        for (int i = 0 ; i < grid.length ; i++){
            for (int j = 0 ; j < grid[0].length ; j++){
                if (grid[i][j] == 1) {
                    return getPerimeter(grid,i,j);
                }
            }
        }
        return 0;
    }

    public int getPerimeter(int[][] grid, int i, int j){
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {return 1;}
        if (grid[i][j] == 0) {
            return 1;
        }
        if (grid[i][j] == -1) return 0;

        int count = 0;
        grid[i][j] = -1;

        count += getPerimeter(grid, i-1, j);
        count += getPerimeter(grid, i, j-1);
        count += getPerimeter(grid, i, j+1);
        count += getPerimeter(grid, i+1, j);

        return count;

    }
}

34%

最优解

class Solution {
    public int islandPerimeter(int[][] grid) {
        int ans = 0, R = grid.length, C = R == 0 ? 0 : grid[0].length;
        for(int r = 0; r < R; ++r){
            for(int c = 0; c < C; ++c){
                ans += grid[r][c] *
                    (4 - (r < 1 ? 0 : 2*grid[r-1][c]) - (c < 1 ? 0 : 2*grid[r][c-1]));
            }
        }
        return ans;
    }
}

遍历整个数组。这个解法中，判断周长增量的方法非常有意思。首先，从一个“口”变成一个“日”，它的周长增加了多少？由4变成了6。为什么呢？我们可以把它理解为，左右两条边向下条延长了1个长度，因此周长的增量就是2。同理，如果在已有的方格右边新加一个方格，那增量也是2。如果它左边和上边都已经有了，那增量其实就是0。

(4 - (r < 1 ? 0 : 2*grid[r-1][c]) - (c < 1 ? 0 : 2*grid[r][c-1]));这行代码表达的就是这个意思。

P475. Heaters (Easy)

给房子供暖。第一个数组代表房子的位置，第二个数组代表暖气的位置。求暖气的最小半径。

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

我的思路

我的代码

public class E_475_Heaters {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int r = heaters[0] - houses[0];
        int close;
        for (int i = 1, j = 0; i < houses.length && j < heaters.length - 1; i++) {
            if (houses[i] >= heaters[j] && houses[i] <= heaters[j+1]) {
                close = Math.min(houses[i] - heaters[j], heaters[j+1] - houses[i]);
                r = Math.max(close, r);
            } else {
                j++;
            }
        }
        r = Math.max(r, houses[houses.length - 1] - heaters[heaters.length - 1]);
        return r;
    }

    public static void main(String[] args) {
        int[] houses = {101027544,144108930,282475249,457850878,458777923,470211272,622650073,984943658};
        int[] heat =   {114807987,115438165,137522503,143542612,16531729,441282327,74243042,784484492,823378840,
                823564440};
        int radius = new E_475_Heaters().findRadius(houses, heat);
        System.out.println("radius = " + radius);
    }
}

代码是错误的，一直有bug，放弃了

讨论区

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);

        // pre represents the heater that's ahead of the current house
        int pre = heaters[0];
        // index of the heater
        int i = 0;
        int res = 0;
        for (int house : houses) {
            // looking for the heater that's immediately after the current house
            while (i < heaters.length - 1 && heaters[i] < house) {
                pre = heaters[i];
                i++;
            }

            int distanceToPreHeater = Math.abs(house - pre);
            int distanceToAfterHeater = Math.abs(house - heaters[i]);
            res = Math.max(res, Math.min(distanceToPreHeater, distanceToAfterHeater));
        }

        return res;
    }
}

其实我的代码已经很接近了。这个题肯定是要两个数组同时推进的过程中比大小。外层循环肯定是长的数组，也就是houses。第一个任务就是找到离我当前房子位置最近的前一个暖气。只要我的暖气不是最后一个，并且暖气的位置在当前房子位置的左边，就再试下一个暖气，直到找到最接近房子位置的暖气为止。

第二个任务是计算两个绝对值——到左边这个暖气的距离和到右边暖气的距离。这两个距离中较小的一个，就决定了当前点位需要的暖气最小供暖距离。所有点位供暖距离的最大值，就是结果。

最优解

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);

        int index = 0;
        int radius = 0;
        int left = -heaters[index];
        int right = heaters[index];

        for (int house : houses) {
            while (house > right) {
                left = right;
                right = index < heaters.length - 1? heaters[++index] : Integer.MAX_VALUE;
            }

            while (left < house - radius && house + radius < right) {
                if (left < 0) {
                    radius = Math.abs(house - right);
                } else if (right ==Integer.MAX_VALUE ) {
                    radius = Math.abs(house - left);
                } else if (Math.abs(house - right) <  Math.abs(house - left) )  {
                    radius =  Math.abs(house - right);
                } else {
                    radius = Math.abs(house - left);
                }
            }
        }
        return radius;
    }
}