第299场

判断矩阵是否是一个 X 矩阵

class Solution {
    
public:
    bool checkXMatrix(vector<vector<int>>& grid) {
    
        int n=grid[0].size();
        for(int i=0;i<n;i++)
        {
    
            for(int j=0;j<n;j++)
            {
    
                if((i==j||n-1-i==j)&&grid[i][j]==0) return false;
                else if(i!=j&&n-1-i!=j&&grid[i][j]!=0) return false;
            }
        }
        return true;
    }
};

统计放置房子的方式数

动态规划 状态转移方程递推

class Solution {
    
const int MOD=1e9+7;
public:
    int countHousePlacements(int n) {
    
        vector<long long>dp(n+1);
        dp[1]=2;
        if(n==1) 
        {
    
            return dp[n]*dp[n];
        }
        dp[2]=3;
      
        if(n==2)
        {
    
            return dp[n]*dp[n];
        }
        for(int i=3;i<=n;i++)
        {
    
            dp[i]=(dp[i-1]+dp[i-2])%MOD;
        }

        return dp[n]*dp[n]%MOD;
    }
};

拼接数组的最大分数

class Solution {
    
public:
    int work(vector<int>&a,vector<int>&b)
    {
    
        int sum=0;
        for(auto&x:a) sum+=x;

        int dt=0,f=0;
        for(int i=0;i<b.size();i++)
        {
    
            f=max(f,0)+b[i]-a[i];
            dt=max(dt,f);
        }
        return sum+dt;
    }
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
    
        return max(work(nums1,nums2),work(nums2,nums1));
    }
};

从树中删除边的最小分数

const int N = 1010, M = N * 2;

int h[N], e[M], ne[M], idx;

class Solution {
    
public:
    int ans = 1e9;
    vector<int> w;

    void add(int a, int b) {
    
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }

    int dfs(int u, int fa, int sumx, int sumy) {
    
        int res = w[u];
        for (int i = h[u]; i != -1; i = ne[i]) {
    
            int j = e[i];
            if (j == fa) continue;
            int t = dfs(j, u, sumx, sumy);
            res ^= t;
            if (sumx != -1) {
    
                int a[3] = {
    sumy, t, sumx ^ t};
                sort(a, a + 3);
                ans = min(ans, a[2] - a[0]);
            }
        }
        return res;
    }

    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
    
        int n = nums.size();
        w = nums;
        for (int i = 0; i < n - 1; i ++ ) {
    
            memset(h, -1, n * 4);
            idx = 0;
            for (int j = 0; j < n - 1; j ++ ) {
    
                if (i != j) {
    
                    int a = edges[j][0], b = edges[j][1];
                    add(a, b), add(b, a);
                }
            }
            int x = edges[i][0], y = edges[i][1];
            int sumx = dfs(x, -1, -1, -1), sumy = dfs(y, -1, -1, -1);
            dfs(x, -1, sumx, sumy);
            dfs(y, -1, sumy, sumx);
        }

        return ans;
    }
};