本文写于 2019年03月16日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

今天早上参加了字节跳动的笔试。

1552716078228

4 道题,做出 3 题,遗憾的是不会做的那一题我甚至不知道他考察的算法是什么,以前至少还知道,哦,这是计算几何,我不会,这是动态规划,我写不出来,这次干脆连题目都不知道问的是什么了。
剩下 3 题都比较简单。

第 1 题,找零。

1552716160329

由于货币是 1、4、16、64 成倍数关系,所以贪心成立。

10:04,1 次直接 AC。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = 1024 - n;
        int ans = 0;
        int[] a = {1, 4, 16, 64};
        for (int i = a.length - 1; i >= 0;i--) {
            ans += x / a[i];
            x %= a[i];
        }
        System.out.println(ans);
        in.close();
    }
}

第 2 题,万万没想到之聪明的编辑。

1552717936651

字符串的处理,估计是考查代码能力的,是不是能够足够细心把一步步操作写清楚。

首先从题意可以知道,连续 3 个同样的字母,就消去 1 个,变成 2 个。

并且,显然可以知道,如果有连续 $n$ 个同样的字母,$n \geqslant 3$,那么最终会变成 2 个该字母,例如 wooooooow 中间有 7 个 o,每连续 3 个同样的字母连在一起就去掉一个,那么若干次操作以后会直接变成 oo

所以,第 1 条规则的化简,就是,如果存在连续 $n$ 个相同的字母,则削减为 2 个。

第 2 条规则,由于说了是从左往右执行的,所以直接模拟。

经过了第 1 条规则的处理以后,剩下的字符串要么是由不同的单字母组成,最多同一个字母连续出现 2 次,从左往右遍历,看是不是存在 AABB 的格式,模拟处理。

难度可能是在于,删除字母以后,字符数组需要将右边的字符左移以填补删除的空位,或者需要构造新的字符串对象,这个操作很容易出错,必须特别小心。

如果用正则表达式来写就非常简单了,这 2 条规则对应的 RegEx 分别是 ("([a-z])\\1{2,}", "$1$1")("([a-z])\\1{1}([a-z])\\2{1}", "$1$1$2"),很简单,不解释。

10:19,1 次直接 AC。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            s = s.replaceAll("([a-z])\\1{2,}", "$1$1");
            s = s.replaceAll("([a-z])\\1{1}([a-z])\\2{1}", "$1$1$2");
            System.out.println(s);
        }
        in.close();
    }
}

第 3 题,奖品分配。

1552718290183

有点难,一下子没有读懂题目意思,所以先做了第 4 题。

第 4 题,剪绳子。

1552718325603

除了样例,还需要注意以下 3 种情况:

  • 5 根绳子,分别为 1、2、6、8、9,需要 3 段等长的,显然是 3 段长度为 6 的,似乎是排序以后倒着贪心?
  • 5 根绳子,分别为 1、2、3、4、100,需要 2 段等长的,显然是将 100 分为 2 段 50,所以排序不可能了,贪心也不成立。
  • 5 根绳子,分别为 1、2、3、50、100,需要 3 段等长的,显然是将 100 分为 2 段 50,加上已经有的那段 50,而不是尝试 100 三等分。

综上,这题既不是贪心(况且贪心已经考过一题了),也不太会是动态规划。

这题的决胜关键在于,花多长时间思考才能意识到这题是二分答案,如果能意识到,那么二分搜索的部分没有任何难度。

左端点是 0,因为显然每一段的长度必须大于 0,右端点是最长的那根绳子,因为不管怎么分,不管分多少段(哪怕是 1 段),都不可能比最长的甚至还长。

二分中点就是期望的裁剪后的长度 $mid$,用这个长度 $mid$ 去算每一根绳子如果切成 $mid$ 长度能够切成多少段,然后加起来。所有段数相加,和目标需要的段数比较。

由于二分中点是浮点数,所以除法结果向下取整计算段数。

  • 如果切出来的段数大于目标段数,说明切得太细了,那么左端点变成 $mid$,尝试加大切割长度。
  • 如果切出来的段数小于目标段数,说明要减小切割长度,右端点左移。
  • 如果切出来的段数等于目标段数,由于题目要求长度尽可能长,所以等效于要加大切割长度,左端点右移。

10:43,1 次直接 AC。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        double left = 0;
        int right = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            if (a[i] > right) {
                right = a[i];
            }
        }
        double ans = binarySearch(a, left, right, m);
        System.out.printf("%.2f", ans);
        in.close();
    }

    private static double binarySearch(int[] a, double left, double right, int target) {
        while (Math.abs(left - right) > 1E-6) {
            double mid = (left + right) / 2;
            int count = 0;
            for (int x : a) {
                count += (int)(x / mid);
            }
            if (count < target) {
                right = mid;
            } else if (count >= target) {
                left = mid;
            }
        }
        return left;
    }
}

还有 80 分钟,回过头做第 3 题。

首先,理解题目意思花了 30 分钟,到 11:10 左右我才看懂第 2 组样例的那个 8 是怎么回事。

然后开始思考到底这题是考查什么东西。

到了大概 11:20 多,接近 11:30 的时候,弹出一个系统消息,说,第 3 题增加了样例的解释,已更新题目,请刷新页面查看。

我刷新了,然后看到题目下面多了这一句话。

1552719269989

垃圾出题人,害我白花 30 分钟去想那个 “比左右高” 到底是什么意思。

然后还剩 30 分钟,却完全不知道这题考的是什么。

随手糊一个算法上去,通过了 11.11% 的测试数据,剩下的超时。

不管了。

1552719362062

后来问了 zerol,他给出的第 1 个思路是,往图论上面转化。

看成有向图。一个必须比另一个大就连边。想想是不是无环的。如果是那就 DAG 上 DP,可以按拓扑序计算答案(或者记忆化搜索),没出度是 1 否则是 max 后继节点 +1。

后来进一步思考,zerol 给出了简单做法:

所有数字从小到大排,按这个顺序贪心填。其实就是一种拓扑序,注意相同数字相邻的情况。就按一定顺序填,数字从小到大,一批一批填。


0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论