网易2017秋招编程题集合--完全解析

2024-09-04 01:58
文章标签 编程 解析 秋招 完全 集合 2017 网易

本文主要是介绍网易2017秋招编程题集合--完全解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

一些大公司的真题里面总有些含金量很高的几个题，网易2017秋招编程题集合里面也有几个题是非常好的，比如说第三题跳石板，第四题黑暗的字符串都是很好的题目。特别是第四题的那种思路之前几乎完全没有接触过，还有第六题最大的奇约数里面还有部分数学思维在里面。

1.回文序列

题目描述：如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：
{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列,
{1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。
现在给出一个数字序列，允许使用一种转换操作：
选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。

输入描述:
输入为两行，第一行为序列长度n ( 1 ≤ n ≤ 50)
第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000)，以空格分隔。

输出描述:
输出一个数，表示最少需要的转换次数

输入例子1:
4
1 1 1 3

输出例子1:
2

题目分析

这个题目比较简单，因为是回文字符，那么首部和尾部对应的数必须相同，如果前面的数小，那么将相邻的两数相加，反之如果后面的数小则将后面相邻的两个数相加，只需要两个指针从前往后从后往前遍历就够了。

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();int []arr=new int[n];for(int i=0;i<n;i++)arr[i]=sc.nextInt();getPalindrome(arr);}sc.close();}public static void getPalindrome(int []arr){int res=0;int i=0,j=arr.length-1;while(i<j){//如果首尾相等不处理。if(arr[i]==arr[j]){i++;j--;}//如果首部比尾部小，则与其相邻的加if(arr[i]<arr[j]){arr[i+1]+=arr[i];   i++;res++;}//如果尾部比首部小，则与其相邻的加if(arr[j]<arr[i]){arr[j-1]+=arr[j];j--;res++;}}System.out.println(res);}
}

2.优雅的点

题目描述：小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他。
例如：半径的平方如果为25
优雅的点就有：(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0)，一共12个点。

输入描述:
输入为一个整数，即为圆半径的平方,范围在32位int范围内。

输出描述:
输出为一个整数，即为优雅的点的个数

输入例子1:
25

输出例子1:
12

题目分析
这个题目如果用双重循环的话时间复杂度比较大，用单重循环来处理，注意浮点数比较大小。

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int r=sc.nextInt();getElegantPoint(r);}sc.close();}public static void getElegantPoint(int r){if(r==0){System.out.println(1);return;}int res=0;double p=Math.pow(r, 0.5);if(Math.abs(p-Math.ceil(p))<=0.00000001){//条件成立则p是一个正整数res+=4;}for(int x=1;x<p;x++){double y=Math.pow(r-x*x, 0.5);          if(Math.abs(y-Math.ceil(y))<=0.00000001){res+=4;}}System.out.println(res);}}

3.跳石板

题目描述：小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…….
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板
输入描述:
输入为一行，有两个整数N，M，以空格隔开。
(4 ≤ N ≤ 100000)
(N ≤ M ≤ 100000)

输出描述:
输出小易最少需要跳跃的步数,如果不能到达输出-1

输入例子1:
4 24

输出例子1:
5

题目分析

这个题目，比较容易想到的是回溯法，回溯法遍历解空间中所有的解，然后在其中选出最优解，但是当使用回溯法，时间超了，空间也超了，所以回溯法不能，只能使用动态规划，定义一个大小为dp[M-N+1]的数组，数组dp[i-N]表示走到i+N这级楼梯时最少的步数，那么很容易得到关系式：

dp[i+x-N]= Math.min( dp[i+x-N] , dp[i-N] + 1 ); 其中 x 为 i 的公约数。

package 网易2017秋招编程题集合;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int N=sc.nextInt();int M=sc.nextInt();getstep(N, M);}sc.close();}//求最小步数public static void getstep(int N,int M){int dp[]=new int[M-N+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0]=1;for(int i=N;i<=M;i++){if(dp[i-N]==Integer.MAX_VALUE){continue;}ArrayList<Integer> list=getfew(i);for(int j=0;j<list.size();j++){int x=list.get(j);if(i+x<=M)dp[i+x-N]=Math.min(dp[i+x-N], dp[i-N]+1);}       }System.out.println(dp[M-N]==Integer.MAX_VALUE?-1:dp[M-N]-1);}   //求公约数public static ArrayList<Integer> getfew(int n){       ArrayList<Integer> list=new ArrayList<Integer>();for(int i=2;i*i<=n;i++){if(n%i==0){list.add(i);if(n/i!=i)list.add(n/i);}           }       return list;        }
}

