Facebook暖身挑战,我似乎无法解决 – 海战游戏

huangapple go评论87阅读模式
英文:

Facebook warm up challenge that I can't seem to figure out - Battleship

问题

我正在解决 这个 MetaCareers 代码挑战(需要一个账户):

您正在一个具有 𝑅 行和 𝐶 列的单元格网格上玩战舰游戏。网格上可能有 0 个或更多艘战舰,每艘占据一个单独的单元格。从顶部数第 𝑖 行和从左数第 𝑗 列的单元格可能包含一艘战舰(𝐺<sub>𝑖,𝑗</sub>​=1),也可能不包含(𝐺<sub>𝑖,𝑗</sub>​=0)。

您将对网格中的一个随机单元格进行射击。您将从可能的 𝑅∗𝐶 单元格中均匀随机选择此单元格。您对被您的射击命中的单元格是否包含战舰感兴趣。

您的任务是实现函数 getHitProbability(R, C, G),该函数返回此概率。

注意:您的返回值的绝对或相对误差最多为 10<sup>─6</sup> 才能被视为正确。

约束条件

  • 1 ≤ 𝑅,𝐶 ≤ 100
  • 0 ≤ 𝐺<sub>𝑖,𝑗</sub>​ ≤ 1

示例测试案例 #1

R = 2
C = 3
G = 0 0 1
    1 0 1
期望返回值 = 0.50000000

示例测试案例 #2

R = 2
C = 2
G = 1 1
    1 1
期望返回值 = 1.00000000

示例解释

在第一个案例中,网格中有 6 个单元格,其中 3 个包含战舰。因此,您的射击命中其中一个的概率是 3&nbsp;/&nbsp;6&nbsp;=&nbsp;0.5。

在第二个案例中,所有 4 个单元格都包含战舰,命中战舰的概率为 1.0。

所以很明显概率 = 船只数 / 网格大小

我将它四舍五入到第 8<sup>th</sup> 位小数 -- 我似乎做错了.... 我的错误是什么?

我的代码尝试:

if (G.length == 0) return 0;
double ships = 0.00000000;
for (int[] i : G) {
    if (i[0] == 1) ships++;
}
float ans = Math.round((ships / (float) G.length) * 100000000) / 100000000.0f;
System.out.println(String.valueOf(ans));
String ans = String.format(&quot;%.8f&quot;, (ships / G.length));
// System.out.println(ans);
// BigDecimal bd1 = new BigDecimal(ships/G.length);
// System.out.println(bd1);
英文:

I am working on this MetaCareers code challenge (needs an account):

> You're playing Battleship on a grid of cells with 𝑅 rows and 𝐶 columns. There are 0 or more battleships on the grid, each occupying a single distinct cell. The cell in the 𝑖<sup>th</sup> row from the top and 𝑗<sup>th</sup> column from the left either contains a battleship (𝐺<sub>𝑖,𝑗</sub>​=1) or doesn't (𝐺<sub>𝑖,𝑗</sub>​=0).
>
> You're going to fire a single shot at a random cell in the grid. You'll choose this cell uniformly at random from the 𝑅∗𝐶 possible cells. You're interested in the probability that the cell hit by your shot contains a battleship.
>
> Your task is to implement the function getHitProbability(R, C, G) which returns this probability.
>
> Note: Your return value must have an absolute or relative error of at most 10<sup>─6</sup> to be considered correct.
>
> ### Constraints
>
> * 1 ≤ 𝑅,𝐶 ≤ 100
> * 0 ≤ 𝐺<sub>𝑖,𝑗</sub>​ ≤ 1
>
> ### Sample test case #1
>
> none
&gt; R = 2
&gt; C = 3
&gt; G = 0 0 1
&gt; 1 0 1
&gt;

>
> none
&gt; Expected Return Value = 0.50000000
&gt;

>
> ### Sample test case #2
>
> none
&gt; R = 2
&gt; C = 2
&gt; G = 1 1
&gt; 1 1
&gt;

