网站建设服务上海,如何安装wordpress博客,中建招聘网,360导航建设网站怎么建【问题描述】面试题 16.03. 交点
给定两条线段#xff08;表示为起点start {X1, Y1}和终点end {X2, Y2}#xff09;#xff0c;如果它们有交点#xff0c;请计算其交点#xff0c;没有交点则返回空值。要求浮点型误差不超过10^-6。若有多个交点#xff08;线段重叠表示为起点start {X1, Y1}和终点end {X2, Y2}如果它们有交点请计算其交点没有交点则返回空值。要求浮点型误差不超过10^-6。若有多个交点线段重叠则返回 X 值最小的点X 坐标相同则返回 Y 值最小的点。
【解答思路】
https://leetcode-cn.com/problems/intersection-lcci/solution/jiao-dian-by-leetcode-solution/ 需要认真考虑所有情况 联立方程各种优化
1. 时间复杂度O(1) 空间复杂度O(1)
class Solution {public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {int x1 start1[0], y1 start1[1];int x2 end1[0], y2 end1[1];int x3 start2[0], y3 start2[1];int x4 end2[0], y4 end2[1];double[] ans new double[2];Arrays.fill(ans, Double.MAX_VALUE);// 判断两直线是否平行if ((y4-y3)*(x2-x1) (y2-y1)*(x4-x3)) {// 判断两直线是否重叠if ((y2-y1)*(x3-x1) (y3-y1)*(x2-x1)) {// 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上if (isInside(x1, y1, x2, y2, x3, y3)) {updateRes(ans, x3, y3);}// 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上if (isInside(x1, y1, x2, y2, x4, y4)) {updateRes(ans, (double)x4, (double)y4);}// 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上if (isInside(x3, y3, x4, y4, x1, y1)) {updateRes(ans, (double)x1, (double)y1);}// 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上if (isInside(x3, y3, x4, y4, x2, y2)) {updateRes(ans, (double)x2, (double)y2);}}} else {// 联立方程得到 t1 和 t2 的值double t1 (double)(x3 * (y4 - y3) y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));double t2 (double)(x1 * (y2 - y1) y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));// 判断 t1 和 t2 是否均在 [0, 1] 之间if (t1 0.0 t1 1.0 t2 0.0 t2 1.0) {ans[0] x1 t1 * (x2 - x1);ans[1] y1 t1 * (y2 - y1);}}if (ans[0] Double.MAX_VALUE) {return new double[0];}return ans;}// 判断 (x, y) 是否在「线段」(x1, y1)~(x2, y2) 上// 这里的前提是 (x, y) 一定在「直线」(x1, y1)~(x2, y2) 上private boolean isInside(int x1, int y1, int x2, int y2, int x, int y) {// 若与 x 轴平行只需要判断 x 的部分// 若与 y 轴平行只需要判断 y 的部分// 若为普通线段则都要判断return (x1 x2 || (Math.min(x1, x2) x x Math.max(x1, x2))) (y1 y2 || (Math.min(y1, y2) y y Math.max(y1, y2)));}private void updateRes(double[] ans, double x, double y) {if (x ans[0] || (x ans[0] y ans[1])) {ans[0] x;ans[1] y;}}
}2. 时间复杂度O(N) 空间复杂度O(1) 【总结】
1. 编程需要一定的数学基础思维要有广度和深度
2. 善于封装函数
