欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

今日头条2018春季校园招聘研发岗位笔试编程题第一、二题

程序员文章站 2024-03-15 19:42:36
...

参考了大神的解法,这是地址https://www.nowcoder.com/discuss/70299?type=0&order=0&pos=19&page=3

第一题:

题目:

n个元素的数组中,找到差值为k的数字对去重后的个数。

输入描述:

第一行,nkn表示数字个数,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);
	}
}

第二题:

题目:

定义两个字符串变量:sm,再定义两种操作, 
  
第一种操作:

m = s
s = s + s
第二种操作:

s = s + m
  
假设sm初始化如下:

s = "a"
m = s
求最小的操作步骤数,可以将s拼接到长度等于n

输入描述:

一个整数n,表明我们需要得到s字符长度,0<n<100000<n<10000

输出描述:

一个整数,表明总共操作次数

样例

in:
6
out:
3
第一种做法:BFS,我用Java实现的当n=660时,时间达到了2490毫秒

今日头条2018春季校园招聘研发岗位笔试编程题第一、二题

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);
	}
}