携程第二批笔试题
1. 在软件系统中，经常会使用到IP黑名单功能。例如下面的黑名单样例，条目可能是单个IP，也可能是一个子网，IP黑名单样例
62.33.12.122
221.58.4.0/24
8.9.88.1
……
请构建数据结构，在加载黑名单后，能判定给定的IP是否命中指定的IP黑名单。
输入：
第一行输入指定的IP地址，IPv4格式输入；
第二行输入指定的IP黑名单地址，可以是一个IPv4地址，或一个子网地址。
输出：
判断指定的IP是否命中指定的IP黑名单
样例输入：
2.33.128.9
2.33.128.0/24
样例输出：
1
计算机网络知识点：
IP地址
IP地址被用来给Internet上的电脑一个编号。大家日常见到的情况是每台联网的PC上都需要有IP地址，才能正常通信。我们可以把“个人电脑”比作“一台电话”，那么“IP地址”就相当于“电话号码”，而Internet中的路由器，就相当于电信局的“程控式交换机”。
IP地址是一个32位的二进制数，通常被分割为4个“8位二进制数”（也就是4个字节）。IP地址通常用“点分十进制”表示成（a.b.c.d）的形式，其中，a,b,c,d都是0~255之间的十进制整数。例：点分十进IP地址（100.4.5.6），实际上是32位二进制数（01100100.00000100.00000101.00000110）。
网络地址:
1、如果是192的C段地址，那么，网络地址就是：192.168.1.0，地址掩码是：255.255.255.0。
2、如果地址掩码是：255.255.0.0，那么网络地址就是：192.168.0.0。
3、网络地址很大一部分是由地址掩码决定的。
子网掩码
子网掩码(subnet mask)又叫网络掩码、地址掩码、子网络遮罩，它是一种用来指明一个IP地址的哪些位标识的是主机所在的子网，以及哪些位标识的是主机的位掩码。
子网掩码不能单独存在，它必须结合IP地址一起使用。子网掩码只有一个作用，就是将某个IP地址划分成网络地址和主机地址两部分。
子网掩码是一个32位地址，用于屏蔽IP地址的一部分以区别网络标识和主机标识，并说明该IP地址是在局域网上，还是在远程网上。
子网掩码——屏蔽一个IP地址的网络部分的“全1”比特模式。对于A类地址来说，默认的子网掩码是255.0.0.0；对于B类地址来说默认的子网掩码是255.255.0.0；对于C类地址来说默认的子网掩码是255.255.255.0。
通过子网掩码，就可以判断两个IP在不在一个局域网内部。
子网掩码可以看出有多少位是网络号，有多少位是主机号
ip段/数字-如192.168.0.1/24是什么意思?
后面这个数字标示了我们的网络号的位数，也就是子网掩码中前多少号为1
129.168.1.1 /24 这个24就是告诉我们网络号是24位
也就相当于告诉我们了
子网掩码是：11111111 11111111 11111111 00000000
即：255.255.255.0
172.16.10.33/27 中的/27
也就是说子网掩码是255.255.255.224 即27个全1
子网掩码是：11111111 11111111 11111111 11100000
192.168.2.0/24表示的IP范围
192.168.2.0换成32位二进制，四组，每组8位
/24 表示前24位不变，后8位由全0变化到全1的过程，也就是由“00000000”变化到“11111111”
又因为全0是子网网络地址，全1是子网广播地址，这两个地址是不分配给主机使用的。
所以有效的可分配的范围是前24位不变，后8位由“00000001”变化为“11111110”的范围
再转换回十进制就是192.168.2.1~192.168.2.254
编码解题：
import java.util.Scanner;
public class Problem16 {
static boolean CheckBlackList(String userIP, String blackIP) {
String[] user = userIP.split("\\.");
String[] black = blackIP.split("\\.");
if (black[black.length-1].contains("/")) {
String temp = black[black.length-1];
String[] qujian = temp.split("/");
int num = Integer.valueOf(qujian[1]);
int change = 32 - num;
int count = (int) Math.pow(2,change);
int userIp = Integer.valueOf(user[user.length-1]);
if (userIp >= 0 && userIp <= count) {
return true;
}
} else {
for (int i = 0; i < user.length-1; i++) {
if (!user[i].equals(black[i])) {
return false;
}
}
}
if (user[user.length-1].equals(black[black.length-1])) {
return true;
}
return false;
}
/******************************结束写代码******************************/
public static void main(String[] args){
Scanner in = new Scanner(System.in);
boolean res;
String _userIP;
try {
_userIP = in.nextLine();
} catch (Exception e) {
_userIP = null;
}
String _blackIP;
try {
_blackIP = in.nextLine();
} catch (Exception e) {
_blackIP = null;
}
res = CheckBlackList(_userIP, _blackIP);
System.out.println(String.valueOf(res ? 1 : 0));
}
}
因为第二题比较难，还没什么思路。因此跳过
3.豚厂开发了一个酒店客服机器人，机器人要送水到客人房间，此时机器人在一个M*N网格的左上角，客人房间在右下角，这个机器人在任意点只能向下或者向右移动一步，机器人要把水送到客人房间，有多少种可能的唯一路径？
说明：
网格中的障碍物和空位置分别用1和0表示
M*N的值均不超过100
输入：
第一行输入网格的长款M和N
第二行至M+1行输入障碍物和空位，以空格分开
输出：
机器人在给定网络上可能的路径数。
输入样例：
3
3
0 0 0
0 1 0
0 0 0
输出样例：
2
解决方案：
import java.util.Scanner;
public class Main {
public static int sum = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int M = scan.nextInt();
int N = scan.nextInt();
int[][] data = new int[M][N];
for(int i=0;i<M;i++) {
for(int j=0;j<N;j++) {
data[i][j]=scan.nextInt();
}
}
caj(data,0,0,M,N);
System.out.println(sum);
}
public static void caj(int[][] data,int i,int j,int M,int N) {
if(i==(M-1) && j==(N-1)) {
sum++;
}
if((i+1)<=(M-1)) {
if(data[i+1][j]!=1)caj(data,i+1,j,M,N);
}
if((j+1)<=(N-1)) {
if(data[i][j+1]!=1)caj(data,i,j+1,M,N);
}
}
}