首页 > 猿辅导3.14后端笔试
头像
木有offer
编辑于 2021-03-14 22:24
+ 关注

猿辅导3.14后端笔试

总共有15道选择题,每题5分,3道编程题,考试时间90分钟

1. 给定长度为n的数组(0 <n <=10, 对应元素在0~9范围内),随意拼接这些数值,找到能被k整除的最小整数,并且起始元素不为0;

/*
输入
第一行 :长度n 除数k
第二行: 数组元素
4 7 
4 0 1 3 
输出
1043
*/
public class MinInteeger {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		String[] arr = new String[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.next();
		}

		boolean[] dp = new boolean[n];
        //保留所有拼接数值
		Set<Integer> set = new HashSet<>();
        //拼接字符串
		String tmp = "";
        //深度优先拼接字符串
		for (int i = 0; i < n; i++) {
            //确保开头不为0
			if (!arr[i].equals("0")) {
				dfs(arr,i,0, tmp,dp,set);
			}
		}

		int min = Integer.MAX_VALUE;
        //遍历找能被整除的最小整数
		for (int i : set) {
			if (i % k == 0) {
				min =Math.min(min, i);
			}
		}
		System.out.println(min);
	}
    
    /**
	* @Param: index 待拼接字符下标
	* @Param: count 已拼接元素个数
	* @Param: tmp 拼接字符串
	* @Param: dp 标识是否遍历过
	*/
	private static void dfs(String[] arr, int index, int count, String tmp, boolean[] dp,Set<Integer> set) {
		tmp += arr[index];
		dp[index] = true;
		if(count == arr.length-1) set.add(Integer.parseInt(tmp));

		for (int i = 0; i < arr.length; i++) {
			if (!dp[i]) {
				dfs(arr,i,count+1, tmp,dp,set);
			}
		}
		dp[index] = false;
		tmp = tmp.substring(0, tmp.length()-arr[index].length());
	}
}
数组元素均在0~9范围内,记得题目没有提及是否会有重复值,如果有多个重复的0,复杂度又会提高。。。

2. lc329. 矩阵中的最长递增路径

3. 给定长度为n的数组,找到一个最大素数,并且数组中部分元素相加可得到该素数

这道题,有点麻烦,大致分两步:
  • 保存数组中部分元素之和,也就是说可选取的数组元素个数从1到n,因此选定元素个数后,使用深度优先求和,完成后将元素之和添加到HashSet中
  • 得到数组全部元素之和sum,由大到小挨个遍历,判断Hashset中是否有该元素并且该元素是否为素数,存在则返回该元素并退出循环,否则返回-1;
/*
输入:
第一行: 元素个数
第二行 元素值
5
1 3 5 7 9
输出最大素数:
19
*/
public class SingleValue {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];

		int sum = 0;//保留数组元素之和
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
			sum += arr[i];
		}

		//保存选取元素之和
		Set<Integer> set = new HashSet<>();
		boolean[] dp = new boolean[n];
		int k = n;//选取元素个数
		while (k > 0) {
			for (int i = 0; i < n; i++) {
				dfs(arr, set, i, k, 0, dp);
			}
			//每次循环减少一个长度
			k--;
		}

		//标记是否存在该数,存在即输出该素数,不存在输出-1
		boolean existed = false;
		//根据sum倒序遍历,查询是否包含该素数值
		for (int i = sum; i > 0; i--) {
			if (set.contains(i) && isPrime(i)) {
				System.out.println(i);
				existed = true;
				break;
			}
		}
		if (!existed) System.out.println(-1);
	}

	private static boolean isPrime(int n) {
		for (int i = 2; i < n; i++) {
			if (n % i == 0) return false;
		}
		return true;
	}

    /**
	 * @Param: set 保留所有添加元素之和
	 * @Param: index 待添加元素索引
	 * @Param: k 待添加元素数目
	 * @Param: sum 已添加元素之和
	 */
	private static void dfs(int[] arr, Set<Integer> set, int index, int k, int sum, boolean[] dp) {
		sum += arr[index];
		dp[index] = true;
		if (k == 1) set.add(sum);

		for (int i = 0; i < arr.length; i++) {
			if (!dp[i]) {
				dfs(arr, set, i, k - 1, sum, dp);
			}
		}
		sum -= arr[index];
		dp[index] = false;
	}
}
这几道题基本上都是深度优先了,不知道为什么这次考的这么集中。做题速度还是有点慢,一些都来不及做,太菜了,眼睛也有点花。。。

全部评论

(6) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