Check if Matrix Is X-Matrix

Easy problem. Iterate all the element a[i][j] of matrix, determine:

  • if i == j or i + j == n - 1: this element should be non-zero
  • otherwise: this element should be zero
class Solution {
public:
    bool checkXMatrix(vector<vector<int>>& grid) {
        bool flag = true;
        int n = grid.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i + j == n - 1) {
                    if (grid[i][j] == 0) flag = false;
                } else {
                    if (grid[i][j] > 0) flag = false;
                }
            }
        }
        return flag;
    }
};

Count Number of Ways to Place Houses

We can use dynamic programming to solve this problem. Let f[i][0] represent the number of legal binary digitals end with zero, and f[i][1] represents the number of legal binary digitals end with one.

f[i][0] = f[i - 1][0] + f[i - 1][1]
f[i][1] = f[i - 1][0]

f[n][0] + f[n][1] is the final answer. We should module the result by 1e9+7 while adding numbers.

class Solution {
public:
    int countHousePlacements(int n) {
        int mod = 1000000007;
        int f[10001][2] = {0};
        f[0][0]  = 1;
        for (int i = 1; i <= n; i++) {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            f[i][1] = f[i - 1][0];
        }
        long long x = f[n][0] + f[n][1];
        x = (x * x) % mod;
        return x;
    }
};

Maximum Score Of Spliced Array

We can transform this statement into the maximum subarray sum problem. Assume we select the first array as the final maximum result. Then, We subtract all the elements in the second array by each element in the first array. For example:

nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
after subtract:
nums2_sub = [30, -20, 30, 40, -10]

Then, we use dynamic programming to calculate the maximum subarray sum of the array nums2_sub. The sum of each element in num1adding with the maximum subarray sum of nums2_sub named ans2, is one possible answer. We calculate ans1 with the same method.

class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int a[100001], n = min(nums1.size(), nums2.size());
        for (int i = 0; i < n; i++) a[i] = nums1[i] - nums2[i];
        int now = 0, a1 = 0;
        for (int i = 0; i < n; i++) {
            if (now + a[i] >= 0) now += a[i];
            else now = 0;
            a1 = max(a1, now);
        }
        for (int i = 0; i < n; i++) a[i] = nums2[i] - nums1[i];
        int a2 = 0;
        now = 0;
        for (int i = 0; i < n; i++) {
            if (now + a[i] >= 0) now += a[i];
            else now = 0;
            a2 = max(a2, now);
        }
        for (int i = 0; i < nums1.size(); i++) {
            a2 += nums1[i];
        }
        for (int i = 0; i < nums2.size(); i++) {
            a1 += nums2[i];
        }
        return max(a1, a2);
    }
};

Minimum Score After Removals on a Tree

We treat node 0 as the root of the tree. Then, we can calculate the xor sum of each subtree s[i]. Each node pair (x, y) is divided into the following three conditions:

  • x is an ancestor of y: the result is the min difference of s[x] ^ s[y], s[y], s[0] ^ s[x];
  • y is an ancestor of x: the result is the min difference of s[x], s[y] ^ s[x], s[0] ^ s[y];
  • otherwise: the result is the min difference of s[x], s[y], s[0] ^ s[x] ^ s[y].

We can use dfs to initialize the node pairs’ ancestor relationship.

struct edge {
    int v, next, t;
} e[100000];
int p[10000], eid, ans = 2e9, a[10000];
bool g[1000][1000];
void insert(int x, int y) {
    e[eid].v = y;
    e[eid].next = p[x];
    p[x] = eid++;
}
int s[1001];
void insert2(int x, int y) {
    insert(x, y);
    insert(y, x);
}
void dfs(int now, int fa) {
    s[now] ^= a[now];
    for (int i = p[now]; ~i; i = e[i].next) {
        if (e[i].v != fa) {
            dfs(e[i].v, now);
            s[now] ^= s[e[i].v];
            e[i].t = 1;
        }
    }
}
int diff(int x, int y, int z) {
    int s[3] = {x, y, z};
    sort(s, s + 3);
    return s[2] - s[0];
}
void go1(int x, int now) {
    g[x][now] = 1;
    for (int i = p[now]; ~i; i = e[i].next) {
        if (e[i].t) {
            go1(x, e[i].v);
        }
    }
}
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        memset(p, -1, sizeof(p));
        memset(s, 0, sizeof(s));
        memset(g, 0, sizeof(g));
        memset(e, 0, sizeof(e));
        eid = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            a[i] = nums[i];
        }
        for (int i = 0; i < edges.size(); i++) {
            insert2(edges[i][0], edges[i][1]);
        }
        ans = 2e9;
        dfs(0, -1);
        for (int i = 0; i < n; i++) {
            go1(i, i);
        }
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (g[i][j]) {
                    ans = min(ans, diff(s[i] ^ s[j], s[j], s[0] ^ s[i]));
                } else if (g[j][i]) {
                    ans = min(ans, diff(s[j] ^ s[i], s[i], s[0] ^ s[j]));
                } else {
                    ans = min(ans, diff(s[i], s[j], s[0] ^ s[i] ^ s[j]));
                }
            }
        }
        return ans;
    }
};