LeetCode Hot 100
概述
先更个Hot 100， 预计更新一个月左右。
本篇主要以总结为主，会在hot100的基础上延伸一些同类型的题目，以及每一部分题型的大致解题思路.
分类还是以LeetCode上的分，但会穿插几道有意思且经典的题。
点击题目标号和 题解 可跳转至对应页面
题目清单
哈希
题解 经典夜里看海，数组找数做优化一般都是用哈希，存了之后O(1)就能找到
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map <int,int> hashmap; for(int i = 0; i < nums.size(); i ++){ int res = target - nums[i]; //如果hash表中存在 if(hashmap.count(res)) return {hashmap[res],i}; //如果没有，把当前的数插入到hash表中 hashmap[nums[i]] = i; } return {}; } };
题解 找出分组规则 -> 怎么让不同组合的字符串都变得一样 -> 排序，不管你之前是啥，排完序后都是小登到老登，这样就成一组了
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string,vector<string>> hash; for(auto& str:strs){ string newstring = str; sort(newstring.begin(),newstring.end()); hash[newstring].push_back(str); } vector<vector<string>> res; for(auto & item : hash) res.push_back(item.second); return res; } };
题解 说下哈希的思路，要找最长的连续序列，那就每个数都往后找就行，例如从x找x+1...一直找到y结束，此时该段长度就为y-x+1。最后存在若干段数段，但此时枚举的话还是会超时，为了减少次数，我们去找x前面还有没有更小的数，如果还有那么就一直找到最开始的那段。
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> S; for(auto num : nums) S.insert(num); int res = 0; for(auto num: nums) { //每次找最小的那段连续子序列 if(S.count(num) && !S.count(num-1)) { int y = num; S.erase(num); while(S.count(y+1)) { y++; S.erase(y); } res = max(res,y-num+1); } } return res; } };
双指针
题解 找到不为0的数->将其移动到k指针后的那个位置->所有非0移动完了->后续置0
class Solution { public: void moveZeroes(vector<int>& nums) { int k = 0; for(int x : nums) { if(x) nums[k++] = x; } while(k < nums.size()) nums[k++] = 0; } };
题解 主要是证明， 可以反证-> 因为两边肯定有一边先到最优的位置，假定左边先到->此时右边向左移动，如果左边还存在更大的范围，那么说明左边不是最大的，但只要是最大的，那么就能放小边界到答案范围
class Solution { public: int maxArea(vector<int>& height) { int res = 0; for(int i= 0, j = height.size()-1; i < j; ) { res = max(res,min(height[i],height[j]) * (j-i)); if(height[i] > height[j]) j --; else i ++; } return res; } };
题解 j和k的双指针->传统双指针模板->判断指针移动条件，这里是三数相同->显然越往右k越大，想要=0，k只能往左走
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(), nums.end()); //先固定一个 for(int i = 0; i < nums.size(); i ++){ if(i && nums[i-1] == nums[i]) continue; for(int j = i+1, k = nums.size()-1; j < k; j ++) { if(j > i+1 && nums[j] == nums[j-1]) continue; while(j < k-1 && nums[i]+nums[j]+nums[k] > 0) k--; if(nums[i] + nums[j] + nums[k] == 0) res.push_back({nums[i], nums[j], nums[k]}); } } return res; } };
题解 核心是左右有差值才有凹槽，这样就可以拆分这段数组，循环去逼近。双指针可行是因为从左右往中间首先保证不重不漏，其次可以不管高度一样的情况，而一旦有高度差，即可确定小的那部分就是它的凹槽值，确定后往中间拓展即可。
class Solution { public: int trap(vector<int>& height) { //不关注具体数值，比较左右大小即可知道指针移动方向，算部分 int ans = 0, left = 0, right = height.size() - 1, pre_max = 0, suf_max = 0; while (left < right) { pre_max = max(pre_max, height[left]); suf_max = max(suf_max, height[right]); if(pre_max < suf_max) ans += pre_max - height[left++]; else ans += suf_max - height[right--]; } return ans; } };
滑动窗口
题解 用个哈希表维护区间，每次放字符进去，如果重复就是刚进来的那小子重复了，此时左边那个指针向右移动至没有重复元素的位置。这样这块区间就搞完了，接着往后走就行。两个指针最多2n就遍历完。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> heap;
int res = 0;
for(int i = 0, j = 0; i < s.size(); i ++){
heap[s[i]] ++;
while(heap[s[i]] > 1) heap[s[j++]]--;
res = max(res,i-j+1);
}
return res;
}
};438. 找到字符串中所有字母异位词
题解 哈希加双指针。 维护一个哈希表记录字符出现的次数 -> 判断窗口中字符种类和题目子串中的字符种类是否一致。
用一张哈希表来存，使用--操作来判断是否满足要求，之后维护ij窗口对种类变量进行修改即可
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char,int> cnt;
vector<int> res;
for(auto x: p) cnt[x] ++;
int tot = cnt.size();
for(int i = 0, j = 0, okay = 0; i < s.size(); i ++)
{
if(--cnt[s[i]] == 0) okay ++; //说明有一种字符和目标串的这种字符相等了
while(i-j+1 > p.size())
{
if(cnt[s[j]] == 0) okay--;
cnt[s[j++]] ++;
}
if(okay == tot) res.push_back(j);
}
return res;
}
};
子串
题解 前缀和加hash。 区间和问题 模板前缀和
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> s(n+1);
for(int i = 1; i <= n; i ++) s[i] = s[i-1] + nums[i-1];
unordered_map<int,int> hash;
hash[0] = 1; int res = 0;
for(int i = 1; i <= n; i ++){
res += hash[s[i] - k];
hash[s[i]] ++;
}
return res;
}
};题解 大致题意是去掉旧的，插入新的，维护一个窗口，即先进先出。那么可以使用一个双端队列来模拟过程。如果暴力去求最大值，那么n次*k个会超时，所以考虑O（1）的复杂度去求窗口最大值。 此处选择的是维护队列的单调性，队列中的元素按值递减排序，这样队列的头部始终是当前窗口的最大值。如果当前元素 nums[i] 大于或等于队列尾部的元素，则移除队列尾部的元素。这是因为这些较小的元素在未来不会成为窗口的最大值。
这样，当窗口的大小达到 k 时（即 i >= k - 1），将队列头部的元素（即当前窗口的最大值）添加到 res 中。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for(int i = 0; i < nums.size(); i ++)
{
if(q.size() && i-k+1 > q.front()) q.pop_front();
while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();
q.push_back(i);
if(i >= k-1) res.push_back(nums[q.front()]);
}
return res;
}
};题解 双指针维护窗口，比对字符出现的次数，返回最小的那个就行。 即一张哈希表存答案字符出现的次数，另一张拿来做比对。i，j指针具有单调性，故维护一个区间找最小的答案
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hs, ht;
for(auto s: t) ht[s]++;
string res;
int cnt = 0;
for(int i = 0, j = 0; i < s.size(); i ++)
{
… return res;
}
};普通数组
题解 有很多种解释，评论有句挺好的，我自己走着，如果你的融合可以拓展彼此的生命长度那么就一起走，如果你的到来会让彼此消耗，那不如各自安好，各走各的，这一段就不符就往下走。 动归，定义个f[i]表示就是以nums[i]结尾的最大和是多少，这个一般都是题目问啥就先想啥。之后就是找递推关系，划分下集合，例如划分为区间长度>=2 的和区间长度为1这两部分，区间长度为1的部分就是nums[i]；而区间长度>=2的那块其实就是f[i-1]+nums[i]，之后每次更新下答案就行
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN;
//fi为之前的总和
for(int i = 0, fi = 0; i < nums.size(); i ++)
{
fi = nums[i] + max(fi, 0);
res = max(res, fi);
}
return res;
}
};题解 模板题。1.左端点排序 --> 2.排完序后判断下一段的起点是否在上一段内 --> 3.循环处理，再加上最后一次
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
if(intervals.empty()) return res;
//左端点排序
sort(intervals.begin(),intervals.end());
int l = intervals[0][0], r = intervals[0][1];
for(int i = 1; i < intervals.size(); i ++){
if(intervals[i][0] > r){
res.push_back({l,r});
l = intervals[i][0], r = intervals[i][1];
}else r = max(r,intervals[i][1]);
}
//最后一段
res.push_back({l,r});
return res;
}
};
题解 脑筋急转弯，用的别人的题解，原地翻转一开始想的双指针能用来翻转一段。 一开始将整段翻转->所有元素都是逆序->让之前的后k个变为正序->让之前的前n-k个变为正序
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
//三次反转
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};题解 不让用除法并保证空间复杂度，可以考虑从当前数 i 分为前部分和后部分，前缀，后缀都很好算，全部乘起来就行
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
//前后缀
int n = nums.size();
vector<int> p(n,1);
//先计算当前这个数i的前缀
for(int i = 1; i<n; i ++) p[i] = p[i-1] * nums[i-1];
//后缀
for(int i = n-1, back = 1; i >= 0; i --)
{
p[i] *= back;
back *= nums[i];
}
return p;
}
};class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for(int i=0; i<nums.size(); i++){
while(nums[i]>0 && nums[i]<=n && nums[i]!=i+1 && nums[nums[i]-1]!=nums[i])
//n 的数字应该放在索引 n-1 的位置上
swap(nums[i],nums[nums[i]-1]);
}
for(int i=0; i<n; i++){
//索引 i 上应该存放的是值 i + 1，如果不是，则说明 i + 1 是缺失的正整数。
if(nums[i] != i+1)
return i+1;
}
return n+1;
}
};矩阵
73. 矩阵置零
题解 使用第一行和第一列充当额外的数组做标记，并在执行的过程中，将内部的元素标记为0
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.empty()) return;
int n = matrix.size(), m = matrix[0].size();
//拿第一行和第一列充当额外的数组做标记
int col0 = 1, row0 = 1;
//预处理
for (int i = 0; i < n; i ++ )
if (!matrix[i][0]) col0 = 0;
for (int i = 0; i < m; i ++ )
if (!matrix[0][i]) row0 = 0;
//标记
for (int i = 1; i < n; i ++ )
for (int j = 1; j < m; j ++ )
if (!matrix[i][j])
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
//将标记的行列置0
for (int i = 1; i < n; i ++ )
if (!matrix[i][0])
for (int j = 1; j < m; j ++ )
matrix[i][j] = 0;
for (int i = 1; i < m; i ++ )
if (!matrix[0][i])
for (int j = 1; j < n; j ++ )
matrix[j][i] = 0;
//处理第0行和第0列
if (!col0)
for (int i = 0; i < n; i ++ )
matrix[i][0] = 0;
if (!row0)
for (int i = 0; i < m; i ++ )
matrix[0][i] = 0;
}
};题解 开个偏移量数组就行
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int n = matrix.size();
if (!n) return res;
int m = matrix[0].size();
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
vector<vector<bool>> st(n, vector<bool>(m));
for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++ ) {
res.push_back(matrix[x][y]);
st[x][y] = true;
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
return res;
}
};顺时针 90： 主对角线翻转，垂直轴水平翻转
逆时针 90： 主对角线翻转，水平轴上下翻转
顺时针180 & 逆时针180： 先主对角线翻，后副对角线翻
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
//先主对角线翻转
for (int i = 0; i < n; i ++ )
for (int j = i + 1; j < n; j ++ )
swap(matrix[i][j], matrix[j][i]);
//再竖直轴水平翻转
for (int i = 0; i < n; i ++ )
for (int j = 0, k = n - 1;
j < k; j ++, k -- )
swap(matrix[i][j], matrix[i][k]);
}
};题解 从左下或者右上开始，t==时找到，t<时排除一行， t>时排除一列
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
//从左下或者右上开始，t==时找到，t<时排除一行， t>时排除一列
if (matrix.empty() || matrix[0].empty()) return false;
int n = matrix.size(), m = matrix[0].size();
int i = 0, j = m - 1;
while (i < n && j >= 0) {
int t = matrix[i][j];
if (t == target) return true;
else if (t > target) j -- ;
else i ++ ;
}
return false;
}
};题解 先把自己走完，再从另一条开头走。另一条同步操作，总路程不变，最后的交点就是结果
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto p = headA, q = headB;
//先把自己走完，再从另一条开头走。另一条同步操作，总路程不变，最后的交点就是结果
while(p!=q){
p = p ? p->next : headB;
q = q ? q->next : headA;
}
return p;
}
};
版权声明：
本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
周几小屋！
喜欢就支持一下吧
