条件语句？

976. Largest Perimeter Triangle

Analysis

这个题乍一看挺简单的，其实需要稍微思考一下。
首先，能否组成三角形，可以借助两边之和或者之差来进行判断。接下来的问题就是如何得到周长最大的三角形，要使周长最大，边长肯定得最大。自然而然，不妨将数组从大到小排序，然后依次判断是否是三角形，符合就直接返回周长，可以确定的是，这个周长一定是最大值。为什么？可以用反证法来说明，假设 $nums[0]$、$nums[1]$和$nums[2]$能构成三角形，存在 $nums[i]$ 使得由 $nums[0]$、$nums[1]$ 和 $nums[i]$ 构成的三角形的周长更大，就必有 $nums[i] > nums[2]$，那么此时这个数组一定不是有序的。同样的，如果 $nums[0]$、$nums[1]$ 和 $nums[2]$ 不能构成三角形，那么 $nums[i], 2 < i < n$ 也不能与 $nums[1]$ 和 $nums[0]$ 组成三角形。

Code

按照上面的思路，可以写出下面的代码：

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; });
        for(int i = 0; i < nums.size() - 2; i++) {
            int a = nums[i], b = nums[i + 1], c = nums[i + 2];
            if(a + b > c && a + c > b && b + c > a) return a + b + c; 
        }
        return 0;
    }
};

回过头再来想一下，可以发现这实际是个贪心问题。

1779. Find Nearest Point That Has the Same X or Y Coordinate

Analysis

题目有点长，要耐心的读下题。

Code

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int minmd = 0x3fffffff, index = -1;
        for(int i = 0; i < points.size(); i++) {
            if(points[i][0] == x && points[i][1] == y) return i;
            else if(points[i][0] == x || points[i][1] == y) {
                int tmp = abs(x - points[i][0]) + abs(y - points[i][1]);
                if(tmp < minmd) {
                    minmd = tmp;
                    index = i;
                }
            }
        }
        return index;
    }
};

Summary

考贪心的题目，有时候挺难想的，而且只要想到了就很简单，想不到就很难...