算法分析课程博客分享 6
475. 供暖器(Heaters)
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
- 给出的房屋和供暖器的数目是非负数且不会超过 25000。
- 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
- 只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
- 所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
解题思路:
这道题的设定其实挺迷幻的，刚开始我也没想到好的解决方案，直到看见了题目的相关话题为二分查找，我才开始往二分查找的方向去思考解题方法。而这道题的本质其实也比较抖机灵，所以很难去描述我的解题思路。首先，观察题目形式，我们可以考虑到往 heaters 中插入 houses 或者往 houses 中插入 heaters 两种思路。对于往 heaters 中插入 houses，我们可以通过计算一个 house 到其最近 heater 的距离，从而判断是否需要用到更大的供热半径。此时，一共有三种情况：house 在第一个 heater 的左边、house 在两个 heater 之间、house 在最后一个heater 右边。这三种情况分别对应不同的最近距离计算方法，而具体的计算公式可以参考下面的代码。到了这一步，我们还需要解决的问题就只剩下正确地将一个 house 定位到 heater 区间中了，由于前面已经提及到二分查找，我们不难想到先对 heaters 数组进行排序，然后在使用二分查找定位每一个 house。我们假设 houses 的长度为 n，heaters 的长度为 m，则对 heaters 进行排序的时间复杂度为 O(nlogn)，定位 houses 中的所有元素的时间复杂度为 O(m)xO(logn)，因此，整个算法的时间复杂度为 O((m+n)logn)。
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
// sort the heaters first
sort(heaters.begin(), heaters.end());
// current radius
int radius = 0;
// use binary search to locate houses into proper heater intervals
for (int house : houses) {
int pos = binarySearch(heaters, house);
if (pos == -1) {
radius = max(radius, heaters[0]-house);
} else if (pos == heaters.size()-1) {
radius = max(radius, house-heaters[pos]);
} else {
radius = max(radius, min(house-heaters[pos], heaters[pos+1]-house));
}
}
return radius;
}
private:
int binarySearch(vector<int>& heaters, int house) {
int begin = 0, end = heaters.size()-1;
int median;
while (begin <= end) {
median = (begin+end) / 2;
if (heaters[median] == house) {
return median;
} else if (heaters[median] < house) {
begin = median + 1;
} else {
end = median -1;
}
}
if (heaters[median] > house) {
--median;
}
return median;
}
456. 132模式(132 Pattern)
给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意： n 的值小于15000。
示例1:
输入: [1, 2, 3, 4]
输出: False
解释: 序列中不存在132模式的子序列。
示例 2:
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2]。
示例 3:
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0]。
解题思路:
这道题目要求我们寻找一个 132 模式的子序列，在这种情况下，如果我们能先确定好位于 ak 的值，我们可以更容易确定 ai 与 aj 的值。因此，我们从后往前扫描数组，先假定 ak 的初始值为 INT_MIN，并用栈 s 来储存 aj 的候选值。在扫描过程中，若 ak 小于等于当前元素，我们将更新 aj 的可能值，我们把 s 中所有小于当前元素的值移除，通过这个操作，我们能让 aj 的候选值尽可能地大，从而使我们更容易构造出 ak < aj 的序列。然后，我们将 ak 的值更新为刚刚被移除的元素中最大的值，这样，我们就能够更容易地构造出 ai < ak 的序列，同时，对于当前 ak，必然存在一个 aj 使 ak < aj 成立。当我们找到一个当前元素满足 num < ak 时，此时的 num 即可作为 ai，构造出 num < ak < s.top() 的序列，而这个序列正是我们要找的 132 模式的子序列。如果我们在扫描完整个数组后，仍然没有构造出 num < ak < s.top() 的序列，这证明输入序列不包含 132 模式的子序列。
为了能更清晰地描述这个算法，接下来将证明 aj 的候选值的正确性。在初始状态中，栈 s 为空，压入栈中的第一个元素将保证大于等于 ak，即当前栈中的值皆大于等于 ak。当我们要压入第二个元素的时候，将会有两种可能的情况发生：第一种为当前元素大于等于栈顶元素，我们将栈顶元素视作新的 ak，当前元素视作新的 aj；第二种为当前元素小于栈顶元素，则我们在压栈后可以保证栈中的元素是降序储存的。由此，我们可以确保每次更新 ak 的时候，我们能找到的值都是能满足 ak < aj 的最大的值，而最后，我们将获得整个序列中能满足 ak < aj 的最大的 ak 的值。若我们无法找到一个 ai 满足 ai < max(ak)，我们则可认为在当前序列中 132 模式的子序列是不存在的。
bool find132pattern(vector<int>& nums) {
// optimal value of ak
int ak = INT_MIN;
// used to store alternatives of aj in a descending order
stack<int> s;
for (auto num = nums.rbegin(); num != nums.rend(); ++num) {
if (ak > *num) {
return true;
} else while (!s.empty() && s.top() < *num) {
ak = s.top();
s.pop();
}
s.push(*num);
}
return false;
}
99. 恢复二叉搜索树(Recover Binary Search Tree)
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
解题思路:
显然，这一题的实现必然与树的遍历相关，对于这道题，我们可以先假设有且只有两个节点被错误地交换了。考虑一棵二叉搜索树，我们对其进行中序遍历，在正确的情况下，前一个访问的节点的值必然小于当前正在访问的节点的值，则我们的问题可以转化为寻找中序遍历过程中的降序节点对。我们在前面已经假设了输入有且只有两个节点被错误地交换了，则我们只会遇到两种情况：在遍历过程中发现一个降序节点对、在遍历过程中发现两个降序节点对。第一种情况意味着两个相邻的节点被错误地交换了，我们只需要简单交换两个节点的值即可；至于第二种情况，被交换的两个节点是不相邻的，其中，一个节点比应有的值要大，另一个节点比应有的值要小。在实现过程中，我们可以用三个 TreeNode 指针分别指向第一个错误的节点、第二个错误的节点、前一个节点，当我们搜索到降序节点对时，对指向错误节点的指针进行更新。通过中序遍历，我们获得的第一个节点必然是比应有值大的那一个，因此，当我们检测到第一个降序节点对时，我们将 first 设成 prev，将 second 设成 root。当我们第二次检测到降序节点对时，此时的错误节点比应有的值要小，故我们只需要将 second 的值更新为 root。在遍历完成后，我们交换 first 与 second 的值即可正确复原二叉搜索树。
public:
void recoverTree(TreeNode* root) {
// to travel the tree and figure out the 2 elements swapped by mistake
inorder(root);
// to recover the tree by swapping those 2 wrong elements
if (first != NULL && second != NULL) {
swap(first->val, second->val);
}
}
private:
TreeNode* first = NULL; // the first misplaced element
TreeNode* second = NULL; // the second misplaced element
TreeNode* prev = NULL; // the last node visited
void inorder(TreeNode* root) {
if (root == NULL)
return;
inorder(root->left);
// to judge whether there is a pair of nodes in a descending order
if (prev != NULL && prev->val > root->val) {
if (first == NULL) {
first = prev;
}
second = root;
}
prev = root;
inorder(root->right);
}
之前，我并没有听说过 Morris 遍历，在网上搜索资料后，我发现这是一种时间复杂度为 O(n)，空间复杂度为 O(1) 的遍历算法。在上述的思路的基础上，我们应用 Morris 遍历即可实现只使用常数空间的解决方案了。想知道更多有关 Morris 遍历的内容可以参考以下这篇博客。
public:
void recoverTree(TreeNode* root) {
// to travel the tree and figure out the 2 elements swapped by mistake
morrisInorder(root);
// to recover the tree by swapping those 2 wrong elements
if (first != NULL && second != NULL) {
swap(first->val, second->val);
}
}
private:
TreeNode* first = NULL; // the first misplaced element
TreeNode* second = NULL; // the second misplaced element
TreeNode* prev = NULL; // the last node visited
TreeNode *cur, *leaf;
void morrisInorder(TreeNode* root) {
if (root == NULL)
return;
cur = root;
while (cur != NULL) {
// if the current node has a left-hand subtree
if (cur->left != NULL) {
leaf = cur->left;
// to reach the rightmost leaf of its left-hand subtree
while (leaf->right != NULL && leaf->right != cur) {
leaf = leaf->right;
}
// to judge whether we should visit the current node now
if (leaf->right == NULL) {
leaf->right = cur;
cur = cur->left;
// to visit the left-hand subtree of the current node first
continue;
} else {
// recover the value of free pointer
leaf->right = NULL;
}
}
// then visit the current node
// to judge whether there is a pair of nodes in a descending order
if (prev != NULL && prev->val > cur->val) {
if (first == NULL) {
first = prev;
}
second = cur;
}
prev = cur;
// to visit the right-hand subtree of the current node at the end
cur = cur->right;
}
}