9.1 阿里笔试思路

题目1

【题干回忆】

两个字符串S和T，求S的子串和T的子序列有多少是相同的
子串：必须连续
子序列：可以不是连续的
“ab”是“abcd”的子串，也是子序列，但“abd”是“abcd”的子序列不是子串

【思路】

遍历S的子串sub，判断S的子串sub是不是T的子序列
需要注意的是剪枝。比如，S的子串“ab”不是T的子序列，那子串“abc”或者“abcd”都不可能再是T的子序列

题目2

【题干回忆】
一个原始二进制字符串，位数是m。
有n个传输后的字符串，可能某些位数发生了改变，对于传输后的字符串只知道有多少位数是正确的。
比如：

原始二进制字符串：
010010 （m=6）

传输后的二进制字符串+正确位数：（n=2）
010000 5 （有5位正确）
100010 4 （有4位正确）

求根据传输后的字符串，判断原始字符串有多少种可能？如果只有1种可能，要将这种可能打印下来；其他情况只打印可能的个数。

【思路】
主要是将二进制字符串看成是二进制的数字，然后列举所有可能的正确二进制字符串，范围是0～2^m，再做一些位运算。
（因为考场上没试，不知道会不会超时，欢迎大家提更好的思路～）

import java.util.*;

public class Ali2 {
    int[] sequence;
    int[] rightNum;
    int n, m;

    public void Solution() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sequence = new int[n]; // 存的是将二进制字符串转换成十进制后的int
        rightNum = new int[n]; // 存的是正确的位数
        List<Integer> results = new ArrayList<>();

        for (int i=0; i<n; i++) {
            sequence[i] = Integer.parseInt(sc.next(), 2);
            rightNum[i] = sc.nextInt();
        }

        // 列举原始字符串的所有可能，即 0～2的m次方 中任意一个数
        for (int origin=0; origin<(1 << m); origin++) {
            boolean flag = true;
            for (int i =0; i<n; i++) {
                if (getSameNum(origin, sequence[i]) != rightNum[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                results.add(origin);
            }
        }

        // 根据题目要求，结果不同输出不同
        if (results.size() == 1) { // 只有唯一的结果
            String str = Integer.toBinaryString(results.get(0));
            if (str.length() != m) { // 注意：输出的二进制字符串左边要补0
                for (int i = 0; i<m-str.length(); i++) {
                    System.out.print("0");
                }
                System.out.println(str);
            } else {
                System.out.println(str);
            }

        } else {
            System.out.println(results.size());
        }

    }
    // 判断原始字符串和有问题字符串有相同的位数，即有问题字符串正确的位数
    private int getSameNum(int origin, int current) {
        int diff  = origin ^ current; // 异或之后相同的位置是0，不同的位置是1
        int diffNum = 0;
        while (diff > 0) {
            if ((diff & 1) == 1) diffNum ++; // 找到异或之后有多少位是1
            diff >>= 1;
        }
        return m - diffNum;
    }

    public static void main(String[] args) {
        new Ali2().Solution();

    }
}