一道腾讯面试题
偶然看到一道腾讯面试题：
题目：给定一个8*8的方格子，如下图所示，求A点到B点的最短路径有多少条？用算法实现。
想出了一种很简单的方法解决这个问题，A点到B点的最短路径肯定是16，其中8步横走，8步竖走，设横走为\’1\’，竖走为\’0\’，那么最短路径是一个16位的二进制字符串。只要一个16位二进制字符串里面有8个\’1\’，或者8个\’0\’，那么这个二进制字符串就是一条可行的最短路径。
0000000000000000=0
1111111111111111=65535
把0~65535之间的每一个数字转换成二进制字符串，再数其中\’1\’或者\’0\’的个数是否是8，就可以判断是不是一条可行的最短路径。
package Transfer;
public class findNumber {
static int num=0;
static String s;
public static void main(String[] args) {
for (int i=0; i<65536; i++){
s = Integer.toBinaryString(i);
if (isRight(s)){
num++;
System.out.println(s);
}
}
System.out.println("解的数量为：" + String.valueOf(num));
}
static boolean isRight(String s){
boolean res = false;
int x=0;
char c;
for(int i=0; i<s.length(); i++){
c = s.charAt(i);
if (c == \'1\')
x++;
}
if (x == 8)
res = true;
return res;
}
}
运行结果：
版权声明：本文为mstk原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。