这就是单调队列裸题，不知道为啥难度是困难
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
deque<int> q;
for (int i = 0; i < nums.size(); i++) {
// 最大值 应该是队首的元素最大
// 所以进来的如果比队尾的大 就违反了单调性
// 维护一个单减队列
while (q.size() && nums[q.back()] < nums[i]) q.pop_back();
q.push_back(i);
if (i - q.front() == k) q.pop_front();
if (i + 1 < k) continue;
ret.push_back(nums[q.front()]);
}
return ret;
}
};借助单调队列mq来实现max_value的操作
class MaxQueue {
public:
// 队列的max_value
// 可以看做q.size()长的滑动窗口的最值
// mq是辅助队列
deque<int> q, mq;
MaxQueue() { }
int max_value() {
if (mq.size() == 0) return -1;
return mq.front();
}
void push_back(int value) {
q.push_back(value);
// 维护单减队列
// 因为是最大值
while (mq.size() && value > mq.back()) mq.pop_back();
mq.push_back(value);
return ;
}
int pop_front() {
if (q.size() == 0) return -1;
// 如果mq有q的队首元素
// 那么也需要弹出mq的队首
if (q.front() == mq.front()) mq.pop_front();
int ret = q.front();
q.pop_front();
return ret;
}
};这个题主要是要思考清楚19行为什么是$\gt$
和28行为什么相等就要出队？
单调队列是对原序列另外的一种信息的表示方式
因为这两行是强关联的
假设原序列是:star::star::crescent_moon::crescent_moon::star: 其中:star:是最大值
那么单调队列就会是三个一样的星星
这样在28行pop的时候才能正确的弹出（按顺序进来的）
如果19行改成$\ge$
一样大的元素就只能进来一个，也就是只能进来一个:star:
那这样就没法在28行pop的时候判断这个:star:是哪个了
就必须再存储额外的信息
比如存个下标，和优先队列里的下标比较
给你一个整数数组
nums和一个整数k，找出nums中和至少为k的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回-1。子数组 是数组中 连续 的一部分。
看到和了，就想到常用的编程技巧--前缀和数组
那么对于 数组a1, a2...an
有前缀和 数组s1, s2...sn
那么对于任意si 肯定是想让子数组和又大并且自数组又短
满足大——肯定是要减去前面最小的sj1(i > j)
满足短——假设sj2(j1 < j2 < i)，如果si - sj2也满足
我们肯定是希望更短的！
如果再有sj3 那么就再试试sj3能否满足
那么我们发现了
sj1, sj2, sj3 就是(j, i)的单调队列的元素呀，并且是单增的队列
也就变成了找这个单调队列最后一个位置（为了让子数组尽可能短）
上面是固定末尾的情况
如果i再向后移动，比如为i + 1
并且i对应的和为k的最短子数组为j3
那么s{i + 1}能找到的和为k的最短子数组的j一定 > j3
也就是j1 j2 j3 永远不可能成为i + 1位置满足条件的的了！
这个非常好的性质！
这说明之前pop出去的元素我们不用再考虑了！
push——保证单增队列就行
pop——新进入的元素比头要短，并且pop出去的不再考虑
如果还不清楚
请看
1是全局最小值，2是1之后的最小值。。。以此类推（维护单增，并且元素个数一直在减小）
那么对应到这个题，
J1, J2, J3 不也是一样的吗，为什么j1之后还要找j3，那不就是j3代表了元素个数较少的时候的最小值么！
就像1之后为什么找8，8就剩下俩元素了！
分析问题的时候，发现要记录某种性质（最大，最小），而单调队列刚好能满足这种性质
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
deque<int> q;
vector<long long> sum(nums.size() + 1);
sum[0] = 0;
for (int i = 0; i < nums.size(); ++i) sum[i + 1] = sum[i] + nums[i];
q.push_back(0);
// 上一次答案的位置, 长度
int pos = -1, ans = -1;
for (int i = 1; i < sum.size(); ++i) {
// 先找符合条件的
// q存的是符合条件的头元素下标
while (q.size() && sum[i] - sum[q.front()] >= k) {
// 找到了一个符合条件的
pos = q.front();
q.pop_front();
}
// 说明找到了更短的
if (pos != -1 && (i - pos < ans || ans == -1)) ans = i - pos;
// 维护一个单增队列
while (q.size() && sum[i] < sum[q.back()]) q.pop_back();
q.push_back(i);
}
return ans;
}
};给你一个整数数组
nums，和一个表示限制的整数limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组，则返回
0。
假设有一段连续子数组，长度为s:[l, r]，且满足题目给定的条件：任意两个元素之间的绝对差必须小于或者等于 limit 。
那么对于任意s - 1 < s$\in$[l, r] 肯定都满足limit条件
但是对于s + 1长度的课就不一定了
那这不就是1111100000 找最后一个1的模型吗
就可以用二分
那么二分的check条件怎么判断呢？
上面的二分已经确定了长度为s的子数组
这不就是滑动窗口最值吗
这就简单了，如果最大值减最小值都小于limit
肯定所有的元素都小于limit
那就维护两个单调队列呗！
class Solution {
public:
// 二分 + 判定
// 判定的是给定序列的长度
bool check(vector<int> &nums, int k, int limit) {
deque<int> qmin, qmax;
for (int i = 0; i < nums.size(); ++i) {
while (qmin.size() && nums[i] < nums[qmin.back()]) qmin.pop_back();
while (qmax.size() && nums[i] > nums[qmax.back()]) qmax.pop_back();
qmin.push_back(i);
qmax.push_back(i);
if (i + 1 < k) continue;
if (i - qmin.front() == k) qmin.pop_front();
if (i - qmax.front() == k) qmax.pop_front();
if (nums[qmax.front()] - nums[qmin.front()] <= limit) return true;
}
return false;
}
int bs(vector<int> &nums, int l, int r, int limit) {
if (l == r) return l;
// 这个题的二分模型是找最后出现的1
// 所以为了防止无限循环 mid要 + 1
int mid = (l + r + 1) >> 1;
// 二分的是序列长度
// 看看长度为mid的序列能不能满足limit条件
// 每次从0循环到 nums.size() - mid
// mid就是滑动窗口（子数组）的大小
if (check(nums, mid, limit)) l = mid;
else r = mid - 1;
return bs(nums, l, r, limit);
}
int longestSubarray(vector<int>& nums, int limit) {
// 从1开始就行
return bs(nums, 1, nums.size(), limit);
}
};class Solution {
public:
// 也可以每次记录当前深度出现的第一个值
// 最后返回最大深度的那个就行
void getResult(TreeNode *root, int k, vector<int> &ret) {
if (root == nullptr) return ;
if (k == ret.size()) ret.push_back(root->val);
getResult(root->left, k + 1, ret);
getResult(root->right, k + 1, ret);
return ;
}
int findBottomLeftValue(TreeNode* root) {
vector<int> ret;
getResult(root, 0, ret);
return ret[ret.size() - 1];
}
};脑筋急转弯题
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
注意边界条件
第一次左向右遍历的时候
0是不用考虑的 也就是从1开始，考虑左边的即可，
因为nums.size() - 1位置上的元素也没有右边的
而第二次开始的时候就要考虑右边的
从nums.size() - 2的位置开始 到0 因为第一次没更新0
而且0的值只受1影响 所以必须是考虑右边的
class Solution {
public:
// 遍历两次
// 左向右一次 求出满足条件的值
// 右向左一次 取这两个值的max
// 什么叫满足条件呢？
// -> 的时候 如果a[x] < a[x + 1] 那么candy[x + 1] > candy[x]
// 不大于的话1个就够了
// <- 的时候比较a[x + 1] < a[x] 那么candy[x] 就得 > candy[x + 1]
int candy(vector<int>& ratings) {
vector<int> l(ratings.size()), r(ratings.size());
for (int i = 0, j = 1; i < ratings.size(); ++i) {
if (i && ratings[i] > ratings[i - 1]) j += 1;
else j = 1;
l[i]= j;
}
for (int i = ratings.size() - 1, j = 1; i >= 0; --i) {
if (i < ratings.size() - 1 && ratings[i] > ratings[i + 1]) j += 1;
else j = 1;
r[i] = j;
}
int ans = 0;
for (int i = 0; i < ratings.size(); ++i) {
ans += max(l[i], r[i]);
}
return ans;
}
};搜索 + 状态转移
有两个水壶，容量分别为
jug1Capacity和jug2Capacity升。水的供应是无限的。确定是否有可能使用这两个壶准确得到targetCapacity升。如果可以得到
targetCapacity升水，最后请用以上水壶中的一或两个来盛放取得的targetCapacity升水。你可以：
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水，直到装满或者倒空
也就是说水壶（假设标号为1，2，装水和没装水分别为0，1）的状态转化有如下关系：
1: (0, 1) -> (1, 1)(可以将1倒满，也可以将2中的倒入1)
2: (0, 1) -> (0, 0)
3: (1, 0) -> (1, 1)
4: (1, 0) -> (0, 0)
5: (0, 0) -> (0, 1)
6: (0, 0) -> (1, 0)
7: (1, 1) -> (1, 0)
8: (1, 1) -> (0, 1)
以上八种情况可以合并成六种
因为2和7都是将2中的水倒光
这就是所谓的状态转移
class Solution {
public:
// 搜索题
// 两个水壶的状态就构成了问题求解树！
// 因为状态之间是可以相互转化的！
typedef pair<int, int> PII;
// 状态 第一个水壶里的水和水壶上限
PII getNext(int k, int x, int X, int y, int Y) {
switch (k) {
// 清空第一个水壶里的水
case 0: return PII(0, y);
case 1: return PII(x, 0);
// 将1中的部分水倒入2
// 根据1中的水和2中剩余的水的关系
case 2: {
int delta = min(x, Y - y);
return PII(x - delta, y + delta);
}
case 3: {
int delta = min(X - x, y);
return PII(x + delta, y - delta);
}
case 4: return PII(X, y);
case 5: return PII(x, Y);
}
return PII(0, 0);
}
struct cmp {
long long operator()(const PII &a) const {
return ((long long)(a.first) << 31) + a.second;
}
};
bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
unordered_set<PII, cmp> vis;
queue<PII> q;
vis.insert(PII(0, 0));
q.push(PII(0, 0));
// bfs
while (!q.empty()) {
// 取状态
PII cur = q.front();
// 取到了目标状态
if (cur.first + cur.second == targetCapacity) return true;
q.pop();
// 状态转移
// 遍历6个状态
for (int i = 0; i < 6; ++i) {
PII temp = getNext(i, cur.first, jug1Capacity, cur.second, jug2Capacity);
// 用vis 哈希集合去重
if (vis.find(temp) != vis.end()) continue;
vis.insert(temp);
q.push(temp);
}
}
return false;
}
};给你一个整数数组
nums，其中nums[i]表示第i个袋子里球的数目。同时给你一个整数maxOperations。你可以进行如下操作至多
maxOperations次：
- 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。
- 比方说，一个袋子里有
5个球，你可以把它们分到两个新袋子里，分别有1个和4个球，或者分别有2个和3个球。你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
也就是要返回最小的maxOp次分割之后的数组的最大值
假设得到正确答案，也就是最小化每堆的最大值为x
那么maxOp次分割内，可以得到x + 1吧，也可以得到x + 2吧
但是无法得到x - 1，x - 2吧
这不就是000001111找第一个1的模型么！
只不过maxOp和开销需要建立一个映射
分类讨论：
if能整除 $ \ \frac{n}{x} = \hat{n} \ maxOp = \hat{n} - 1$
If不能整除 $ \ \frac{n}{x} = \hat{n}...n_1 \ maxOp = \hat{n} + 1 - 1$
class Solution {
public:
// 二分 + 判定
int f(vector<int> &nums, int x) {
int cnt = 0;
for (int i = 0; i < nums.size(); ++i) {
// !! 两次取反 可以正则化
// 也就是能把非零值化成1
// 0还是0
cnt += nums[i] / x + !!(nums[i] % x) - 1;
}
return cnt;
}
int bs(vector<int> &nums, int l, int r, int n) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (f(nums, mid) <= n) r = mid;
else l = mid + 1;
return bs(nums, l, r, n);
}
int minimumSize(vector<int>& nums, int maxOperations) {
int l = 1, r;
for (auto x : nums) r = max(r, x);
// param ：每一堆球的数量
return bs(nums, l, r, maxOperations);
}
};class Solution {
public:
// 简单贪心
// 每次都往最远跳
int jump(vector<int>& nums) {
// 记录两个位置
// pre为上一次跳跃的位置
// 假设上一次跳跃的位置最远在pre
// 然后pre之前所有的元素能跳到的最远的位置是pos
// 下一次起跳就是从pre - pos中选一个最远的
// 一开始一定是在0点起跳的
if (nums.size() <= 1) return 0;
int pre = 0, pos = nums[0], cnt = 1;
while (pos + 1 < nums.size()) {
// j记录最远的
int j = pre;
for (int i = pre + 1; i <= pos; ++i) {
if (i + nums[i] > j + nums[j]) j = i;
}
pre = pos + 1;
pos = j + nums[j];
cnt += 1;
}
return cnt;
}
};
这个就是一个暴力搜索 + 大模拟题
不断尝试往str里插.就行
class Solution {
public:
// 就是往str插.
// 递归枚举.所有的情况就行
// param s, 当前正在插入第几个点（3个就够），当前合法ip的起始位置
void dfs(string &s, int k, int ind, vector<string> &ret) {
if (ind >= s.size()) return ;
// 终止条件
if (k == 4) {
int num = 0;
// 判断数组合法性
// 如果有元素（也就是IP子段开始了） 并且子段开头 == 0 那就是非法的
if (s.size() - ind > 1 && s[ind] == '0') return ;
for (int i = ind; i < s.size(); ++i) {
num = num * 10 + s[i] - '0';
if (num > 255) return ;
}
ret.push_back(s);
return ;
}
for (int i = ind, num = 0; i < s.size(); ++i) {
num = num * 10 + s[i] - '0';
if (num > 255) return ;
if (i - ind >= 1 && s[ind] == '0') return ;
s.insert(i + 1, ".");
// 因为在i + 1的地方插入了"."
// 所以下一个开始的位置是i + 2
dfs(s, k + 1, i + 2, ret);
// 回溯的时候删去i + 1的.
s.erase(i + 1, 1);
}
return ;
}
vector<string> restoreIpAddresses(string s) {
vector<string> ret;
dfs(s, 1, 0, ret);
return ret;
}
};可以直接排序之后调next_permutation就是下一个排列
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
do {
ret.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return ret;
}
};也可以搜索
class Solution {
public:
void getReult(vector<int> &nums, bitset<10> &bs, vector<int> &buff, vector<vector<int>> &ans) {
if (buff.size() == nums.size()) {
ans.push_back(buff);
return ;
}
for (int i = 0; i < nums.size(); ++i) {
if (bs[i]) continue;
bs[i] = 1;
buff.push_back(nums[i]);
getReult(nums, bs, buff, ans);
buff.pop_back();
bs[i] = 0;
}
return ;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> buff;
// use数组 来标记nums[i]是否被使用过
// 因为循环不是从ind开始的
// 而是每次都循环一遍nums
// 就需要看那个用没用过
// 组合问题才需要从ind开始，每次更新ind
bitset<10> bs(0);
getReult(nums, bs, buff, ans);
return ans;
}
};class Solution {
public:
// 经典BigInt
string multiply(string num1, string num2) {
vector<int> a(num1.size()), b(num2.size());
vector<int> c(a.size() + b.size() - 1);
for (int i = 0; i < num1.size(); ++i) a[a.size() - i - 1] = num1[i] - '0';
for (int i = 0; i < num2.size(); ++i) b[b.size() - i - 1] = num2[i] - '0';
for (int i = 0; i < a.size(); ++i) {
for (int j = 0; j < b.size(); ++j) {
c[i + j] += a[i] * b[j];
}
}
for (int i = 0; i < c.size(); ++i) {
if (c[i] < 10) continue;
if (i + 1 == c.size()) c.push_back(0);
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
while (c.size() > 1 && c[c.size() - 1] == 0) c.pop_back();
string ret = "";
for (int i = c.size() - 1; i >= 0; --i) {
ret += c[i] + '0';
}
return ret;
}
};