2019校招真题_被3整除/安置路灯/迷路的牛牛

01_被3整除

题目描述

小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。

并且小Q对于能否被3整除这个性质很感兴趣。

小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。

输入描述:
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。
输出描述:
输出一个整数, 表示区间内能被3整除的数字个数。

解题思路

计算数列前12项能否被3整除，结果如下表：
图片说明

可以得出一个结论：
数组的f(3n+1) n>=0项不能被3整除，其余的可以被整除。
所以用数学归纳法可以得出一下公式：
设数组前n项中能被3整除的项的个数为count,则
count=2*n/3;
因此，要计算第l到r项中能被3整除的数字个数，只需要计算1到l和1到r能被3整除的数字的个数，再相减即可。
count(l,r)=count(1,r)-count(1,l)+1
但在计算中会忽略边界问题，比如
第2到第5项
count(2,5)=count(1,5)-count(1,2)=3-2+1=2
而实际有3个可以被3整除的数。
因此需要添加一个判段条件
“l%3!=0&&(l+1)%3==0||l%3==0”
如果l%3!=0&&(l+1)%3==0,比如f(2)、f(5)
l%3==0,比如f(3)、f(6)
此时就需要给差值上加1。因为在求通项时是从n=1开始的，而实际计算时n不一定为1。

java代码实现：

import java.util.Scanner;
public class 被3整除 {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int l = sc.nextInt();
    int r = sc.nextInt();
    System.out.println(Division(l, r));
    }

    public static int Division(int l, int r) {
    int flag = 0;
    if (l % 3 != 0 && (l + 1) % 3 == 0 || l % 3 == 0)
        flag = 1;
    int cl = 2 * l / 3;
    int cr = 2 * r / 3;
    return cr - cl + flag;
    }

}

02_安置路灯

题目描述

小Q正在给一条长度为n的道路设计路灯安置方案。

为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。

小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。

小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯

解题思路

贪心算法求解：
当遇到第一个'.'时，表示该位置sum需要被照亮，此时不安装路灯，在它的下一个位置安装路灯，即sum+1;因为该路灯位置的下一个位置sum+2已经被照亮了，因此下标+2；不需要处理'X'的情况，因为此处不需要安装路灯。

java代码实现：

import java.util.Scanner;

public class 安置路灯 {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    for (int i = 0; i < t; i++) {
        int n = sc.nextInt();
        String s = sc.next();
        System.out.println(Count(n, s));
    }
    }
    private static int Count(int n, String s) {
    int flag = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '.') {
        flag++;
        i = i + 2;
        }
    }
    return flag;
    }
}

03_迷路的牛牛

题目描述

牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。
输出描述:
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。

解题思路

如果一直向右转就是顺时针旋转，反之就是逆时针旋转。因为最初面朝正北，如果转4次或者4整数倍数次，还是面朝正北。所以，只需要统计向左旋转L和向右旋转R的次数，相减，就可以相互抵消一部分旋转次数。
记向左旋转次数为count_L，向右旋转次数为count_R。
用count_L和count_R相减之后的差的绝对值对4取余；
①count_L - count_R > 0
如果余数为1，则最后的方向为“W”
如果余数为3，则最后的方向为“E”
②count_L - count_R > 0
如果余数为1，则最后的方向为“W”
如果余数为3，则最后的方向为“E”
③count_L - count_R = 0
说明向左和向右转的次数一样，最终方向还是“N”

若余数为2，不管count_L 和 count_R 大小关系如何，都是旋转两次，最终方向为“S”

java代码实现：

import java.util.Scanner;

public class 迷路的牛牛 {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String str = sc.next();
    int count_L = 0;
    int count_R = 0;
    for (int i = 0; i < n; i++) {
        if (str.charAt(i) == 'L')
        count_L++;
        if (str.charAt(i) == 'R')
        count_R++;
    }

    int d = Math.abs(count_R - count_L);

    if (d % 4 == 0) {
        System.out.println("N");

    }

    if (d % 4 == 1) {
        if (count_R > count_L)
        System.out.println("E");
        else
        System.out.println("W");
    }

    if (d % 4 == 2) {
        System.out.println("S");
    }

    if (d % 4 == 3) {
        if (count_R > count_L)
        System.out.println("W");
        else
        System.out.println("E");

    }

    }

}