8.8网易笔试四道编程题

网易笔试四道编程题"/>

8.8网易笔试四道编程题

一、一个数组，把里面的元素表示成若干个素数的和，求最多多少个素数

思路：因为要的是最多的素数，所以就把一个数全拆成2，即如果是偶数的话count = a[i] / 2， 而如果是奇数的话，最后会剩下一个1，但是1不是素数，所以只能在count中减去一个2，凑成3，但是2的数量再加上一个3和直接a[i]/ 2值是一样的。count += a[i] / 2;就是每一个数拆的最多的素数。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);//输入int n = in.nextInt();int[] array = new int[n];for (int i = 0; i < n; i++) {array[i] = in.nextInt();}if (array.length == 0) {System.out.println(0);return;}//存储最多的素数int count = 0;//计算每一个数for (int i = 0; i < n; i++) {//遍历数组//1不是素数，不用计算if (array[i] != 1) {//2 和 3 不用拆，也是素数，所以直接添加结果if (array[i] == 2 || array[i] == 3) {count++;continue;}//从4开始找，素数//拆分，从2开始递增拆分int temp = array[i];count += temp / 2;}}System.out.println(count);}}

二、给m个数，比如2 1 5，再给个n，m是n的子序列，求n的最小字典序，n＞m，结果是 2 1 3 4 5有点像单调栈

当时没有AC，下来自己整理了以下思路。测了以下自己的用例
没有OJ环境了，不保证100%正确

样例：

输入：
5 3
2 1 5

输出：

2 1 3 4 5

输入：
5 2
4 2

输出：
1 3 4 2 5

自己的用例

输入:
7 3
6 1 2

输出：
3 4 5 6 1 2 7

思路：从1开始往List里添加，准备一个队列保证字串的顺序，再准备一个Set集合，判断当前的i是否包含在了子串中。①、用7 3 这个例子说明，子串的长度是3，原来的串是7，所以count=n - m就是需要新增的个数，用count控制结束。②、1开始添加（i = 1），判断是否小于队列的第一个，如果小于，判断是否已经包含在子串中，如果包含了，就直接跳过，不包含就需要添加，并将计数的count--;③、加入添加到了7，已经等与了队列的头，所以出队列，然后添加到结果集中。i++；④、如果队列空了，说明子串的值已经都加到了结果集，但有可能count>0，说明原字符串的长度还没有到7，所以继续上次i的值继续加到结果集中。

package com02;import java.util.*;public class Main2 {public static void main(String[] args) {//从1开始遍历//将数组加入set中判断是否包含//加一个队列保证顺序Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[] array = new int[m];Queue<Integer> q = new LinkedList<>();//保证顺序Set<Integer> set = new HashSet<>();//判断是否包含ArrayList<Integer> result = new ArrayList<>();//保存结果//开始输入for (int i = 0; i < m; i++) {array[i] = in.nextInt();q.offer(array[i]);set.add(array[i]);}//添加的次数 : 字符串长度是5，子串长度是3，说明只需要增加2个字符就可以int count = n - m;int i = 1; //从1开始判断while (count > 0) {//判断队列是否为空，如果队列不为空就和队列的第一个比较并且看//是否包含。如果包含直接跳过。if (!q.isEmpty()) {//判断是否比第一个小while (i < q.peek()) {//如果小于队列的第一个，就按顺序添加i的值if (!set.contains(i)) {//如果比队列的第一个小并且没有在子序列中，就添加，并且count--;result.add(i);count--;}i++;}//到这，就到了队列的第一个了result.add(q.poll());} else {// 到这说明长度还小于n，但是字串的值已经用完了，就接着i继续添加if (!set.contains(i)) {//如果比队列的第一个小并且没有在子序列中，就添加，并且count--;result.add(i);count--;}i++;}}//到这就是把需要新增的字符，遍历完了，接下来就要看队列中是否还有元素，有的话按顺序添加进去while (!q.isEmpty()) {result.add(q.poll());}//输出结果for (Integer re : result) {System.out.print(re + " ");}}}

三、平分东西，比如30 30 60 15 5，最少去掉多少东西能让他们相等，输出20（当时没来的及做）

贪心的思想：将东西的价值从小到大排序，然后每次不能平分就丢弃最小的。

import java.util.Arrays;
import java.util.Scanner;public class Main3 {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] array = new int[n];int sum = 0;//总和for (int i = 0; i < n; i++) {array[i] = in.nextInt();sum += array[i];}//从小到大排序Arrays.sort(array);int index = 0; //丢弃的位置int count = 0; //总共丢弃的价值//控制跳出boolean flag = false;while (index < array.length) {//遍历整个数组，贪心从最小的开始丢弃，当两个能平分的时候，就直接返回//sum总价值如果是奇数的话，是不可能平分的if (sum % 2 == 0) {//可能可以平分，从index开始累加// 如果中间正好累加到了sum的一般，退出结果输出，如果大于了一半，丢弃array[index],然后继续向后找int k = index;int temp = 0;while (k < array.length && temp <= sum / 2) {if (temp == sum / 2) {//如果相等，返回flag = true;break;}//说明还小于一般temp += array[k];k++;}//判断是否找到if (flag) {break;}//循环结束，不能平分，丢弃最小的sum -= array[index];count += array[index];index++;} else {//sum是奇数，不可分，直接丢弃第一个sum -= array[index];count += array[index];//丢弃值增加index++;}}if (flag) {System.out.println(count);} else {System.out.println(0);//不能平分输出0}}
}

4、题忘了