Leetcode_14 天数据结构入门_day1

Posted on | Edited on | In ,
| 3k | 25 mins.

再来试试数据结构入门，其实就是想做点树的题。

217. Contains Duplicate

Analysis

这个题排序和哈希都可以做。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> ht;
        for(auto it: nums) {
            if(ht.find(it) != ht.end()) return true;
            ht.insert(it);
        }
        return false;
    }
};

排序的就不写了。

53. Maximum Subarray

Analysis

这个题是个很经典的题目，做法很多。

Code

method 1

第一个做法就是从动态规划的角度来思考。显然，边界就是数组的第一个元素，也即：$dp[0] = nums[0]$；针对数组的第二个元素，此时这个数可能与前一个序列构成和更大的序列，也可能构成和更小的序列（也即前一个序列和是负数，这个数正数），那么就有：$dp[1] = max(dp[0] + nums[1], nums[1])$。按照这样的思路就可以得到状态转移方程：$dp[i] = max(dp[i - 1] + nums[i], nums[i])$。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int maxsum = dp[0];
        for(int i = 1; i < nums.size(); i++) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            if(maxsum < pre) maxsum = dp[i];
        }
        return maxsum;
    }
};

可以发现，每次计算的 $dp[i]$ 其实只与 $dp[i - 1]$ 和 $nums[i]$ 有关，那么就可以不用数组来完成了：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = nums[0];
        int maxsum = pre;
        for(int i = 1; i < nums.size(); i++) {
            pre = max(nums[i], nums[i] + pre);
            if(maxsum < pre) maxsum = pre;
        }
        return maxsum;
    }
};

method 2

其实这个题还可以从贪心的角度来思考，对于一个序列而言，要使其值增大，就必须加上一个正数。也就是说，遇到正数就加上，遇到负数就清 0，重新开始计算。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, maxsum = INT32_MIN;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if(sum > maxsum) maxsum = sum;
            if(sum <= 0) sum = 0;
        }
        return maxsum;
    }
};

虽然这个题可以用贪心的角度来思考，但是不如 dp 直接，然且很不容易想到。
贪心总是没有固定的思考方法，要结合实际条件来思考。

method 3

最后一种方法，就是分治（divede and conquer）了，分治的思路暂时不写了，先记住，分治是递归的去解决子问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* method 3: divide and conquer */
class Solution {
public:
    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(lsun, rsub);
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).msum;
    }
};

Summary

第一道题比较简单，第二个题要复杂一点，不过也不是难到做不出来的那种。不过，分治法确实不是很好理解。仔细想一想，数据结构入门确实是数据结构简单，算法思想可不简单啊😂。

Buy me a coffee ? :)
0%