笔试强训 Day 11：游游的水果大礼包、买卖股票的最好时机(二)、倒置字符串

Day 11游游的水果大礼包解题思路直接枚举其中一个礼包的所有可能数量可以在 O(n) 内计算出价值最高的礼包组合注意使用贪心算价值更大的礼包最大数量下的组合并不能算出最大价值礼盒如100,100,100,101使用贪心得到的结果50 个二号礼包 50 * 101 5050最优解是 33 *100 33 * 101 6633importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);longnin.nextLong(),min.nextLong(),ain.nextLong(),bin.nextLong();System.out.println(cnt(n,m,a,b));}privatestaticlongcnt(longn,longm,longa,longb){longret0;for(longi0;iMath.min(n/2,m);i){longappn-i*2;longpeam-i;retMath.max(ret,i*aMath.min(app,pea/2)*b);}returnret;}}买卖股票的最好时机(二)动态规划定义状态表示f[i], g[i]分别为在 i 天买入卖出的最大收益在遍历数组的过程中不断通过各自的情况更新对应的表注意初始化问题g[1] 表示第一天卖出不可能所以是 0f[1] 表示第一天买入所以是 -num[1]importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();int[]numsnewint[n1];for(inti1;in;i)nums[i]in.nextInt();// 在 i 天买入、卖出的最大收益int[]fnewint[n1];int[]gnewint[n1];f[1]-nums[1];for(inti2;in;i){f[i]Math.max(f[i-1],g[i-1]-nums[i]);g[i]Math.max(g[i-1],f[i-1]nums[i]);}System.out.println(g[n]);}}贪心当前股票售价比前一支高就减去他们的差值1 2 3结果 3 - 1 (2-1) (3-2)importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();int[]numsnewint[n1];for(inti1;in;i)nums[i]in.nextInt();intret0;// 1 2 3for(inti2;in;i){intpnums[i]-nums[i-1];if(p0)retp;}System.out.println(ret);}}倒置字符串用列表手机字符串再反转列表最后拼接为字符串即可importjava.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);ListStringlistnewArrayList();while(in.hasNext())list.add(in.next());Collections.reverse(list);System.out.println(String.join( ,list));}}