4.暗黑的字符串

题目描述：一个只包含’A’、’B’和’C’的字符串，如果存在某一段长度为3的连续子串中恰好’A’、’B’和’C’各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：
BAACAACCBAAA 连续子串”CBA”中包含了’A’,’B’,’C’各一个，所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含’A’,’B’,’C’,所以是暗黑的字符串
你的任务就是计算出长度为n的字符串(只包含’A’、’B’和’C’)，有多少个是暗黑的字符串。
输入描述:
输入一个整数n，表示字符串长度(1 ≤ n ≤ 30)

输出描述:
输出一个整数表示有多少个暗黑字符串

输入例子1:
2
3

输出例子1:
9
21

题目分析
这个题是网易2017秋招编程题集合中含金量最高的一道题，本题的解法也十分的巧妙，分析本题就要从状态转移开始分析：要得到字符串中无三个连续字符中恰好包含A、 B、 C 串个数，我们可以从长度为2的串一次增加字符知道长度为n，分析其状态。

这里写图片描述
长度为2的串有如上所示的两种状态，一种是两个字符相等，另一种是两个字符不同，要使得增加字符后不连续出现3个不同字符，第一种情况之后可以任选A B C三种字符，第二种情况下只能选，A或者 B两种字符，设长度为i的字符串前面都没有出现连续3个不同的字符，后面两个字符相同的情况为：S（i）,后面两个字符不同的为 D（i）,那么可知：S（i+1）=S（i）+D（i），D（i+1）=D（i）+2*S（i）；如下图：
这里写图片描述

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();cal(n);         }sc.close();}public static void cal(int n){if(n==1){System.out.println(3);return;}if(n==2){System.out.println(9);return;}long s=3,d=6;for(int k=3;k<=n;++k){long temp=s;s=s+d;d=2*temp+d;}System.out.println(s+d);}
}

5.数字翻转

题目分析：对于一个整数X，定义操作rev(X)为将X按数位翻转过来，并且去除掉前导0。例如:
如果 X = 123，则rev(X) = 321;
如果 X = 100，则rev(X) = 1.
现在给出整数x和y,要求rev(rev(x) + rev(y))为多少？
输入描述:
输入为一行，x、y(1 ≤ x、y ≤ 1000)，以空格隔开。

输出描述:
输出rev(rev(x) + rev(y))的值

输入例子1:
123 100

输出例子1:
223

题目分析
这个题目很简单，直接上代码。

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int x=sc.nextInt();int y=sc.nextInt();System.out.println(rev(rev(x)+rev(y)));}sc.close();}public static int  rev(int n){       int res=0;while(n!=0){res=10*res+(n%10);n/=10;}return res;}
}

6.最大的奇约数

题目描述：小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数f(x)为x最大的奇数约数，x为正整数。 例如:f(44) = 11.
现在给出一个N，需要求出 f(1) + f(2) + f(3)…….f(N)
例如： N = 7
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21
小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。
输入描述:
输入一个整数N (1 ≤ N ≤ 1000000000)

输出描述:
输出一个整数，即为f(1) + f(2) + f(3)…….f(N)

输入例子1:
7

输出例子1:
21

题目分析

对于上例：f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) =f(1) + f(3) + f(5) + f(7)+ f(2) + f(4) + f(6) 对于前部分的奇数可以直接求和，对于后部分的偶数先全部除以2，如下图：
这里写图片描述

