8月12日网易内推笔试测开算法题

2017-08-13

× 文章目录

1. 彩色方块
2. 操作序列
3. 堆棋子

彩色方块

小易有一些彩色的砖块。每种颜色由一个大写字母表示。各个颜色砖块看起来都完全一样。
现在有一个给定的字符串s,s中每个字符代表小易的某个砖块的颜色。小易想把他所有的砖块排成一行。如果 最多存在一对 不同颜色的相邻砖块,那么这行砖块就很漂亮的。

请你帮助小易计算有多少种方式将他所有砖块排成漂亮的一行。(如果两种方式所对应的砖块颜色序列是相同的,那么认为这两种方式是一样的。)
例如: s = “ABAB”,那么小易有六种排列的结果:
“AABB”,”ABAB”,”ABBA”,”BAAB”,”BABA”,”BBAA”
其中只有”AABB”和”BBAA”满足最多只有一对不同颜色的相邻砖块。
输入描述:
- 输入包括一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),s中的每一个字符都为一个大写字母(A到Z)。
输出描述:
- 输出一个整数,表示小易可以有多少种方式。
输入例子1:
ABAB
输出例子1:
2
解题思路 ：很水的一道题，理解题意后就知道对于存在两种以上颜色的砖块，则不可能“漂亮”；对于存在两种颜色的砖块，则有2种漂亮；对于一种颜色的砖块，则有1种漂亮。

Java AC代码 ：

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
 * Created by thd on 2017/8/12
 */
public class Main1 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        String s = sc.next();
        if (s == null) {
            System.out.println(0);
            return;
        }
        char[] ch = s.toCharArray();
        Set se = new HashSet();
        for (int i = 0; i < ch.length; i++) {
            se.add(ch[i]);
        }
        if (se.size() > 2)
            System.out.println(0);
        if (se.size() == 2)
            System.out.println(2);
        if (se.size() == 1)
            System.out.println(1);
    }
}

操作序列

小易有一个长度为n的整数序列,a_1,…,a_n。然后考虑在一个空序列b上进行n次以下操作:
1. 将a_i放入b序列的末尾
2. 逆置b序列
小易需要你计算输出操作n次之后的b序列。
输入描述:
- 输入包括两行,第一行包括一个整数n(2 ≤ n ≤ 2*10^5),即序列的长度。
- 第二行包括n个整数a_i(1 ≤ a_i ≤ 10^9),即序列a中的每个整数,以空格分割。
输出描述:
- 在一行中输出操作n次之后的b序列,以空格分割,行末无空格。
输入例子1:
4
1 2 3 4
输出例子1:
4 2 1 3
解题思路 ：
- 仔细观察输入输出后不难发现，对于奇数个数的输入，从第1位的右边开始加，例如123，则输出为 1 右边加2，左边加3，即312；对于偶数个的输入，从第1位的左边开始加，例如1234，则输出为 1左边加2，右边加3，左边加4，即4213。
- 当然，在观察后就能发现可以直接从输出数组的两端填充，即输出数组第0位填输入第n-1个，输出数组第n-1位填输入第n-2位。。。

代码在笔试时只能过50%，显示内存超出，但在结束后牛客网放出的题中可以AC。 ：

解法1


import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
/**
 * Created by thd on 2017/8/12
 */
public class Main2 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        Deque<Integer> list = new LinkedList<>();
        int i = 0;
        int num = n;
        if (num % 2 != 0) {
            while (i < n) {
                if (i < n)
                    list.addFirst(nums[i]);
                else
                    break;
                i++;
                if (i < n)
                    list.addLast(nums[i]);
                else break;
                i++;
            }
        }
        else {
            while (i < n) {
                if (i < n)
                    list.addLast(nums[i]);
                else break;
                i++;
                if (i < n)
                    list.addFirst(nums[i]);
                else
                    break;
                i++;
            }
        }
        for (int j = 0; j < n - 1; j++) {
            System.out.print(list.removeFirst() + " ");
        }
        System.out.print(list.removeFirst());
    }
}

解法2


import java.util.Scanner;
/**
 * Created by thd on 2017/8/12
 */
public class Main2_2 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int[] res = new int[n];
        int j = 0;
        int k = n - 1;
        int i = n - 1;
        while (false && j <= k){
            if (j <= k) {
                res[j++] = nums[i];
            }
            else break;
            i--;
            if (j <= k) {
                res[k--] = nums[i];
            } else break;
            i-- ;
        }
        for (int l = 0; l < n - 1; l++) {
            System.out.print(res[l] + " ");
        }
        System.out.print(res[n - 1]);
    }
}

堆棋子

小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.
输入描述:
- 输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数
- 第二行为n个棋子的横坐标x[i]，1 ≤ x[i] ≤ 10^9
- 第三行为n个棋子的纵坐标y[i]，1 ≤ y[i] ≤ 10^9
输出描述:
- 输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格
如样例所示:
- 对于1个棋子: 不需要操作
- 对于2个棋子: 将前两个棋子放在(1, 1)中
- 对于3个棋子: 将前三个棋子放在(2, 1)中
- 对于4个棋子: 将所有棋子都放在(3, 1)中
输入例子1:
4
1 2 4 9
1 1 1 1
输出例子1:
0 1 3 10
解题思路 ：找到一个坐标让所有棋子距离这个距离的曼哈顿距离之和最小。 x和y是独立的，要考虑x和y范围内的所有坐标 。计算这个坐标到所有棋子的距离分别是多少，让后维护k个棋子对于这个坐标最小曼哈顿距离和即可。

Java ac代码

import java.util.Arrays;
import java.util.Scanner;
/**
 * Created by thd on 2017/8/12
 */
public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n + 1];
        int[] y = new int[n + 1];
        //int[][] d = new int[n + 1][n + 1];
        long[] res = new long[n + 1];
        for (int i = 1; i < n + 1; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 1; i < n + 1; i++) {
            y[i] = sc.nextInt();
        }
        for (int i = 1; i < n + 1; i++) {
            res[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < n + 1; i++) {
            long num = 0;
            for (int j = 1; j < n + 1; j++) {
                for (int k = 1; k < n + 1; k++) {
                    int[] distance = new int[n + 1];
                    for (int l = 1; l < n + 1; l++) {
                        distance[l] = Math.abs((y[l] - y[k])) + Math.abs((x[l] - x[j]));
                    }
                    Arrays.sort(distance);
                    num = 0;
                    for (int m = 1; m < i + 1; m++) {
                        num += distance[m];
                    }
                    res[i] = Math.min(res[i], num);
                }
            }
        }
        for (int i = 1; i < n; i++) {
            System.out.print(res[i] + " ");
        }
        System.out.println(res[n]);
    }
}