1.求一个字符串最少修改多少次能变成回文串
只过了30%,用的dp,内存超出了,请问还有更好的做法吗?显示的是字符串长度n<100时的测试数据是30%,n<10000时的测试数据是100%。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String str = in.next(); int[][] dp = new int[n][n]; for (int i = n - 2; i >= 0 ; i--) { for (int j = i + 1; j < n; j++) { if(str.charAt(i) == str.charAt(j)){ dp[i][j] = dp[i+1][j-1]; } else{ dp[i][j] = dp[i+1][j-1] + 1; } } } System.out.print(dp[0][n-1]); }2.一个m*n的方块,种花,每个方块必须有花,每种花的个数必须相等,每个相邻方块的花的种类必须不同,满足这三个条件,求最少的花的种类。
没做。求做法
3.一个数组,求它的连续子数组的或运算取得最大值时,这个连续子数组的长度是多少?
也是用的dp,又是内存超出,只过了50%,菜鸡落泪。
4.没看,图类型的。
全部评论
(5) 回帖