运算符（三角形的最大周长（贪心算法）/找到最近的有相同 X 或 Y 坐标的点)

​

目录

题目：三角形的最大周长(贪心算法)

分析

贪心算法概述

代码 

题目： 找到最近的有相同 X 或 Y 坐标的点

分析 

代码 

博主萌新一枚，如果文章哪里有不妥当的，还请大佬们提出！谢谢支持！

题目：三角形的最大周长(贪心算法)

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：nums = [2,1,2]
输出：5
示例 2：

输入：nums = [1,2,1]
输出：0

提示：

3 <= nums.length <= 104
1 <= nums[i] <= 106

分析

给定一个数组里边放着一些数，要求我们找出三个数（代表三个边）可以组成最大三角形的数。初中我们都学过三角形的三边关系：两边之和大于第三边OR两边之差小于第三边满足其中任意的一个条件就可以构成三角形。于是我就萌生出个这样的想法，如果是找数组中最大的三个数可以构成三角形的周长最大。我们可以对数组进行排序，然后依次从数组中拿出来（最大值 次大值 次大值，所选择的每个边都是局部最优的方案，从而求出构成最大周长的最优解）进行判断他们是否符合了构成三角形的规则。如果可以构成我们直接breek循环。而我们使用的这样方法就是贪心算法。你是不是感到不可思议！！！

你也许会说这不就是生活中的基本常识吗？怎么成了算法了，究竟什么是贪心算法？

​

贪心算法概述

贪心算法是指在对问题进行求解时，在每一步都选择中都选取最好或最优的选项。

贪心算法所得到的结果不一定是最优的结果，但是都是相对于接近最优的结果。

例如:法外狂徒张三每天都要去偷钱，桌子上放着一元、五元、十元、五十元、一百元各一张，每次只能拿走一张，拿多了容易引起怀疑。张三特别喜欢钱，尤其是对红色情有独钟。所以张三每次去偷钱都会拿走一张一百元，每天都是如此。一个月之后是不是张三一共拿走了3000元。每天张三都会选择面值最大的，这也就解释了上边（在每一步都选择中都选取最好或最优的选项）。但是因为情况不同，所得到的结果不一定是最优的结果，但是都是相对于接近最优的结果。

总结:局部最优，从而求出全局最优

代码 

class Solution {
    public int largestPerimeter(int[] nums) {
        int max=0;//最大周长
    Arrays.sort(nums);//数组升序排序
    for(int i=nums.length-1;i>=2;i--){//依次遍历数组
        if(i-2>=0){     //判断从数组中取三个够不够   
    int j=nums[i];     //拿元素
    int k=nums[i-1];
    int l=nums[i-2];
    if(k+l>j){ //判断是否可以构成三角形
        max=l+j+k; //接受最大的周长
        return max;
    }
    }
    }
 return 0;
    }
}

题目： 找到最近的有相同 X 或 Y 坐标的点

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。

请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标 最小 的一个。如果没有有效点，请返回 -1 。

两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。

示例 1：

输入：x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
输出：2
解释：所有点中，[3,1]，[2,4] 和 [4,4] 是有效点。有效点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1 。[2,4] 的下标最小，所以返回 2 。
示例 2：

输入：x = 3, y = 4, points = [[3,4]]
输出：0
提示：答案可以与你当前所在位置坐标相同。
示例 3：

输入：x = 3, y = 4, points = [[2,3]]
输出：-1
解释：没有 有效点。

提示：

1 <= points.length <= 104
points[i].length == 2
1 <= x, y, ai, bi <= 104

分析 

题目给出两个整数x和y，用二位数组来存放每一次x和y的值。数组应该是这样的iny[n][2]，n表示有几组x和y，arr[n][0] x的值，arr[n][1] y的值;我们首先对数组进行遍历，遍历的条件可以分为三种情况。条件一，给定的x==arr[n][0]&&y==arr[n][1]我们直接返回二维数组的一维下标。条件二，给定的x==arr[n][0]||y==arr[n][1],我们计算下曼哈顿距离（两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) ）并记录下二维数组的一维下标判断是否为最小下标并记录。

设置标记b=false;如果数组中的值一次也不符合条件一或者条件而。则返回-1

代码 

class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        double count=Double.MAX_VALUE;
        //坐标t最小坐标
        double q=Double.MAX_VALUE;
        int t=x;
        boolean b=false;
     for(int i=0;i<points.length;i++){
             if(points[i][0]==x&&points[i][1]==y){
                 b=true;
                 t=i;
           break;
             }
           else if(points[i][0]==x||points[i][1]==y){
                b=true;
            double u=Math.abs(x-points[i][0])+Math.abs(y-points[i][1]);
             if(u<q){
                 q=u;
                 //记录下他的坐标
                 t=i;
               //  t=points[i][j];
             }
            }    
     }
    
     if(b){
          return t; 
     }else{
         return -1;
     }
    
}
}