笔试强训 Day 10：最长回文子串、买卖股票的最好时机(一)、过河卒

Day 10最长回文子串动态规划思考状态转移方程i 从后往前遍历j 从 i 往后遍历确保只对 i j 填表分别判断 i j, i 1 j, 以及其他情况publicclassSolution{/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param A string字符串 * return int整型 */publicintgetLongestPalindrome(StringA){char[]chA.toCharArray();intret0,nch.length;boolean[][]dpnewboolean[n][n];// dp[i][j] dp[i1][j-1] (ch[i] ch[j])for(intin-1;i0;i--){for(intji;jn;j){if(ij)dp[i][j]true;elseif(i1j)dp[i][j]ch[i]ch[j];elsedp[i][j]dp[i1][j-1]ch[i]ch[j];if(dp[i][j])retMath.max(ret,j-i1);}}returnret;}}中心扩散法枚举每一个中心点左右指针同时处理以一个点为中心点和以两个点为中心点的情况扩散至非回文字符串更新 ret注意此时 l , r 在非回文字符串范围使用 (r-l1)-2 更新回文串最大值importjava.util.*;publicclassSolution{/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param A string字符串 * return int整型 */publicintgetLongestPalindrome(StringA){char[]chA.toCharArray();intret0,nch.length;for(inti0;in;i){intli-1,ri1;while(l0rnch[l]ch[r]){l--;r;}retMath.max(ret,r-l-1);li-1;ri;while(l0rnch[l]ch[r]){l--;r;}retMath.max(ret,r-l-1);}returnret;}}买卖股票的最好时机(一)dp - 贪心算法dp 思路dp[i] 表示第 i 天卖出股票找 i - 1 天的最小值更新 ret 最大值贪心优化第 i 天卖出股票维护 i - 1 天的最小股票价格轻松计算出第 i 天卖出股票的最大利润更新 ret 最大值importjava.util.*;importjava.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();int[]pricenewint[n];for(inti0;in;i)price[i]in.nextInt();intret0,minprice[0];for(inti1;in;i){retMath.max(ret,price[i]-min);minMath.min(min,price[i]);}System.out.println(ret);}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}过河卒动态规划 路径问题注马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 ∣x1−x∣∣y1−y∣3且x1≠x,y1≠y ∣x1−x∣∣y1−y∣3且x1\x,y1\y数据范围 1≤n,m≤20 1≤n,m≤20 马的坐标 0≤x,y≤20 0≤x,y≤201≤a,b,c,d≤1000 1≤a,b,c,d≤1000重点根据当前坐标以及马锁定的坐标进行坐标计算的位置判断来更新 dp 表初始化过程m 1, n 1实际需要的是一张dp[m1][n1]的表为了处理状态状态方程越界问题使用dp[m2][n2]的表路径总数可能会溢出 int 范围dp 表使用 long 类型importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{privatestaticintx0;privatestaticinty0;publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intmin.nextInt(),nin.nextInt();xin.nextInt()1;yin.nextInt()1;long[][]dpnewlong[m2][n2];dp[0][1]1;for(inti1;im1;i){for(intj1;jn1;j){if(check(i,j))dp[i][j]0;elsedp[i][j]dp[i-1][j]dp[i][j-1];}}System.out.println(dp[m1][n1]);}privatestaticbooleancheck(inti,intj){if(xiyj)returntrue;if((Math.abs(i-x)Math.abs(j-y)3)(x!iy!j))returntrue;returnfalse;}}