第一题直接排序,这里就不贴代码了
第二题 我的理解是从后往前找最长回文子串,写了两个辣鸡解法,a了64%
import java.util.Arrays; import java.util.Scanner; /** * description: * author:zt * date:2021-08-15 */ public class A { public static void main(String[] args) { Scanner in = new Scanner(System.in); String text = in.next(); System.out.println(solve2(text)); } //判断原字符串是不是回文 //不是 在判断该字符串结尾的最长回文子串是多长 public static int solve(String text){ // char[] c = text.toCharArray(); int n = text.length(); int[][] dp = new int[n][n]; for (int i = n-1; i >= 0; i--) { dp[i][i] = 1; for (int j = i+1; j < n; j++) { if (text.charAt(i)!=text.charAt(j)) dp[i][j] = -1; //不能构成回文 else { if (j-i<=2) dp[i][j] = j-i+1; else { if (dp[i+1][j-1]!=-1) dp[i][j] = dp[i+1][j-1]+2; else dp[i][j] = -1; } } } } int max = 0; for (int i = 0; i < n; i++) { if (dp[i][n-1]>max) max = dp[i][n-1]; } return n-max; } public static int solve2(String text){ if (check(text)) return 0; StringBuilder sb = new StringBuilder(); StringBuilder sb2 = new StringBuilder(); sb.append(text); for (int i = 1; i <= text.length(); i++) { String s = text.substring(0, i); String s1 = sb2.append(s).reverse().toString(); sb.append(s1); if (check(sb.toString())) return i; sb = new StringBuilder(); sb2 = new StringBuilder(); } return text.length(); } public static boolean check(String text){ int L=0, R=text.length()-1; while (L<R){ if (text.charAt(L)!=text.charAt(R)) return false; L++; R--; } return true; } }第三题两个list分别统计将往右走和往左走的节点,然后排序。两层遍历统计会相遇的最近的两个节点
import java.util.*; /** * description: * author:zt * date:2021-08-15 */ public class B { public static void main(String[] args) { Scanner in = new Scanner(System.in); int count = in.nextInt(); ArrayList<Integer> left = new ArrayList<>(); ArrayList<Integer> right = new ArrayList<>(); Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < count; i++) { int index = in.nextInt(); String dir = in.next(); if (dir.equals("R")) right.add(index); else left.add(index); map.put(index,i); } for (int i : solve(left, right, map)) { System.out.println(i); } } //right向右走 left向左走 public static int[] solve(ArrayList<Integer> left,ArrayList<Integer> right,Map<Integer,Integer> map){ int l=left.size(), r=right.size(); int len = left.size()+right.size(); int[] res = new int[len]; for (int i = 0; i < res.length; i++) { res[i] = -1; } Collections.sort(left); Collections.sort(right); for (int i = right.size()-1; i >= 0; i--) { if (right.get(i)>left.get(l-1)) { Integer index = map.get(right.get(i)); res[index] = -1; } int target = -1; for (int j = left.size()-1; j >= 0; j--) { if (left.get(j)==Integer.MAX_VALUE) continue; else if (left.get(j)>right.get(i) && (left.get(j)-right.get(i))%2==0){ target = left.get(j); } } if (target!=-1) { int tmp1 = map.get(right.get(i)); int tmp2 = map.get(target); int tmp3 = (target-right.get(i))/2; res[tmp1] = tmp3; res[tmp2] = tmp3; left.set(left.indexOf(target),Integer.MAX_VALUE); } else res[map.get(right.get(i))] = -1; } return res; } }第四题放弃了....直接看第五题,动态规划(类似跳台阶)
import java.util.Scanner; /** * description: * author:zt * date:2021-08-15 */ public class C { public static void main(String[] args) { Scanner in = new Scanner(System.in); int count = in.nextInt(); int maxJump = in.nextInt(); int[] take = new int[maxJump]; String s = in.next(); for (int i = 0; i < maxJump; i++) { take[i] = in.nextInt(); } //take[i-1]表示跳i格 int solve = solve(s.toCharArray(), take, s.length()); System.out.println(solve); } public static int solve(char[] c,int[] take,int n){ int[] dp = new int[n]; for (int i = 0; i < dp.length; i++) { if (c[i]=='x') dp[i] = -1; else dp[i] = Integer.MAX_VALUE; } dp[0] = 0; for (int i = 1; i < c.length; i++) { if (c[i]=='o'){ for (int j = take.length; j > 0; j--) { if (i>=j) { if (dp[i-j]!= -1) dp[i] = Math.min(dp[i],dp[i-j]+take[j-1]); } } } } return dp[n-1]; } }
全部评论
(5) 回帖