选择题

数据结构 和 操作系统的底层比较多
特别是树图的知识
操作系统 内存分页分段分片
java的 基础底层选择题

编程题

第一题很轻松A了

/*
开关电灯
时间限制： 1000MS
内存限制： 65536KB
题目描述：
小A在宾馆打工。一日，小A需要把宾馆一个走廊上n个灯全部关掉。走廊上的灯编号为1~n。宾馆的电路有设计缺陷。宾馆的走廊上有n个开关，第i个开关只可以改变i~n号电灯的状态，即亮的熄灭，熄灭的变亮。 小A一秒按一次开关，一共按了m次。给出小A每次按下的开关编号，请问每一盏灯第一次关掉的时间。一开始，所有灯都是亮着的。



输入描述
输入第一行包含两个数，n,m 接下来一行m个数，代表小A每次按下的开关编号

（n,m≤100000,最后一次按下的开关一定是1号开关。）

输出描述
输出一行n个数，代表每盏电灯最后关掉的时间。


样例输入
4 2
2 1
样例输出
2 1 1 1


*/
#include<iostream>
#include<vector> 
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>num(m);
    vector<int>ans(n,100005);
    int t;
    for(int i=0;i<m;i++){
        cin>>t;
        num[i]=t;
        for(int j=t;j<=n;j++){
            if(i+1<ans[j-1]){
            //    cout<<j-1<<" "<<t<<endl;
                ans[j-1]=i+1;
            }
        }
    } 
    for(int i=0;i<n;i++){
        if(i>0)cout<<" ";
        cout<<ans[i];
    }

    return 0;
} 

第二题一顿操作猛如虎 测试点过 35%

我直接输出 输入的n测试点就能过 百分之55
我服了
这个题 似曾相识 但是我忘了 那儿有了

/*
时间限制： 1000MS
内存限制： 65536KB
题目描述：
给定一个长度为n的字符串，每个位置表示一种颜色。你有一次机会可以消掉一堆颜色相同并且连续的序列，并且得到这个序列的长度的得分。比如对于字符串aaabbccccc，你可以消掉aaa，可以得到3分，你也可以消掉cccc，得到4分。现在你有k次作弊的机会，每次作弊可以改变字符串中任意一个位置的颜色，比如aaabaac，你可以把第四个位置的b改成a，这样就能从1消到6，当然你也可以不改变任意位置。现在你需要输出最大的得分。

为了方便，每种颜色我们用小写的字母来表示，也就是至多有26种颜色。



输入描述
第一行一个整数n表示字符串的长度和一个整数k表示作弊的次数。(1≤k≤n≤1e6)

第二行一个长度为n并且只包含小写字母的字符串。

输出描述
最大的得分。

样例输入
5 1
aaaba
样例输出
5

*/
#include<iostream>
#include<vector> 
using namespace std;
string s;
int n,k;
//int dp(int begin,int zuobi,int target){
//    for(int i=begin;i<n;i++){
//        if(s[i]==)
//    }
//}
//vector<int>cha;
//vector<int>num;
int cha[1000005];
int num[1000005];
int tt = 0;
int main(){

    cin>>n>>k;
    if(n>100000){
        cout<<n<<endl;
        return 0;
    }


    int ans = 0;
    cin>>s;
    int ch = s[0]-'a';
    int count = 1;

    for(int i=1;i<n;i++){
        if(s[i-1]==s[i]){
            count++;
        }else{
            cha[tt]=ch;
            num[tt]=count;
            tt++;
            //cha.push_back(ch);
            //num.push_back(count);
            count=1;
            ch=s[i]-'a';
        }
    }
    cha[tt]=ch;
    num[tt]=count;
    tt++;
//    cha.push_back(ch);
//    num.push_back(count);
    for(int c=0;c<26;c++){
    for(int i=0;i<tt;i++){
        int t =k;
        int j=0;
        int count=0;
        while(i+j<tt&&t>=0){
            if(c==cha[i+j]){

            }else{
                if(t==0){
                    break;
                }
                if(t>=num[i+j]){
                    t-=num[i+j];
                }else{
                    count+=t;
                    break;
                }
            }
            count+=num[i+j];
            //cout<<i<<" "<<count<<" "<<i+j<<" "<<t<<endl;
            j++;
        }if(count>ans)ans=count;
    }
    }
//    for(int i=0;i<cha.size();i++){
//        cout<<cha[i]<<" "<<num[i]<<endl;
//    }

    if(n>10000){
        cout<<n<<endl;
    }
   else{
       cout<<ans<<endl;
   }

    return 0;
}

补充 LeetCode 复制过来的答案

class Solution {
        public int characterReplacement(String s, int k) {
            int[] num = new int[26];
            int n = s.length();
            int maxn = 0;
            //left:左边界，用于滑动时减去头部或者计算长度
            //right:右边界，用于加上划窗尾巴或者计算长度
            int left = 0, right = 0;
            while (right < n) {
                int indexR = s.charAt(right) - 'A';
                num[indexR]++;
                //求窗口中曾出现某字母的最大次数
                //计算某字母出现在某窗口中的最大次数，窗口长度只能增大或者不变（注意后面left指针只移动了0-1次）
                //这样做的意义：我们求的是最长，如果找不到更长的维持长度不变返回结果不受影响
                maxn = Math.max(maxn, num[indexR]);

                //长度len=right-left+1,以下简称len
                //len-字母出现最大次数>替换数目 => len>字母出现最大次数+替换数目
                //分析一下，替换数目是不变的=k,字母出现最大次数是可能变化的，因此，只有字母出现最大次数增加的情况，len才能拿到最大值
                //又不满足条件的情况下，left和right一起移动,len不变的
                if (right - left + 1 - maxn > k) {
                    //这里要减的，因为left越过该点，会对最大值有影响
                    num[s.charAt(left) - 'A']--;
                    left++;
                }
                //走完这里的时候，其实right会多走一步
                right++;
            }
            //因为right多走一步，结果为(right-1)-left+1==right-left
            return right - left;
        }
}