406. 根据身高重建队列
题解思路
1.先从高到矮排序
2.按照第二个参数k(前面有几个人)将其放到index为k的位置
vec的insert用法
iterator insert( iterator loc, const <T>&val );
void insert( iterator loc, size_type num, const <T>&val );
void insert( iterator loc, input_iterator start, input_iterator end );
这题里用到的是第一种做法，似乎不用加const？
for (vector<int>& p : people) {
res.insert(res.begin() + p[1], p);
}
416. 分割等和子集
题解思路
很明显是一个01背包问题
然而我忘记怎么做了
vector<bool> dp(sum + 1);
dp[0] = true;
for (const int num : nums) {
for (int i = sum; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
437. 路径总和 III
我的思路【Failed】
对于每一个支路，都有多个任务，一个是8，还有上面节点下来的task，第二层是target和target - rootval，我打算用vector来存但是考虑到复杂度太高了就不考虑了
题解思路
使用前缀和,看题解一下子还没看懂.然后做了一题简单一点的类似的题
[3,4,7,6,1,3]假设k为7,求和为7的子数组个数
使用unordered_map m来做,需要注意的点.m[0] = 1,i从0到len,如果m[当前的前缀和 - 目标值]存在,
ans += m[presum - target]
m[presum]++
m[0]是为了[4+3 -7]这样的前缀和
回到本题
void dfs(TreeNode* root) {
if (root == nullptr) return;
pre += root -> val;
if (m.find(pre - sum) != m.end()) {
res += m[pre - sum];
}
m[pre]++;
dfs(root -> left);
dfs(root -> right);
m[pre]--;
pre -= root -> val;
}
需要注意的是,trace back的时候,pre要减减,m[pre]也要减减
438. 找到字符串中所有字母异位词
题解思路
使用滑动窗口比较哈希表。
我卡在比较两个哈希表相等上了，我用unordered_map存的,要一个一个比较过去有点麻烦.
- skill
使用字母哈希,直接比较两个vector是否相等就可以了,因为vector重载了==运算符
for (int i = 0; i < s.size(); ++i) {
window[s[i]]++;
if (window == pch) {
ans.push_back(i - plen + 1);
}
if (i >= plen - 1) {
window[s[i + 1 - plen]]--;
}
}
448. 找到所有数组中消失的数字
题解思路
我只能说是技巧题
有n个数的数组，数均在[1,n]之间,有的数重复了,有的数没出现,找出没出现的数的下标
1.把出现的数为下标的那个数+n
2.遍历一遍,<n的数的下标就是没出现的数.过程中需要考虑基0这个条件
for (int& num : nums) {
int x = (num - 1) % nums.size();
nums[x] += nums.size();
}
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] <= nums.size()) {
ans.push_back(i + 1);
}
}
