【牛客题】数字匹配 ＜模拟＞

题目描述
dd 最近比较喜欢二进制数，她认为对于任意两个正整数x，y（x不等于y），当且仅当 x，y的二进制非前导零部分最大连续重合位数 >=k 时，x，y是匹配的，比如175的二进制形式为（10101111），472的二进制形式为（111011000），因此，175 和 472 最大连续重合部分为（1011），故这两个数的最大连续重合位数为4。
现在给定一个正整数n（n<=2000）和一个k，求对于所有x，y（且1<=x

输入描述:
读入共一行，包括两个正整数 n,k(n≤2000,k≤10)
输出描述:
输出共一行，表示匹配数

示例输入

6 2
1

输出

7
1

说明

2(10)和4(100)
2(10)和5(101)
2(10)和6(110)
3(11)和6(110)
4(100)和5(101)
4(100)和6(110)
5(101)和6(110)
共7对
1
2
3
4
5
6
7
8

题解

思路：使用 Integer.toBinaryString(int num)去作比较

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int num = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                num += matchLength(i, j, k);
            }
        }
        System.out.println(num);
    }

    public static int matchLength(int num1, int num2, int k) {
        String num1_str = Integer.toBinaryString(num1);
        //System.out.println("num1是："+num1+"  "+num1_str);
        String num2_str = Integer.toBinaryString(num2);
        //System.out.println("num2是："+num2+"  "+num2_str);

        int left = 0;
        if (num1_str.length() < k || num2_str.length() < k) {
            return 0;
        }
        //取短的来遍历
        String tempStr = num1_str.length() <= num2_str.length() ? num1_str : num2_str;
        for (int i = k - 1; i < tempStr.length(); i++) {
            String temp = tempStr.substring(left, i + 1);
            if (num2_str.contains(temp)) {
                return 1;
            } else {
                left++;
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40