算法和c++类面经

改进以下类

struct MyStruct{
    int a;
    double b;
    uint64_t c;
}

class MyClass{
public:
    explicit MyClass(std::vector<MyStruct> && _val) : val(_val) {};
protected:
    std::vector<MyStruct> val;
}

有两处要修改，一个内存对齐，把b放最前面；另外一个是val(_val)改为val(std::move(_val))

vector的resize和reserve的区别

1. reserve() 函数用于预先分配一定数量的内存空间，以容纳指定数量的元素，但并不改变 vector 的实际大小（即元素数量）。 仅影响容量（capacity），不影响大小（size）。不会初始化元素，也不会调用元素的构造函数。 如果 new_cap 小于等于当前容量，则 reserve() 不做任何操作。主要用于优化性能，减少因多次动态分配内存导致的开销。
2. resize() 函数用于改变 vector 的大小（size），即元素的数量。根据新的大小，vector 会增加或减少元素。 当新的大小大于当前大小时：vector 会增加新的元素，并对新元素进行默认初始化（或使用提供的 value 初始化）。如果新的大小超过当前容量（capacity），vector 会重新分配内存。 当新的大小小于当前大小时：vector 会删除多余的元素，调用它们的析构函数。 可能会改变容量，如果新的大小超过当前容量，vector 会自动扩容：如果 vector 之前已经包含元素，需要将这些元素从旧的内存区域移动或复制到新的内存区域。对于支持移动语义的元素类型（即具有移动构造函数），元素将被移动到新内存区域。如果元素类型不支持移动构造函数，但支持复制构造函数，元素将被复制到新内存区域。在成功分配新内存并移动/复制元素后，vector 会释放旧的内存空间。

题1

Point是两个浮点数pnl,drawdown的tuple，A是一个包含N个Point的List，求出所有处于efficient frontier上的Point， Point x处于efficient frontier上当且仅当A中不存在其他的Point y使得y.pnl > x.pnl 并且 y.drawdown < x.drawdown.

struct Point {
    double pnl;
    double drawdown;
    Point(double p, double d) : pnl(p), drawdown(d) {}
};

// 比较函数，用于排序
bool compare(const Point& a, const Point& b) {
    if (a.pnl != b.pnl) {
        return a.pnl > b.pnl; // pnl 从大到小排序
    } else {
        return a.drawdown < b.drawdown; // drawdown 从小到大排序
    }
}

std::vector<Point> findEfficientFrontier(const std::vector<Point>& points) {
    // 复制一份数据，避免修改原始数据
    std::vector<Point> sorted_points = points;

    // 按照定义的规则排序
    std::sort(sorted_points.begin(), sorted_points.end(), compare);

    std::vector<Point> efficient_frontier;
    double min_drawdown = std::numeric_limits<double>::infinity();

    for (const auto& point : sorted_points) {
        if (point.drawdown < min_drawdown) {
            efficient_frontier.push_back(point);
            min_drawdown = point.drawdown;
        }
    }

    return efficient_frontier;
}

最小子序和

int MaxSubsequenceSum (const int A[], int N)
{
    int ThisSum, MaxSum;
    ThisSum = MaxSum = 0; 
    
    for(int i = 0; i != N; ++i){ 
        ThisSum += A[i];
        if(MaxSum > ThisSum)
            MaxSum = ThisSum;
        else if(ThisSum > 0)
            ThisSum = 0;
    }
    return MaxSum;
    }

最大子序列乘积

int maxProduct(const vector<int>& nums) {
    if (nums.empty()) return 0;

    int max_ending_here = nums[0];
    int min_ending_here = nums[0];
    int max_so_far = nums[0];

    for (size_t i = 1; i < nums.size(); ++i) {
        int temp_max = max_ending_here;
        int temp_min = min_ending_here;

        if (nums[i] < 0) {
            swap(temp_max, temp_min);
        }

        max_ending_here = max(nums[i], temp_max * nums[i]);
        min_ending_here = min(nums[i], temp_min * nums[i]);

        max_so_far = max(max_so_far, max_ending_here);
    }

    return max_so_far;
}

• 面经