头像

_wyp_




在线 


最近来访(16)
用户头像
格子格子
用户头像
RyanMoriarty
用户头像
Pscode
用户头像
Heebiejeebies
用户头像
matt
用户头像
小宋
用户头像
tongfs
用户头像
Quinn
用户头像
Dinas
用户头像
朴小明
用户头像
苦逼的生活
用户头像
填海难....填心更难
用户头像
minnn
用户头像
zdkk
用户头像
夏语聪

活动打卡代码 LeetCode 216. 组合总和 III

_wyp_
10小时前
class Solution {
public:
    bool vis[10];
    vector<int> path;
    vector<vector<int>> res;
    void dfs(int u, int k, int n) {
        if(n < 0) return;
        if(!k && !n) {
            res.push_back(path);
            return;
        }
        for(int i = u; i <= 9; i++)
            if(!vis[i]) {
                path.push_back(i);
                vis[i] = true;
                dfs(i, k - 1, n - i);
                vis[i] = false;
                path.pop_back();
            }
        return;
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        // 当前搜索的数字 共k个数字 和为n
        dfs(1, k, n);
        return res;
    }
};



_wyp_
10小时前
// STL
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};
// 基于快排的选择排序
class Solution {
public:
    int dfs(vector<int>& nums, int l, int r, int k) {
        if(l >= r) return nums[k];
        int x = nums[l + r >> 1],i = l - 1, j = r + 1;
        while(i < j) {
            do i++; while(nums[i] > x);
            do j--; while(nums[j] < x);
            if(i < j) swap(nums[i], nums[j]);
        }
        if(k <= j) return dfs(nums, l, j, k);
        return dfs(nums, j + 1, r, k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        return dfs(nums, 0, nums.size() - 1, k - 1);
    }
};


活动打卡代码 LeetCode 213. 打家劫舍 II

_wyp_
10小时前
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        vector<int> f(n + 5, 0);
        // 由于首尾不能同时偷窃 因此根据是否偷第一家 分为两种情况
        // 偷第一家 则范围 1 ~ n - 1
        f[1] = nums[0];
        for(int i = 2; i <= n - 1; i++) {
            // 偷第i家
            f[i] = nums[i - 1] + f[i - 2];
            // 不偷第i家
            for(int j = 1; j < i; j++)
                f[i] = max(f[i], f[j]);
        }
        int L = f[n - 1];
        // 不偷第一家 则范围 2 ~ n
        f = vector<int>(n + 5, 0);
        f[2] = nums[1];
        for(int i = 3; i <= n; i++) {
            // 偷第i家
            f[i] = nums[i - 1] + f[i - 2];
            // 不偷第i家
            for(int j = 2; j < i; j++)
                f[i] = max(f[i], f[j]);
        }
        int R = f[n];
        return max(L, R);
    }
};



_wyp_
11小时前
class WordDictionary {
public:
    struct Node {
        bool is_end;
        Node* son[26];
        Node() {
            is_end = false;
            for(int i = 0; i < 26; i++) son[i] = NULL;
        }
    }*root;

    WordDictionary() {
        root = new Node();
    }

    void addWord(string word) {
        auto p = root;
        for(auto c : word) {
            int u = c - 'a';
            if(!p -> son[u]) p -> son[u] = new Node();
            p = p -> son[u];
        }
        p -> is_end = true;
        return;
    }

    bool search(string word) {
        return dfs(root, word, 0);
    }

