双指针问题-LeetCode 88、125（双指针，大小写转换）
双指针问题-LeetCode 88、125（双指针，大小写转换）
作者：TeddyZhang，公众号：算法工程师之路
回溯问题：LeetCode #88 #125
1
编程题
【LeetCode #88】合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
算法原理：
这道题目的方法十分巧妙，由于题目中nums1有足够的空间，可以用来保存nums2的元素，将nums2合并到nums1，并且两者有序，这其实就是一个归并排序的方法。但巧妙之处在于如何调整合并后的顺序？
从后向前比较并放置较大的元素，如果nums1中前m个元素设置完成后，并且nums2有剩余，那么直接把剩下的元素拷贝到nums1中，这就是归并排序的思想！
C++代码：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int len = m+n-1;
m = m-1, n = n-1;
while(m >= && n >= ){
if(nums1[m] > nums2[n]){
nums1[len--] = nums1[m--];
}else{
nums1[len--] = nums2[n--];
}
}
while(n >= ){
nums1[len--] = nums2[n--];
}
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-sorted-array
【LeetCode #125】验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。
示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true 示例 2: 输入: "race a car" 输出: false
解题思路：
这个思路很好想，我们利用双指针l和r，从字符串两端开始比较每个字符，如果字符不相同，则返回false。如果相同，则l++，r--，向中间靠拢。 但关键的关键，就是检测每个字符有效，并忽略字母大小写。并且程序还要解决一个字符串没有有效字母的情况！
字母大小写转换的快捷方法：
- 统一转成大写：ch & 0b11011111 简写：ch & 0xDF
- 统一转成小写：ch | 0b00100000 简写：ch | 0x20
C++代码：
class Solution {
public:
bool isvalid(char c){
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
|| (c >= '0' && c <= '9')){
return false;
}
return true;
}
bool isPalindrome(string s) {
if(s == "") return true;
int l = , r = s.length() - ;
while(l < r){
while(isvalid(s[l]) && (l <r)) l++;
while(isvalid(s[r]) && (l <r)) r--;
if (l < r){
if((s[l++] | 0x20) != (s[r--] | 0x20)){
return false;
}
}
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-palindrome