美文网首页
Day19 丑数 + 构建乘积数组 + 队列的最大值

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

作者: 吃掉夏天的怪物 | 来源:发表于2021-07-01 11:34 被阅读0次

    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();
     */
    

    相关文章

      网友评论

          本文标题:Day19 丑数 + 构建乘积数组 + 队列的最大值

          本文链接:https://www.haomeiwen.com/subject/ryipyltx.html