头像




离线:22小时前


最近来访(94)
用户头像
kulukulu二十代
用户头像
__007
用户头像
小雪菜本大菜
用户头像
人民有信仰国家有力量
用户头像
桂花煮柚子
用户头像
鳕鱼饭
用户头像
1013308992
用户头像
Acwer
用户头像
beautifulworld
用户头像
zz想ac
用户头像
白塔
用户头像
阿骨打
用户头像
WAWA鱼
用户头像
Lionel1999
用户头像
PRC
用户头像
为菈妮
用户头像
Payxtl
用户头像
点典_4
用户头像
jiudaozheliba
用户头像
迷人的源



9天前
使用双向图,以任意结点为根节点来进行一次dfs。
在dfs过程中,求出以子节点和父亲节点为根的 树的结点数,其中父亲节点为 n - cnt(子节点)
#include <iostream>
#include <string.h>

using namespace std;
const int N = 1e5+5;
int h[N], e[N * 2], ne[N * 2];
bool visit[N];
int idx;
int n;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int res = 1e9;
int dfs(int u){//结点数

    int cnt = 1;
    int ans = 0;
    //visit[u] = true;//设置已访问
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(visit[j]) continue;
        visit[j] = true;
        int tmp = dfs(j);//没必要恢复现场。若恢复 相当于再重复计算一次父亲节点数
        cnt += tmp;
        ans = max(ans, tmp);
    }
    ans = max(ans, n - cnt);//父亲节点肯定是一整个联通块(只能有一个父亲)
    /*
    举个栗子,假设主函数调用的是dfs(1),按照上面那个图,会以1这个点通过for来遍历邻接点,
    会有s=dfs(2),s=dfs(4),s=dfs(7),你可以求出以1为重心的所有连通块的最大值,但是我刚才
    写的有一个s=dfs(2),你在dfs(2)的时候只能求出来2的所有未被访问的邻接点,也就是只能求
    出来dfs(5)和dfs(8),求不出来以1为根的这个联通块的数量,这时候就只能通过总结点数n减
    去以2为根节点的数量来求出,也就是n-sum,然后在取一个max(n-sum,res),就是以2为重心的
    最大连通块数量,这个难就难想在他是通过以一个点为起点开始递归,在递归的过程中求出res,
    再用res来更新ans,yxctql!
    */
    //对于首次遍历的节点来说是没必要的;但对后续的子节点dfs时由于已经过滤掉其父节点了,
    //for循环中就不能获取到以父节点为根的子树,这种情况就需要max(n-sum,res)来保证
    res = min(res, ans);
    return cnt;
}

int main(){

    cin>>n;

    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin>>a>>b;
        add(a, b);
        add(b, a);
    }

    visit[2] = true;
    dfs(2);
    cout<<res;
    return 0;
}




11天前
#include <iostream>

using namespace std;

const int N = 1005 * 32, V = 2005;

int v[N], w[N], s[N];
int f[V];

int main(){
    int n, m;
    cin>>n>>m;


    int cnt = 0;
    for(int i = 0; i < n; i ++){//这里不是将其转为二进制
                                //而是转为1,2,4,8等的堆,这些堆任意组合可以组成1~c中的任何数
        int a, b, c;

        cin>>a>>b>>c;
        int k = 1;

        while(k <= c){
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            c -= k;
            k *= 2;

        }
        if(c > 0){
            cnt ++;
            v[cnt] = a * c;
            w[cnt] = b * c;
        }
    }

    //01
    for(int i = 1; i <= cnt; i ++){
        for(int j = m; j >= v[i]; j --){
            // f[i][j] = f[i - 1][j];
            // if(j >= v[i])
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout<<f[m];
    return 0;
}




17天前
1. 非递归版本
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr) return res;

        vector<int> path;
        queue<TreeNode*> que;
        que.push(root);

        while(que.size()){
            int len = que.size();

            for(int i = 0; i < len; i ++){
                auto tmp = que.front();
                que.pop();
                path.push_back(tmp->val);
                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
            }
            res.push_back(path);
            path.clear();
        }
        return res;
    }
};




1个月前
1. spfa
const int inf = 0x3f3f3f3f;
class Solution {
public:
    struct Node{
        int x, y, d;
         bool operator< (const Node& b){
             return d < b.d;
         }
    };
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    //转化为求最短路问题
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        queue<Node> que;
        vector<vector<int>> dist(n + 5, vector<int>(m + 5, inf));
        vector<vector<bool>> st(n + 5, vector<bool>(m + 5));//记录que中的元素
        que.push({0, 0, 0});
        dist[0][0] = 0;
        st[0][0] = true;
        while(que.size()){
            auto tmp = que.front();
            que.pop();
            st[tmp.x][tmp.y] = false;

            for(int i = 0; i < 4; i ++){
                int s = tmp.x + dx[i], t = tmp.y + dy[i];
                if(s < 0 || t < 0 || s >= n || t >= m) continue;

                if(dist[s][t] > dist[tmp.x][tmp.y] + grid[s][t]){
                    dist[s][t] = dist[tmp.x][tmp.y] + grid[s][t];
                    if(! st[s][t]){
                        que.push({s, t, dist[tmp.x][tmp.y] + grid[s][t]});
                        st[s][t] = true;
                    }


                }
            }

        }
        return dist[n - 1][m - 1];
    }
};
2. dijkstra
const int inf = 0x3f3f3f3f;
class Solution {
public:
    struct Node{
        int x, y, d;
         bool operator > (const Node& b) const{
             return d > b.d;
         }
    };
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    //转化为求最短路问题
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        //dijk
        priority_queue<Node, vector<Node>, greater<Node>> pque;
        vector<vector<int>> dist(n + 5, vector<int>(m + 5, inf));
        vector<vector<bool>> st(n + 5, vector<bool>(m + 5));//记录已经计算完毕的元素

