2021-04-09

1. Best Time to Buy and Sell Stock

首先是一道ez题，用到了一点DP的思想。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty() || prices.size()<2) return 0;
        int minpri = prices[0];
        int maxpro = 0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]>prices[i-1])
                maxpro = max(maxpro, prices[i]-minpri);
            
            else{
                minpri = min(minpri, prices[i]);
            }
        }
        return maxpro;
    }
};

2. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

乍一看就是数组中返回除了自己以外其他数相乘，题目要求tc=o(n), sc=o(1)

• 首先初始化一个res数组，其中res[i]就是nums[i]前面i-1个数的乘积（nums[i]左边所有数的乘积）
• 接下来显然是要将nums[i]右边的数全乘上去，结果保存在res中

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int N = nums.size();
        vector<int> res(N,1);
        for(int i = 1; i<N; i++){
            res[i] = res[i-1] * nums[i-1];
        }
        
        int prod = 1;
        for(int i = N-1; i>=0; i--){
            res[i] *= prod;
            prod *= nums[i];
        }
        
        return res;
    }
};

3.Subsets

本题打算采用两种解题思路

a.迭代法

无需多言，直接上代码。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int N = nums.size(); 
        vector<vector<int>> ans;
        ans.push_back({});
        for (int i = 0; i < N; i++){
            int sz = ans.size();
           
            for(int j = 0; j < sz; j++){
                vector<int> temp = ans[j];
                temp.push_back(nums[i]);
                ans.push_back(temp);
            }
        }
        return ans;
    }
};

b. 位掩码法

首先，关于位掩码的简单介绍可以参考博客：https://www.jianshu.com/p/4e73512c03b8
我个人还是觉得挺好用的，至少理解和记忆可能会比迭代法ez一点。

class Solution {
public:
    vector<int> findsubset(int n, vector<int>& nums){
        vector<int> sub;
        int i = 0;
        while(n){
            if(n&1)
                sub.push_back(nums[i]);
            n = n>>1;
            i++;
        }
        return sub;
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        int total = 1<<nums.size();
        for(int i = 0; i < total; i++){
            ans.push_back(findsubset(i, nums));
        }
        return ans;
    }
};