汉德公司的笔试编程题有两个,一个很简单,另一个感觉是加分题,当场没做出来后来做出来了。
1、充电桩
N个电桩
第一个输入为ele数组,就是能充多少电,第二个输入为耗电数组,到下一站费多少电,要求输出为从任意一个充电桩进入,能跑一圈,则输出这个电桩位置,没有一个电桩可以作为起点跑一圈,则输出-1。
我的思路很简单就是从每一个电桩都计算能不能跑一圈,计算到就输出,没计算到就输出-1;
例:
输入:
1,2,3,4,5 5,4,3,2,1
输出:
3
从第三个可以跑一圈。
package hande;
//我的思路很简单就是从每一个电桩都计算能不能跑一圈,计算到就输出,没计算
//到就输出-1;
import java.util.Scanner;
public class hande1chongdianzhuang {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String str1=input.next();
String str2=input.next();
String[] s1=str1.split(",");
String[] s2=str2.split(",");
int ele=0,fin=-1,temp=0;
int[] a=new int[s1.length];
int[] b=new int[s2.length];
for (int i = 0; i < a.length; i++) {
a[i]=Integer.parseInt(s1[i]);
b[i]=Integer.parseInt(s2[i]);
}
for (int i = 0; i < a.length; i++) {
ele=0;temp=0;
for (int j = i; j < b.length + i; j++) {
if (j>=b.length){
ele=ele+a[j-b.length]-b[j-b.length];
if (ele>=0){ temp++; }
else {break;}
if (temp==b.length)
{ fin=i; }
}
else if (j<b.length){
ele=ele+a[j]-b[j];
if (ele>=0){ temp++; }
else {break;}
if (temp==b.length)
{ fin=i; }
}
}
}
System.out.println(fin);
}
}
第二题感觉是比较难的
小明有一部旧手机,他的密码为n位,n取1-6,密码每一位为0-k-1中随机一位,可以输入无限长度的字符串,只要字符串中有密码就可以解锁,比如说密码为3456,字符串123456,03456,34569756都可以解锁,求能解锁小明手机的最短字符串。
输入为n,k,输出为所求字符串
例:
输入:2,2
输出:01100
01100和10011和11001和00110都可以解锁,只要有一个输出就行
我的思路:
手机密码为n位,每一位取值为0~k-1
可以输密码的字符串为无限长
只要其中有密码就可以打开
要求输入:n,k
输出:能把密码打开的最短字符串
由于时间太短只有一个小时,20道选择,2道编程,当时没有做出
我的思路将可能成为密码的字符串存在字符数组里,字符数组长度为c的b次方,将字符数组的所有字符串进行最短超级串的拼接
先递归存入数组
再动态规划解决最短超级串的问题
package hande;
import java.util.Arrays;
import java.util.Scanner;
//手机密码为n位,每一位取值为0~k-1
//可以输密码的字符串为无限长
//只要其中有密码就可以打开
//要求输入:n,k
//输出:能把密码打开的最短字符串
//由于时间太短当时没有做出
//我的思路将可能成为密码的字符串存在字符数组里,字符数组长度为c的b次方,将字符数组的所有字符串进行最短超级串的拼接
//先递归存入数组
//再动态规划解决最短超级串的问题
public class hande2 {
/**
* 打印序列,用来记录打印序列面出最内层外的外层循环数据
*/
private static int[] flag = null;
static int k=0;
/**
* main 函数入口
* @param args
*/
public static void main(String[] args) {
// 入参
Scanner input=new Scanner(System.in);
String str=input.nextLine();
String[] a=str.split(",");
int b=Integer.parseInt(a[0]);
int c=Integer.parseInt(a[1]);
int[] array = new int[b];
for (int i = 0; i < b; i++) {
array[i]=c;
}
flag = new int[array.length - 1];
String[] s=new String[(int)Math.pow(c,b)];
for (int i = 0; i < s.length; i++) {
s[i]="";
}
// 执行
printDeep(array,array.length,s,k,b,c);
System.out.println(shortestSuperstring(s));
}
/**
* 执行入口
* @param array
* @param length
*/
private static String[] printDeep(int[] array,int length,String[] s,int k,int b,int c) {
// 当数组长度唯一,代表数据已经入最内层循环,即可 开始打印数据
if (array.length == 1) {
for (int i = 0; i < array[0]; i++) {
for (int j = 0; j < flag.length; j++) {
s[k]=s[k]+flag[j];
}
s[k]=s[k]+i;
k++;
}
return s;
}
// 剥离最外层循环,记录外层循环次数
int index = array[0];
for (int i = 0; i < index; i++) {
// 分别记录每一层需要打印的数据
flag[length-array.length] = i;
// 定义新数组,来处理剥离外层循环后剩下的n维数组
int[] arr = new int[array.length - 1];
System.arraycopy(array, 1, arr, 0, array.length - 1);
// 递归调用,实现一层一层剥离循环,达到最后实现用一维数组解决数据打印问题
printDeep(arr,length,s,k,b,c);
k= (int) (k+(Math.pow(c,arr.length)));
}
return s;
}
public static String shortestSuperstring(String[] A) {
int N = A.length;
int[][] overlaps = new int[N][N];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) if (i != j) {
int m = Math.min(A[i].length(), A[j].length());
for (int k = m; k >= 0; --k)
if (A[i].endsWith(A[j].substring(0, k))) {
overlaps[i][j] = k;
break;
}
}
int[][] dp = new int[1<<N][N];
int[][] parent = new int[1<<N][N];
for (int mask = 0; mask < (1<<N); ++mask) {
Arrays.fill(parent[mask], -1);
for (int bit = 0; bit < N; ++bit) if (((mask >> bit) & 1) > 0) {
int pmask = mask ^ (1 << bit);
if (pmask == 0) continue;
for (int i = 0; i < N; ++i) if (((pmask >> i) & 1) > 0) {
int val = dp[pmask][i] + overlaps[i][bit];
if (val > dp[mask][bit]) {
dp[mask][bit] = val;
parent[mask][bit] = i;
}
}
}
}
int[] perm = new int[N];
boolean[] seen = new boolean[N];
int t = 0;
int mask = (1 << N) - 1;
int p = 0;
for (int j = 0; j < N; ++j)
if (dp[(1<<N) - 1][j] > dp[(1<<N) - 1][p])
p = j;
while (p != -1) {
perm[t++] = p;
seen[p] = true;
int p2 = parent[mask][p];
mask ^= 1 << p;
p = p2;
}
for (int i = 0; i < t/2; ++i) {
int v = perm[i];
perm[i] = perm[t-1-i];
perm[t-1-i] = v;
}
for (int i = 0; i < N; ++i) if (!seen[i])
perm[t++] = i;
StringBuilder ans = new StringBuilder(A[perm[0]]);
for (int i = 1; i < N; ++i) {
int overlap = overlaps[perm[i-1]][perm[i]];
ans.append(A[perm[i]].substring(overlap));
}
return ans.toString();
}
}