Leetcode_14 天数据结构入门_day3

Posted on | Edited on | In ,
| 4.5k | 38 mins.

每日几道题，不要偷懒~

350. Intersection of Two Arrays II

Analysis

这是个很直观的题目，找出两个数组的交集即可。

Code

method 1

在不要求保留原数据的情况下，可以直接查找。之所以要把找到过的元素改为 -1，是为了避免在一个数组中出现了 2 次，但在另外一个数组中只出现一次的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* method 1 */
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        int m = nums1.size(), n = nums2.size();
        for(int i = 0; i < m; i++) {
            int tmp = nums1[i];
            for(int j = 0; j < n; j++) {
                if(tmp == nums2[j]) {
                    nums2[j] = -1;
                    ret.push_back(tmp);
                    break;
                }
            }
        }
        return ret;
    }
};

method 2

为了提高效率，不妨设置两个散列表，用来统计每个数组中数字的出现次数，接着再从散列表中挑出同时出现的数字即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        int ht1[1005] = {0}, ht2[1005] = {0};
        for(int i = 0; i < nums1.size(); i++) {
            ht1[nums1[i]]++;
        }
        for(int i = 0; i < nums2.size(); i++) {
            ht2[nums2[i]]++;
        }
        for(int i = 0; i < 1001; i++) {
            if(ht1[i] && ht2[i]) {
                int tmp = ht1[i] > ht2[i] ? ht2[i] : ht1[i];
                for(int j = 0; j < tmp; j++) {
                    ret.push_back(i);
                }
            }
        }
        return ret;
    }
};

但是这样用散列表不够聪明，应该可以只用一个散列表，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        int ht[1005] = {0};
        for(int i = 0; i < nums1.size(); i++) {
            ht[nums1[i]]++;
        }
        for(int i = 0; i < nums2.size(); i++) {
            if(ht[nums2[i]]) {
                ret.push_back(nums2[i]);
                ht[nums2[i]]--;
            }
        }
        return ret;
    }
};

这个题还有 3 个进阶提示：

  1. 给出的数组如果是排序的如何优化？
    如果是排序的，就可以用双指针了。换句话说，第一种解法就可以改成先排序，在遍历数组了。
  2. nums1 的容量小于 nums2 的容量，哪种方法更优？
    如果两个数组的容量大小差距过大，那么排序 + 双指针会更好一些。
  3. 内存无法一次性读取数组的元素，那种方法更优？
    显然散列更优。

121. Best Time to Buy and Sell Stock

Analysis

从问题的复杂性来看，这个题的题意还算简单。

Code

method 1

最先想到的永远是暴力解法，毫无疑问的超时了😂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size(), max = 0;
        vector<int> profit(size);
        for(int i = 0; i < size; i++) {
            int index = i, tmax = prices[i];
            for(int j = index + 1; j < size; j++) {
                if(tmax < prices[j]) {
                    tmax = prices[j];
                    index = j;
                }
            }
            if(index == i) profit[i] = -1;
            else profit[i] = prices[index] - prices[i];
            if(profit[i] > max) max = profit[i];
        }
        return max;
    }
};

暴力解法的思路是基于贪心的，不过好像还可以优化一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size(), ans = 0;
        for(int i = 0; i < size; i++) {
            for(int j = i + 1; j < size; j++) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};

method 2

容易发现，第 i 天的利润只与第 i 天之前的最低价有关。选择在不同的天数购买，最终会得到不同的利润结果，这种题目多半要用动态规划的思路。设置一个 dp 数组用来表示第 i 天之前的最低价，再设置一个变量 ans 来维护当前最大的利润。

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

这里，再利用滚动数组的思想来优化一下代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int days = prices.size(), ans = 0, minprice = prices[0];
        for(int i = 1; i < days; i++) {
            minprice = min(minprice, prices[i]);
            ans = max(ans, prices[i] - minprice);
        }
        return ans;
    }
};

Summary

虽然是两道简单题，但是考察的思想是很重要的思想。另外，动态规划的题目可真是灵活啊...还是题目做少了吗？😂

Buy me a coffee ? :)
0%