leecode每日一练

打家劫舍

我一开始的思路也是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;
}