面试算法题之合并系列
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
双指针解法
因为两个数组本身是有序的，那么我们可以定义两个指针，从数组尾部开始遍历，如果nums1[m] > nums2[n]则说明nums1[m]是最大的，放置在最后，并且移动 m 指针。若小于等于则说明nums2[n]大，移动nums2[n]至后面排序好数组前。
如此遍历完后得到的就是合并后的数组。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = nums1.size() - 1;
m--;
n--;
while(n >= 0) {
while(m >= 0 && nums1[m] > nums2[n]) {
swap(nums1[i--], nums1[m--]);
}
swap(nums1[i--], nums2[n--]);
}
}
};思考
"思考是学习的源泉。"
- n、m 为何需要先自减 1 ？
- 示例代码是数组尾部开始遍历，可以改成从数组头开始遍历吗？
合并后再排序解法
利用库函数直接偷懒，不过在学习算法时最好不要使用库函数，可以自己实现一下排序算法，巩固下十大排序算法。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i=0; i<n; i++) {
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
双指针解法
这里采用了合并两个有序数组的题解思路，思路是一样的。值得注意的是，链表需要定义一个头节点，这样返回新链表的时候可以使用head->next指明。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* head = new ListNode(-1);
ListNode* p = head;
while(list2 != nullptr) {
while(list1 != nullptr && list1->val <= list2->val) {
p->next = list1;
list1 = list1->next;
p = p->next;
}
p->next = list2;
list2 = list2->next;
p = p->next;
}
p->next = list1 != nullptr ? list1 : list2;
return head->next;
}
};思考
- 去掉
p->next = list1 != nullptr ? list1 : list2;会如何？
迭代解法
迭代解法思路更容易理解，即逐个判断list1 或 list2的值大小，然后按照顺序将节点拼接成新链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* head = new ListNode(-1);
ListNode* p = head;
while(list1 != nullptr && list2 != nullptr) {
if(list1->val > list2->val) {
p->next = list2;
list2 = list2->next;
} else {
p->next = list1;
list1 = list1->next;
}
p = p->next;
}
p->next = list1 != nullptr ? list1 : list2;
return head->next;
}
};递归解法
上面迭代的方法，可以分解成子步骤，并可以找到递归出口，list1 或 list2为空的时候。
那么我们可以这样实现，list1 或 list2为空时，不需要进行合并，返回另一个链表即可。否则，就需要比较两个链表的元素值，看谁的值更小，由此递归其中一个链表的下一个节点。
递归的最后，即两个链表出现一个为空的链表，这时候就会结束递归。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr) {
return list2;
} else if(list2 == nullptr) {
return list1;
} else if(list1->val > list2->val) {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
} else {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
}
};合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
深度优先搜索
我们可以用递归实现深度优先搜索，递归出口即root1或root2为空的时候，这时候返回另一个树。
当两个节点都不会空时，需要创建一个新节点，元素值即为两个节点元素值之和。然后分别递归两颗树左节点和右节点。
递归的最后，即两个树出现一个为空，这时候就会结束递归。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1 == nullptr) {
return root2;
} else if(root2 == nullptr) {
return root1;
}
TreeNode* merged = new TreeNode(root1->val + root2->val);
merged->left = mergeTrees(root1->left, root2->left);
merged->right = mergeTrees(root1->right, root2->right);
return merged;
}
};