hash删除
hash.erase(key)
lcr172
找区间
简单的开区间二分
两次二分，找到左右边界
target+1找上边界的设计：
target+1不在数组中是否存在影响呢?
class Solution {
public:
//开区间写法
int lowwer(vector<int>& nums,int targ)
{
int l=-1,r=nums.size();
while(l+1<r)
{
int mid=l+(r-l)/2;
if(nums[mid]<targ)
l=mid;
else r=mid;
}
return l;
}
int countTarget(vector<int>& scores, int target)
{
int l=lowwer(scores,target);
int r=lowwer(scores,target+1);
return r-l;
}
};
谨记 我们找的是开区间，利用顺序也可以这么计数
int countTarget(vector<int>& scores, int target)
{
int l=lowwer(scores,target)+1;
int cnt=0;
while(l<scores.size() && scores[l]==target)
{
cnt++;
l++;
}
return cnt;
}
};
经典例题：
知道二叉树 前中后遍历中的两个结果，反推二叉树
lcr134. 推理二叉树
分治
class Solution {
public:
TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for(int i = 0; i < inorder.size(); i++)
hmap[inorder[i]] = i;
return recur(0, 0, inorder.size() - 1);
}
private:
vector<int> preorder;
unordered_map<int, int> hmap;
TreeNode* recur(int root, int left, int right) {
if(left > right) return nullptr; // 递归终止
TreeNode* node = new TreeNode(preorder[root]); // 建立根节点
int i = hmap[preorder[root]]; // 划分根节点、左子树、右子树
node->left = recur(root + 1, left, i - 1); // 开启左子树递归
node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
};
lc1638.统计只差一个字符的子串
暴力
class Solution {
public:
int countSubstrings(string s, string t) {
int m = s.size();
int n = t.size();
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int diff = 0;
for (int k = 0; i + k < m && j + k < n; ++k) {
diff += (s[i + k] != t[j + k]);
if (diff > 1) {
break;
}
if (diff == 1) {
++ans;
}
}
}
}
return ans;
}
};
dp
lc337.打家劫舍iii
pair<int,int> dfs
return {rob,not_rob}
利用return 归，后序计算，返回子树结果，自底向上
class Solution {
pair<int, int> dfs(TreeNode* node) {
if (node == nullptr)
{ // 递归边界
return {0, 0}; // 没有节点，怎么选都是 0
}
auto [l_rob, l_not_rob] = dfs(node->left); // 递归左子树
auto [r_rob, r_not_rob] = dfs(node->right); // 递归右子树
int rob = l_not_rob + r_not_rob + node->val; // 选
int not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob); // 不选
return {rob, not_rob};
}
public:
int rob(TreeNode* root) {
auto [root_rob, root_not_rob] = dfs(root);
return max(root_rob, root_not_rob); // 根节点选或不选的最大值
}
};
扩展
没有上司的舞会
综合
lc2014. 重复k次的最长子序列
可以拆分为后面的两道=
枚举排列➕判断子序列
lc392.判断子序列
class Solution {
public:
bool isSubsequence(string s, string t) {
int i=0,j=0;
while(i<s.size() && j<t.size())
{
if(s[i]==t[j])
i++;
j++;
}
return i==s.size();
}
};
lc47. 全排列 II
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<bool> check;
vector<vector<int>> permuteUnique(vector<int>& nums)
{
//排序
sort(nums.begin(),nums.end());
check.resize(nums.size(),false); //初始化数组
dfs(nums,0);
return ret;
}
void dfs(vector<int>& nums,int pos)
{
if(path.size()==nums.size())//终止条件
{
ret.push_back(path);
return;
}
for(int i=0;i<nums.size();i++)//遍历所有元素
{
//legal
if(check[i]==false && (i==0 || nums[i]!=nums[i-1] || check[i-1]==true))
{
check[i]=true;
path.push_back(nums[i]);
dfs(nums,i);
check[i]=false;//处理标记
path.pop_back();
}
}
}
};
lc2673. 路径值相等的最小代价
自底向上，取最大值补全
ans等于做差
class Solution {
public:
int minIncrements(int n, vector<int>& cost) {
int ans = 0;
function<int(int)> dfs = [&](int u)
{
if(u >= n) return 0;
int l = dfs(u*2 + 1); //+1
int r = dfs(u*2 + 2);
//+2 数组下标为0 起始
ans += abs(l-r); //加上差的绝对值
return cost[u] + max(l, r);
//补全为最大值
};
dfs(0);
return ans;
}
};
取出hash第一个次数为例的方法
int cnt=hash.begin()->second;