    bool dfs(Node* p, string word, int i) {
        if(i == word.size()) return p -> is_end;
        if(word[i] != '.') {
            int u = word[i] - 'a';
            if(!p -> son[u]) return false;
            return dfs(p -> son[u], word, i + 1);
        }
        else {
            for(int j = 0; j < 26; j++)
                if(p -> son[j] && dfs(p -> son[j], word, i + 1)) return true;
            return false;
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */


活动打卡代码 LeetCode 210. 课程表 II

_wyp_
1天前
class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& edges) {
        vector<int> d(n + 5);
        vector<vector<int>> g(n + 5);
        queue<int> q;
        for(auto edge : edges) {
            int a = edge[0], b = edge[1];
            g[b].push_back(a);
            d[a]++;
        }
        // 找源点
        for(int i = 0; i < n; i++)
            if(!d[i]) q.push(i);
        vector<int> res;
        int n_course = 0;
        // top_sort排序
        while(q.size()) {
            auto ft = q.front(); q.pop();
            n_course++;
            res.push_back(ft);
            for(int i = 0; i < g[ft].size(); i++) {
                d[g[ft][i]]--;
                if(d[g[ft][i]] == 0)
                    q.push(g[ft][i]);
            }
        }
        if(n_course != n) res = {};
        return res;
    }
};



_wyp_
1天前
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for(int i = n; i >= 1; i--)
        for(int j = 0; j <= m; j++) {
            f[i][j] = f[i + 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    int j = m;
    for(int i = 1; i <= n; i++)
        if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << " ";
            j -= v[i];
        }
    return 0;
}



_wyp_
1天前
// 暴力
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        for(int i = 0, j = 0; i < nums.size(); i++) {
            int s_tp = 0;
            j = i;
            while(j < nums.size()) {
                s_tp += nums[j++];
                if(s_tp >= target) {
                    res = min(res, j - i);
                    break;
                }
            }
        }
        if(res == INT_MAX) res = 0;
        return res;
    }
};
// 滑动窗口
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        queue<int> q;
        int res = INT_MAX;
        int tp = 0;
        for(int i = 0; i < nums.size(); i++) {
            tp += nums[i];
            q.push(i);
            while(tp >= target) {
                res = min(res, i - q.front() + 1);
                tp -= nums[q.front()];
                q.pop();
            }
        }
        if(res == INT_MAX) res = 0;
        return res;
    }
};



_wyp_
1天前
class Trie {
public:
    int idx = 0;
    int trie[2010 * 30][30];
    bool sign[2010 * 30];
    Trie() {
        memset(trie, 0, sizeof trie);
        memset(sign, false, sizeof sign);
    }

    void insert(string word) {
        int rt = 0;
        for(int i = 0; i < word.size(); i++) {
            if(!trie[rt][word[i] - 'a'])
                trie[rt][word[i] - 'a'] = ++idx;
            rt = trie[rt][word[i] - 'a'];
        }
        sign[rt] = true;
        return;
    }

    bool search(string word) {
        int rt = 0;
        for(int i = 0; i < word.size(); i++) {
            if(!trie[rt][word[i] - 'a']) return false;
            rt = trie[rt][word[i] - 'a'];
        }
        return sign[rt];
    }

    bool startsWith(string prefix) {
        int rt = 0;
        for(int i = 0; i < prefix.size(); i++) {
            if(!trie[rt][prefix[i] - 'a']) return false;
            rt = trie[rt][prefix[i] - 'a'];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */


活动打卡代码 LeetCode 207. 课程表

_wyp_
1天前
class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& edges) {
        if(edges.empty()) return true;
        vector<vector<int>> g(n + 5);
        vector<int> d(n + 5);
        queue<int> q;
        for(auto edge : edges) {
            int a = edge[0], b = edge[1];
            g[b].push_back(a);
            d[a]++;
        }
        // 找源点
        for(int i = 0; i < n; i++)
            if(!d[i])
                q.push(i);
        int n_course = 0;
        // 拓扑排序
        while(q.size()) {
            int ft = q.front(); q.pop();
            n_course++;
            for(int i = 0; i < g[ft].size(); i++) {
                d[g[ft][i]]--;
                if(!d[g[ft][i]])
                    q.push(g[ft][i]);
            }
        }
        return n_course == n;
    }
};


活动打卡代码 AcWing 204. 计数质数

_wyp_
1天前
class Solution {
public:
    int countPrimes(int n) {
        // 第一步:筛质数
        vector<int> primes(n + 5);
        vector<int> vis(n + 5);
        int k = 0;
        for(int i = 2;i < n;i++) {
            if(!vis[i]) primes[k++] = i;
            // 不能写成primes[j] < n / i,会出错
            // 例如:3 * 3 < 10 但是 3 < 10 / 3吗?
            for(int j = 0;i * primes[j] < n;j++) { // 枚举所有质数
                vis[i * primes[j]] = true;
                if(i % primes[j] == 0) break;
            }
        }
        return k;
    }
};