求子序列(状态压缩)

子序列

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。比如 [1,4,5] 就是 [1,2,3,4,5] 的子序列

状态压缩

状态压缩就是通过二进制枚举子集的方法,举几个列子:

  1. 假设要求 [a]的子序列,那么只有一个 a
  2. 如果要求 [a,b] ,有 {b},{a},{a,b} 有3种
  3. 如果是 [a,b,c] 的子序列 一共有 {c},{b},{b,c},{a},{a,c},{a,b},{a,b,c},一共有7个子序列

那么可以得出 长度为 n 的字符串,它的子序列个数为 2n-1
我们把[a,b,c] 和 一个 三位二进制一一一对应,0表示没有被选中,1表示选中

  • 1的二进制: 001,对应的子序列为{c}
  • 2的二进制: 010,对应的子序列为{b}
  • 3的二进制: 011,对应的子序列为{b,c}
  • 4的二进制: 100,对应的子序列为{a}
  • 5的二进制: 101,对应的子序列为{a,c}
  • 6的二进制: 110,对应的子序列为{a,b}
  • 7的二进制: 111,对应的子序列为{a,b,c}

求子序列(状态压缩)_第1张图片

代码

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int len = s.length();
        // 二进制位数
        int index = 1<<len;

        // 这一层循环表示 选中了几个元素
        for (int i = 0; i < index; i++) {
            StringBuilder sb = new StringBuilder();
            // 这一层循环表示判断每一位元素是否被选中
            for (int j = 0; j < len; j++) {
                if ((i&(1<<j)) != 0) {
                    //sb.append(j);
                    sb.append(s.charAt(len-j-1));
                }
            }
            if (sb.length() != 0) {
                System.out.println(i+"->"+sb);
            }

        }
    }

你可能感兴趣的