首页 > 9.1 阿里笔试思路
头像
杨子琦
编辑于 2020-09-02 18:25
+ 关注

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();

    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