2021.02.27 剪绳子

今日题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
image.pngimage.png
提示：2 <= n <= 58

  • 思路：

  • 自己的菜鸡代码：

    1. class Solution {
    2.   public int cuttingRope(int n) {
    3.       if(n < 2) return 0;
    4.       if(n == 2) return 1;
    5.       if(n == 3) return 2;
    7.       int[] rec = new int[n+1];
    8.       rec[0] = 0;
    9.       rec[1] = 1;
    10.       rec[2] = 2;
    11.       rec[3] = 3;
    13.       int max;
    14.       for(int i = 4; i <= n; i++){
    15.           max = 0;
    16.           for(int j = 1; j <= i/2; j++){
    17.               if(rec[j]*rec[i-j] > max){
    18.                   max = rec[j]*rec[i-j];
    19.               }
    20.           }
    21.           rec[i] = max;
    22.       }
    23.       return rec[n];
    24.   }
    25. }

  • 运行结果：

image.png

2021.02.14 正则表达式匹配（未做，好难）

今日题目：请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。
image.pngimage.pngimage.pngimage.png
image.png

  • s 可能为空，且只包含从 a-z 的小写字母。

  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘‘。

  • 思路：非确定有限状态自动机

  • 自己的菜鸡代码：
  • 运行结果：