题集来源：GitHub - changgyhub/leetcode_101: LeetCode 101：力扣刷题指南
使用C++完成相关题目，以训练笔试
贪心
采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。
分配问题
455. 分发饼干 - 力扣（LeetCode）
题解：分别对孩子和饼干排序，从小到大尽可能多的满足孩子
class Solution
{
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int child = 0, cookie = 0;while(child < g.size() && cookie < s.size()){if(g[child] <= s[cookie]) child ++;cookie ++;}return child;}
};135. 分发糖果 - 力扣（LeetCode）
题解：先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。
class Solution
{
public:int candy(vector<int>& ratings) {int size = ratings.size();if(size < 2) return size;vector<int> num(size, 1);for(int i = 1; i < size; i ++)if(ratings[i] > ratings[i - 1])num[i] = num[i - 1] + 1;for(int i = size - 1; i > 0; i --)if(ratings[i] < ratings[i - 1])num[i - 1] = max(num[i - 1], num[i] + 1);return accumulate(num.begin(), num.end(), 0);}
};区间问题
435. 无重叠区间 - 力扣（LeetCode）
题解：先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。
class Solution
{
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.empty())return 0;int n = intervals.size();sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[1] < b[1];});int removed = 0, prev = intervals[0][1];for(int i = 1; i < n; i ++){if(intervals[i][0] < prev)removed ++;elseprev = intervals[i][1];}return removed;}
};练习
605. 种花问题 - 力扣（LeetCode）
题解：花不能种植在相邻的地块上！！！
class Solution
{
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int count = 0, size = flowerbed.size();for(int i = 0; i < size; i ++)if((i == 0 || flowerbed[i-1] == 0) && //0号坑or前一坑没种flowerbed[i] == 0 && //当前坑没种(i == size-1 || flowerbed[i+1] == 0))//最后一个坑or下一个坑没种{count ++;//在当前坑种花flowerbed[i] = 1;}return count >= n;}
};452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
题解：类435，单位判断条件不同
class Solution
{
public:int findMinArrowShots(vector<vector<int>>& points) {if(points.empty())return 0;int n = points.size();sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){return a[1] < b[1];});int arrows = 1, prev = points[0][1];for(int i = 1; i < n; i ++)if(points[i][0] > prev){arrows ++;prev = points[i][1];}return arrows;}
};763. 划分字母区间 - 力扣（LeetCode）
题解：第一次遍历确定每个字母的最后出现的下标，第二次遍历实时更新每个片段的最后下标
class Solution
{
public:vector<int> partitionLabels(string s) {int last[26];for(int i = 0; i < s.size();i ++)last[s[i] - 'a'] = i;vector<int> ans;int l = 0, r = 0;for(int i = 0; i < s.size(); i ++){r = max(r, last[s[i] - 'a']);if(i == r){ans.push_back(r - l + 1);l = i + 1;}}return ans;}
};122. 买卖股票的最佳时机 II - 力扣（LeetCode）
题解：每天保证至少不亏钱
class Solution
{
public:int maxProfit(vector<int>& prices) {int ans = 0;for(int i = 1; i < prices.size(); i ++)ans += max(0, prices[i] - prices[i-1]);return ans;}
};406. 根据身高重建队列 - 力扣（LeetCode）
题解：先按身高从高往低排，再按前边比自身高的人数依次插入队列即可
class Solution
{
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b){return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);});vector<vector<int>> ans;for(auto person : people)ans.insert(ans.begin() + person[1], person);return ans;}
};665. 非递减数列 - 力扣（LeetCode）
题解：不仅要确保不小于上一位，还好比较上上一位，以确定整体非递减
class Solution
{
public:bool checkPossibility(vector<int>& nums) {int count = 0, n = nums.size();for(int i = 1; i < n; i ++)if(nums[i] < nums[i-1]){if(i == 1 || nums[i] >= nums[i-2])nums[i-1] = nums[i];elsenums[i] = nums[i-1];count ++;}return count <= 1;}
};双指针
两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。
两数之和
167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
题解：双指针分别从左往右，从右往左遍历数组
class Solution
{
public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0, r = numbers.size()-1, sum = 0;while(l < r){sum = numbers[l] + numbers[r];if(sum == target) break;if(sum < target) l ++;else r --;}return vector<int>{l + 1, r + 1};}
};归并数组
88. 合并两个有序数组 - 力扣（LeetCode）
题解：倒序将两数组归并在第一个数组，避免开辟额外空间
++ 和 -- 的小技巧： a++ 和 ++a 都是将 a 加 1，但是 a++ 返回值为 a，而++a 返回值为 a+1。如果只是希望增加 a 的值，而不需要返回值，则推荐使用 ++a，其运行速度会略快一些。
class Solution
{
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int k = m-- + n-- - 1;while(m >= 0 && n >= 0)nums1[k -- ] = nums1[m] > nums2[n] ? nums1[m --] : nums2[n --];while(n >= 0)nums1[k --] = nums2[n --]; }
};快慢指针
142. 环形链表 II - 力扣（LeetCode）
题解：
Floyd 判圈法：给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步， slow 前进一步。如果 fast可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。
class Solution
{
public:ListNode *detectCycle(ListNode *head) {ListNode* slow = head;ListNode* fast = head;while (true) {if (fast == nullptr || fast->next == nullptr) return nullptr;fast = fast->next->next;slow = slow->next;if (fast == slow) break;}fast = head;while(slow != fast){slow = slow -> next;fast = fast -> next;}return fast;}
};滑动窗口
76. 最小覆盖子串 - 力扣（LeetCode）
题解：先统计字符串情况，再根据字符串情况滑动窗口
class Solution
{
public:string minWindow(string s, string t){//先统计字符情况int baseHash[128] = { 0 }, curHash[128] = { 0 };for(auto& ch : t){++baseHash[ch];}int k = 0, minLen = s.size() + 1;//k:记录窗口起始位置 minLen:记录最小窗口长度int l = 0, r = 0, count = 0;//外层循环：窗口扩张while(r < s.size()){char i = s[r++];if(++curHash[i] <= baseHash[i]){++count;}//内层循环：窗口收缩while(count == t.size()){if(r-l < minLen){k = l;minLen = r-l;}char o = s[l++];if(curHash[o]-- <= baseHash[o]){--count;}}}return minLen > s.size() ? "" : s.substr(k, minLen);}
};练习
633. 平方数之和 - 力扣（LeetCode）
题解：类167，将c开根后与0进行平方和并判断大小
class Solution
{
public:bool judgeSquareSum(int c) {long l = 0;long r = (long)sqrt(c);while(l <= r){long sum = l*l + r*r;if(sum == c) return true;else if(sum > c) r --;else l ++;}return false;}
};680. 验证回文串 II - 力扣（LeetCode）
题解：类167，双指针循环判断
class Solution
{
private:bool isPalindrome(string& s, int left, int right) {for(;left < right; ++left, --right)if (s[left] != s[right]) return false;return true;}public:bool validPalindrome(string s) {for(int l = 0, r = s.size()-1; l < r; ++l, --r)if(s[l] != s[r])return isPalindrome(s, l+1, r) || isPalindrome(s, l, r-1);return true;}
};524. 通过删除字母匹配到字典里最长单词 - 力扣（LeetCode）
题解：排序 + 贪心 + 双指针
class Solution
{
public:string findLongestWord(string s, vector<string>& dictionary) {sort(dictionary.begin(), dictionary.end(), [](string& a, string& b){return a.size() == b.size() ? a < b : a.size() > b.size();});int n = s.size();for(auto& ss : dictionary){int m = ss.size();if(m > n) continue;int i = 0, j = 0;while(i < n && j < m){if(s[i] == ss[j]) j ++;i++;}if(j == m) return ss;}return "";}
};340. 至多包含 K 个不同字符的最长子串 - 力扣（LeetCode）
题解：类76
class Solution
{
public:int lengthOfLongestSubstringKDistinct(string s, int k) {if (s.size() == 0 || k == 0)return 0;int l = 0, r = 0, count = 0;int char_set[256] = {0};int ans = 0;//外层循环：窗口扩张while (r < s.size()) {if (char_set[s[r]] == 0)count++;char_set[s[r ++]]++;//内层循环：窗口收缩while (count > k){char_set[s[l]]--;if (char_set[s[l ++]] == 0)count--;}ans = max(ans, r - l);}return ans;}
};
