聊一个有点“头大”的事情。前几天，我的新同事刚刚入职一周，就提交了一份让人震惊的代码：新增了2万行，删减了1.4万行。
看到这个提交，我的第一反应是：“这是什么情况？我不想review这段代码，脑袋痛了。” 😅
你没听错，这小伙伴刚进公司，代码量就这么庞大。
作为一个老程序员，看到这样的提交，我的内心是崩溃的。不是因为他写的不好，而是实在是太多了，单是审查这些代码就得花上好几个小时。
你要知道，2w行代码可是个巨大的工程，很多时候，代码量大不代表质量高，有可能里面藏了不少坑啊。
我还特地看了下这位新同事的提交日志，他做的新增和删减看起来是为了一个大功能模块的改进。但是，代码量这么大，真心担心会出问题。
尤其是对于刚入职的新人来说，他可能还没完全熟悉团队的开发规范和项目架构。
所以，我想说的是，尽管这个提交量看起来让人心脏不稳，但还是得认认真真地review。只能祈祷他下次提交时能少一点代码，多一些思考~
算法题：凸多边形
聊一个经典的算法题：凸多边形。
说实话，作为一个程序员，每当碰到“凸多边形”这类几何问题时，我的脑袋就会开始自动生成一堆数学公式和算法步骤。其实，数学这东西，有时候看似高大上，但处理起来却有不少的套路可循。
首先，什么是凸多边形？简单来说，凸多边形是指所有的内角都小于180度的多边形，换句话说，它没有内凹的部分。所以说，如果你给我一堆点，我要判断它们能不能构成一个凸多边形，理论上就要做一些几何上的判断。好了，废话不多说，我们先看看这题的典型要求：给定一组二维坐标，找出这些点组成的凸多边形。
在解决这类问题时，我们通常会采用“凸包算法”。凸包是一个很有意思的概念，指的是把一堆点“包起来”，就像是一个橡皮筋把一堆钉子围住一样。
我们可以用Graham 扫描算法或者Andrew's 算法来求解。今天我决定用更简单的Graham扫描来举例子。首先，我们要做的就是根据极角排序，将点按照与某个点的连线角度从小到大排序。
好了，话不多说，给大家上代码。以Java为例，我们可以这样写：
import java.util.*;
public class ConvexHull {
// 用于表示点的类
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
// 计算叉积，用来判断转向
static int crossProduct(Point o, Point a, Point b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
// 计算凸包
public static List<Point> convexHull(Point[] points) {
if (points.length <= 1) return Arrays.asList(points);
// 先按x排序，如果x一样则按y排序
Arrays.sort(points, (p1, p2) -> p1.x == p2.x ? p1.y - p2.y : p1.x - p2.x);
// 建立下凸包
List<Point> lower = new ArrayList<>();
for (Point p : points) {
while (lower.size() >= 2 && crossProduct(lower.get(lower.size() - 2), lower.get(lower.size() - 1), p) <= 0) {
lower.remove(lower.size() - 1);
}
lower.add(p);
}
// 建立上凸包
List<Point> upper = new ArrayList<>();
for (int i = points.length - 1; i >= 0; i--) {
while (upper.size() >= 2 && crossProduct(upper.get(upper.size() - 2), upper.get(upper.size() - 1), points[i]) <= 0) {
upper.remove(upper.size() - 1);
}
upper.add(points[i]);
}
// 删除重复的起点和终点
lower.remove(lower.size() - 1);
upper.remove(upper.size() - 1);
// 合并上下凸包
lower.addAll(upper);
return lower;
}
public static void main(String[] args) {
Point[] points = { new Point(0, 0), new Point(1, 2), new Point(2, 2), new Point(3, 1), new Point(3, 3) };
List<Point> hull = convexHull(points);
for (Point p : hull) {
System.out.println("(" + p.x + ", " + p.y + ")");
}
}
}
这里，代码通过极角排序和叉积判断来决定是否需要继续加入当前点。简单来说，就是我们先从左下角的点开始，顺时针或逆时针地去“扫”这些点，检查是否构成凸多边形。这个算法的时间复杂度是O(n log n)，因为我们首先要进行排序，然后再进行线性扫描。
是不是很简单呢？你可能会想，程序看上去像是一个简单的几何问题，但实际上它涉及了很多数学细节，尤其是关于叉积的部分。这也是为什么很多人一开始会觉得这类题目很复杂，实际上，只要理清了每一步，算法就能轻松搞定。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
