Blog of Xingyu Wang
0%

LC周报-分治法、记忆化搜索(20221024-20221030)

Posted on Edited on In

本周做题记录

LC-241、LC-22、LC-10、LC-32、LC-42，涉及知识点记忆化搜索、动态规划等。

本周总结 1-分治法

简介

参考《算法导论》简单介绍分治法的核心思想：将一个大问题分解为若干子问题，然后递归地求解子问题，最终合并为大问题的答案。二分查找等经典算法本质上也是使用了分治策略的思想，因为之前已经详细介绍二分查找，因此此处不再介绍，仅介绍几个在其他背景下涉及分治思想的题目。

LC-53 最大子数组和

原问题实际要求整数数组 nums 中具有最大和的连续子数组（子数组最少包含一个元素）。思路是对于一个区间 [l,r]，取 m=(l+r)/2，对区间 [l,m] 和 [m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归开始回升。之后考虑如何通过 [l.m] 区间的信息和 [m+1,r] 区间的信息合并成区间 [l,r] 的信息。LC 的官方解答如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct Status
{
    int lSum, rSum, mSum, iSum;
};

Status pushUp(Status l, Status r)
{
    int iSum = l.iSum + r.iSum;
    int lSum = max(l.lSum, l.iSum + r.lSum);
    int rSum = max(r.rSum, r.iSum + l.rSum);
    int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
    return (Status){lSum, rSum, mSum, iSum};
};

Status get(vector<int> &a, int l, int r)
{
    if (l == r)
    {
        return (Status){a[l], a[l], a[l], a[l]};
    }
    int m = (l + r) >> 1;
    Status lSub = get(a, l, m);
    Status rSub = get(a, m + 1, r);
    return pushUp(lSub, rSub);
}

int maxSubArray(vector<int> &nums)
{
    return get(nums, 0, nums.size() - 1).mSum;
}

时间复杂度\(O(n)\),空间复杂度为\(O(logn)\)。

另外，本题还可以使用动态分配方法解决。

LC-169 多数元素

搜索数组 nums 中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

思想：将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。

官方题解中代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int count_in_range(vector<int> &nums, int target, int lo, int hi)
{
    int count = 0;
    for (int i = lo; i <= hi; ++i)
        if (nums[i] == target)
            ++count;
    return count;
}
int majority_element_rec(vector<int> &nums, int lo, int hi)
{
    if (lo == hi)
        return nums[lo];
    int mid = (lo + hi) / 2;
    int left_majority = majority_element_rec(nums, lo, mid);
    int right_majority = majority_element_rec(nums, mid + 1, hi);
    if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
        return left_majority;
    if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
        return right_majority;
    return -1;
}

int majorityElement(vector<int> &nums)
{
    return majority_element_rec(nums, 0, nums.size() - 1);
}

记忆化搜索

记忆化搜索本身其实并不构成一类算法，而是一种用空间换时间的算法技巧。在 DFS、DP 算法中，可能会有同一个子问题被反复计算，为节省时间，可将其结果存储下来，这样可以在第二次计算子问题时直接返回结果。

LC-139 单词拆分

给定字符串\(s\)和字符串列表\(wordDict\)作为字典，判断是否可以利用字典中出现的单词拼接出\(s\)。

题目本质是一个 DFS 算法，若 \(s[0,⋯ ,i−1]\) 在 单词字典 中，则\(s\)能否被拆分就取决于\(s[i,...,n-1]\)能否被拆分，将每一个计算子结果使用数据结构map<string, bool> m记录下来，我的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <map>
using namespace std;

map<string, bool> m;
bool back_track(string s, unordered_set<string> dic)
{
    // cout<<s<<endl;
    if (m.find(s) != m.end())
        return m[s];
    if (s.size() == 0)
        return true;
    bool res = false;
    for (int i = 1; i <= s.size(); i++)
    {
        string curr = s.substr(0, i);
        if (dic.find(curr) != dic.end())
        {
            cout << curr << endl;
            cout << res;
            curr = s.substr(i, s.size() - i);
            res = back_track(curr, dic) || res;
            cout << res << endl;
        }
    }
    m[s] = res;
    return res;
}
bool wordBreak(string s, vector<string> &wordDict)
{
    unordered_set<string> dic;
    for (int i = 0; i < wordDict.size(); i++)
    {
        dic.insert(wordDict[i]);
    }
    bool a = back_track(s, dic);
    return a;
}

int main()
{
    string s = "abcd";
    vector<string> wordDict = {"a", "abc", "b", "cd"};

    bool a = wordBreak(s, wordDict);
}

LC-140 单词拆分 II

本题和 139 的区别是需要返回\(s\)拆分后的结果。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<int, vector<string>> ans;
unordered_set<string> wordSet;

void backtrack(const string &s, int index)
{
    if (ans.count(index) == 0)
    {
        if (index == s.size())
        {
            ans[index] = {""};
            return;
        }
        ans[index] = {};
        for (int i = index + 1; i <= s.size(); ++i)
        {
            string word = s.substr(index, i - index);
            if (wordSet.count(word))
            {
                backtrack(s, i);
                for (const string &succ : ans[i])
                {
                    ans[index].push_back(succ.empty() ? word : word + " " + succ);
                }
            }
        }
    }
}
vector<string> wordBreak(string s, vector<string> &wordDict)
{
    for (int i = 0; i < wordDict.size(); i++)
        wordSet.insert(wordDict[i]);
    backtrack(s, 0);
    return ans[0];
}
int main()
{
    string s = "pineapplepenapple";
    vector<string> wordDict{"apple", "pen", "applepen", "pine", "pineapple"};

    wordBreak(s, wordDict);
    for (int i = 0; i < ans[0].size(); i++)
        cout << ans[0][i] << endl;
}

LC-241 为运算表达式设计优先级

题目大意：对一个数字和运算符组成的字符串\(s\)，返回按照不同优先级计算返回的所有计算结果。

题目思路是，对于每一个运算符，分别计算其左侧和右侧子串的所有可能运算结果，再合并即为最终答案。值得注意的是，为节省时间，需将每个子问题的答案记录，以便重复利用。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    unordered_map<string, vector<int>> m;
    vector<int> diffWaysToCompute(string expression)
    {
        if(m.find(expression) != m.end())
        return m[expression];

        if(expression.find_first_of("+*-")==expression.npos)
        return {stoi(expression)};
        vector<int> ans;
        int pos = 0;
        while((pos = expression.find_first_of("+-*", pos+1))!= expression.npos)
        {
            //cout<<pos;
            vector<int> left = diffWaysToCompute(expression.substr(0,pos));
            vector<int> right = diffWaysToCompute(expression.substr(pos+1));

            for(auto l:left)
            {
                for(auto r:right)
                {
                    if(expression[pos] == '+')
                    ans.push_back(l+r);
                    else if(expression[pos] == '-')
                    ans.push_back(l-r);
                    else
                    ans.push_back(l*r);
                }
            }
        }
        m[expression] = ans;
        return m[expression];
    }
};

其他备注

  1. string 的find_first_of函数的用法：
1
s.find_first_of(x)==s.npos

该函数用于搜索字符串\(s\)中是否存在字符串\(x\)中的任一字符，若存在，返回第一个出现的位置，若不存在，返回s.npos。