Day19 丑数 + 构建乘积数组 + 队列的最大值

TODO:

1. 重新做一遍丑数独立思考
2. 重做一遍队列的最大值

剑指 Offer 49. 丑数(中等))

动态规划问题，没有做出来。
题解

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n+1,0);
        dp[0] = 1;
        int ia = 0, ib = 0,ic =0;
        for(int i = 1; i <n; i++){
            int a = dp[ia]*2;
            int b = dp[ib]*3;
            int c = dp[ic]*5;
            dp[i] = min(min(a,b),c);
            if(dp[i] == a)  ++ia;;
            if(dp[i] == b)  ++ib;
            if(dp[i] == c)  ++ic; 
        }
        return dp[n-1];
    }
};

剑指 Offer 66. 构建乘积数组(中等)

此题的考点在于不能用除法，以自己遍历两次得结果的方法来看是道简单题。题解的做法就比我少了一个数组的开辟，大体思路是一致的。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        if(n ==0) return {};
        vector<int> left(n,0);
        vector<int> right(n,0);
        left[0] = 1;
        right[n-1] = 1;
        for(int i = 1; i < n;i++){
            left[i] = left[i-1]*a[i-1];
            right[n-i-1] = right[n-i]*a[n-i];
        }
        vector<int> res(n,0);
        for(int i = 0; i <n; i++){
            res[i] = left[i] * right[i];
        }
        return res;

    }
};

题解的方法:

class Solution {
public:
   vector<int> constructArr(vector<int>& a) {
       int n = a.size();
       // 返回结果的计算
       vector<int> b(n, 1);
       // 从上到下，左下角的遍历
       for (int i = 1; i < n; ++i)
       {
           b[i] *= b[i-1] * a[i-1];
       }

       
       int accu = 1; // 累计乘积的结果，用于和b[i] 来计算
       // 从下到上，左上角的遍历
       for (int i = n-2; i >=0 ; --i)
       {
           accu *= a[i+1];
           b[i] *= accu;
       }

       return b;
   }
};

剑指 Offer 59 - II. 队列的最大值(中等)

题解跟之前滑动窗口维持最小/大值做法差不多。重点是对双端队列的使用，还有注意while不要写成if。

class MaxQueue {
public:
    queue<int> prim;
    deque<int> maxVal;
    
    MaxQueue() {
      
    }
    
    int max_value() {
        return maxVal.empty()? -1:maxVal.front();
    }
    
    void push_back(int value) {
        while(!maxVal.empty() && value > maxVal.back()){
             maxVal.pop_back();
        }
        prim.push(value);
        maxVal.push_back(value);
    }
    
    int pop_front() {
        if(prim.empty()) return -1;
        int val = prim.front();
        prim.pop();
        if(val == maxVal.front()){
        maxVal.pop_front();
        }
        return val ;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */