👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：几何
作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。本文将举出三道面试题来体验一下计算几何在算法中的应用
👉⭐️第一题💎
✨题目
✨思路：
今天的题是计算几何，竞赛中会出现的题型，一般都会难一点，第一道还算可以，ans = 每一行的最大值之和 + 每一列的最大值之和 + 不为0的点数量，知道这个核心点其余代码就是coding问题了
✨代码：
class Solution: def projectionArea(self, grid: List[List[int]]) -> int: n = len(grid) x = sum([max(row) for row in grid]) y = sum([max([grid[i][j] for i in range(n)]) for j in range(n)]) z = sum([sum([1 if grid[i][j] != 0 else 0 for i in range(n)]) for j in range(n)]) return x + y + z
👉⭐️第二题💎
✨题目
2280. 表示一个折线图的最少线段数 - 力扣（LeetCode）
✨思路：
由于题目中给出了日期与价格的变化趋势，分析可知，按day排序stockPrices后计算每两个点的斜率，斜率变化表示不在同一条直线，根据这一点就可以得出最少的线段数，也就是去掉在同一条直线上的无效点
✨代码：
class Solution { private: int getLen(vector<int>& p1, vector<int>& p2) { return pow(p2[0]-p1[0], 2) + pow(p2[1]-p1[1],2); } public: bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) { vector<int> lens; lens.resize(6, 0); lens[0] = getLen(p1, p2); lens[1] = getLen(p1, p3); lens[2] = getLen(p1, p4); lens[3] = getLen(p2, p4); lens[4] = getLen(p2, p3); lens[5] = getLen(p3, p4); for(int i = 0; i < 6; i++) { if(lens[i] == 0){ return false; } } std::sort(lens.begin(), lens.end()); if(lens[0] == lens[1] && lens[1] == lens[2] && lens[2] == lens[3] && lens[4] == lens[5] && lens[0]*2 == lens[5]) { return true; } return false; } };
👉⭐️第三题💎
✨题目
✨思路：
通过题目容易得出正方形的属性如下：四个边相等，对角线相等。先说明它是平行四边形；再说明它是菱形(或矩形)；最后说明它是矩形(或菱形)，然后判定是否对角线，可以考虑用unordered_set基于哈希表的判重，相比于set基于红黑树的判重性能上会快很多，也可以定义数组去标记，空间换时间，但是数据量太大的时候就不建议这么做。
✨代码：
class Solution { private: int getLen(vector<int>& p1, vector<int>& p2) { return pow(p2[0]-p1[0], 2) + pow(p2[1]-p1[1],2); } public: bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) { vector<int> lens; lens.resize(6, 0); lens[0] = getLen(p1, p2); lens[1] = getLen(p1, p3); lens[2] = getLen(p1, p4); lens[3] = getLen(p2, p4); lens[4] = getLen(p2, p3); lens[5] = getLen(p3, p4); for(int i = 0; i < 6; i++) { if(lens[i] == 0){ return false; } } std::sort(lens.begin(), lens.end()); if(lens[0] == lens[1] && lens[1] == lens[2] && lens[2] == lens[3] && lens[4] == lens[5] && lens[0]*2 == lens[5]) { return true; } return false; } };
🌹写在最后💖：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹
