第102场双周赛

class Solution {
public:
    vector<int> findColumnWidth(vector<vector<int>>& grid) {
        vector<int> res;
        int m = grid.size(); int n = grid[0].size();
        for(int j=0;j<n;j++){
            int len = 0;
            for(int i=0;i<m;i++){
            len = max(len,judge(grid[i][j]));
        }
            res.push_back(len);
        }
        return res;
    }
    int judge(int num){
        int len = 0;
        if(num==0) {return 1;}
        if(num<0){len++;num=-1*num;}
        while(num!=0){
            num/=10;
            len++;
        }
        return len;
    }
};

class Solution {
public:
    vector<long long> findPrefixScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> premax(n);
        vector<long long> convert(n);
        int cur = INT_MIN;
        for(int i=0;i<n;i++){
            if(nums[i]>cur)
                cur = nums[i];
            premax[i]=cur;
            convert[i] = nums[i]+premax[i];
        }
        for(int i=1;i<n;i++)
            convert[i] = convert[i-1]+convert[i];
        return convert;
    }
};

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        if(!root) return root;
        queue<TreeNode*> q;
        q.push(root);
        vector<int> cursum;
        while(!q.empty()){
            int sum =0;//当前层的和
            int n = q.size();
            for(int i=0;i<n;i++){
                TreeNode* temp = q.front();
                q.pop();
                if(temp==nullptr) continue;
                sum+= temp->val;
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            } 
            cursum.push_back(sum);
    }
         visit(root,0,cursum,root->val);
         return root;
    }
        void visit(TreeNode* root,int deep,vector<int> &cursum,int sub){
            if(!root) return;
            int left = root->left?root->left->val:0;
            int right = root->right?root->right->val:0;
            
            root->val = cursum[deep]-sub;
            visit(root->left,deep+1,cursum,left+right);
            visit(root->right,deep+1,cursum,left+right);
            }
        
    
};

class Graph {
public:
    vector<vector<int>> graph;
    Graph(int n, vector<vector<int>>& edges) {
        graph.resize(n);
        for(auto &point:graph)
            point.resize(n,INT_MAX);//初始赋无穷远距离
        for(int i=0;i<edges.size();i++){
            int from = edges[i][0];
            int to = edges[i][1];
            int cost = edges[i][2];
            graph[from][to] = cost;
        }     
    }
    
    void addEdge(vector<int> edge) {
            int from = edge[0];
            int to = edge[1];
            int cost = edge[2];
            graph[from][to] = cost;
    }
    
    int shortestPath(int node1, int node2) {
        if(node1==node2) return 0;
        int n =graph.size();
        vector<int> dis(n);//记录到各点的距离
        vector<bool> mark(n);//标记访问情况
        mark[node1] = true;//加入源点
        for(int i=0;i<n;i++)
            dis[i] = graph[node1][i];//初始化源点到各点距离
        
        for(int count=1;count<n;count++){//更新n-1次
            int minpath = INT_MAX;//记录最小距离
            int nextpoint = -1;//下一个邻近节点
            for(int i=0;i<n;i++)//贪心找下一个最近节点
            {
                if(mark[i]==0&&dis[i]<minpath){
                    minpath = dis[i];
                    nextpoint = i;
                }
            }
            if(nextpoint==node2) return dis[node2];
            //如果没有下一个邻近节点
            if(nextpoint==-1) return -1;
            
            mark[nextpoint] = true;//将节点加入访问集合
            for(int i=0;i<n;i++){//根据新加入的节点更新所有节点离源点的距离
                if(graph[nextpoint][i]<INT_MAX&&mark[i]==false){//该点到新加入节点有边
                    if(dis[i]>dis[nextpoint]+graph[nextpoint][i])
                        dis[i]=dis[nextpoint]+graph[nextpoint][i];//更新该点到源点距离
                    }
                }
    
        }
        return dis[node2]==INT_MAX?-1:dis[node2];
    }
};