leetcode电脑下载-triangulating_polygons:triangulating_polygons

leetcode电脑下载三角多边形 总体概述 这个问题的一般前提是填充由三角形组成的多边形上的内部点，使得“完成”（即，由所有三种颜色组成）三角形的数量不超过给定数量。 该程序如何工作的简单英文描述是它识别二值“配对”边，例如 ab、ac 或 bc，然后确定它是否可以使它们消失。 如果成对的边是回文的（例如，aba 或 caaaaac），它会尝试通过用序列两端的值对其进行着色来“覆盖”回文的中间。 如果这可以在不意外完成三角形的情况下完成，它就会这样做。 然后更新多边形的活动边界并再次执行回文搜索，直到低垂的果实消失。 从这一点开始，分析活动边界以确定剩余的（现在有向的）对边的数量。 每当每一对类型中至少有一个剩余时，无论内部三角形结构如何，都不可能在不产生至少一个完整三角形的情况下填充多边形。 因此，ab/ac/bc 的每个完整三元组恰好对应一个完整的三角形。 通过找到最少出现的对，然后可以直接计算可以生成的完整三角形的最小数量。 此外，因为回文边缘已尽可能被消除，（一种或多种）为多边形的其余部分着色的正确方法是简单地用不在最小出现次数对中的颜色填充所有空白空间（或者如果有是多个最小