• Leetcode 第 108 場雙周賽 Problem C 將字符串分割為最少的美麗子字符串（動態(tài)規(guī)劃）
• 題目
  • 給你一個二進(jìn)制字符串 s ，你需要將字符串分割成一個或者多個 子字符串 ，使每個子字符串都是 美麗 的。
  • 如果一個字符串滿足以下條件，我們稱它是 美麗 的：
    • 它不包含前導(dǎo) 0 。
    • 它是 5 的冪的 二進(jìn)制 表示。
  • 請你返回分割后的子字符串的 最少 數(shù)目。如果無法將字符串 s 分割成美麗子字符串，請你返回 -1 。
  • 子字符串是一個字符串中一段連續(xù)的字符序列。
  • 1 <= s.length <= 15
  • s[i] 要么是 ‘0’ 要么是 ‘1’ 。
• 解法
  • 動態(tài)規(guī)劃：首先第一位為 0 一定有前導(dǎo) 0，
  • 定義狀態(tài)（子問題）：dp[i] 下標(biāo) i 前面結(jié)束，最少可以分割成多少美麗子字符串
  • 定義轉(zhuǎn)移方程：當(dāng)前為 1 前面才可以分割，然后當(dāng) [i,j] 以及 [j+1,n+1）均符合要求時 dp[i] = min(dp[j + 1] + 1)
  • 設(shè) m 為 5 次冪的個數(shù)，n 為 s.length(n)，時間復(fù)雜度：O（n ^ 2），空間復(fù)雜度：O（n + m）
• 代碼

    /**
     * 動態(tài)規(guī)劃：首先第一位為 0 一定有前導(dǎo) 0，
     * 定義狀態(tài)（子問題）：dp[i] 下標(biāo) i 前面結(jié)束，最少可以分割成多少美麗子字符串
     * 定義轉(zhuǎn)移方程：當(dāng)前為 1 前面才可以分割，然后當(dāng) [i,j] 以及 [j+1,n+1）均符合要求時 dp[i] = min(dp[j + 1] + 1)
     * 設(shè) m 為 5 次冪的個數(shù)，n 為 s.length(n)，時間復(fù)雜度：O（n ^ 2），空間復(fù)雜度：O（n + m）
     */
    private int solution2(String s) {
        // 第一位為 0 一定有前導(dǎo) 0
        if (s.charAt(0) == '0') {
            return -1;
        }

        // 定義狀態(tài)（子問題），多加一位方便計算
        int[] dp = new int[s.length() + 1];

        // 初始化
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[s.length()] = 0;

        // 將符合要求的 5 的次冪放入集合
        Set<Integer> beautifulSet = setBeautifulSet();

        // 定義轉(zhuǎn)移方程
        doMinimumBeautifulSubstrings(s, beautifulSet, dp);

        return dp[0] == Integer.MAX_VALUE ? -1 : dp[0];
    }

    /**
     * 將符合要求的 5 的次冪放入集合
     */
    private Set<Integer> setBeautifulSet() {
        Set<Integer> beautifulSet = new HashSet<>();

        int beautifulNum = 1;
        for (int i = 0; i < 7; i++) {
            beautifulSet.add(beautifulNum);
            beautifulNum *= 5;
        }

        return beautifulSet;
    }

    /**
     * 定義轉(zhuǎn)移方程
     */
    private void doMinimumBeautifulSubstrings(String s, Set<Integer> beautifulSet, int[] dp) {
        for (int i = s.length() - 1; i >= 0; i--) {

            // 當(dāng)前為 1 前面才可以分割
            if (s.charAt(i) == '1') {
                int num = 0;

                // 當(dāng) [i,j] 以及 [j+1,n+1）均符合要求時 dp[i] = min(dp[j + 1] + 1)
                for (int j = i; j < s.length(); j++) {
                    // 計算 [i,j）二進(jìn)制代表的數(shù)
                    num = (num << 1) + s.charAt(j) - '0';

                    if (dp[j + 1] != Integer.MAX_VALUE && beautifulSet.contains(num)) {
                        dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                    }
                }
            }
//            System.out.println(i + " : " + dp[i]);
        }
    }

文章來源地址http://www.zghlxwxcb.cn/news/detail-556622.html

到了這里，關(guān)于Leetcode 第 108 場雙周賽 Problem C 將字符串分割為最少的美麗子字符串（動態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！