由此可得等式：sum（n）=小数n的奇数和+sum（n/2）;这是递归的，所以很容易写出如下代码：

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){long n=sc.nextLong();System.out.println(getMaxOddFew(n));}sc.close();}public static long getMaxOddFew(long n){long sum=0;if(n<=1)return n;for(int i=1;i<=n;i++){sum+=(i&1)*i;//所有奇数相加。}return sum+getMaxOddFew(n/2);}}

上面代码通过率只有40%,时间复杂度太大，上面奇数相加的时候循环n次，这里可以使用公式替代，将上面代码改成如下：

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){long n=sc.nextLong();System.out.println(getMaxOddFew(n));}sc.close();}public static long getMaxOddFew(long n){long sum=0;if(n<=1)return n;if((n&1)==1){sum=(n+1)*(n+1)/4;}else {sum=n*n/4;}//使用数学公式计算奇数和，大大减小了时间复杂度。return sum+getMaxOddFew(n/2);}}

7.买苹果

题目描述：小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。
输入描述:
输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述:
输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

输入例子1:
20

输出例子1:
3

题目分析

这个题目可以用回溯法，也可以用动态规划，回溯法比较简单，是一棵子集数，每次有两种选择要么选6，要么选8 ，如下树结构，假设选6节点用0表示，选8节点有1表示：
这里写图片描述
遍历这棵子集树，如果有解就返回，如果超过了限制条件就剪枝，整个解空间中找不到解也返回。

package 网易2017秋招编程题集合;import java.util.Arrays;
import java.util.Scanner;public class Main {static int min=Integer.MAX_VALUE;public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();getapple(n);}sc.close();}public static void getapple(int n){min=Integer.MAX_VALUE;getapple(n,0);System.out.println(min==Integer.MAX_VALUE?-1:min);}public static void getapple(int n,int count){if(n<=0){if(n==0)min=Math.min(count, min);return;}       getapple(n-6,count+1);//遍历左子树getapple(n-8,count+1);//遍历右子树   }       
}

解法2可以使用动态规划来做，动态规划思路和跳楼梯差不多，dp[i]表示买i个苹果需要最少的搭配，则可以得到以下方程：

if(i+6<=n)

dp[i+6]=Math.min(dp[i+6], dp[i]+1);

if(i+8<=n)

dp[i+8]=Math.min(dp[i+8], dp[i]+1); 

public static void getapple_dp(int n){int []dp=new int[n+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0]=0;for(int i=0;i<=n;i++){if(dp[i]==Integer.MAX_VALUE)continue;if(i+6<=n)dp[i+6]=Math.min(dp[i+6], dp[i]+1);if(i+8<=n)dp[i+8]=Math.min(dp[i+8], dp[i]+1);         }System.out.println(dp[n]==Integer.MAX_VALUE?-1:dp[n]);  }

8.计算糖果

**题目描述：**A,B,C三个人是好朋友,每个人手里都有一些糖果,我们不知道他们每个人手上具体有多少个糖果,但是我们知道以下的信息：
A - B, B - C, A + B, B + C. 这四个数值.每个字母代表每个人所拥有的糖果数.
现在需要通过这四个数值计算出每个人手里有多少个糖果,即A,B,C。这里保证最多只有一组整数A,B,C满足所有题设条件。
输入描述:
输入为一行，一共4个整数，分别为A - B，B - C，A + B，B + C，用空格隔开。
范围均在-30到30之间(闭区间)。

输出描述:
输出为一行，如果存在满足的整数A，B，C则按顺序输出A，B，C，用空格隔开，行末无空格。
如果不存在这样的整数A，B，C，则输出No

输入例子1:
1 -2 3 4

输出例子1:
2 1 3

题目分析
这个题比较简单，直接上代码。

