本文主要是介绍LeetCode 面试题 16.13. 平分正方形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 一、题目
- 二、C# 题解
一、题目
给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。
每个正方形的数据 square
包含3个数值,正方形的左下顶点坐标 [X,Y] = [square[0],square[1]]
,以及正方形的边长 square[2]
。所求直线穿过两个正方形会形成4个交点,请返回4个交点形成线段的两端点坐标(两个端点即为4个交点中距离最远的2个点,这2个点所连成的线段一定会穿过另外2个交点)。2个端点坐标 [X1,Y1]
和 [X2,Y2]
的返回格式为 {X1,Y1,X2,Y2}
,要求若 X1 != X2
,需保证 X1 < X2
,否则需保证 Y1 <= Y2
。
若同时有多条直线满足要求,则选择斜率最大的一条计算并返回(与Y轴平行的直线视为斜率无穷大)。
示例:
输入:
square1 = {-1, -1, 2}
square2 = {0, -1, 2}
输出: {-1,0,2,0}
解释: 直线 y = 0 能将两个正方形同时分为等面积的两部分,返回的两线段端点为[-1,0]和[2,0]
提示:
square.length == 3
square[2] > 0
点击此处跳转题目。
二、C# 题解
纯正的数学题,没啥好说的,直接上代码:
public class Solution {public double[] CutSquares(int[] square1, int[] square2) {double l1 = square1[2], l2 = square2[2];double[] c1 = { square1[0] + l1 / 2, square1[1] + l1 / 2 }; // square1 中心坐标double[] c2 = { square2[0] + l2 / 2, square2[1] + l2 / 2 }; // square2 中心坐标double dx = c2[0] - c1[0], dy = c2[1] - c1[1]; // 中心坐标差值if (dx == 0 && dy == 0) { // 中心重合double ml = Math.Max(l1, l2);return new[] { c1[0], c1[1] - ml / 2, c2[0], c2[1] + ml / 2 };}if (Math.Abs(dx) > Math.Abs(dy)) { // 直线靠近 x 轴double k = dy / dx;double[] xs = { square1[0], square1[0] + l1, square2[0], square2[0] + l2 };double x1 = xs.Min(), x2 = xs.Max();double y1 = k * (x1 - c1[0]) + c1[1];double y2 = k * (x2 - c2[0]) + c2[1];return new[] { x1, y1, x2, y2 };}else { // 直线靠近 y 轴double k = dx / dy;double[] ys = { square1[1], square1[1] + l1, square2[1], square2[1] + l2 };double y1 = ys.Min(), y2 = ys.Max();double x1 = k * (y1 - c1[1]) + c1[0];double x2 = k * (y2 - c2[1]) + c2[0];if (x1 <= x2) return new[] { x1, y1, x2, y2 };return new[] { x2, y2, x1, y1 };}}
}
- 时间:124 ms,击败 100.00% 使用 C# 的用户
- 内存:40.60 MB,击败 100.00% 使用 C# 的用户
这篇关于LeetCode 面试题 16.13. 平分正方形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!