今日头条2018春季校园招聘研发岗位笔试编程题第一、二题
程序员文章站
2024-03-15 19:42:36
...
参考了大神的解法,这是地址https://www.nowcoder.com/discuss/70299?type=0&order=0&pos=19&page=3
第一题:
题目:
在
n
个元素的数组中,找到差值为k
的数字对去重后的个数。
输入描述:
第一行,
n
和k
,n
表示数字个数,k
表示差值
第二行,n
个正整数
输出描述:
差值为
k
的数字对去重后的个数
样例
in: 5 2 1 5 3 4 2 out: 3
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
//判断边界条件
if(k<0) k = -k;
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i] = sc.nextInt();
}
Arrays.sort(a);
int r=1,ans =0,pre =0;
for(int i=0;i<n;i++){
while(r<n && a[r]-a[i] <k) r++;
if(r==n) break;
if(a[r]-a[i] == k) {
ans++;
//忽略重复的元素
pre = a[r];
while(r<n &&pre == a[r]) r++;
}
}
System.out.println(ans);
}
}
第二题:
题目:
定义两个字符串变量:
s
和m
,再定义两种操作,
第一种操作:
m = s
;s = s + s
;
第二种操作:
s = s + m
;
假设s
,m
初始化如下:
s = "a"
;m = s
;
求最小的操作步骤数,可以将s
拼接到长度等于n
输入描述:
一个整数
n
,表明我们需要得到s
字符长度,0<n<100000<n<10000
输出描述:
一个整数,表明总共操作次数
样例
in: 6 out: 3
第一种做法:BFS,我用Java实现的当n=660时,时间达到了2490毫秒
import java.util.Scanner;
import java.util.Queue;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
class Entry{
int s;
int m;
public Entry(){
}
public Entry(int s,int m){
this.s=s;
this.m=m;
}
}
public class Main2 {
//用BFS,转向右子结点相当于第一种操作:m=s,s = s+s;转向左子节点相当于第二种操作: s = s+m。
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int step=0;
Entry entry = new Entry(1,1);
Map<Entry,Integer> map = new HashMap<Entry,Integer>();
Queue<Entry> q = new LinkedList<Entry>();
q.add(entry);
map.put(entry,0);
long time = System.currentTimeMillis();
while(!q.isEmpty()){
Entry e = q.poll();
System.out.println("e.s:"+e.s);
if(e.s == n){
System.out.println(map.get(e));
break;
}
Entry tmp =new Entry();
tmp.m = e.s;tmp.s = 2*e.s;
q.add(tmp);
map.put(tmp,map.get(e)+1);
Entry tmp1 =new Entry();
tmp1.m = e.m; tmp1.s = e.s+e.m;
q.add(tmp1);
map.put(tmp1,map.get(e)+1);
}
long time2 = System.currentTimeMillis();
System.out.println(time2-time);
}
}
从网上找到这个网址,大神用动态规划做的https://blog.csdn.net/flushhip/article/details/79685488,,当时也想到用动态规划了,可惜没推出递归关系,下面是改编的大神的代码
import java.util.Scanner;
public class Main2 {
//用动态规划
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long time = System.currentTimeMillis();
//用s和m分别表示第一维和第二维
int[][] dp = new int[n+1][n/2+1];//尽量减少数组所占的空间,数组为NxN时,n到9999时会堆会溢出
//为dp中每个元素赋最大值
for(int i =2;i<= n;i++){
for(int j =1;j<=n/2;j++){
dp[i][j] = Integer.MAX_VALUE/2;
}
}
for(int i =2;i<= n;i++){
for(int j=1;j<=i/2;j++){
if(i==2*j){//如果i为j的2倍,dp[i][j]则一定是m=s,s=s+s这种操作得到的
for(int t = 1;t<=i/4+1;t++){
//dp[i][j] = Math.min(dp[i][j],Math.min(dp[i/2][t]+1, dp[i-j][j]+1));
dp[i][j] = Math.min(dp[i][j],dp[i/2][t]+1);
}
}else{//否则,dp[i][j]一定是s=s+m得到的
dp[i][j] = Math.min(dp[i][j], dp[i-j][j]+1);
}
}
}
int step =Integer.MAX_VALUE;
for(int j=1;j<=n/2;j++){
if(step>dp[n][j]) step=dp[n][j];
}
System.out.println(step);
}
}
上一篇: 网易2020前端笔试提前批试题解析
下一篇: MVP模式使用示例详解