给定两个大小分别为
m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
实现途径：
思路1：简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
// 定义一个函数来找到两个有序数组的中位数
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
// 创建一个新数组，用于存放合并后的有序数组
int arr[nums1Size + nums2Size];
int i = 0, j = 0, k = 0; // i 和 j 分别为 nums1 和 nums2 的索引，k 为 arr 的索引
// 遍历 nums1 和 nums2 直到其中一个数组被完全遍历
while (i < nums1Size && j < nums2Size) {
// 比较当前两个数组元素的大小，将较小的元素放入 merged 中，并移动相应的索引
if (nums1[i] < nums2[j]) {
arr[k++] = nums1[i++];
} else {
arr[k++] = nums2[j++];
}
}
// 如果 nums1 还有剩余元素，将其全部复制到 merged 中
while (i < nums1Size) {
arr[k++] = nums1[i++];
}
// 如果 nums2 还有剩余元素，将其全部复制到 merged 中
while (j < nums2Size) {
arr[k++] = nums2[j++];
}
// 计算合并后数组的长度
int length = nums1Size + nums2Size;
// 根据合并后的数组长度是奇数还是偶数来计算中位数
if (length % 2 == 0) {
// 如果是偶数，中位数为中间两个数的平均值
return (double)(arr[length / 2 - 1] + arr[length / 2]) / 2.0;
} else {
// 如果是奇数，中位数为中间的数
return (double)arr[length / 2];
}
}
思路二：
中位数相关的二分查找算法如下：
代码：
// 函数：在两个已排序数组中找到第k小的元素
// 参数：nums1和nums2是两个已排序数组，len1和len2分别是它们的大小，k是要找的第k小的元素的位置
// 返回值：第k小的元素的值
int find_k_th_nums(int* nums1, int len1, int* nums2, int len2, int k) {
int low1 = 0; // nums1的起始索引
int low2 = 0; // nums2的起始索引
// 循环直到找到第k小的元素或者其中一个数组被遍历完
while (k > 1 && low1 < len1 && low2 < len2) {
int x1 = low1 + k / 2 - 1; // nums1的中间索引
int x2 = low2 + k / 2 - 1; // nums2的中间索引
int reduce_len; // 需要减去的长度
// 处理其中一个数组已经被遍历完的情况
if (x1 >= len1 && x2 < len2) {
reduce_len = len1 - low1;
} else if (x1 < len1 && x2 >= len2) {
reduce_len = len2 - low2;
} else {
// 计算需要减去的长度，选取较小的长度
if (len1 - low1 > len2 - low2) {
reduce_len = len2 - low2;
} else {
reduce_len = len1 - low1;
}
}
// 更新减去的长度
int x3 = k / 2;
if (x3 < reduce_len) {
reduce_len = x3;
}
// 更新k值和数组起始索引
k = k - reduce_len;
if (nums1[low1 + reduce_len - 1] > nums2[low2 + reduce_len - 1]) {
low2 += reduce_len;
} else {
low1 += reduce_len;
}
}
// 返回第k小的元素
if (k == 1) {
if (low1 < len1 && low2 < len2) {
return nums1[low1] < nums2[low2] ? nums1[low1] : nums2[low2];
} else if (low1 >= len1) {
return nums2[low2];
} else {
return nums1[low1];
}
} else if (low1 >= len1) {
return nums2[low2 + k - 1];
} else {
return nums1[low1 + k - 1];
}
}
// 函数：在两个已排序数组中找到中位数
// 参数：nums1和nums2是两个已排序数组，nums1Size和nums2Size分别是它们的大小
// 返回值：中位数的值
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int len = nums1Size + nums2Size; // 总长度
// 如果总长度为偶数
if (len % 2 == 0) {
int x1 = find_k_th_nums(nums1, nums1Size, nums2, nums2Size, len / 2); // 找到第 len/2 个元素
int x2 = find_k_th_nums(nums1, nums1Size, nums2, nums2Size, len / 2 + 1); // 找到第 len/2 + 1 个元素
return (double)(x1 + x2) / 2; // 返回中位数
} else {
int ret = find_k_th_nums(nums1, nums1Size, nums2, nums2Size, len / 2 + 1); // 找到第 len/2 + 1 个元素
return ret; // 返回中位数
}
}
给你一个字符串
s，找到s中最长的回文子串
。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd" 输出："bb"
思路1如下：
思路是通过中心扩展法来找到字符串中的最长回文子串。其主要步骤如下：
定义了两个函数：
expandAroundCenter和longestPalindrome。
expandAroundCenter函数用于判断以给定的中心位置为中心的回文子串的长度。longestPalindrome函数用于找到整个字符串中的最长回文子串。在
longestPalindrome函数中，遍历字符串中的每个字符，以当前字符为中心，分别向左右两边扩展，同时判断扩展的回文子串的长度。在扩展过程中，利用
expandAroundCenter函数计算以当前字符为中心的奇数长度和偶数长度的回文子串的长度，并记录最长的回文子串的起始和结束位置。不断更新最长回文子串的起始和结束位置，直到遍历完整个字符串。
最后，根据记录的最长回文子串的起始和结束位置，截取出最长回文子串，并返回。
整体思路是从每个字符开始，以其为中心向两边扩展，寻找回文子串，并记录最长的回文子串。通过这种方法，可以在遍历一次字符串后找到最长的回文子串。
代码如下：
// 判断字符串 s 中以 left 和 right 为中心的回文子串的长度
int expandAroundCenter(char *s, int left, int right) {
int len = strlen(s);
while (left >= 0 && right < len && s[left] == s[right]) {
left--; // 向左移动左边界
right++; // 向右移动右边界
}
return right - left - 1; // 返回回文子串的长度
}
// 找到字符串 s 中最长的回文子串
char *longestPalindrome(char *s) {
if (s == NULL || strlen(s) < 1) return ""; // 空串或长度小于1的情况直接返回空字符串
int start = 0, end = 0; // 记录最长回文子串的起始和结束位置
for (int i = 0; i < strlen(s); i++) {
int len1 = expandAroundCenter(s, i, i); // 以 s[i] 为中心的奇数长度的回文子串长度
int len2 = expandAroundCenter(s, i, i + 1); // 以 s[i] 和 s[i+1] 为中心的偶数长度的回文子串长度
int len = len1 > len2 ? len1 : len2; // 取较长的回文子串长度
if (len > end - start) { // 如果当前回文子串长度比之前记录的最长回文子串长度长
start = i - (len - 1) / 2; // 更新最长回文子串的起始位置
end = i + len / 2; // 更新最长回文子串的结束位置
}
}
// 截取最长回文子串
char *result = (char *)malloc((end - start + 2) * sizeof(char)); // 分配内存
strncpy(result, s + start, end - start + 1); // 复制最长回文子串
result[end - start + 1] = '\0'; // 添加字符串结束符
return result; // 返回最长回文子串
}
方法2:动态规划
回文天然具有「状态转移」性质：一个长度严格大于 222 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。
动态规划五部曲：
dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
2 确定递推公式
在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
3
dp数组如何初始化
首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
4
确定遍历顺序
| dp[ i ][ j-1] | dp[ i ] [ j ] |
| dp[ i+1 ][ j-1 ] | dp[i+1][ j ] |
从递归公式中，可以看出，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，如图
所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。
j的话，可以正常从左向右遍历。
代码如下：