笔试强训 Day 16：字符串替换 + 神奇数 + DNA 序列
Day 16
字符串替换
解题思路：
- 当遍历到 % 时，将字符数组的参数拼接，同时将标记位设为 true
- 当标记为 true，说明上一个是 %，做一个是 s，无需再次拼接，标记位恢复为 false
代码实现：
importjava.util.*;publicclassStringFormat{publicStringformatString(StringA,intn,char[]arg,intm){intindex=0;booleanflag=false;StringBuildersb=newStringBuilder();for(inti=0;i<A.length();i++){charch=A.charAt(i);if(ch=='%'){flag=true;sb.append(arg[index++]);}elseif(flag){flag=false;}else{sb.append(ch);}}while(index<arg.length){sb.append(arg[index++]);}returnsb.toString();}}神奇数
解题思路：
可以精简成这样：
- 枚举区间
[a, b]中的每个整数，判断其是否为神奇数，若是则计数加一。 - 对每个整数转成字符串，使用双重循环枚举两个不同位置的数位，分别作为十位和个位。
- 若十位为
0，说明存在前导零，跳过；若两个位置相同，也跳过。 - 将两个数位组成两位数，并判断其是否为质数。
- 质数判断：从
2枚举到sqrt(n)，可以通过 i * i <= n 判断，若存在因子能整除n，则不是质数；否则是质数。 - 只要找到一个满足条件的两位质数，该整数就是神奇数。
代码实现：
// 存在不同位置的两个数位，组成一个两位数（且不含前导0）// 这个两位数为质数// 只要找到一个质数即满足神奇数// 输入为两个整数a和b，代表[a, b]// 输出为一个整数，表示区间内满足条件的整数个数// 11 13 14 16 17 18importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);inta=sc.nextInt();intb=sc.nextInt();intcount=0;for(intnum=a;num<=b;num++){if(isMagic(num)){count++;}}System.out.println(count);}publicstaticbooleanisMagic(intnum){Strings=String.valueOf(num);for(inti=0;i<s.length();i++){for(intj=0;j<s.length();j++){if(i==j)continue;inttens=s.charAt(i)-'0';intones=s.charAt(j)-'0';// 两位数不能有前导 0if(tens==0)continue;intvalue=tens*10+ones;if(isPrime(value)){returntrue;}}}returnfalse;}publicstaticbooleanisPrime(intn){if(n<2)returnfalse;for(inti=2;i*i<=n;i++){if(n%i==0){returnfalse;}}returntrue;}}DNA 序列
解题思路
- 滑动窗口，找到所有长度为 N 的 DNA 子序列，找到最大的 GC-Ratio 的第一个；
- 认真读一遍题目，把重要的信息列出来即可
代码实现：
// 由 A/C/G/T 四个字母的排列组合组成// G 和 C 的比例 : GC-Ratio = (nG + nC) / nSum// 在序列中, 从左往右, 找出 GC-Ratio 最高, 且长度为 N 的第一个子串// ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);Stringstr=in.next();intn=in.nextInt();char[]chs=str.toCharArray();intlen=0,retl=0;Doublegc=0.0,gcr=0.0;for(intl=0,r=0;r<chs.length;r++){charinput=chs[r];if(input=='G'||input=='C'){gc++;}len=r-l+1;while(len==n){if(gcr<gc/n){gcr=gc/n;retl=l;}charoutput=chs[l++];if(output=='G'||output=='C'){gc--;}len=r-l+1;}}System.out.println(str.substring(retl,retl+n));}}