回溯问题: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--,向中间靠拢。 但关键的关键,就是检测每个字符有效,并忽略字母大小写。并且程序还要解决一个字符串没有有效字母的情况!
字母大小写转换的快捷方法:
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