笔试强训 Day 19：小易的升级之路、礼物的最大价值、对称之美
小易的升级之路
解题思路：
处理题目输入，先读第一组 n，然后在循环中消耗 n 行 token，再判断是否有下一个 token；
计算最大公约数，在于辗转相除法：
48 ÷ 18 = 2 余 12 → 转为求 gcd(18, 12) 18 ÷ 12 = 1 余 6 → 转为求 gcd(12, 6) 12 ÷ 6 = 2 余 0 → 余数为0，除数 6 即为最大公约数。
代码实现：
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);while(sc.hasNext()){intn=sc.nextInt(),a=sc.nextInt();int[]b=newint[n];for(inti=0;i<n;i++)b[i]=sc.nextInt();System.out.println(count(a,b));}}privatestaticintcount(inta,int[]b){intcnt=a;for(inti=0;i<b.length;i++){intnum=b[i];if(cnt>=b[i])cnt+=b[i];else{intx=num,y=cnt;while(y!=0){inttmp=x%y;x=y;y=tmp;}cnt+=x;}}returncnt;}}礼物的最大价值
解题思路：
- 动态规划
代码实现：
importjava.util.*;publicclassSolution{publicintmaxValue(int[][]grid){intm=grid.length,n=grid[0].length;int[][]dp=newint[m+1][n+1];for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];}}returndp[m][n];}}对称之美
解题思路：
难在理解题目：给定一组字符串，需要从每个字符串中各选择一个字符，并按原来的行顺序组成一个新的字符串。判断是否存在一种选择方式，使得这个新字符串是回文串。
3 abc de cfa cdc Yes --- n = 3 ab c de .... No
代码实现：
importjava.util.*;importjava.io.*;publicclassMain{privatestaticReadin=newRead();privatestaticPrintWriterout=newPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticvoidmain(String[]args)throwsIOException{intt=in.nextInt();for(inti=0;i<t;i++){intn=in.nextInt();String[]strs=newString[n];for(intj=0;j<n;j++){strs[j]=in.next();}out.println(check(strs));}out.close();}privatestaticStringcheck(String[]str){booleanflag=true;for(intl=0,r=str.length-1;l<r;){int[]hash=newint[26];booleantFlag=false;for(charch:str[l].toCharArray()){hash[ch-'a']++;}for(charch:str[r].toCharArray()){tFlag|=(hash[ch-'a']>0);}flag=tFlag;if(!flag){return"No";}l++;r--;}return"Yes";}}classRead{StringTokenizerst=newStringTokenizer("");BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringline=bf.readLine();if(line==null)returnnull;st=newStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}