美团笔试4.23

估计是缺快递员了，劝退题，让咱们去送外卖

第一题黑白...就找矩阵(i+j)%==0和(i+j)%==1的最多和第二多的数的数量...全ac了。第二道超内存没时间改了

第二题是 codeforces 461B B. Appleman and Tree(树形dp)

黑白矩阵 print n + 1能过27%🤣

第一题就是矩阵按斜交替分为两组，最后两组各自的数字要一样，所以每组分别保存数字出现的次数，由于两组不能取一样的数字，所以每组要保存前二多的数字，根据情况判断选取，最后用总数字减去就行了，ac 第二题不一样就不知道了

黑白矩阵那题，可以将输入数字的坐标(i,j) 分为两类：i+j 为奇数（设为黑色），i+j为偶数（设为白色）。修改数字，使得黑色部分全是x，白色部分全是y，且x！=y。所以可以统计黑色部分所有数字的出现频度和白色部分所有数字的出现频度（我用了python dict）。为了修改数字最少，令x和y为出现频度最高的数字即可，不过还要考虑x==y以及一些边界条件。

第一题73%... x o x o o x o x x o x o 如果是合法的黑白矩阵，所有的x都会是同一个数字，所有的o也是 那么，把x和o位置的元素分别放到两个数组里，找出每个数组的众数，最后的矩阵就是由这两个众数交替出现组成的矩阵... 那么，所需要的翻转次数就是（矩阵元素数-众数1出现的次数-众数2出现的次数）... 但是！如果众数1和众数2是同一个数，就需要额外考虑，把众数2换成数组2里的次众数，算一次翻转次数，再把众数1换成数组1里的次众数，再算一次翻转次数，取小的那个，就可以了。。。 不知道还有哪里没考虑到... 第二题91%...感觉比第一题简单很多啊 行和列分开数，先数行，不用考虑重复。再在数列的时候判一下重就可以了。 在读数据的时候，判定一下是对行染色还是对列染色（看x1和x2是否相等） 建立两个hashmap<int,int[]>分别存储行和列，以行染色map举例，如果y1=y2，就是行染色，map的key存储行坐标也就是y，int[]数组里存储x1,x2，小的放在[0]，大的放在[1]，也就是这一行的起点和终点。 然后先统计行，每行的染色格子数是不会重复的，所以直接遍历map，把 每行的终点-起点+1 加到result上就可以了。 再统计列，每读一列时，遍历所有的染色行，当满足两个条件：这一行的行坐标在列的起点和终点之间，这一列的列坐标在行的起点和终点之间时，就是说这行覆盖了你要染色的列，就把重复格子+1（只可能覆盖一次）。遍历完所有的染色行后，把这一列的 终点-起点+1-重复格子数 加到result上即可。 同样...不知道还有哪里没有考虑到

怕了怕了

同求 两题都找不出有什么简化模型的思路..无从下手

我……那两题想了五分钟，果断交卷了😂

同求这两题

溜了溜了

绝对劝退题

黑白树没见过，想了想逻辑按递归做的，复杂度应该差很多。最后27%

幸亏被提前拉出来去面了，菜鸡瑟瑟发抖

挣扎了一下，27%，9%。。。果然菜鸡本人了

不是超时就是超内存，解不了了……

只有第二题45%，哭了

黑白矩阵是leetcode的994烂橘子的变型吧…………没写完，枯了

想了一个小时，无从下手，就树这个本来以为写的挺对的，没想到也是过27%，真是想不到还有什么其它情况