网易2017校招笔试算法题(一)

题目一：数字翻转

对于一个整数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))的值.

解题思路

本题思路较为简单，题目中已经给出了提示，就是实现Rev方法，只要实现Rev方法剩下的就没什么难度了。将一个整型数字按位翻转可以通过算数计算来实现，也可以通过编程语言的api来实现，因为我还没接触过Java的翻转字符串Api，所以就采用算数计算来实现了。
设原数为x，反数为y；
则y的初值为0；
将原数的个位数字得出乘以10，再加上下一个原数的个位数字，每次求个位数字后，原数除以10；
即：y=y*10+x%10;x/=10;

Java实现（已AC）

import java.util.Scanner;

public class reverse {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        System.out.println(Rev(Rev(m)+Rev(n)));
    }

    /**
     * 将一个整数按位翻转并去除前导0
     * @param x 待翻转的整数
     * @return 翻转后的整数
     */
    private static int Rev(int x) {
        int r = 0;
        while (x > 0) {
            r = r * 10 + x % 10;
            x /= 10;
        }
        return r;
    }
}

题目二：暗黑字符串

一个只包含‘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）.

输出描述

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

解题思路

一开始看到这个题的时候我是打算用排序的思路做的，到后来发现其实行不通，反而越来越复杂。于是就重新思考了。当然这个题在当时笔试的时候我并没有做出来。

参考了http://www.itdadao.com/articles/c15a387781p0.html 的思路，我终于恍然大悟。
以下是我自己的理解：

由于题目要求是长度为3的子串，所以当前两个字符确定的时候，第三个字符的写法个数也就能确定了。例如如果前两个字符是AB的时候，第三个字符就只能是A或者B，这样才能是暗黑字符串。
如果前两个字符是AA的时候，第三个字符就可以是A、B、C任意一个字符；
这样，就可以把暗黑字符串的情况分为这两种，通过这两种类型的暗黑字符串就可以构建 n+1 长度的暗黑字符串：
若某一字符串的最后两个字符不相同，即AB型的时候，只要在最后添加A或者B就是新的暗黑字符串，每一个长度为n的暗黑字符串可以构建出2个n+1长度的暗黑字符串（AB型）；
若某一字符串的最后两个字符相同，即AA型的时候，最后一个字符就可以是A、B、C任意一个字符；即每一个长度为n的暗黑字符串可以构建出3个n+1长度的暗黑字符串（AA型）；

为了便于后面的计算，需要将新构建出的暗黑字符串进行分类：
1个AB型可以构建1个AB型暗黑字符串和1个AA型暗黑字符串；
1个AA型可以构建1个AA型暗黑字符串和2个AB型暗黑字符串；

长度为n的字符串的两种暗黑字符串个数相加就是n+1长度字符串的暗黑字符串个数。

由以上分析得：
设长度为n（n>=2）的字符串的AB型暗黑字符串个数为x1，AA型暗黑字符串个数为y1;
设长度为n+1的字符串的AB型暗黑字符串个数为x2,AA型暗黑字符串个数为y2;
则长度为n+1的字符串的AB型暗黑字符串个数为：x2=x1+2*y1;
长度为n+1的字符串的AA型暗黑字符串个数为：y2=x1+y1;
其中当n=2的时候，x1=6;y1=3;
另外当n=1的时候，暗黑字符串的总个数为３；

Java实现（已AC）

import java.util.Scanner;

public class dark {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        System.out.println(cal(m));
        in.close();
    }

    /**
     * 计算长度为n的字符串的暗黑字符串个数
     * @param n 字符串长度
     * @return 暗黑字符串个数
     */
    private static long cal(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 3;
        long x1 = 6;//初始AB型暗黑字符串个数
        long y1 = 3;//初始AA型暗黑字符串个数
        n = n - 2;
        while (n-- > 0) {
            long x2 = x1 + 2 * y1;//n+1长度字符串的AB型暗黑字符串个数
            long y2 = x1 + y1;    //n+1长度字符串的AA型暗黑字符串个数
            x1 = x2; //恢复x1,x2的值
            y1 = y2;
        }
        return x1 + y1;
    }
}

