【LeetCode——编程能力入门第二天】运算符(三角形的最大周长(贪心算法)/找到最近的有相同 X 或 Y 坐标的点)

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

 

目录

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

分析

贪心算法概述

代码

题目: 找到最近的有相同 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循环。而我们使用的这样方法就是贪心算法。你是不是感到不可思议!!!

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

image.gif编辑

贪心算法概述

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

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

例如:法外狂徒张三每天都要去偷钱,桌子上放着一元、五元、十元、五十元、一百元各一张,每次只能拿走一张,拿多了容易引起怀疑。张三特别喜欢钱,尤其是对红色情有独钟。所以张三每次去偷钱都会拿走一张一百元,每天都是如此。一个月之后是不是张三一共拿走了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;
    }
}

image.gif

题目: 找到最近的有相同 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;
     }
}
}

image.gif

目录
相关文章
|
29天前
|
存储 算法
【C算法】编程初学者入门训练140道(1~20)
【C算法】编程初学者入门训练140道(1~20)
|
21天前
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
42 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
1月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
34 6
|
1月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
40 2
|
1月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
35 1
|
1月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
32 1
|
1月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
55 0
|
1月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
30 0
|
1月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
40 0
|
1月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
18 0