LeetCode Weekly Contest 119-白红宇

LeetCode Weekly Contest 119

阅读量：5142 次

发布时间：2019-06-13

本文共 2977 字，大约阅读时间需要 9 分钟。

第一题：

973. K Closest Points to Origin

We have a list of

points on the plane. Find the

K closest points to the origin

(0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1Output: [[-2,2]]Explanation: The distance between (1, 3) and the origin is sqrt(10).The distance between (-2, 2) and the origin is sqrt(8).Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2Output: [[3,3],[-2,4]](The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000

-10000 < points[i][0] < 10000

-10000 < points[i][1] < 10000

题目大意：给你一些点，让你找离远点最近的K个点。主要考的是二维数组排序。

class Solution {public:    vector
      
       
         > kClosest(vector
        
         
           >& points, int K) {        vector
          
           
             > ans; int len = points.size(); for(int i=0; i

&a, const vector

&b) { return a[2] < b[2]; }); for(int i=0; i

res; res.push_back(points[i][0]); res.push_back(points[i][1]); ans.push_back(res); } return ans; }};

View Code

第二题：

976. Largest Perimeter Triangle

Given an array

A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]Output: 5

Example 2:

Input: [1,2,1]Output: 0

Example 3:

Input: [3,2,3,4]Output: 10

Example 4:

Input: [3,6,2,3]Output: 8

Note:

3 <= A.length <= 10000

1 <= A[i] <= 10^6

题目大意：从数组中，找出三个点组成一个周长最大的三角形，然后输出周长。

数据比较小，直接暴力的。

class Solution {public:    bool ok(int a, int b, int c) {        return a-b

& A) { int len = A.size(); sort(A.begin(), A.end()); for(int i=len-1; i>=0; i--) { for(int j=i-1; j>=0; j--) { if( ok(A[i], A[j], A[j-1])) { return A[i]+A[j]+A[j-1]; } } } return 0; }};

View Code

第三题：

974. Subarray Sums Divisible by K

Given an array

A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by

K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5Output: 7Explanation: There are 7 subarrays with a sum divisible by K = 5:[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000

-10000 <= A[i] <= 10000

2 <= K <= 10000

题目大意：统计有多少条满足条件的子序列。条件1：连续，必须是连续子序列，条件2：序列和可以整除K。

思路：求出前缀和，想要找到连续子序列之和是可以整除K的话，那么前缀和只差模K也就是为0，也就是说统计模K相等的前缀和之差的个数，求一个等差数列求和。

做题的时候开始考虑错了，后面想到了解决方法但是没时间了，对照rank写出了一个我自己都认为是错的程序，提交AC。想不清楚，等过几天想清楚了，在仔细写下吧。

class Solution {public:      int subarraysDivByK(vector
      
       & A, int K) {        int a[K];        memset(a, 0, sizeof(a));        int len = A.size(); a[0] = 1;        int res = 0;        for(int i=0; i

View Code

转载于:https://www.cnblogs.com/Asimple/p/10262296.html