title: 20220622leetcode周赛（前3道）
第一题，难度：简单
题目描述：
如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：
矩阵对角线上的所有元素都 不是 0
矩阵中所有其他元素都是 0
给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。
示例 1：
输入：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
输出：true
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 是一个 X 矩阵。
示例 2：
输入：grid = [[5,7,0],[0,3,1],[0,5,0]]
输出：false
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 不是一个 X 矩阵。
提示：
n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 10^5
代码如下：
bool checkXMatrix(int** grid, int gridSize, int* gridColSize){
int col = gridColSize[0];
int i, j;
for (i = 0; i < gridSize; ++i) {
for (j = 0; j < col; ++j) {
if (i == j || j == gridSize - 1 - i) {
if (grid[i][j] == 0) {
return false;
}
} else {
if (grid[i][j] != 0) {
return false;
}
}
}
}
return true;
}
第二题，难度：中等
题目描述：
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：
输入：n = 1
输出：4
解释：
可能的放置方式：
- 所有地块都不放置房子。
- 一所房子放在街道的某一侧。
- 一所房子放在街道的另一侧。
- 放置两所房子，街道两侧各放置一所。
示例 2：
输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。
提示：
1 <= n <= 10^4
思路如下：
一侧房子的放置不影响另一侧房子的放置情况，所以先单独看其中一侧房子的放置方案。
dp[n]表示前n块地房子的放置方案数。
第n块地有两种放置方案，放房子或者不放房子：
不放房子的话，和dp[n-1]方案数一致；
放房子的话，第n-1块地一定是不放房子的（确定的），则和dp[n-2]方案数一致。
dp[n] = dp[n-1] + dp[n-2]
dp[0] = 1, 空也是一种放置方案
dp[1] = 2, 放置房子或者不放置房子
在一侧的dp[n]中选择其中一种方案，另一侧仍然是dp[n]种方案
所以总方案数是：dp[n] * dp[n]
代码如下：
#define MOD 1000000007
int countHousePlacements(int n){
long *dp = (long *)malloc(sizeof(long) * (n + 2));
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n + 2; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
return (int)(dp[n] * dp[n] % MOD);
}
第三题，难度：困难
题目描述：
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。
你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。
例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。
你可以选择执行上述操作 一次 或不执行任何操作。
数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。
返回 可能的最大分数 。
子数组 是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。
示例 1：
输入：nums1 = [60,60,60], nums2 = [10,90,10]
输出：210
解释：选择 left = 1 和 right = 1 ，得到 nums1 = [60,90,60] 和 nums2 = [10,60,10] 。
分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210 。
示例 2：
输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
输出：220
解释：选择 left = 3 和 right = 4 ，得到 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30] 。
分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220 。
示例 3：
输入：nums1 = [7,11,13], nums2 = [1,1,1]
输出：31
解释：选择不交换任何子数组。
分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31 。
提示：
n == nums1.length == nums2.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= 10^4
思路如下：
可以参考最长子序列和的题目
先求出nums1和nums2数组的和，以及两数组相同下标数的差值
sub数组表示nums1数组 - nums2数组的差值
然后对sbu数组中的正数求最大子序列和，对sub数组中的负数求最小子序列和
最后返回（sum1-最小子序列和，sum2+最大子序列和）两者的最大值
代码如下：
#define MIN_NUM 0
#define MAX_NUM 10000
#define MAX_LENGTH 100000
int maximumsSplicedArray(int* nums1, int nums1Size, int* nums2, int nums2Size){
int sub[MAX_LENGTH] = { 0 };
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < nums1Size; ++i) {
sub[i] = nums1[i] - nums2[i];
sum1 += nums1[i];
sum2 += nums2[i];
}
int s1 = 0;
int s1Max = MIN_NUM;
int s2 = 0;
int s2Min = MAX_NUM;
for (int i = 0; i < nums1Size; ++i) {
s1 = s1 < 0 ? sub[i] : s1 + sub[i];
s1Max = s1 > s1Max ? s1 : s1Max;
s2 = s2 > 0 ? sub[i] : s2 + sub[i];
s2Min = s2 < s2Min ? s2 : s2Min;
}
return sum1 - s2Min > sum2 + s1Max ? sum1 - s2Min : sum2 +s1Max;
}