当前位置:   article > 正文

48天笔试训练错题——day20

48天笔试训练错题——day20

目录

选择题

1.

2.

编程题

1. 公共子串计算


选择题

1.

访问节点一般是用下标访问,所以是 O(1),增加节点考虑的是最坏的情况,在数组的头部增加节点,需要往后挪动元素。

2.

编程题

1. 公共子串计算

代码实现:

  1. import java.util.Scanner;
  2. // 注意类名必须为 Main, 不要有任何 package xxx 信息
  3. public class Main {
  4. public static void main(String[] args) {
  5. Scanner in = new Scanner(System.in);
  6. // 注意 hasNext 和 hasNextLine 的区别
  7. while (in.hasNextLine()) { // 注意 while 处理多个 case
  8. String a = in.nextLine();
  9. String b = in.nextLine();
  10. int ret = 0;
  11. if (a.length() > b.length()) {
  12. ret = getStr(b, a);
  13. } else {
  14. ret = getStr(a, b);
  15. }
  16. System.out.println(ret);
  17. }
  18. }
  19. // 假设 a 是短串,b 为长串
  20. public static int getStr(String a, String b) {
  21. // 可以用动态规划来做
  22. int la = a.length();
  23. int lb = b.length();
  24. // a 和 b 的最长公共子串长度
  25. int maxLen = 0;
  26. int ia = -1;// 记录结束下标
  27. int ib = -1;
  28. // 多初始化是为了避免越界
  29. int[][] dp = new int[la + 1][lb + 1];
  30. for (int i = 1; i <= la; i++) {
  31. for (int j = 1; j <= lb; j++) {
  32. char ca = a.charAt(i - 1);
  33. char cb = b.charAt(j - 1);
  34. // 如果 a 的 i 下标字符 和 b 的 j 下标字符相同,则更新
  35. if (ca == cb) {
  36. dp[i][j] = dp[i - 1][j - 1] + 1;
  37. // 更新 maxLen
  38. if (dp[i][j] > maxLen) {
  39. ia = i;
  40. ib = j;
  41. maxLen = dp[i][j];
  42. }
  43. }
  44. }
  45. }
  46. return maxLen;
  47. }
  48. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/864380
推荐阅读
相关标签
  

闽ICP备14008679号