打家劫舍
我一开始的思路也是dp，但是转移方程想错了，这个题目转移方程应该是dp[i] = max(dp[i-2]+nums[i],dp[i-1])
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len);
int ans = 0;
if(len>=1)
dp[0] = nums[0],ans=max(ans,dp[0]);
if(len>=2)
dp[1] = max(nums[0],nums[1]),ans=max(ans,dp[1]);
for(int i=2;i<len;i++){
dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
ans = max(ans,dp[i]);
}
return ans;
}
};
拆炸弹
纯模拟就是sb，我用了差分数组，但是转移方程写死我了
我写的代码
class Solution {
public:
vector<int> decrypt(vector<int>& code, int k) {
int len = code.size();
vector<int> ans(len);
vector<int> p(len+1);
p[0] = code[0];
for(int i=1;i<len;i++){
p[i] = p[i-1]+code[i];
}
if(k==0){
return ans;
}
else if(k>0){
for(int i=0;i<len;i++){
if(i+k<len){
ans[i] += p[i+k]-p[i];
}else{
ans[i] += p[len-1]-p[i];
int cha = k-(len-1-i);
if(cha>0)
ans[i] += p[cha-1];
}
}
}else{
k = -k;
for(int i=0;i<len;i++){
if(i>k){
if(i-1-k>=0)
ans[i] += p[i-1]-p[i-1-k];
else{
ans[i] += p[i-1];
}
}else{
if(i>0)
ans[i] += p[i-1];
int cha = k-i;
ans[i] += p[len-1]-p[len-1-cha];
}
}
}
return ans;
}
};
但是其实只要开两倍的空间就可以简单完成,下面这个思路是滑动窗口，但是其实差分也是可以的
class Solution {
public:
vector<int> decrypt(vector<int>& code, int k) {
int n = code.size();
vector<int> res(n);
if (k == 0) {
return res;
}
code.resize(n * 2);
copy(code.begin(), code.begin() + n, code.begin() + n);
int l = k > 0 ? 1 : n + k;
int r = k > 0 ? k : n - 1;
int w = 0;
for (int i = l; i <= r; i++) {
w += code[i];
}
for (int i = 0; i < n; i++) {
res[i] = w;
w -= code[l];
w += code[r + 1];
l++;
r++;
}
return res;
}
};
基站建设
一开始我的思路是差分，但是只能过五分之一的数据集，这是因为如果这些重叠的区域过多的话就会出现问题
给你看一下差分的代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int s[N];
int p[N];
int n;
int main() {
cin >> n;
int a, b;
int mm = 0;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
int l = (a - b) > 1 ? a - b : 1;
int r = (a + b) < N ? a + b : N - 1; mm = max(mm, r);
s[l] += 1;
s[r + 1] -= 1;
}
for (int i = 1; i <= mm; i++) {
p[i] += p[i - 1] + s[i];
}
int re = 0;
int now;
int flag = 0;
for (int i = 1; i <= mm; i++) {
//cout << p[i] << " ";
if (flag == 0 && p[i] > 1) {
flag = 1; // 进入区域
now = p[i];
}
if (flag == 1 && p[i] <= 1) {
flag = 0; //出去
re += now - 1;
}
if (flag == 1 && p[i] > 1) {
now = max(now, p[i]);
}
}
cout << n - re;
return 0;
}
应该用贪心来做，就是一个活动安排问题
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
struct node
{
int start, end;
bool operator<(node b) {
return this->end < b.end;
}
}a[N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x, b;
cin >> x >> b;
a[i].start = x - b;
a[i].end = x + b;
}
sort(a + 1, a + 1 + n);
if (n == 0) {
cout << 0;
return 0;
}
int ans = 1;
int now = a[1].end;
for (int i = 2; i <= n; i++) {
if (a[i].start <= now) continue;
now = a[i].end; ans++;
}
cout << ans;
return 0;
}
leecode 每日温度
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int len = temperatures.size();
deque<int> p;
vector<int> ans(len);
for (int i = 0; i < len; i++) {
int temp = temperatures[i];
while (p.size() && temp > temperatures[p.back()]) {
int po = p.back();
cout << "尾巴的 " << po << endl;
p.pop_back();
ans[po] = i - po;
}
p.push_back(i);
}
return ans;
}
};
leecode 1475
class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int len = prices.size();
vector<int> ans(len);
deque<int> q;
for (int i = 0; i < len; i++) {
int now = prices[i];
while (q.size()&&now<=prices[q.back()])
{
int pos = q.back();
q.pop_back();
ans[pos] = prices[pos] - now;
}
q.push_back(i);
}
// 别忘记这一步
while(q.size()){
int pos = q.back();
ans[pos] = prices[pos];
q.pop_back();
}
return ans;
}
};
落谷2422
我们还要注意退出for循环后的边界处理，这时候单调栈里面还有东西
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int a[N];
int n;
int ans = 0;
int p[N];
int l[N], r[N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
l[i] = r[i] = i;
}
deque<int> q;
for (int i = 1; i <= n; i++) {
int now = a[i];
while (q.size()&& now<a[q.back()])
{
int u = q.back();
q.pop_back();
r[u] = i;
}
q.push_back(i);
}
while (q.size()) {
int u = q.back();
q.pop_back();
r[u] = n+1;
}
q.clear();
for (int i = n; i >= 1; i--) {
int now = a[i];
while (q.size() && now < a[q.back()]) {
int u = q.back();
q.pop_back();
l[u] = i;
}
q.push_back(i);
}
while (q.size())
{
int u = q.back();
q.pop_back();
l[u] = 0;
}
for (int i = 1; i <= n; i++) {
ans = max(ans, a[i] * (p[r[i]-1] - p[l[i]]));
}
//for (int i = 1; i <= n; i++) {
// cout << l[i] << " " << r[i] << endl;
//}
cout << ans;
return 0;
}
leecode2244
class Solution {
public:
int minimumRounds(vector<int>& tasks) {
unordered_map<int, int> cnt;
for (int t : tasks) {
cnt[t]++;
}
int ans = 0;
for (auto& [_, c] : cnt) {
if (c == 1) {
return -1;
}
ans += (c + 2) / 3;
}
return ans;
}
};
leecode2589
这个题目和活动安排问题很相似，所以采用贪心的思路
我的代码
class Solution {
public:
int findMinimumTime(vector<vector<int>>& tasks) {
vector<int> d(20005,0);
sort(tasks.begin(), tasks.end(), cmp);
int len = tasks.size();
int ans = 0;
for (int i = 0; i < len; i++) {
int du = tasks[i][2];
int l = tasks[i][0], r = tasks[i][1];
for (int j = l; j <= r; j++) {
if (d[j] == 1) du--;
}
for (int j = r; du > 0; j--) {
if (d[j]) continue;
d[j] = 1; du--; ans++;
}
}
return ans;
}
static bool cmp(vector<int> a, vector<int> b) {
return a[1] < b[1];
}
};
leecode 1953
看到题目的数据范围就知道不能暴力算
稍微模拟一下就知道答案
class Solution {
public:
long long numberOfWeeks(vector<int>& milestones) {
int len = milestones.size();
if(len==1) return 1;
sort(milestones.begin(),milestones.end());
long long qian = 0;
for(int i=0;i<len-1;i++) qian+=milestones[i];
long long ma = milestones[len-1];
if(qian>=ma) return qian+ma;
else return qian*2+1;
}
};
leecode 2644
class Solution {
public:
int maxDivScore(vector<int>& nums, vector<int>& divisors) {
unordered_map<int, int> mp;
for (int u : divisors) {
int flag = 0;
if (mp.contains(u)) continue; // 避免重复
if (!u) mp[u] = 0;
else {
for (int t : nums) {
if (t % u == 0) mp[u]++,flag = 1;
}
}
if (flag == 0) mp[u] = 0; // 避免没有初始化
}
int ans = -1, record = 10000;
for (auto u : mp) {
if (u.second > ans) {
record = u.first;
ans = u.second;
}
else if (u.second == ans) {
record = min(record, u.first);
}
}
return record;
}
};
leecode 1535
我一开是想开两倍空间，然后用单调栈来记录每个值后面有多少个比它小的，但是没有考虑k的问题
class Solution {
public:
int getWinner(vector<int>& arr, int k) {
int mx = arr[0], win = 0;
for (int i = 1; i < arr.size() && win < k; i++) {
if (arr[i] > mx) { // 新的最大值
mx = arr[i];
win = 0;
}
win++; // 获胜回合 +1
}
return mx;
}
};
class Solution:
def getWinner(self, arr: List[int], k: int) -> int:
mx = arr[0]
win = -1 # 对于 arr[0] 来说，需要连续 k+1 个回合都是最大值
for x in arr:
if x > mx: # 新的最大值
mx = x
win = 0
win += 1 # 获胜回合 +1
if win == k:
break
return mx
leecode 2225
以后和桶相关的都不必开数组，开个哈希表就行
class Solution {
public:
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
int n = matches.size();
unordered_map<int, int> mp;
for (int i = 0; i < n; i++) {
int win = matches[i][0], lose = matches[i][1];
if (mp[win] % 2 == 0) {
mp[win] += 2;
}
if (mp[lose]!=-1) {
if(mp[lose] % 2)
mp[lose] = -1;
else {
mp[lose] += 1;
}
}
}
vector<vector<int>> ans(2);
for (auto u : mp) {
if (u.second %2==0 && u.second!=0) {
ans[0].push_back(u.first);
}
if (u.second % 2 && u.second != -1) {
ans[1].push_back(u.first);
}
}
sort(ans[0].begin(), ans[0].end());
sort(ans[1].begin(), ans[1].end());
return ans;
}
};
leecode1673
第一眼看的时候感觉要用贪心算法，每次找到一个最小的
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
int m = 0; // 栈的大小
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
while (m && x < nums[m - 1] && m + nums.size() - i > k) {
m--; // 出栈
}
if (m < k) {
nums[m++] = x; // 入栈（把 nums 当作栈）
}
}
nums.resize(m);
return nums;
}
};