您正在查看：2020年2月
2020-02-05 |HHR
在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：
输入：[30,20,150,100,40] 输出：3 解释：这三对的总持续时间可被 60 整数： (time[0] = 30, time[2] = 150): 总持续时间 180 (time[1] = 20, time[3] = 100): 总持续时间 120 (time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：
输入：[60,60,60] 输出：3 解释：所有三对的总持续时间都是 120，可以被 60 整数。
class Solution {
public:
int numPairsDivisibleBy60(vector<int> &time) {
int num[60] = {0}, sum = 0;
for (int n:time) {
num[n % 60]++;
}
//60+60
sum += (num[0] - 1) * num[0] / 2;
//30+30
sum += (num[30] - 1) * num[30] / 2;
//(1-29)+(31-59)
for (int x = 1; x <= 29; x++) {
sum += num[x] * num[60 - x];
}
return sum;
}
};https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
2020-02-05 |HHR
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例 1：
输入：points = [[1,3],[-2,2]], K = 1 输出：[[-2,2]] 解释： (1, 3) 和原点之间的距离为 sqrt(10)， (-2, 2) 和原点之间的距离为 sqrt(8)， 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
示例 2：
输入：points = [[3,3],[5,-1],[-2,4]], K = 2 输出：[[3,3],[-2,4]] （答案 [[-2,4],[3,3]] 也会被接受。）
class point {
public:
int x, y, d;
point(int x, int y) {
this->x = x;
this->y = y;
d = x * x + y * y;
}
};
bool cmp(point &p1, point &p2) {
return p1.d < p2.d;
}
class Solution {
public:
static vector<vector<int>> kClosest(vector<vector<int>> &points, int K) {
vector<point> p;
p.reserve(points.size());
for (vector<int> P:points) {
p.emplace_back(P[0], P[1]);
}
sort(p.begin(), p.end(), cmp);
vector<vector<int>> ans;
for (int x = 0; x < K; x++) {
vector<int> tmp;
tmp.push_back(p[x].x);
tmp.push_back(p[x].y);
ans.push_back(tmp);
}
return ans;
}
};https://leetcode-cn.com/problems/k-closest-points-to-origin/
2020-02-05 |HHR
给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
- 输入的数组只包含
0和1。 - 输入数组的长度是正整数，且不超过 10,000。
class Solution {
public:
static int findMaxConsecutiveOnes(vector<int> &nums) {
int max = 0, num = 0;
for (int i : nums) {
if (i == 1)
num++;
else
num = 0;
if (max < num)
max = num;
}
return max;
}
};
2020-02-05 |HHR
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123 输出: 321
示例 2:
输入: -123 输出: -321
示例 3:
输入: 120 输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [-2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
class Solution {
public:
int reverse(int x) {
long long sum = 0, num = x;
int flag = 1;
if (num < 0) {
flag = -1;
num = -num;
}
while (num > 0) {
sum = sum * 10 + num % 10;
num /= 10;
}
if (sum > pow(2, 31)) {
return 0;
}
return flag * sum;
}
};
2020-02-04 |HHR
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *link1 = l1, *link2 = l2;
int y = 0;
ListNode *ans = new ListNode(0), *head = ans;
while (link1 && link2) {
ans->next = new ListNode((link1->val + link2->val + y) % 10);
ans = ans->next;
y = (link1->val + link2->val + y) / 10;
link1 = link1->next;
link2 = link2->next;
}
if (link1) {
while (link1) {
ans->next = new ListNode((link1->val + y) % 10);
ans = ans->next;
y = (link1->val + y) / 10;
link1 = link1->next;
}
}
if (link2) {
while (link2) {
ans->next = new ListNode((link2->val + y) % 10);
ans = ans->next;
y = (link2->val + y) / 10;
link2 = link2->next;
}
}
if (y != 0) {
ans->next = new ListNode(y);
}
return head->next;
}
};