2767. 将字符串分割为最少的美丽子字符串

发表于 分类于 阅读次数： Waline： 本文字数： 308 阅读时长 ≈ 1 分钟

考点

  • 划分DP

思路

将一个数组拆分为若干个连续的子数组，那么以当前数字为其子数组的结尾，向前枚举即可，枚举的过程中判定是否为5的幂次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  bool judge(string s) {
    if (s[0] == '0') return 0;
    int x = 0;
    for (char& chr : s) x = x * 2 + (chr - '0');
    while (x % 5 == 0) x /= 5;
    return x == 1;
  }
  int minimumBeautifulSubstrings(string s) {
    // 加哨兵，方便下标处理
    int n = s.size();
    s = "0" + s;
    // DP
    int f[20];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j >= 1; --j) {
        if (judge(s.substr(j, i - j + 1))) f[i] = min(f[i], f[j - 1] + 1);
      }
    }
    return f[n] == inf ? -1 : f[n];
  }
};

当然，也可以提前打表，不过在力扣模式下没多大帮助：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int minimumBeautifulSubstrings(string s) {
    // 加哨兵，方便下标处理
    int n = s.size();
    s = "0" + s;
    // 打表，2^15 - 1以内的5的幂次
    unordered_set<int> st;
    for (int i = 1; i < (1 << 15); i *= 5) st.emplace(i);
    // DP
    int f[20];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int sum = 0, p = 1;
      for (int j = i; j >= 1; --j) {
        sum += (s[j] - '0') * p;
        p <<= 1;
        if (s[j] == '0') continue;
        if (st.find(sum) != st.end()) f[i] = min(f[i], f[j - 1] + 1);
      }
    }
    return f[n] == inf ? -1 : f[n];
  }
};