Algo_1

code c++ algo

學習算法

前言

  • 主要紀錄個人認為較為困難的題目

Leetcode 56

#include <bits/stdc++.h>
 
using namespace std;
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b)
             { return a[0] < b[0]; });
 
        vector<vector<int>> megred;
        vector<int> prev = intervals[0];
        for (int i = 1; i < intervals.size(); i++)
        {
            vector<int> interval = intervals[i];
            if (interval[0] <= prev[1])
            {
                prev[1] = max(prev[1], interval[1]);
            }
            else
            {
                megred.push_back(prev);
                prev = interval;
            }
        }
        megred.push_back(prev);
        return megred;
    }
};

Leetcode 238

#include <bits/stdc++.h>
using namespace std;
 
class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> pre(n);
        vector<int> suf(n);
        pre[0] = 1;
        suf[n - 1] = 1;
        for (int i = 1; i < n; i++)
        {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
 
        for (int i = n - 2; i >= 0; i--)
        {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        vector<int> ans(n);
        for (int i = 0; i < n; i++)
        {
            ans[i] = pre[i] * suf[i];
        }
        return ans;
    }
};