前言
简单记录一下笔试情况。
一、判断一点是否在三角形中
题目简介
输入四个二维坐标，前三个点表示一个三角形，判断最后一个点是否在其内（不包含恰好在边上的情况）。
一、面积
海伦公式：p=(a+b+c)/2，S=sqrt(p*(p-a)*(p-b)*(p-c));
假设三角形三个点为A，B，C，若O点位于三角形内，则有：S(ABC)=S(ABO)+S(ACO)+S(BCO)。并且任意一个小三角形面积不为0，例如：S(ABO)=0，表示 O 点落于AB边上。
代码实现
import java.math.BigDecimal;
public class Solution {
public boolean judge (double[] point1, double[] point2, double[] point3, double[] point) {
double S=getArea(point1,point2,point3);
double S1=getArea(point1,point2,point),
S2=getArea(point1,point3,point),
S3=getArea(point2,point3,point);
// if(S1==0.0||S2==0.0||S3==0.0||Math.abs(S-S1-S2-S3)<1e-6)// 误差精度：0.000001;
// return false;
// return true;
//或者采用 BigDecimal
BigDecimal s1=BigDecimal.valueOf(S1),
s2=BigDecimal.valueOf(S2),
s3=BigDecimal.valueOf(S3);
BigDecimal s=BigDecimal.valueOf(S);
BigDecimal a=new BigDecimal("0.0");
if(s1.compareTo(a)==0||s2.compareTo(a)==0||s3.compareTo(a)==0||s.compareTo(s1.add(s2).add(s3))!=0)
return false;
return true;
}
private double getArea(double[] a,double[] b,double[] c){
double ab=Math.sqrt(Math.pow(b[1]-a[1],2)+Math.pow(b[0]-a[0],2));
double ac=Math.sqrt(Math.pow(c[1]-a[1],2)+Math.pow(c[0]-a[0],2));
double bc=Math.sqrt(Math.pow(b[1]-c[1],2)+Math.pow(b[0]-c[0],2));
double p=(ab+bc+ac)/2;
return Math.sqrt(p*(p-ab)*(p-ac)*(p-bc));
}
}
二、向量
由于double数比较时存在精度损失，对于某些情况可能会产生错误的结果。
二维坐标系中：A(x1,y1) 和 B(x2,y2) 构成的向量 AB（A指向B）：(x2-x1,y2-y1);
AB(x1,y1)， BC(x2,y2) ：
向量点乘：AB · AC=|AB|*|AC|*cosθ = x1*y1+x2*y2; 若 AB // AC，则点乘结果和|AB|*|AC|相等。
向量叉乘：AB x AC = (x1*y2，x2*y1); 叉乘生成一个第三维的向量，其大小为 |AB|*|AC|*sinθ，方向通过右手法则来判定：(x1*y2-x2*y1的值为正，其方向指向z轴正方向；为负指向z轴负方向（可以采用向量 (1，1) 分别与 (1，0) (0，1) 尝试验证）；为零时，两向量平行。
https://zhuanlan.zhihu.com/p/359975221
https://zhuanlan.zhihu.com/p/356529702
代码实现
public class Solution {
public boolean judge (double[] point1, double[] point2, double[] point3, double[] point) {
// 将三个点 逆时针 排列，
if(getDirect(point1,point2,point3))// 1,2,3 逆时针排列。
return getDirect(point1,point2,point)&&getDirect(point2,point3,point)
&&getDirect(point3,point1,point);
else //顺序为 1,3,2
return getDirect(point1,point3,point)&&getDirect(point3,point2,point)
&&getDirect(point2,point1,point);
}
private boolean getDirect(double[] a,double[] b,double[] c){ // 点 c 是否在 ab向量的左侧，即叉乘结果大于0
double x1=b[0]-a[0],y1=b[1]-a[1];
double x2=c[0]-a[0],y2=c[1]-a[1];
return x1*y2-y1*x2>0;
}
}
二、求矩阵中的最小步数
题目简介
二维数组中 n*m，值为0或者1，0表示可以通过，1表示不能通过。求从(0,0)处走到(n-1,m-1)处所需要的最小步数（一次只能走一步）
题目保证可以从 （0，0）可以走到（n-1,m-1）。
代码实现
import java.util.*;
public class Solution {
/**
* @param map int整型二维数组
* @return int整型
*/
public int floodFill(int[][] map, int n, int m) {
// write code here
Deque<int[]> q=new ArrayDeque<>();
int[] x={1,-1,0,0},y={0,0,1,-1};
int step=0;
q.offer(new int[]{0,0,0});
map[0][0]=1;
int res=Integer.MAX_VALUE;
while(!q.isEmpty()){
int t=q.size();
step++;
int newX,newY;
while(t--!=0){
int[] tmp=q.poll();
if(tmp[0]==n-1&&tmp[1]==m-1)
return tmp[2];
for(int i=0;i<4;i++){
newX=tmp[0]+x[i];
newY=tmp[1]+y[i];
if(newX>=0&&newX<n&&newY>=0&&newY<m&&map[newX][newY]==0){
q.offer(new int[]{newX,newY,step});
map[newX][newY]=1;
}
}
}
}
return 0;
}
public static void main(String[] args) {
int[][] a=new int[][]{
{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}
};
Solution s=new Solution();
int res=s.floodFill(a,4,4);
System.out.println(res);
}
}
总结
完
