Leetcode week 299

6101. Judge whether the matrix is a X matrix

If a square matrix satisfies the following All Conditions , It is called a X matrix ：

All the elements on the diagonal of the matrix are No 0
All other elements in the matrix are 0
Give you a size of n x n A two-dimensional array of integers grid , Represents a square matrix . If grid It's a X matrix , return true ; otherwise , return false .

Example 1：

Input ：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
Output ：true
explain ： The matrix is shown in the figure above .
X The matrix should satisfy ： Green elements （ On the diagonal ） Are not 0 , Red elements are 0 .
therefore ,grid It's a X matrix .

Example 2：

Input ：grid = [[5,7,0],[0,3,1],[0,5,0]]
Output ：false
explain ： The matrix is shown in the figure above .
X The matrix should satisfy ： Green elements （ On the diagonal ） Are not 0 , Red elements are 0 .
therefore ,grid Is not a X matrix .

Tips ：

n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 105

Simulation question

Go through it , Determine whether the two diagonal elements are not 0, Whether other elements are all 0
The main diagonal ：i == j

Sub diagonal ：i + j == n - 1( Because the subscript is from 0 At the beginning )

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

6100. Count the number of ways to place the house

There are... In one street n * 2 individual Plot , On each side of the street n Lots of land . The plots on each side are arranged from 1 To n Number . A house can be placed on each plot .

It is required that two houses on the same side of the street should not be adjacent , Please calculate and return the number of ways to place houses . Because the answer can be big , Need to be right 109 + 7 Take the remainder and return to .

Be careful , If a house is placed on the third floor on one side of the street i Lots of land , Does not affect the second... On the other side i A plot of land to place a house .

Example 1：

Input ：n = 1
Output ：4
explain ：
Possible placement ：

1. No houses are placed on all plots .
2. A house is on one side of the street .
3. A house is on the other side of the street .
4. Put two houses , One on each side of the street .

Example 2：

Input ：n = 2
Output ：9
explain ： As shown in the figure above , share 9 There are two possible ways to place .

Tips ：

1 <= n <= 104

Dynamic programming

It can be seen from the meaning of the question , The upper and lower sides do not affect each other , So we just need to figure out one side , Then square it .
use 0 It means that there is no house in this position , use 1 Indicates that a house is placed at this location .
dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
dp[i][1] = dp[i - 1][0];
When there is no house in this position , There can be a house in the previous position , Or there can be no house
When the house is placed in this position , The previous position can only be one without a house .

The final result is the square of the sum of the two
Remember to add , Sum of the square mod once .
And to prevent explosion int, You can drive long long

class Solution {
    
public:
//  There is no conflict between the upper and lower sides , You can just count one side , Find the square 
    long long dp[10005][2];
    const int mod = 1e9 + 7;
    int countHousePlacements(int n) {
    
        dp[1][0] = 1;
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++) {
    
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            dp[i][1] = dp[i - 1][0] % mod;
        }
        long long t = dp[n][0] + dp[n][1];
        t = t * t % mod;
        return t;
    }
};

Looking for a regular

I didn't understand the questions very well during the competition ,n = 3 The enumeration is wrong , Lead to wa 了 ,wa After two times , There is a prompt for Li Kou , You can know which data you are in wa Of , What should be output , I know n = 5 when , The result is 169, yes 13 The square of , Think of the Fibonacci sequence , That's how the problem came out
from n = 3 Start
s[n] = s[n - 1] + s[n - 2], And initialize s[1] = 2, s[2] = 3
Output after the calculation Square is enough

class Solution {
    
public:
    const int mod = 1e9 + 7;
    long long s[10005];
    int countHousePlacements(int n) {
    
        long long t = 0;
        s[1] = 2;
        s[2] = 3;
        for (int i = 3; i <= n; i++) {
    
            s[i] = s[i - 1] + s[i - 2];
            s[i] %= mod;
        }
        t = s[n] * s[n] % mod;
        int res = t;
        return res;
    }
};

5229. The maximum score of a concatenated array

Give you two subscripts from 0 The starting array of integers nums1 and nums2 , All the lengths are n .

You can choose two integers left and right , among 0 <= left <= right < n , next In exchange for Two subarrays nums1[left…right] and nums2[left…right] .

for example , set up nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] , Integer selection left = 1 and right = 2, that nums1 Will turn into [1,12,13,4,5] and nums2 Will turn into [11,2,3,14,15] .
You can choose to do the above once Or do nothing .

Array of fraction take sum(nums1) and sum(nums2) Maximum of , among sum(arr) It's an array arr The sum of all the elements in .

return Maximum possible score .

Subarray Is a sequence of consecutive elements in an array .arr[left…right] Indicates that the subarray contains nums Middle subscript left and right Between the elements （ contain Subscript left and right The corresponding element ）.

Example 1：

Input ：nums1 = [60,60,60], nums2 = [10,90,10]
Output ：210
explain ： choice left = 1 and right = 1 , obtain nums1 = [60,90,60] and nums2 = [10,60,10] .
The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210 .

Example 2：

Input ：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
Output ：220
explain ： choice left = 3 and right = 4 , obtain nums1 = [20,40,20,40,20] and nums2 = [50,20,50,70,30] .
The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220 .

Example 3：

Input ：nums1 = [7,11,13], nums2 = [1,1,1]
Output ：31
explain ： Choose not to swap any subarrays .
The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31 .

Tips ：

n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 104

Maximal continuous suborder sum

The general idea is the sum of maximal continuous subsequences , It is just the sum of the largest continuous sub columns for the difference between the corresponding position values of two arrays .
The last largest sum = a Array and sum + c The maximum continuous suborder sum of
You can write greedily when you ask , It's fine too dp Push it out .
The maximum continuous subsequence sum of the current position is to see The maximum continuous suborder sum of the previous position Is it greater than 0, If it is greater than, add the current value , Otherwise, it is the current value

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