1. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
【解析】
求这两个数组合并之后的中位数，如果合并后的数组有奇数个数，
中位数是最中间那个数，如果有偶数个数，中位数是最中间两个数的平均数。
以下解法时间复杂度： O(log (m+n))
【子问题】求两个数从小到大排列，第k个数是多大。
求中位数时，让k = ( m + n ) / 2
【解析】
目前A，B是两个有序数组，假如：
（1）A[k/2] < B[k/2]，（先不考虑A、B数组长度总和是奇数还是偶数）
A 中 <= A[k/2] 的个数有 k/2 个；
B 中 <= A[k/2] 的个数有小于 k/2 个；
A + B 中<= A[k/2] 的个数有小于 k 个；
那就说明，A 中的 a段（黄色区域） 一定在第 k 个数的前面，那我们就可以把 a 段删掉。
（2）A[k/2] > B[k/2]，将情况（1）反一下。
（3）A[k/2] == B[k/2]，说明，A[k/2] == B[k/2] 恰好就是第 k 个数，
找到答案了。
我们比较完一次 A[k/2] 与 B[k/2] 值的大小，一定可以删 k/2 个元素。
那么下一次，问题就变成了，让我们在剩余的数组中找出第 k - k/2 个数。
就会变成一个递归的子问题。
当 k == 1 时，就是求两个数组最小的值。递归结束。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
if(len % 2 == 0){
// 如果两个数组和一块有偶数个数，中位数就是最中间两个数的平均数
// 就是求 第 len/2 和 第 len/2+1 个数的平均数
int left = find(nums1, 0, nums2, 0, len / 2);
int right = find(nums1, 0, nums2, 0, len / 2 + 1);
return (left + right) / 2.0;
}else{
// 如果两个数组和一块长度是奇数，中位数就是最中间那个数：第 len/2+1 个数
return find(nums1, 0, nums2, 0, len / 2 + 1);
}
}
// find ：
// nums1 数组：从 i 开始到 nums1 的结尾；nums2 数组：从 j 开始到 nums2 的结尾。
// 找 nums1 数组 nums2 数组合一块 第 k 个数
int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k){
// nums1 从 i 开始，nums2 从 j 开始，找出第 k 个数
// 假设第一个数组比较短
if(nums1.size() - i > nums2.size() - j)
return find(nums2 , j , nums1 , i , k);
// 如果第一个数组比较长，那就把两个位置交换一下
// 遇到以下两种边界情况，递归结束
if(k == 1){ // 第一个边界问题 （边界情况一）
if(nums1.size() == i) // 如果 nums1 数组是空的
return nums2[j];
else return min(nums1[i],nums2[j]);
}
if(nums1.size() == i){ //（边界情况二）
// 如果 nums1 数组是空的，那么要求的第 k 个数，直接就是 nums2 数组的第 k 个数
return nums2[j + k - 1];
}
int si = min((int)nums1.size(),i + k / 2) , sj = j + (k - k / 2);
// si = min(nums1.size(),i + k / 2) ， si这样取是因为 nums1 比较短，防止越界
// 假如 nums1 是从 i 开始的，求 nums1 的第1个数：nums[i + 0]，
//第2个数：nums1[i + 1] ... 第 k/2 个数：nums1[i + k/2 - 1]；第 k/2 + 1 个数：nums1[i + k/2]
// nums1[si]：第 k/2 + 1 个数
if(nums1[si - 1] > nums2[sj - 1]){
// 就可以删除 nums2 的 j ~ sj - 1 这 (k-k/2) 个数了
// 删了 (k-k/2) 个数 ，求剩余数组 第 k - (k - k/2) = k - (sj - j)个数
return find(nums1, i, nums2, sj, k - (sj - j));
// num1 不变
}else{
// 删除 nums1 的 i ~ si - 1 ，求剩余数组的第 k - (si - i) 个数
return find(nums1, si, nums2, j, k - (si - i));
}
}
};
2. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
输入：s = "cbbd"
输出："bb"
【解析】"回文串”是一个正读和反读都一样的字符串。
1. s 长度为奇数，i = len / 2，初始：l = i - 1,r = i + 1;
2. s 长度为偶数，i = len / 2，初始：l = i，r = i + 1;
枚举中心 i 需要 O(n)次操作，枚举作用两个指针也是 O(n)，
所以总共的时间复杂度是 O(n^2)。
我的解法
class Solution {
public:
string longestPalindrome(string s) {
int left = 0;
int res = 1;
for(int i = 0;i < s.size();i ++){
// 子串长度是奇数
int l = i - 1,r = i + 1;
while(l >= 0 && r <= 2*i){
// 找 0 ~ 2*i 之间的最长回文子串（以 i 作为中心，回文子串的最右端就在 2*i 处）
if(s[l] == s[r]){
if(r-l+1 > res){ // 更新
left = l;
res = r-l+1;
}
l--;
r++;
}else{
break;
// 否则以当前 i 指向的元素为中心不会有回文子串
}
}
}
for(int i = 0;i < s.size();i ++){
int l = i,r = i + 1;
while(l >= 0 && r <= 2*i + 1){
if(s[l] == s[r]){
if(r-l+1 > res){ // 更新
left = l;
res = r-l+1;
}
l--;
r++;
}else{
break;
// 否则以当前 i 指向的元素为中心不会有回文子串
}
}
}
// 这两个 for 可以和一块
return s.substr(left,res);
}
};
3. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
class Solution {
public:
string convert(string s, int n) {
string res;
if(n == 1)
return s;
for(int i = 0;i < n;i++)
{
if(i == 0 || i == n-1) // 第一行或最后一行
{
for(int j = i;j < s.size(); j += 2*n - 2)
res += s[j];
}
else // 中间其他行
{
for(int j = i,k = 2*n - i - 2;j < s.size() || k<s.size(); j += 2*n - 2,k += 2*n - 2)
{
if(j < s.size())
res += s[j];
if(k < s.size())
res += s[k];
}
}
}
return res;
}
};