头像

非科班想刷千题再改名

scu -- ustc




离线:2小时前



题目链接 LeetCode 139

为什么这里用vector才可以,开数组就会报错了

错误的代码:

    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        unordered_set<ULL> hash;
        const int P = 131;
        for(auto &word : wordDict) {
            ULL h = 0;
            for(auto c : word) h = h * P + c;
            hash.insert(h);
        } 
        int n = s.size();
        s = ' ' + s;
        vector<bool> f(n+1);
        //bool f[n+1];
        f[0] = true;
        for(int i = 0; i < n; i++) {
            if(f[i]) {
                ULL h = 0;
                for(int j = i + 1; j <= n; j++) {
                    h = h * P + s[j];
                    if(hash.count(h)) f[j] = true;
                }
            }
        }
        return f[n];
    }

Line 18: Char 16: runtime error: load of value 173, which is not a valid value for type ‘bool’ (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:27:16



活动打卡代码 AcWing 1010. 拦截导弹

贪心,每次都找到一个大于自己的最小的位置后面加入当前数,如果没有则创建一个新子序列

#include <iostream>

using namespace std;
const int N = 1010;
int q[N], f[N], g[N];
int n;

int main() {
    while(cin >> q[n]) n++;
    int res = 0;
    for(int i = 0; i < n; i++) {
        f[i] = 1;
        for(int j = 0; j < i; j++) 
            if(q[j] >= q[i]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        int k = 0;
        while(k < cnt && g[k] < q[i]) k++;
        g[k] = q[i];
        if(k == cnt) cnt++;
    }
    cout << cnt << endl;
    return 0;
}



f[i],以i为结尾的最大上升子序列和

#include <iostream>

using namespace std;

const int N = 1010;
int a[N], f[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        f[i] = a[i];
        for(int j = 1; j < i; j++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res;
    return 0;
}


活动打卡代码 AcWing 3208. Z字形扫描

横纵坐标之和找规律

#include <iostream>

using namespace std;
const int N = 510;
int a[N][N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for(int i = 2; i <= n + n; i++) {
        if(i % 2) {
            for(int j = 1; i - j > 0; j++) {
                if(j > 0 && j <= n && i - j > 0 && i - j <= n) printf("%d ", a[j][i-j]);
            }
        }else{
            for(int j = i - 1; j; j--) {
                if(j > 0 && j <= n && i - j > 0 && i - j <= n) printf("%d ", a[j][i-j]);
            }
        }
    }
    return 0;
}


活动打卡代码 AcWing 3203. 画图

暴力求解

#include <iostream>

using namespace std;
const int N = 110;
bool a[N][N];

int main() {
    int x1, y1, x2, y2;
    int n;
    cin >> n;
    while(n--) {
        cin >> x1 >> y1 >> x2 >> y2;
        for(int i = x1; i < x2; i++) 
            for(int j = y1; j < y2; j++) 
                a[i][j] = true;
    }
    int ans = 0;
    for(int i = 0; i <= 100; i++)
        for(int j = 0; j <= 100; j++)
            if(a[i][j]) ans++;
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 3232. 最大波动

语法题

#include <iostream>

using namespace std;
const int N = 1010;
int a[N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for(int i = 1;  i < n; i++) ans = max(ans, abs(a[i] - a[i-1]));
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 3227. 折点计数

语法题

#include <iostream>

using namespace std;

const int N = 1010;
int a[N];

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 1; i < n - 1; i++) {
        if(a[i] < a[i-1] && a[i] < a[i+1] || a[i] > a[i-1] && a[i] > a[i+1]) ans++;
    }
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 3257. 跳一跳

暴力模拟即可

#include <iostream>

using namespace std;

int main() {
    bool flag = true;
    int n;
    int last = 0, ans = 0;
    while(cin >> n, n) {
        if(n == 1) {
            last = 1;
            ans += 1;
        }else{
            if(flag || last == 1) {
                if(flag) flag = false;
                ans += 2;
                last = 2;
            }else{
                last += 2;
                ans += last;
            }
        }
    }
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 441. 数字统计

暴力枚举

#include <iostream>

using namespace std;
int l, r;

int main() {
    cin >> l >> r;
    int res = 0;
    for(int i = l; i <= r; i++) 
        for(int j = i; j; j /= 10)
            if(j % 10 == 2) res++;
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

不相交可以转化最长上升子序列问题

#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 5e3 + 10;
PII a[N];
int f[N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    sort(a, a + n);
    int ans = 0;
    for(int i = 0; i < n; i++) {
        f[i] = 1;
        for(int j = 0; j < i; j++) if(a[j].second < a[i].second) f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}