剑指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