当前位置：首页 > article >正文

刷爆leetccode Day5

article 2024/10/23 3:41:49

leetcode

21. ⼭峰数组的峰顶（easy）
22. 寻找峰值（medium）
23. 搜索旋转排序数组中的最小值（medium）
24. 0〜n-1中缺失的数字（easy）
25. 【模板】⼀维前缀和（easy）

21. ⼭峰数组的峰顶（easy）

题目

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
     //端点是上升得来的
     //因此端点应该在左区间
     //左端点的左区间小于等于左端点
     //左端点的右区间大于左端点
     int left=0,right=arr.size()-1;
     while(left<right)
     {
        int mid=left+(right-left+1)/2;
        if(arr[mid]>=arr[mid-1])
        left=mid;
        else
        right=mid-1;
     }
     return right;   
    }
};

22. 寻找峰值（medium）

题目

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]>=nums[mid-1])
            left=mid;
            else right=mid-1;
        }
        return left;
    }
};

23. 搜索旋转排序数组中的最小值（medium）

题目

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left=0,right=nums.size()-1,target=nums[nums.size()-1];
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>target)
            left=mid+1;
            else
            right=mid;
        }
        return nums[right];
    }
};

24. 0〜n-1中缺失的数字（easy）

题目

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left=0,right=records.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(records[mid]==mid)
            left=mid+1;
            else
            right=mid;
        }
        return records[right]==right?right+1:right;
    }
};

25. 【模板】⼀维前缀和（easy）

题目

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,q;
    cin>>n>>q;
    vector<int>v(n+1,0);
    for(int i=1;i<n+1;i++)
    cin>>v[i];
    vector<long long>dp(n+1,0);//防止溢出
    for(int j=1;j<n+1;j++)
    dp[j]=dp[j-1]+v[j];//下标从1开始保证等式成立，数组大小应为n+1
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")