leetcode

Leetcode -561.数组拆分

题目：给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如(a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例 1：
输入：nums = [1, 4, 3, 2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：

1. (1, 4), (2, 3)->min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4)->min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4)->min(1, 2) + min(3, 4) = 1 + 3 = 4
   所以最大总和为 4

示例 2：
输入：nums = [6, 2, 6, 5, 1, 2]
输出：9
解释：最优的分法为(2, 1), (2, 5), (6, 6).min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

思路是先升序排序，再比较相邻两项的较小值，累加到ans中，最后返回ans即可；

		//取较小值
		int minnum(int num1, int num2)
		{
		    return num1 < num2 ? num1 : num2;
		}
		
		int compare(void* p1, void* p2)
		{
		    return *(int*)p1 - *(int*)p2;
		}
		
		int arrayPairSum(int* nums, int numsSize)
		{
		    //升序排序
		    qsort(nums, numsSize, sizeof(int), compare);
		    int ans = 0;
		
		    //从倒数第二项开始，比较此项与后一项的最小值，取最小值累加到ans
		    for (int i = numsSize - 2; i >= 0; i -= 2)
		    {
		        ans += minnum(nums[i], nums[i + 1]);
		    }
		    return ans;
		}

Leetcode -566.重塑矩阵

题目：在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1：
输入：mat = [[1, 2], [3, 4]], r = 1, c = 4
输出： [[1, 2, 3, 4]]

示例 2：
输入：mat = [[1, 2], [3, 4]], r = 2, c = 4
输出： [[1, 2], [3, 4]]

思路是将这个二维数组映射成一个一维数组再将这个一维数组映射回 r 行 c 列的二维数组返回，具体步骤参考以下代码以及注释；

		int** matrixReshape(int** mat, int matSize, int* matColSize, int r, int c, int* returnSize, int** returnColumnSizes)
		{
		    //要求重塑的行和列的乘积大于原数组的行列乘积，无法重塑
		    if (r * c != matSize * matColSize[0])
		    {
		        *returnSize = matSize;
		        *returnColumnSizes = matColSize;
		        return mat;
		    }
		
		    //返回的二级指针，返回的行是r
		    //返回的列是个二级指针，我们需要把列的数放到一个数组中返回去，所以先开辟 r 个一级指针的空间，在下面循环中把列的数量放进去
		    int** ret = (int**)malloc(sizeof(int*) * r);
		    *returnSize = r;
		    *returnColumnSizes = (int*)malloc(sizeof(int) * r);
		
		    //把列的数量放入数组返回列的数量
		    //为返回的二级指针中的一级指针开辟 c 个空间
		    for (int i = 0; i < r; i++)
		    {
		        (*returnColumnSizes)[i] = c;
		        ret[i] = (int*)malloc(sizeof(int) * c);
		    }
		
		    //我们的思路是将这个二维数组映射成一个一维数组
		    //再将这个一维数组映射回 r 行 c 列的二维数组返回
		    //二维数组m*n，arr2[i][j]映射成一维数组对应的下标为 i*n+j,数组中下标表示为arr1[i*n+j]
		    //同理二维数组对应的一维数组arr1[i*n+j]映射回二维数组对应为 arr2[i/n][i%n]
		    for (int i = 0; i < matSize * matColSize[0]; i++)
		    {
		        ret[i / c][i % c] = mat[i / matColSize[0]][i % matColSize[0]];
		    }
		
		    return ret;
		}