本文主要是介绍21/04/11度小满笔经,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
选择题
数据结构 和 操作系统的底层比较多
特别是树图的知识
操作系统 内存分页分段分片
java的 基础底层选择题
编程题
第二题是 LeetCode原题 424. 替换后的最长重复字符
https://leetcode-cn.com/problems/longest-repeating-character-replacement/
那大家岂不是都AC了我可能 凉透了
第一题很轻松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-leftreturn right - left;}
}
「滑动窗口」是一类使用「双指针」技巧,通过两个变量在数组上同向交替移动解决问题的算法。这一类问题的思考路径通常是:先思考暴力解法,分析暴力解法的缺点(一般而言暴力解法的缺点是重复计算),然后 结合问题的特点,使用「双指针」技巧对暴力解法进行剪枝。因此,思考算法设计的合理性是更关键的,这一点适用于所有算法问题。
作者:LeetCode
链接:https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/ti-huan-hou-de-zui-chang-zhong-fu-zi-fu-eaacp/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
这篇关于21/04/11度小满笔经的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!