数字问题-LeetCode 452、453、454、455、456、459（KMP算法）
数字问题-LeetCode 452、453、454、455、456、459（KMP算法）
作者：TeddyZhang，公众号：算法工程师之路
数字问题：
LeetCode # 452 453 454 455 456 459
1
编程题
【LeetCode #452】用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example: 输入: [[10,16], [2,8], [1,6], [7,12]] 输出: 2
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
auto cmp = [](vector<int>& a, vector<int>& b) {
return a[] < b[];
};
sort(points.begin(), points.end(), cmp);
int res = ;
int end = INT_MIN;
for(auto p: points) {
if (end == INT_MIN || end < p[]) {
res++;
end = p[];
} else
end = min(end, p[]);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons
【LeetCode #453】最小移动次数使得数组元素相等
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
示例: 输入: [1,2,3] 输出: 3
解题思路：移动一次使得n-1个元素增加1，那么相反的意思就是每移动一次元素，使得一个元素减1，最后全部相等即可（必定相等于最小值）。
class Solution {
public:
int minMoves(vector<int>& nums) {
int min = INT_MAX;
for(auto num: nums) {
if (min > num) min =num;
}
int res = ;
for(auto num: nums)
res += (num-min);
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements
【LeetCode #454】四数相加 II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int res = ;
unordered_map <int, int> mm;
for(const auto& a: A) {
for(const auto& b: B) {
++mm[a+b];
}
}
for(const auto& c: C) {
for(const auto& d: D) {
res += mm[-(c+d)];
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum-ii
【LeetCode #455】分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意： 你可以假设胃口值为正。 一个小朋友最多只能拥有一块饼干。
示例 1: 输入: [1,2,3], [1,1] 输出: 1
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = , cookie = ;
while(child < g.size() && cookie < s.size()) {
if (g[child] <= s[cookie]) {
child++;
}
cookie++; // 一块饼干对应一个孩子
}
return child;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/assign-cookies
【LeetCode #456】132模式
给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例1: 输入: [1, 2, 3, 4] 输出: False
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
int last = INT_MIN; // 次大元素
stack<int> sta; // sta中存放最大元素
for(int i = n-1; i >= ; i--) {
if (nums[i] < last) return true;
while(!sta.empty() && nums[i] > sta.top()) {
last = sta.top();
sta.pop();
}
sta.push(nums[i]);
}
return false;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/132-pattern
【LeetCode #459】重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1: 输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。
(简单版，将字符串拼到一起，然后从位置 1 开始搜索字符串)
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s+s).find(s, ) != s.length();
}
};
(KMP算法，其中next数组中保存最大前缀后缀公共子串)
class Solution {
public:
bool repeatedSubstringPattern(string s) {
// 最大前缀与后缀长度是next[i]+1
int n = s.length();
vector<int> next(n+);
next[] = -1;
int j = , k = -1;
while(j < n) {
if (k == -1 || s[k] == s[j]) {
k++;
j++;
next[j] = k;
}else
k = next[k];
}
return next[n] && n % (n-next[n]) == ;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/repeated-substring-pattern