剑指Offer——网易笔试之不要二——欧式距离的典型应用

举报
SHQ1874009 发表于 2020/12/29 23:24:51 2020/12/29
【摘要】 剑指Offer——网易笔试之不要二——欧式距离的典型应用 前言       欧几里得度量(euclidean metric)(也称欧氏距离)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。      &n...

剑指Offer——网易笔试之不要二——欧式距离的典型应用

前言

      欧几里得度量(euclidean metric)(也称欧氏距离)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

      二维空间的公式

      0ρ = sqrt( (x1-x2)^2+(y1-y2)^2 ) |x| = √( x2 + y2 )

      三维空间的公式

      0ρ = √( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 ) |x| = √( x2 + y2 + z2 )

      解题思路:欧式距离不能为2,左上角(4*4)满足,右上角中即在同一行中看a[i][j-2]是否存在蛋糕,若不存在,则放置蛋糕。左下角中若在同一列,则看a[i-2][j]是否存在蛋糕,若不存在,则放置蛋糕。对于右下角,则看a[i-2][j]、a[i][j-2]是否存在蛋糕,若不存在,则放置蛋糕。

 


      package cn.edu.ujn.nk;
      import java.util.Scanner;
      import java.util.regex.Pattern;
      /**
       * 2016-08-09 --01
       * 不要二
       * 二货小易有一个W*H的网格盒子,网格的行编号为0~H-1,网格的列编号为0~W-1。每个格子至多可以放一块蛋糕,任意两块蛋糕的欧几里得距离不能等于2。
       * 对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为: ( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) )的算术平方根
       * 小易想知道最多可以放多少块蛋糕在网格盒子里。
       * 输入描述: 每组数组包含网格长宽W,H,用空格分割.(1 ≤ W、H ≤ 1000)
       *
       * 输出描述: 输出一个最多可以放的蛋糕数
       *
       * 输入例子: 3 2
       *
       * 输出例子: 4
       *
       * @author SHQ
       *
       */
      public class NotTwo {
      /**
       * @param args
       */
      public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      while (in.hasNextLine()) {
      String str = in.nextLine();
      if (str.length() == 0) {
      break;
      }
      Pattern pattern = Pattern.compile("[ ]+");
      String[] arr = pattern.split(str);
      int w = Integer.parseInt(arr[0]);
      int h = Integer.parseInt(arr[1]);
      System.out.println(notTwoGreed(h, w));
      }
      }
      private static int notTwo(int h, int w) {
      int cnt = 0;
      for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
      if ((i / 2 + j / 2) % 2 == 0)
      cnt++;
      }
      }
      return cnt;
      }
      private static int notTwoGreed(int h, int w) {
      int [][] a = new int [h][w];
      int cnt = 0;
      for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
      // 左上
      if(i< 2 && j < 2){
      a[i][j] = 1;
      cnt++;
      // 右上
      }else if(i < 2 && j-2 >= 0 && a[i][j-2] != 1){
      a[i][j] = 1;
      cnt++;
      // 左下
      }else if(j < 2 && i - 2 >= 0 && a[i-2][j] != 1){
      a[i][j] = 1;
      cnt++;
      // 右下
      }else if(i >= 2 && j >= 2 && a[i-2][j] != 1 && a[i][j-2] != 1){
      a[i][j] = 1;
      cnt++;
      }
      }
      }
      return cnt;
      }
      }
  
 

 

美文美图

 

文章来源: shq5785.blog.csdn.net,作者:No Silver Bullet,版权归原作者所有,如需转载,请联系作者。

原文链接:shq5785.blog.csdn.net/article/details/52169793

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。