数字问题-LeetCode 435、436、441、442、443、445、448（数字）
数字问题-LeetCode 435、436、441、442、443、445、448（数字）
作者：TeddyZhang，公众号：算法工程师之路
数字问题：
LeetCode # 435 436 441 442 443 445 448
1
编程题
【LeetCode #435】无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
- 可以认为区间的终点总是大于它的起点。
- 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
auto cmp = [](vector<int>& a, vector<int>& b) {
return a[] <= b[];
};
if (intervals.size() == ) return ;
// 根据第二个数排序，看不重合的数量
sort(intervals.begin(), intervals.end(), cmp);
int end = intervals[][];
int count = ;
for(int i = ; i < intervals.size(); i++) {
if (intervals[i][] >= end) {
end = intervals[i][];
count++;
}
}
return intervals.size() - count;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/non-overlapping-intervals
【LeetCode #436】寻找右区间
给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。
对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。
示例 1: 输入: [ [1,2] ] 输出: [-1]
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
if (intervals.size() <= ) return {-1};
vector<int> res;
map<int, int> record; // 使用low_bound
res.reserve(intervals.size());
for(int i = ; i < intervals.size(); i++) {
record[intervals[i][]] = i;
}
for(auto val: intervals) {
auto it = record.lower_bound(val[]);
if (it != record.end()) {
res.push_back(it->second);
} else
res.push_back(-1);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-right-interval
【LeetCode #441】排列硬币
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。 给定一个数字 n，找出可形成完整阶梯行的总行数。 n 是一个非负整数，并且在32位有符号整型的范围内。
class Solution {
public:
int arrangeCoins(int n) {
long sum = ;
long val = ;
int res = ;
while(sum < n) {
sum += val++;
res++;
}
if (sum == n) return res;
else return res-1;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/arranging-coins
【LeetCode #442】数组中重复的数据
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。 找到所有出现两次的元素。 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例： 输入: [4,3,2,7,8,2,3,1] 输出: [2,3]
解题思路：注意vector中元素的范围，可以作为vector的索引，因此可以通过遍历改变vector中重复元素的符号，进而得到结果。
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
for(auto num: nums) {
num = abs(num); // 1 <= a[i] <= n
if (nums[num-1] > ) {
nums[num-1] *= -1; // 不可能是零
}else {
res.push_back(num);
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
【LeetCode #443】压缩字符串
给定一组字符，使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。 在完成原地修改输入数组后，返回数组的新长度。
class Solution {
public:
int compress(vector<char>& chars) {
int len = ;
for(int i = , cnt = ; i < chars.size(); i++, cnt++) {
if (i+ == chars.size() || chars[i] != chars[i+]) {
chars[len++] = chars[i];
if (cnt > ) {
for(auto ch: to_string(cnt)) {
chars[len++] = ch;
}
}
cnt = ;
}
}
return len;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/string-compression
【LeetCode #445】两数相加 II
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶: 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例: 输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<ListNode*> sta1;
stack<ListNode*> sta2;
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* res = new ListNode();
bool carry = false;
while(p1 != nullptr) {
sta1.push(p1);
p1 = p1->next;
}
while(p2 != nullptr) {
sta2.push(p2);
p2 = p2->next;
}
while(!sta1.empty() || !sta2.empty()) {
int r1 = sta1.empty() ? : sta1.top()->val;
int r2 = sta2.empty() ? : sta2.top()->val;
int sum = r1 + r2 + (carry ? : );
carry = (sum >= );
ListNode* newNode = new ListNode(sum % );
newNode->next = res->next;
res->next = newNode;
if (!sta1.empty()) sta1.pop();
if (!sta2.empty()) sta2.pop();
}
if (carry) {
ListNode* newNode = new ListNode();
newNode->next = res->next;
res->next = newNode;
}
return res->next;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers-ii
【LeetCode #448】找出所有数组中消失的数字
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例: 输入: [4,3,2,7,8,2,3,1] 输出: [5,6]
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i = ; i < nums.size(); i++)
nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
vector<int> res;
for(int i = ; i < nums.size(); i++) {
if (nums[i] > ) res.push_back(i+);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array