LeetCode日記20200218

LeetCode日記2020.2.18
文書ディレクトリ

LeetCode日記2020.2.18

723私のスケジュール

986区間リストの交差(mid)

442配列における重複データ(mid)

64最小経路および(mid)

238自身以外の配列の積(mid)

106中序と後序からシーケンスを遍歴して二叉木(mid)

を構築する

48回転画像(mid)

5配列+ 1ランダムmid + 1ランダムhard
723私のスケジュール(hard)
自分の遅い解法は、後でsetで自分に「重複データがあるかどうか」と聞いてみましょう.

class MyCalendarThree {
public:
    MyCalendarThree() {
        
    }
    
    int book(int start, int end) {
        calen.insert(make_pair(start, end));
        int res = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(const auto& c: calen)
        {
            while(!pq.empty() && pq.top() <= c.first)
            {
                pq.pop();
            }
            pq.push(c.second);
            res = max(res, int(pq.size()));
        }
        return res;
    }

    multiset<pair<int, int>> calen;
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(start,end);
 */

最適化後の高速解法:

class MyCalendarThree {
public:
    MyCalendarThree() {
        
    }
    
    int book(int start, int end) {
        if(calen.find(start) != calen.end())
            ++calen[start];
        else
            calen[start] = 1;

        if(calen.find(end) != calen.end())
            --calen[end];
        else
            calen[end] = -1;

        int res = 0;
        int k = 0;
        for(const auto& c: calen)
        {
            k += c.second;
            if(k>res)
                res = k;
        }
        return res;
    }

    map<int, int> calen;
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(start,end);
 */

986区間リストの交差(mid)
各リスト内の区間を用いて並べ替えられ、互いに交差しない性質に注意してください.

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res;
        int i=0, j=0;
        while(i<A.size()&&j<B.size())
        {
            if(A[i][0]<=B[j][1] && A[i][1]>=B[j][0])
                res.push_back(vector<int>{max(A[i][0], B[j][0]), min(A[i][1], B[j][1])});

            if(A[i][1] == B[j][1])
            {
                ++i;
                ++j;
            }
            else if(A[i][1]<B[j][1])
                ++i;
            else
                ++j;
        }
        return res;
    }
};

442配列の重複データ(mid)

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i=0;i<nums.size();++i)
        {
            int num = abs(nums[i]);
            if(nums[num-1]<0)
                res.push_back(num);

            nums[num-1] = -nums[num-1];
        }
        return res;
    }
};

64最小パスおよび(mid)

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid.front().size();
        vector<int> dp(n+1, 0);
        for(int i=n-1;i>=0;--i)
            dp[i] = dp[i+1] + grid[m-1][i];
        
        dp[n] = numeric_limits<int>::max();
        for(int i=m-2;i>=0;--i)
        {
            for(int j=n-1;j>=0;--j)
            {
                dp[j] = grid[i][j] + min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
    }
};

238自己以外の配列の積(mid)

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

106中序と後序からシーケンスを遍歴して二叉木(mid)を構築する

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    using Iter = vector<int>::const_iterator;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        reverse(postorder.begin(), postorder.end());
        return buildT(inorder.cbegin(), inorder.cend(), postorder.cbegin(), postorder.cend());
    }

    TreeNode* buildT(Iter inBeg, Iter inEnd, Iter pBeg, Iter pEnd)
    {
        if(pBeg == pEnd)
            return NULL;
        
        int val = *pBeg;
        TreeNode* root = new TreeNode(val);
        auto pos = find(inBeg, inEnd, val);
        int dis = inEnd - pos - 1;
        auto lpEnd = pBeg + 1;
        advance(lpEnd, dis);
        root->right = buildT(pos+1, inEnd, pBeg + 1, lpEnd);
        root->left = buildT(inBeg, pos, lpEnd, pEnd);
        return root;
    }
};

48回転画像(mid)

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n;++i)
        {
            for(int j=i;j<n;++j)
            {
                std::swap(matrix[i][j], matrix[j][i]);
            }
        }
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n/2;++j)
            {
                std::swap(matrix[i][j], matrix[i][n-1-j]);
            }
        }
    }
};