题集来源：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 ++;
else
prev = 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];
else
nums[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;
}
};
