g家面经

vegito2002 发表于 2018-3-13 23:56
不知道这个思路有没没有问题; 不计算on circle的点;

需要计算 on circle 的点，其实可以计算出一个象限的点 乘4 减去重复计算点，我一开始是这个方法.你这方法的话..r=1 时 似乎不work

lyh2017 发表于 2018-3-14 01:24
需要计算 on circle 的点，其实可以计算出一个象限的点 乘4 减去重复计算点，我一开始是这个方法.你这方 ...

你说的对, 稍微改了一下:

1. class Solution {
   
2.     int count (int r) {
   
3.         if (r < 1)
   
4.             return 1;
   
5.         int res = 1 + 4 * r;
   
6.         for (int i = 1; i < r; i++) {
   
7.             res += 4 * (int) Math.sqrt (r * r - i * i);
   
8.         }
   
9.         return res;
   
10.     }
    
11. }

复制代码

跟暴力N^2方法的结果对比了一下, 好像没问题;

1. int circlr(int n)
   
2. {
   
3.     n = abs(n);
   
4.     if(n <1)
   
5.         return 1;
   
6.     int res = 4 * n + 1; // x,0 or 0,y
   
7.    
   
8.     for(int i = 1; i < n; i++)
   
9.     {
   
10.         int x = (int)sqrt(n * n - i * i);
    
11.         if(x > i)
    
12.         {
    
13.             res += 8 * (x - i); // x > y
    
14.         }
    
15.         else if(x == i)    // x == y
    
16.         {
    
17.             res += 4;
    
18.         }
    
19.     }
    
20.     return res;
    
21. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

诶？两轮电面吗？

tinylic 发表于 2018-3-13 22:46
那直接暴力枚举呀，第二题是地里高频面经，按面积加权随机选矩形就行

为啥要考虑面积？

1. 应该通过计算整数点与圆心的距离来吧？ 2. 先取一个0-1之间随机数，根据长方形面积（例如三个长方形面积为10，10，10，小于等于1/3选第一个长方形，小于等于2/3用第二个，剩下的选第三个长方形），选好长方形之后，然后生成随机的横纵坐标，保证在该长方形的横纵坐标之内就可以了吧，可以用现有的random function么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

idatascience 发表于 2018-3-19 02:53
求问大侠，我第二题的思路对么？见下：

2. 先取一个0-1之间随机数，根据长方形面积（例如三个长方形面 ...

是的就是这么做紫薯紫薯

tinylic 发表于 2018-3-19 03:09
是的就是这么做紫薯紫薯

多谢大侠的肯定！那么随机的函数可以用系统自带的，对吧？