        pque.push({0, 0, 0});
        dist[0][0] = 0;
        while(pque.size()){
            auto tmp = pque.top();
            pque.pop();

            if(st[tmp.x][tmp.y]) continue;

            st[tmp.x][tmp.y] = true;
            for(int i = 0; i < 4; i ++){
                int s = tmp.x + dx[i], t = tmp.y + dy[i];
                if(s < 0 || t < 0 || s >= n || t >= m) continue;
                if(dist[s][t] > dist[tmp.x][tmp.y] + grid[s][t]){
                    dist[s][t] = min(dist[s][t], dist[tmp.x][tmp.y] + grid[s][t]);
                    pque.push({s, t, dist[s][t]});
                }

            }   
        }
        return dist[n - 1][m - 1];
    }
};




1个月前
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        //首先放最大频率的元素,每行空位个数为n + 1,总行数为maxn
        //每行依次放元素
        //A B D
        //A B D
        //... 
        //A B
        //所以长度为(maxn - 1) * (n + 1) + k,这是有空位的情况
        //
        //考虑 1.频率为maxn的元素个数k大于n + 1时;2.剩余字母怎么排
        //第一种情况直接在矩阵后增加列
        //第二种剩余字母,直接在空位自上到下排;若空位不够,往后增加列(需要多少增加多少,不一定增加整条列,这种情况会没有空位!所以这种情况长度一定等于字母总量!)
        //所以综上,res等于max(有空位,无空位),无空位情况也就是数组的长度

        unordered_map<char, int> hash;
        int maxn = 0, cnt = 0;
        for(auto c: tasks) {
            hash[c] ++;
            maxn = max(maxn, hash[c]);
        }
        for(auto [k, v]: hash){
            if(v == maxn) cnt ++;
        }
        int res = max((maxn - 1) * (n + 1) + cnt, (int)tasks.size());
        return res;
    }
};




1个月前
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        //单调栈
        stack<int> sta;

        for(int i = n - 1; i >= 0; i --){
            //维护一个单调递减的栈
            while(sta.size() && temperatures[sta.top()] <= temperatures[i]) sta.pop();//栈中小于等于ti的永远不会再输出
            if(sta.size())
                ans[i] = sta.top() - i;
            sta.push(i);

        }
        return ans;
    }
};




1个月前
class Solution {
public:
//将数组分为三个区间    
    //左侧区间满足条件:1. 递增 2. 左边最后一个元素小于右边区间的最小值
    //先满足第一个条件,再将l向左移动(使左边区间满足条件2)
    //同理,处理r
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        //先将l和r移动到区间满足条件1的位置
        while(l + 1 < n && nums[l] <= nums[l + 1]) l ++;
        if(l == n - 1) return 0;
        while(r - 1 >= 0 && nums[r] >= nums[r - 1]) r --;

        //移动l
        for(int i = l + 1; i < n; i ++){
            while(l >= 0 && nums[l] > nums[i]) l --;
        }
        //移动r
        for(int i = r - 1; i >= 0; i --){
            while(r < n && nums[r] < nums[i]) r ++;
        }

        return r - l - 1;//l 和 r分别为左区间的最右,右区间的最左,所以中间区间大小为r-l-1
    }   
};




1个月前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->right);//中序遍历,先遍历右子树,保证大于当前节点的已经遍历完!
        sum += root->val;
        root->val = sum;
        dfs(root->left);
    }
};




1个月前
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        //对于元素numsi,将其对应的下标取反(真正的值可以取绝对值)
        //最终大于0的元素,其下标值为消失的数字
        for(auto x: nums){
            int tmp = abs(x) - 1;
            if(nums[tmp] > 0)
                nums[tmp] *= -1;
        }
        vector<int> res;
        for(int i = 0; i < nums.size(); i ++){
            if(nums[i] > 0) res.push_back(i + 1);
        }
        return res;
    }
};




1个月前
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        //使用绝对值,
        //每次将元 素值对应的下标 的 元素 取反
        vector<int> res;
        for(auto c: nums){
            int tmp = abs(c) - 1;// -1因为nums从0开始
            nums[tmp] *= -1;
            if(nums[tmp] > 0) res.push_back(abs(c));//大于0说明对nums[tmp]取反了两次,即c重复
        }
        return res;
    }
};