LeetCode究极刷题班( 二 ) _指针变量

思路
由于时间复杂度是log(m+n) ，就要思考一种递归的做法来实现。对于给定的两个数组nums1 ， nums2 ，我们从中找出第 k 个数是多少，在这里要找的k = (m+n)/2 。我们去判断 nums1[k/2?1] ， nums2[k/2?1]大小关系：
class Solution {public:double findMedianSortedArrays(vector& nums1, vector& nums2) {//首先计算两个数组的长度之和int tot = nums1.size() + nums2.size();//对于tot要分奇偶两种情况讨论if(tot % 2 == 0) {int left = findkthnumber(nums1, 0, nums2, 0, tot / 2);int right = findkthnumber(nums1, 0, nums2, 0, tot / 2 + 1);return (left + right) / 2.0;} else {return findkthnumber(nums1, 0, nums2, 0, tot / 2 + 1);}}int findkthnumber(vector nums1, int i, vector nums2, int j, int k) {//先判断nums1和nums2的大小关系，保证第一个数组是小的if(nums1.size() - i > nums2.size() - j) return findkthnumber(nums2, j, nums1, i, k);//判断小数组是否为空if(nums1.size() == i) return nums2[j + k - 1];//当k == 1时候选择最小的起始点就是答案if(k == 1) return min(nums1[i], nums2[j]);int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;if(nums1[si - 1] > nums2[sj - 1]) {return findkthnumber(nums1, i, nums2, sj, k - (sj - j));} else {return findkthnumber(nums1, si, nums2, j, k - (si - i));}}};
这题难点一个是怎么相处log(m+n)的解法，另一个难点就是递归过程中完整的边界情况的考虑
5. 最长回文子串
思想
这道题目解法很多，我们这里使用一个比较容易想的方法
对于给定的字符串，我们可以枚举每一个可能的回文串的中心位置，由于回文串长度可能是奇数，也可能是偶数所以我们都需要考虑，从回文串的中心位置开始，如果左右两边相等，我们就使两个指针分别左右移动。
class Solution {public:string longestPalindrome(string s) {string res;for(int i = 0; i < s.size(); i++){//如果是奇数长int l = i - 1, r = i + 1;while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;if(res.size() < r - l - 1)res = s.substr(l + 1, r - l - 1);//如果是偶数长l = i, r = l + 1;while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;if(res.size() < r - l - 1)res = s.substr(l + 1, r - l - 1);}return res;}};
6. Z 字形变换
思想
我们可以假设数字来模拟，可以发现第一行和最后一行都是以第一个数字为起点的等差数列，公差 = 2n - 2；
对于中间的行，我们可以进行分组，每一行的第一组是再竖线上的数列，公差同样满足 2n - 2；第二组数列是在斜线上的，同样满足2n - 2
class Solution {public:string convert(string s, int numRows) {string res;//对于1行的情况需要特殊判断if(numRows == 1) return s;for(int i = 0; i < numRows; i++){//对于第一行或者最后一行情况if(i == 0 || i == numRows - 1) {for(int j = i; j < s.size(); j += 2 * numRows - 2) {res += s[j];}//对于中间行的处理} else {for(int k = i, j = 2 * numRows - 2 - k; k < s.size() || j < s.size(); k += 2 * numRows - 2, j += 2 * numRows - 2) {//只有k ， j都没有超出边界的时候才能加入结果if(k < s.size()) res += s[k];if(j < s.size()) res += s[j];}}}return res;}};
7. 整数反转
思想
对于正数例如1234 ，我们就是分别取出各个数字，算法就是通过循环 1234 % 10 = 4；1234 / 10；
对于负数例如-1234 ， C++中取模运算有所不同， -1234 % 10 = -4；-1234 / 10；
当我们获得各个数字的以后我们可以每位 * 10 相加恢复成一个整数