头像

fjiaotang

七中英才学校




离线:2天前


最近来访(2236)
用户头像
AcWing2AK
用户头像
Semion
用户头像
00001
用户头像
摸鱼_
用户头像
铁锅炖大鹅
用户头像
LeftBracket
用户头像
乘湘去
用户头像
Baily1234
用户头像
GI_001
用户头像
peak
用户头像
古今无不同
用户头像
夏艺菲
用户头像
TonyStank
用户头像
jiayou
用户头像
RainSure
用户头像
开始_7
用户头像
一万小时定律
用户头像
我复往矣
用户头像
带带大雪莱
用户头像
Quinn

活动打卡代码 LeetCode 28. 实现 strStr()

fjiaotang
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 28. 实现 strStr()

fjiaotang
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



fjiaotang
5个月前

题目描述

给定一个大小为n≤106n≤106的数组。

有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为[1 3 -1 -3 5 3 6 7],k为3。
不会写Markdown的表格,所以请自行看题目

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式
输入包含两行。

第一行包含两个整数n和k,分别代表数组长度和滑动窗口的长度。

第二行有n个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式
输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

样例

输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7

算法1

(单调队列)

单调队列模拟滑动窗口(百万级别数据最好用scanf和printf)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int a[N],q[N],hh,tt=-1;
int main()
{
    int n,k;
    cin >> n>>k;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        //cin>>a[i];
        if(i-k+1>q[hh]) ++hh;
        while(hh<=tt&&a[i]<=a[q[tt]]) tt--;//当进入的元素较小,前面的较大的元素直接出队
        q[++tt]=i;//存下标(千万不能忘)
        if(i+1>=k) printf("%d ",a[q[hh]]);//找完直接输出
    }
/*
分开找最大和最小
*/
    cout<<endl;
    hh=0,tt=-1;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        if(i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[i]>=a[q[tt]]) tt--;//当进入的元素较大,前面的较小的元素直接出队
        q[++tt]=i;//存下标(千万不能忘)
        if(i+1>=k) printf("%d ",a[q[hh]]);//找完直接输出
    }
    return 0;
}



fjiaotang
5个月前

题目描述

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。

例如,如果输入数组 [2,3,4,2,6,2,5,1]
及滑动窗口的大小 3
,那么一共存在 6
个滑动窗口,它们的最大值分别为 [4,4,6,6,6,5]

注意:

数据保证 k
大于 0
,且 k
小于等于数组长度。
数据范围

数组长度 [1,1000]

样例

输入:[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

算法1

(单调队列)

通过单调队列来模拟滑动窗口,寻找最大值。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;//储存答案
        int q[100010];//模拟队列
        int hh=0,tt=-1;//队列中的头和尾 
        for(int i=0;i<nums.size();i++)
        {
            if(hh<=tt&&i-q[hh]>=k)//队头是否在窗口中
                hh++;
            while(hh<=tt&&nums[q[tt]]<nums[i])//较大元素入队
                tt--;//较小元素出队
            q[++tt]=i;//i入队
            if(i>=k-1)
                ans.push_back(nums[q[hh]]);
        }
        return ans;
    }
};


活动打卡代码 AcWing 808. 最大公约数

fjiaotang
5个月前
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    int ans;
    for(int i=1;i<=max(a,b)-min(a,b);i++)
    {
        if(a%i==0&&b%i==0)
        ans=i;
    }
    return ans;
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
}


活动打卡代码 AcWing 807. 区间求和

fjiaotang
5个月前
#include<bits/stdc++.h>
using namespace std;
int ans;
int sum(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        ans+=i;
    }
    return ans;
}
int main()
{
    int l,r;
    cin>>l>>r;
    cout<<sum(l,r);
}


活动打卡代码 AcWing 806. 两个数的和

fjiaotang
5个月前
#include<bits/stdc++.h>
using namespace std;
double add(double x,double y)
{
    double ans;
    ans=x+y;
    return ans;
}
int main()
{
    double a,b;
    cin>>a>>b;
    printf("%.2lf",add(a,b));
}


活动打卡代码 AcWing 805. x和y的最大值

fjiaotang
5个月前
#include<iostream>
using namespace std;
int a,b;
int maxn(int x,int y)
{
    if(x>y)
    cout<<x;
    if(x<y)
    cout<<y;
}
int main()
{
    int x,y;
    cin>>x>>y;
    maxn(x,y);
    return 0;
}


// #include<iostream>
// using namespace std;
// int main()
// {
//     int a,b,c;
//     cin>>a>>b;
//     c=max(a,b);
//     cout<<c;
//     return 0;
// }


活动打卡代码 AcWing 804. n的阶乘

fjiaotang
5个月前
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,ans=1;
    cin>>a;
    for(int i=a;i>=1;i--)
    {
        ans*=i;
    }
    cout<<ans;
}



fjiaotang
5个月前
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    while(cin >> n, n)
    {
        string s, a;
        int MAX = 999999;
        cin >> s;
        for(int i = 1; i < n; ++ i)
        {
            int res = 0;
            cin >> a;
            for(int j = 0; j < a.size() && j < s.size(); ++ j)
                if(a[a.size() - 1 - j] == s[s.size() - 1 - j]) res++;
                else break;
            MAX = min(MAX, res);
        }
        if(MAX) cout << s.substr(s.size()-MAX) << endl;
        else cout << endl;
    }
    return 0;
}