leetcodeCup.打地鼠

题目链接

九宫格，任意位置到其他位置最多只需要四步，所以两个地鼠出现时间差 >= 4s 时，所以在第一个地鼠之前的位置都可以到达当前位置。

首先把数组按照出现时间排序，新构建一个数组，第一个元素为锤子的初始位置。

可以构建dp数组，dp[i][0]代表第i个地鼠不打时，可以打到的最大地鼠数，dp[i][1]代表第i个地鼠打时可以打到的最大数量。

解法一：动态规划

class Solution {
    int max = 0;
    public int getMaximumNumber(int[][] moles) {
        Arrays.sort(moles, (a, b) -> {
            return a[0] - b[0];
        });
        int[][] nums = new int[moles.length + 1][3];
        nums[0][0] = 0;
        nums[0][1] = 1;
        nums[0][2] = 1;
        int[][] dp = new int[nums.length][2];
        for (int i = 1; i < nums.length; i++) {
            nums[i] = moles[i - 1];
        }

        for (int i = 1; i < nums.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            for (int j = i - 1; j >= 0 ; j--) {
                if (isValid(nums, i, j)) {
                    dp[i][1] = Math.max(dp[j][1] + 1, dp[i][1]);
                }

                if (nums[i][0] - nums[j][0] >= 4) {
                    dp[i][1] = Math.max(dp[j][0] + 1, dp[i][1]);
                    break;
                }
            }
        }

        return Math.max(dp[dp.length - 1][0], dp[dp.length - 1][1]);
    }

    public boolean isValid(int[][] nums, int i, int j) {
        int time = nums[i][0] - nums[j][0];
        if (Math.abs(nums[i][1] - nums[j][1]) + Math.abs(nums[i][2] - nums[j][2]) <= time) {
            return true;
        }
        return false;
    }
}

解法二：dfs，超时了。。。寄

class Solution {
    int max = 0;
    public int getMaximumNumber(int[][] moles) {
        Arrays.sort(moles, (a, b) -> {
            return a[0] - b[0];
        });
        dfs(moles, 0, 0);
        return max;
    }
    
    public void dfs(int[][] moles, int start, int count) {
        if (start == moles.length - 1) {
            if (count > max) {
                max = count;
            }
            return;
        }

        for (int i = start; i < moles.length; i++) {
            if (start == 0 && count == 0) {
                if (moles[i][0] >= Math.abs(moles[i][1] - 1) + Math.abs(moles[i][2] - 1)) {
                    dfs(moles, i, 1);
                }
            } else {
                if (moles[i][0] != moles[start][0] && moles[i][0] - moles[start][0] >= Math.abs(moles[i][1] - moles[start][1]) + Math.abs(moles[i][2] - moles[start][2])) {
                    dfs(moles, i, count + 1);
                }
            }
        }

        if (count > max) {
            max = count;
        }
    }
}