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;}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！