第一题：
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 = 1
Output: [[-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 = 2
Output: [[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<vector<int> > kClosest(vector<vector<int> >& points, int K) {
vector<vector<int> > ans;
int len = points.size();
for(int i=; i<len; i++) {
int x = points[i][];
int y = points[i][];
points[i].push_back(x*x+y*y);
}
sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b) { return a[] < b[]; });
for(int i=; i<K; i++) {
vector<int> res;
res.push_back(points[i][]);
res.push_back(points[i][]);
ans.push_back(res);
}
return ans;
}
};第二题：
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 <= 100001 <= A[i] <= 10^6
题目大意：从数组中，找出三个点组成一个周长最大的三角形，然后输出周长。
数据比较小，直接暴力的。
class Solution {
public:
bool ok(int a, int b, int c) {
return a-b<c;
}
int largestPerimeter(vector<int>& A) {
int len = A.size();
sort(A.begin(), A.end());
for(int i=len-; i>=; i--) {
for(int j=i-; j>=; j--) {
if( ok(A[i], A[j], A[j-])) {
return A[i]+A[j]+A[j-];
}
}
}
return ;
}
};第三题：
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 = 5
Output: 7
Explanation: 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] <= 100002 <= K <= 10000
题目大意：统计有多少条满足条件的子序列。条件1：连续，必须是连续子序列，条件2：序列和可以整除K。
思路：求出前缀和，想要找到连续子序列之和是可以整除K的话，那么前缀和只差模K也就是为0，也就是说统计模K相等的前缀和之差的个数，求一个等差数列求和。
做题的时候开始考虑错了，后面想到了解决方法但是没时间了，对照rank写出了一个我自己都认为是错的程序，提交AC。想不清楚，等过几天想清楚了，在仔细写下吧。
class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
int a[K];
memset(a, , sizeof(a));
int len = A.size(); a[] = ;
int res = ;
for(int i=; i<len; i++) {
A[i] += A[i-];
int cnt = (A[i]%K+K)%K;
a[cnt] ++;
}
for(int i=; i<K; i++) {
res += (a[i]-)*a[i]/;
}
return res;
}
};