Tag: 贪心

两个球员网格遍历游戏

给定一个M * N网格和两个玩家p1和p2在网格上的位置。 有n个球放在网格上的不同位置。 设这些球的位置为B(1), B(2), B(3) …, B(n) 。 我们需要计算选择所有球所需的最小曼哈顿距离 。 如果i < j则应按升序选择球，即如果在B(j)之前选择B(j) 。 请考虑以下示例案例： p1 = (1, 1) p2 = (3, 4)让我们考虑球的位置为B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5) 输出将为5因为p1将首先选择B(1), B(2), B(3)并且p1将选择B(4) 我的方法 我做了一个贪婪的 方法并计算了给定球B(i)的p1和p2距离（从i = 1 to n ）并且将最小值加到输出并相应地更新了玩家的位置。 但是这种方法在许多测试用例中都失败了。 PS：在我过去的一次采访中提出了这个问题， O(n)解决了这个问题的预期。 编辑：更多的测试用例可以是 […]

覆盖较大线的最小线段数

我给出了相同长度的n个线段（1维）的坐标，我需要找到这些线段的最小数量以完全覆盖更大的线或发现这是不可能的。 较大的行从0开始，到L结束。 线段可以从[0-D，LD]范围开始，并且所有线段都具有相同的长度2 * D. 因此，例如对于以下输入： 15 2 4 // L, n, D -2 7 // beginning coordinates of line segments 21 14 4 10 4 6 3 16 17 -1 2 14 11 12 8 5 1 9 9 3 -2 -1 4 0 5 -3 6 3 1 14 12 5 -3 -2 […]

动态编程 – 改变

我在查找动态硬币更改问题的最后一段代码时遇到了麻烦。 我已经包含了以下代码。 我无法弄清楚最后的else 。 我应该在那时使用贪婪算法，还是可以根据表中已有的值计算答案？ 我努力尝试理解这个问题，我觉得我很接近。 该方法通过创建表并使用存储在表中的结果来解决较大的问题而不使用递归，从而找到进行特定更改所需的最小硬币数量。 public static int minCoins(int[] denom, int targetAmount){ int denomPosition; // Position in denom[] where the first spot // is the largest coin and includes every coin // smaller. int currentAmount; // The Amount of money that needs to be made // remainingAmount = 0 ; denomPosition–) { for(currentAmount […]