力扣Hot100题单个人计划c++版（一）
力扣Hot100题单个人计划c++版（二）
力扣Hot100题单个人计划c++版（三）
力扣Hot100题单个人计划c++版（四）
刷题链接：力扣Hot 100
每日一题，每日一更，白板手写。
- 61.课程表
- 62.实现Trie(前缀树)
- 63.数组中第k个最大元素
- 64.最大正方形
- 65.翻转二叉树
- 66.回文链表
- 67.二叉树的最近公共祖先
- 68.除自身以外数组的乘积
- 69.滑动窗口最大值
61.课程表
11.3打卡
拓扑排序，还是待补吧。有点难写。
11.3打卡
这个还是等深入了解吧。本题只是皮毛，没有可以参考的标准代码。
11.4打卡
经典topk问题。快速排序的思想可以找到第k大元素。堆排序的思想可以找到前k个数。
class Solution {
public:
int partation(vector& nums, int l, int r) {
int idx=l+rand()%(r-l+1);
swap(nums[l],nums[idx]);
int mid=nums[l];
while(l=mid)++l;
nums[r]=nums[l];
}
nums[l]=mid;
return l;
}
int findKthLargest(vector& nums, int k) {
int n=nums.size();
int l=0,r=n-1;
int p;
while(l<=r){
p=partation(nums,l,r);//p是坐标
if(p==k-1)return nums[p];
else if(p>k-1)r=p-1;
else l=p+1;
}
return nums[p];
}
};
64.最大正方形
11.5打卡
动态规划问题，这个递推关系很巧妙，我们用
dp
(
i
,
j
)
textit{dp}(i, j)
dp(i,j) 表示以
(
i
,
j
)
(i, j)
(i,j)为右下角，且只包含 1 的正方形的边长最大值。如果该位置的值是 0，则
dp
(
i
,
j
)
=
0
textit{dp}(i, j)=0
dp(i,j)=0，如果该位置的值是 1，则
dp
(
i
,
j
)
textit{dp}(i, j)
dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的
dp
(
i
,
j
)
textit{dp}(i, j)
dp(i,j) 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1。很难想到的思路，mark一下。
class Solution {
public:
int maximalSquare(vector>& matrix) {
int n=matrix.size();
if(!n)return 0;
int m=matrix[0].size();
if(!m)return 0;
int ans=0;
vector> dp(n,vector(m,0));
for(int i=0;i
65.翻转二叉树
11.6打卡
递归版很好写。迭代版要花点时间，就不码了。
class Solution {
public:
void dfs(TreeNode* p){
if(!p)return;
if(p->left)dfs(p->left);
if(p->right)dfs(p->right);
TreeNode* t=p->left;
p->left=p->right;
p->right=t;
}
TreeNode* invertTree(TreeNode* root) {
dfs(root);
return root;
}
};
66.回文链表
11.7打卡
O(1)空间复杂度。。。怎么说呢，只能递归了。很难写而且没必要。本题算了。
class Solution {
public:
ListNode* front;
bool check(ListNode* cur){
if(cur){
if(!check(cur->next))return false;
if(cur->val!=front->val)return false;
front=front->next;
}
return true;
}
bool isPalindrome(ListNode* head) {
front=head;
return check(head);
}
};
67.二叉树的最近公共祖先
11.8打卡
说来惭愧，LCA问题到现在还没完全熟练。一般来说LCA问题有常见三种解法（参考最近公共祖先以及博客LCA 最近公共祖先
Tarjan(离线)算法的基本思路及其算法实现）。Tarjan算法，倍增算法，转化为RMQ问题后DFS+ST解决。Tarjanr是离线算法，而后两者是在线算法。这三个算法待补，闲了回过头写。暂时先写个最简单的，即递归查询左右子树是否有p和q即可。
class Solution {
public:
TreeNode* ans;
bool dfs(TreeNode* pos,TreeNode* p,TreeNode* q){
if(pos==nullptr)return false;
bool l=dfs(pos->left,p,q);
bool r=dfs(pos->right,p,q);
if(l&&r)ans=pos;
if((pos->val==p->val||pos->val==q->val)&&(l||r))ans=pos;
return l||r||pos->val==p->val||pos->val==q->val;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root,p,q);
return ans;
}
};
68.除自身以外数组的乘积
11.9打卡
本题最直观思路就是算出所有数的乘积然后除以每个数放到原数组，如果数组中有零就返回全零的数即可。
但题目要求不能用除法。那么只需要类似前缀和的思想，求出每个数的左侧前缀乘积和右侧后缀乘积即可。但是又题目又要求常数复杂度。所以可以先用返回的答案数组存前缀乘积，用一个变量更新右侧乘积即可。
class Solution {
public:
vector productExceptSelf(vector& nums) {
int n=nums.size();
vector ans(n);
ans[0]=1;
for(int i=1;i=0;--i){
ans[i]=ans[i]*r;
r*=nums[i];
}
return ans;
}
};
69.滑动窗口最大值
11.10打卡
最直观的解法即将窗口的k个数组成最大堆（优先队列）,每次删去第一个数，加入后一个数，维护这个堆即可。
不过本题还有一种巧妙的解法，基于这样一个性质：如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j的左侧（i < j），并且 i 对应的元素不大于 j 对应的元素
（
nums
[
i
]
≤
nums
[
j
]
n
u
m
s
[
i
]
≤
n
u
m
s
[
j
]
）
（textit{nums}[i] leq textit{nums}[j]nums[i]≤nums[j]）
（nums[i]≤nums[j]nums[i]≤nums[j]），那么可以删掉元素i，因为只要 i 还在窗口中，那么 j 一定也还在窗口中，由于
nums
[
j
]
textit{nums}[j]
nums[j] 的存在，
nums
[
i
]
textit{nums}[i]
nums[i]一定不会是滑动窗口中的最大值了。所以我们可以维护一个单调队列，维护下标递增，值非严格递减的队列。
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n=nums.size();
deque dq;
vector ans;
for(int i=0;i 
