LC761.特殊的二进制序列

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author YAM
 */
public class Test01 {
    public static void main(String[] args) {
        String s = "11011000";
        String ans = makeLargestSpecial(s);
        System.out.println("ans="+ans );
    }

    public static String makeLargestSpecial(String s) {
        if (s.length() <= 2) {
            return s;
        }
        int cnt = 0, left = 0;
        List<String> subs = new ArrayList<String>();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++cnt;
            } else {
                --cnt;
                if (cnt == 0) {
                    System.out.println("i="+i);
                    subs.add("1" + makeLargestSpecial(s.substring(left + 1, i)) + "0");
                    //递归如下：
                    // substring ( 1 , 7 ) , >= 1 && < 7
                    // makeLargestSpecial("101100")  first  s = "101100"为 非 特殊的二进制序列
                    // "101100" 拆解：@start
                    // substring ( 1 , 1 )  , >= 1 && < 1 , left = i(1) + 1 = 2
                    // makeLargestSpecial("")  second
                    // return s (空) subs.add("10") 第一次添加
                    // substring ( 3 , 5 )  , >=  3 && < 5
                    // makeLargestSpecial("10") third
                    // return s ("10") subs.add("1100") 第二次添加  @end
                    // subs = [10, 1100];
                    left = i + 1;
                    //i=7
                    //i=1
                    //i=5
                }
            }
        }
        System.out.println("subs2="+subs);
        Collections.sort(subs, Comparator.reverseOrder());
        System.out.println("subs1="+subs);
        StringBuilder ans = new StringBuilder();
        for (String sub : subs) {
            ans.append(sub);
            System.out.println(sub);
        }
        return ans.toString();
    }

}
以上注释即为递归解释
巴特西

LC761.特殊的二进制序列

最新文章

热门文章