>
> none
&gt; Expected Return Value = 1.00000000
&gt;

>
> ### Sample Explanation
>
> In the first case, 3 of the 6 cells in the grid contain battleships. Therefore, the probability that your shot will hit one of them is 3&nbsp;/&nbsp;6&nbsp;=&nbsp;0.5.
>
> In the second case, all 4 cells contain battleships, resulting in a probability of 1.0 of hitting a battleship.

So it seems clear that the probability = ships / grid_size

And I'm rounding it to the 8<sup>th</sup> decimal -- which I can't seem to get right.... What is my mistake?

My code attempt:

if (G.length == 0) return 0;
double ships = 0.00000000;
for (int[] i : G) {
    if (i[0] == 1) ships++;
}
float ans = Math.round((ships / (float) G.length) * 100000000) / 100000000.0f;
System.out.println(String.valueOf(ans));
String ans = String.format(&quot;%.8f&quot;, (ships / G.length));
// System.out.println(ans);
// BigDecimal bd1 = new BigDecimal(ships/G.length);
// System.out.println(bd1);

答案1

得分: 1

以下是你的代码尝试中存在的问题:

  • 它只查看给定网格的第一列 -- 用 i[0] -- 没有考虑到可能会在 i[1]i[2],...等处有船只。
  • 它错误地计算了网格中单元格的总数,因为 G.length 代表了行数,没有考虑到列数。单元格的总数是 G.length * G[0].length
  • 它试图重新定义变量 ans,这将阻止代码编译。
  • 在定义了 ans 后没有执行 return
  • 它将一个计算出的值转换为 String,而函数的返回类型是 double

不是一个真正的问题,但:

  • 它试图将一个值舍入到8位小数,但这是不必要的,因为这只会使答案准确。
  • 它处理网格为空的情况,但这种情况永远不会发生,因为保证了 𝑅 和 𝐶 至少为 1。
  • 你可以直接将单元格的值添加到 ships 值中,而不是测试单元格的值,因为保证单元格的值为 0 或 1,将 0 添加到 ships 的值不会改变其值。

以下是你代码的修正:

public double getHitProbability(int R, int C, int[][] G) {
   double ships = 0;
   for (int[] row : G) {
       for (int val : row) {  // 访问行中的每个单元格
           ships += val; // 无条件地将单元格的值添加到 ships 中
       } 
   }
   return ships / (G.length * G[0].length); // 总单元格数为 R*C
}
英文:

These are the issues in your code attempt:

  • It only looks at the first column of the given grid -- with i[0] -- not considering that there might be ships at i[1], i[2], ...etc.
  • It miscalculates the total number of cells in the grid, as G.length represents the number of rows, not taking into account the number of columns. The total number of cells is G.length * G[0].length.
  • It attempts to redefine the variable ans which will not allow the code to compile.
  • It does not execute a return after having defined ans.
  • It converts a calculated value to String, while the return type of the function is double.

Not a real problem, but:

  • It attempts to round a value to 8 decimal digits, but this is not necessary, as that will only make the answer less accurate.
  • It deals with the case where the grid is empty, but this case will never happen, as 𝑅 and 𝐶 are guaranteed to be at least 1.
  • Instead of testing the value of the cell, you could just add the cell's value to the ships value, given that the cell's value is guaranteed to be 0 or 1 and adding 0 leaves the value of ships unchanged.

Here is the correction of your code as a spoiler:

>! <code> public double getHitProbability(int R, int C, int[][] G) {
>! double ships = 0;
>! for (int[] row : G) {
>! for (int val : row) { // Visit each cell in the row
>! ships += val; // Add the cell's value unconditionally
>! }
>! }
>! return ships / (G.length * G[0].length); // The total number of cells is R*C
>! }</code>

huangapple
  • 本文由 发表于 2023年6月16日 12:48:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/76487028.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定