题目三：回文序列

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：
{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)，以空格分隔。

输出描述

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

解题思路

有两个指针，一个指向序列的开始位置，一个指向序列的末尾位置；
前后比较两个指针指向位置的数字：
若头小于尾，则把头指向的数字加到头后面的位置，同时头指针指向被加的数字，也就是头指针后移一位；此时记一次变换；
若头大于尾，则把尾指向的数字加到尾前面的位置，同时尾指针指向被加的数字，也就是尾指针前移一位；此时记一次变换；
若头尾指针指向的数字相等，则头指针后移一位，尾指针前移一位，继续比较，不计变换次数；
如此，直到头指针指向的位置不小于尾指针指向的位置，停止比较；
此时就可得出变换的次数；

Java实现（已AC）

import java.util.Scanner;

public class palindrome {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int[] q = new int[m];
        for (int i = 0; i < m; i++) {
            q[i] = in.nextInt();
        }
        System.out.println(changeTime(q));
        in.close();
    }

    /**
     * 计算成为回文序列需要变换的最少次数
     * @param q 原始序列
     * @return 变换次数
     */
    private static int changeTime(int[] q) {
        int times=0;
        int start=0;//头指针
        int end = q.length - 1;//尾指针
        while (start < end) {
            if (q[start] < q[end]) {
                q[start + 1] += q[start];
                start++;
                times++;
            } else if (q[start] > q[end]) {
                q[end - 1] += q[end];
                end--;
                times++;
            } else {
                start++;
                end--;
            }
        }
        return times;
    }
}

题目四：优雅的点

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

输入描述

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

输出描述

输出为一个整数，即为优雅的点的个数，即12。

解题思路

思路一：

这是一开始的思路，但是复杂度过高，没有AC。
把n看成直角三角形的斜边的平方，那么就只需要找出可以构建直角三角形的坐标为整数的点即可；
由于圆心在坐标原点，只需要计算出第一象限的点，在乘以相应的倍数即可。如果点在坐标轴上，那么需要乘以2；如果点不在坐标轴上，就乘以4；
如此即可计算出所有坐标为整数且在圆上的点的个数；

思路二：

由于思路一复杂度过高，就需要进行简化。
仍然只计算第一象限中的点，
将以上的判断点为两部分：在坐标轴上、不在坐标轴上。
但是判断是否为整数坐标更换为另外一种方法：
设横坐标为x，则纵坐标y=sqrt（n-x * x）;如果x * x+y * y=n,则这个点就是整数点（整型计算的特性）。
所有不在坐标轴的点在其他三个象限内都有对应的点，所以需要乘以4；
再来考虑坐标轴上的点，直接判断sqrt（n） × sqrt（n）==n；若是则再加4；因为最多就只有处在圆边缘的4个点。

Java实现

思路一：（未AC，结果正确）

import java.util.Scanner;

public class CirclePoint {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        System.out.println(point(m));
    }

    private static int point(int n) {
        int count = 0;
        for (int i = 0; i * i <= n; i++) {
            for (int j = 0; j * j <= n; j++) {
                if (i * i + j * j == n) {
                    if ((i == 0 && j != 0) || (i != 0 && j == 0)) {
                        count += 2;
                    } else {
                        count += 4;
                    }
                }
            }
        }
        return count;
    }
}

思路二：（已AC）

import java.util.Scanner;

public class CirclePoint {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        System.out.println(point2(m));
    }

    private static int point2(int n) {
        int count = 0;
        for (int i = 1; i * i < n; i++) {
            int j = (int) Math.sqrt(n - i * i);
            if (i * i + j * j == n) {
                count++;
            }
        }
        count*=4;
        int x = (int) Math.sqrt(n);
        if (x * x == n) {
            count += 4;
        }
        return count;
    }
}