package 网易2017秋招编程题集合;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int a_b=sc.nextInt();int b_c=sc.nextInt();int ab=sc.nextInt();int bc=sc.nextInt();getABC(a_b, b_c, ab, bc);}sc.close();}public static void getABC(int a_b,int b_c,int ab,int bc){int a=(a_b+ab)/2;int b=(b_c+bc)/2;int c=bc-b;if(a-b==a_b&&(b-c==b_c)&&(a+b==ab)&&(b+c==bc)){System.out.println(a+" "+b+" "+c);}else {System.out.println("No");}}
}

这篇关于网易2017秋招编程题集合--完全解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1134677。

相关文章

C语言中自动与强制转换全解析

C语言中自动与强制转换全解析

《C语言中自动与强制转换全解析》在编写C程序时,类型转换是确保数据正确性和一致性的关键环节,无论是隐式转换还是显式转换,都各有特点和应用场景,本文将详细探讨C语言中的类型转换机制,帮助您更好地理解并在... 目录类型转换的重要性自动类型转换（隐式转换）强制类型转换（显式转换）常见错误与注意事项总结与建议类型
阅读更多...
C#比较两个List集合内容是否相同的几种方法

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法（顺序和内容都相等）2.
阅读更多...
MySQL 缓存机制与架构解析(最新推荐)

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存（InnoDBBufferPool）和二级缓存（QueryCache）,文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查
阅读更多...
在Rust中要用Struct和Enum组织数据的原因解析

在Rust中要用Struct和Enum组织数据的原因解析

《在Rust中要用Struct和Enum组织数据的原因解析》在Rust中,Struct和Enum是组织数据的核心工具,Struct用于将相关字段封装为单一实体,便于管理和扩展,Enum用于明确定义所有... 目录为什么在Rust中要用Struct和Enum组织数据？一、使用struct组织数据：将相关字段绑
阅读更多...
使用Java实现一个解析CURL脚本小工具

使用Java实现一个解析CURL脚本小工具

《使用Java实现一个解析CURL脚本小工具》文章介绍了如何使用Java实现一个解析CURL脚本的工具,该工具可以将CURL脚本中的Header解析为KVMap结构,获取URL路径、请求类型,解析UR... 目录使用示例实现原理具体实现CurlParserUtilCurlEntityICurlHandler
阅读更多...
C#多线程编程中导致死锁的常见陷阱和避免方法

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁（Deadlock）是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁？死锁的典型条件：2. 导致死锁的常见原因2.1 锁的顺序问题错误示例：不同
阅读更多...
深入解析Spring TransactionTemplate 高级用法(示例代码)

深入解析Spring TransactionTemplate 高级用法(示例代码)

《深入解析SpringTransactionTemplate高级用法(示例代码)》TransactionTemplate是Spring框架中一个强大的工具,它允许开发者以编程方式控制事务,通过... 目录1. TransactionTemplate 的核心概念2. 核心接口和类3. TransactionT
阅读更多...
数据库使用之union、union all、各种join的用法区别解析

数据库使用之union、union all、各种join的用法区别解析

《数据库使用之union、unionall、各种join的用法区别解析》：本文主要介绍SQL中的Union和UnionAll的区别,包括去重与否以及使用时的注意事项,还详细解释了Join关键字,... 目录一、Union 和Union All1、区别：2、注意点：3、具体举例二、Join关键字的区别&php
阅读更多...
Spring IOC控制反转的实现解析

Spring IOC控制反转的实现解析

《SpringIOC控制反转的实现解析》：本文主要介绍SpringIOC控制反转的实现,IOC是Spring的核心思想之一,它通过将对象的创建、依赖注入和生命周期管理交给容器来实现解耦,使开发者... 目录1. IOC的基本概念1.1 什么是IOC1.2 IOC与DI的关系2. IOC的设计目标3. IOC
阅读更多...
java中的HashSet与 == 和 equals的区别示例解析

java中的HashSet与 == 和 equals的区别示例解析

《java中的HashSet与==和equals的区别示例解析》HashSet是Java中基于哈希表实现的集合类,特点包括：元素唯一、无序和可包含null,本文给大家介绍java中的HashSe... 目录什么是HashSetHashSet 的主要特点是HashSet 的常用方法hasSet存储为啥是无序的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2