算法分析课程博客分享 2
53. 最大子序和(Maximum Subarray)
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
解题思路:
这道题目的重点在于要求解的是连续自序的和，这显然是一个动态规划的题目，是可以用 O(n) 时间复杂度解决的问题。首先，我们可以考虑输入 [1,-4,2,3]。对于这个输入，拥有最大和的子序列为 [2,3]，而当我们顺序扫描的时候可以发现，剩余的 [1,-4] 的和为负数。由此可见，当我们顺序扫描的时候，若某段子序列的和为负数且其长度大于 1(考虑全为负数的序列，拥有最大和的子序必然只包含一个元素)，则我们所要求的答案必然不包含这段子序列。因此，我们可以使用一个变量 sum 来储存当前子序列的和，而当 sum 的值小于 0 时，我们则将该段子序列舍去，具体代码如下:
int maxSubArray(vector<int>& nums) {
int size = nums.size();
int sum = 0, ans = nums[0];
for (int i = 0; i < size; ++i) {
sum += nums[i];
if (sum > ans)
ans = sum;
if (sum < 0)
sum = 0;
}
return ans;
}
在这段代码中，我们顺序扫描数组，先记录数组从位置 0 到 i 的和，若和的值大于当前的最大记录，则更新最大记录的值，若和的值小于 0，则将位置 0 到 i 的子序列舍去，记录从位置 i+1 开始的子序列的值。
实际上，这道题的难点在于题目的进阶要求为使用分治法求解，在网上查阅资料后，我发现了以下这种解法:
public:
int maxSubArray(vector<int>& nums) {
return maxSubArray(nums, 0, nums.size()-1);
}
private:
int max(int a, int b, int c) const {
return ((a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c));
}
int maxSubArray(vector<int>& nums, int left, int right) {
if (left == right)
return nums[left];
int center = (left + right) / 2;
int maxLeftSum = maxSubArray(nums, left, center);
int maxRightSum = maxSubArray(nums, center+1, right);
int maxLeftBorderSum = INT_MIN;
int curSum = 0;
for (int i = center; i >= left; --i) {
curSum += nums[i];
if (curSum > maxLeftBorderSum)
maxLeftBorderSum = curSum;
}
int maxRightBorderSum = INT_MIN;
curSum = 0;
for (int i = center+1; i <= right; ++i) {
curSum += nums[i];
if (curSum > maxRightBorderSum)
maxRightBorderSum = curSum;
}
int maxCenterSum = maxLeftBorderSum + maxRightBorderSum;
return max(maxLeftSum, maxRightSum, maxCenterSum);
}
对于任意序列，其拥有最大和的子序列只存在三种情况: 在序列的左半边、在序列的右半边、横跨序列的左右两边。这种解法使用了分治的思想，每次递归都检测三种情况，并返回这三种情况的最大值。缺点在于每次递归中都需做一次扫描来求出横跨序列左右两边的子序列和的最大值，因此算法的时间复杂度为 O(nlogn)，在表现上不如动态规划，但其分治的思想也是十分精妙，值得我们学习。
241. 为运算表达式设计优先级(Different Ways to Add Parentheses)
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 1:
输入: “2-1-1”
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
输入: “2x3-4x5”
输出: [-34, -14, -10, -10, 10]
解释:
(2x(3-(4x5))) = -34
((2x3)-(4x5)) = -14
((2x(3-4))x5) = -10
(2x((3-4)x5)) = -10
(((2x3)-4)x5) = 10
解题思路:
这道题目的 tag 是我们上周开始学习的分治算法，而对于这道题，我们首先要考虑如何把问题 divide 成多个子问题，当我们扫描到一个运算符的时候，我们的实际操作为对运算符左边的运算结果与运算符右边的运算结果应用运算符相对应的运算。因此，每当我们扫描到运算符，我们就可以得到两个子问题，其中一个是运算符左边的结果，另一个是运算符右边的结果。若我们采取这样的划分方法，接下来我们需要考虑的就是要如何把结果整合到一起。我们每次执行递归的时候，当前运算符即是当前优先级最高的运算符，而我们将运算符左边的结果集与运算符右边的结果集做一个笛卡尔积即可获得当前运算符运算结果的所有可能性。这种思路用语言还是比较难解释，而且我们并没有在分治的时候进行等分操作，因此复杂度也比较难计算，具体代码如下:
int compute(int& a, int& b, char& op) const {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
}
}
vector<int> diffWaysToCompute(string input) {
vector<int> ans;
for (int i = 0; i < input.length(); ++i) {
if (!isdigit(input[i])) {
vector<int> left = diffWaysToCompute(input.substr(0, i));
vector<int> right = diffWaysToCompute(input.substr(i+1));
for (int l : left) {
for (int r : right) {
ans.push_back(compute(l, r, input[i]));
}
}
}
}
if (ans.empty()) {
ans.push_back(stoi(input));
}
return ans;
}
而实际上，考虑输入 “2x3-4x5”，我们若使用上述算法，需要对 “2” 进行 3 次递归，对 “2x3” 进行 2 次递归。当字符串长度变长时，这部分的开销其实是很大的，所以在这也提供一种以空间换取时间的方法。我们记录每次递归得到的结果集，如果可以在记录中查找到当前字符串对应的结果集，我们无需再执行递归操作，否则，我们将递归得到的结果集记录下来，具体代码如下:
unordered_map<string, vector<int>> dict;
int compute(int& a, int& b, char& op) const {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
}
}
vector<int> diffWaysToCompute(string input) {
vector<int> ans;
for (int i = 0; i < input.length(); ++i) {
if (!isdigit(input[i])) {
vector<int> left, right;
if (dict.find(input.substr(0, i)) != dict.end()) {
left = dict[input.substr(0, i)];
} else {
left = diffWaysToCompute(input.substr(0, i));
}
if (dict.find(input.substr(i+1)) != dict.end()) {
right = dict[input.substr(i+1)];
} else {
right = diffWaysToCompute(input.substr(i+1));
}
for (int l : left) {
for (int r : right) {
ans.push_back(compute(l, r, input[i]));
}
}
}
}
if (ans.empty()) {
ans.push_back(stoi(input));
}
dict[input] = ans;
return ans;
}
23. 合并K个排序链表(Merge k Sorted Lists)
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解题思路:
这道题难度不算很大，主要是运用到分治的思想，假设我们有 3 个链表需要合并，我们可以先把前两个合并成一个新链表，然后再将结果与第三个链表合并。同样的思路，假设我们有 n 个链表，我们也可以将其划分成将 n-1 个子问题，每个子问题中合并两个链表，具体代码如下:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty())
return NULL;
else if (lists.size() == 1)
return lists[0];
ListNode* head = lists[0];
for (int i = 1; i < lists.size(); ++i) {
ListNode* next = lists[i];
head = merge2Lists(head, next);
}
return head;
}
ListNode* merge2Lists(ListNode* a, ListNode* b) {
ListNode* head = new ListNode(0);
ListNode* cur = head;
while (a != NULL && b != NULL) {
if (a->val < b->val) {
cur->next = a;
a = a->next;
} else {
cur->next = b;
b = b->next;
}
cur = cur->next;
}
if (a == NULL)
cur->next = b;
else if (b == NULL)
cur->next = a;
cur = head;
head = head->next;
delete cur;
return head;
}
而对于这一段代码，我们假设所有的链表长度都为 d，则整个算法的时间复杂度将为 O(dxn^2)。在参考了网上资料后，我发现了一处可以改进的地方，若我们想办法让每次要合并的链表长度尽量接近，我们算法的时间复杂度可以得到显著的提升，具体代码如下:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty())
return NULL;
else if (lists.size() == 1)
return lists[0];
vector<ListNode*> ans;
for (int i = 0; i < lists.size()-1; i += 2) {
ans.push_back(merge2Lists(lists[i], lists[i+1]));
}
if (lists.size()%2 == 1) {
ans.push_back(lists[lists.size()-1]);
}
return mergeKLists(ans);
}