牛客网——网易2017秋招编程题集合

在牛客网做的“网易2017秋招编程题集合”练习题。

注：部分题解法学习于他人的解法。

回文序列

题目 样例 思路 两个指针前后同时开始遍历，互相比较，哪边小哪边往中间移并加上前一个遍历的值，记录转换次数，直至不小于，然后判断是否相等，相等则i、j同时往中间移一位进入下一轮循环，不相等则继续判断哪边小哪边往中间移。

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int len=in.nextInt();
        int[] item=new int[len];
        for(int i=0;i<len;i++){
            item[i]=in.nextInt();
        }
        in.close();
 
        int count=0;    //转换次数
        int i=0, j=len-1;
        while(i<j){
            while(i<j && item[i]<item[j]){
                i++;
                item[i] += item[i-1];	//加上前一个遍历的值
                count++;
            }
            if(item[i]==item[j]){
                i++;
                j--;
                continue;	//相等则同时向中间移，并进入下一轮循环
            }
            while(i<j && item[i]>item[j]){
                j--;
                item[j] += item[j+1];
                count++;
            }
            if(item[i]==item[j]){
                i++;
                j--;
                continue;
            }
        }
        System.out.println(count);
    }
}

优雅的点

题目 样例 思路 根据半径平方计算出半径（double），强转为int，截取后32位，然后x从半径遍历到0，计算出y，判断x和y的平方和是否等于半径平方，若相等则优雅点加1。 代码

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int radiusSquare=scanner.nextInt();
		scanner.close();

		int count=0;	//优雅点个数
		int radius=(int) Math.sqrt(radiusSquare);//”假”半径

		//radius小于等于真实半径
		//如果从i=0递增，i<radius，如果radius小于真实半径且为整数，(0,radius)和(radius,0)都是优雅点且在在统一象限，但i<radius，所以少计数一次
		//如果从i=0递增，i<=radius，如果radius等于真实半径且为整数，(0,radius)和(radius,0)都是优雅点，单个象限多计数了一次
		for(int x=radius;x>0;x--){
			int y=(int) Math.sqrt(radiusSquare-x*x);
			if(x*x+y*y==radiusSquare){
				count++;
			}
		}
		System.out.println(count*4);	//四个象限
	}
}

跳石板

题目 样例 思路 运用动态规划。创建数组记录到达每个石板所需最少步数，石板编号为数组索引，到达该石板所需最少步数为数组值。到达起始位置所需步数为0，所以初始化数组起始位置为0，其余部分初始化为无穷大（Integer.MAX_VALUE）。遍历数组，如果数组值为无穷大，即为不可达，跳过进入下一轮循环；如果数组值不是无穷大，获取当前石板编号的所有约数（不含1和它本身），依次遍历，计算能到达的下一石板，步数在当前基础上加1，如果小于下一石板最小步数则更新。 代码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int M = scanner.nextInt();
		scanner.close();
		int res=leastJump(N, M);
		System.out.println(res);
	}

	public static int leastJump(int N, int M){
		//石板编号为索引，到达该石板所需最少步数为数组值
		int steps[]=new int[M+1];	//从N到M，记录到每一个位置所需的步数

		for(int i=N+1;i<=M;i++){	//起始位置steps[N]为0，其余初始化为Integer.MAX_VALUE
			steps[i]=Integer.MAX_VALUE;
		}

		for(int i=N;i<=M;i++){
			//如果steps[i]为Integer.MAX_VALUE，即为不可达，跳过不处理
			if(steps[i]!=Integer.MAX_VALUE){
				ArrayList<Integer> list=getAllFactor(i);
				for(Integer each:list){
					int temp=i+each;	//到达的位置（石板编号）
					int count=steps[i]+1;	//到达下一个石板steps[temp]最少步数 = 到达当前石板最少步数 + 1
					if(temp<=M&&count<steps[temp]){	//如果从i到达位置tmp的次数比以前记录的小，更新steps[tmp]
						steps[temp]=count;
					}
				}
			}
		}
		return steps[M]==Integer.MAX_VALUE?-1:steps[M];
	}

	// 获取N所有大于1、小于N的约数
	public static ArrayList<Integer> getAllFactor(int N) {
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 2; i <= Math.sqrt(N); i++) {
			if (N % i == 0) {
				list.add(i);
				if (i != N / i) { // 防止重复添加，如16=4*4
					list.add(N / i);
				}
			}
		}
		return list;
	}
}

暗黑的字符串

题目 样例 思路 计算长度为n的字符串有多少个是暗黑字符串（记为f(n)），跟n-1时状态有关。 从n-1往后扩展一位还要保证是暗黑串，则只需要知道n-1状态末尾两个字符是否相同，相同记为S(n-1)，不相同记为D(n-1)，则f(n-1)=S(n-1)+D(n-1)。 若n-1状态末尾两个字符相同，则保持暗黑串添加‘A’、‘B’和‘C’均可，即有3*S(n-1)种； 若n-1状态末尾两个字符不同，则保持暗黑串只能添加末尾两个字母中的一个，即有2*D(n-1)种。 所以f(n)=3*S(n-1)+2*D(n-1)=2*f(n-1)+S(n-1)。 S(n-1)项无法消除，需要考虑寻找S(n-1)和f(n-2)之间的关系。 如果n-1状态末尾两个字符相同，则扩展后有1/3是末尾两个字符相同（有S(n-1)种），2/3是不相同（有2*S(n-1)种）。 如果n-1状态末尾两个字符不同，则扩展后有1/2是末尾两个字符相同（有D(n-1)种），1/2是不相同（有D(n-1)种）。 所以S(n)=S(n-1)+D(n-1)，D(n)=2*S(n-1)+D(n-1)。因此可以得到S(n)=f(n-1)，代入f(n)=2*f(n-1)+S(n-1)中， 得到：f(n)=2*f(n-1)+f(n-1)。 代码

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		System.out.println(getBlackStr(n));
	}
	public static long getBlackStr(int n){
		if(n<1) return -1;
		long dp[]=new long[31];	//题目n范围为[1,30]
		dp[1]=3;
		dp[2]=9;
		for(int i=3;i<=n;i++){
			dp[i]=2*dp[i-1]+dp[i-2];
		}
		return dp[n];
	}
}

数字翻转

题目 样例 思路 依次计算数字的每一位，存放到ArrayList中，然后反向遍历，从非0数开始，依次乘以相应位的倍数。 代码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
    	Scanner scanner=new Scanner(System.in);
    	int x=scanner.nextInt();
    	int y=scanner.nextInt();
    	scanner.close();
    	System.out.println(rev(rev(x)+rev(y)));

    }
    public static int rev(int num){
		//计算每位数
    	ArrayList<Integer> list=new ArrayList<>();
    	while(num>0){
    		int mod=num%10;
    		list.add(mod);
    		num /= 10;
    	}

		//从非0开始
    	int beginning=list.size()-1;
    	for(beginning=list.size()-1;beginning>=0;beginning--){
    		if(list.get(beginning)!=0){
    			break;
    		}
    	}

		//计算rev结果
    	int res=0;
    	int times=1;
    	for(;beginning>=0;beginning--){
    		res += list.get(beginning) * times;
    		times *= 10;
    	}
    	return res;

    }
}

最大的奇约数

题目 样例 思路 代码

买苹果

题目 样例 思路 代码

计算糖果

题目 样例 思路 代码