去谷歌面试。
其中有个很有趣的问题， 有个矩阵 里面 都是 0 或者 1 例如
1 0 1
0 0 0
1 1 1
现在又两个方法 一个是吧一行都刷成1 or 0 或者一列刷成1 or 0.
输入时两个矩阵， 问用方法刷其中一个矩阵， 问能刷到的最多只会有几个field 不一样
题目没看懂额，能不能举个例子呀？
同没看懂题目。。。
谷歌01矩阵问题 微信群上的聊天记录如下，请查收。
————— 2019-03-11 —————
B 12:33
就是说通过改其中一个矩阵，让它和另一个尽可能接近，返回最终不相同格子的个数？
命运的果实 12:35
是尽可能远的意思吧
B 12:36
问能刷到的最多只会有几个field 不一样………最多只有……
B 12:36
感觉首先是个文字题
B 12:37
是最多有几个不一样…还是只有几个不一样…
命运的果实 12:37
对啊就是极限情况嘛
B 12:37
那就是最多有几个不一样？
命运的果实 12:37
可以让第一个和第二个可以差多少
B 12:38
尽可能多的格子不一样？
命运的果实 12:38
比方第二个全是1
命运的果实 12:38
那我把第一个全部刷0
命运的果实 12:40
比方说第一个和第二个都是01，10
命运的果实 12:41
那肯定是不能全部不一样的，我没想到把第一个刷成10，01的方法
B 12:41
嗯嗯
B 12:41
明白了
B 12:42
尽可能不同
B 12:42
数据规模呢？格子最大有多大？
命运的果实 12:45
不知道，应该不影响做题
B 12:46
要是很小…暴力搜搜加cache？
A 12:46
题目的意思似乎是给两个矩阵 经过不定次数变换后 最少有几个格子不一样
B 12:47
最多只有嘛
B 12:47
分析一下
B 12:47
啥叫最多只有
A 12:47
最多只有
A 12:48
就是least
命运的果实 12:48
？
A 12:48
Minimize to extreme
B 12:48
我觉得最多就最多，只有就只有，反正看不太懂啥叫最多只有
命运的果实 12:48
应该是最多的
B 12:48
只有是最少
命运的果实 12:49
最少的就直接问最少了
B 12:49
有道理
命运的果实 12:49
可以暴力解吧
A 12:50
最多 是修饰 只有 的
B 12:50
如果格子小，试试暴力解
命运的果实 12:50
每行每列就算刷很多次也只有最后一次有效
RBY 12:50
最多只有感觉就是最多多少不一样吧
A 12:50
所以题意求的是不同格子的最小数量
B 12:51
难道这就是谷歌面试的威力
B 12:52
连题目本身都有坑
B 12:52
羡慕妹子
命运的果实 12:52
把只字去掉好了
命运的果实 12:52
别纠结这个
A 12:52
好 去掉只
A 12:52
那就最多几个格子不一样了
命运的果实 12:53
最多最少应该只影响判断条件
你好，可以麻烦拉一下微信群吗，我最近也在准备谷歌面试。谢谢
多谢了
谷歌01矩阵问题 微信群上的聊天记录如下，请查收。
————— 2019-03-11 —————
命运的果实 12:49
最少的就直接问最少了
B 12:49
有道理
命运的果实 12:49
可以暴力解吧
A 12:50
最多 是修饰 只有 的
B 12:50
如果格子小，试试暴力解
命运的果实 12:50
每行每列就算刷很多次也只有最后一次有效
RBY 12:50
最多只有感觉就是最多多少不一样吧
A 12:50
所以题意求的是不同格子的最小数量
B 12:51
难道这就是谷歌面试的威力
B 12:52
连题目本身都有坑
B 12:52
羡慕妹子
命运的果实 12:52
把只字去掉好了
命运的果实 12:52
别纠结这个
A 12:52
好 去掉只
A 12:52
那就最多几个格子不一样了
命运的果实 12:53
最多最少应该只影响判断条件
A 12:54
暴力解 解空间 好像非常大
A 12:55
2^(m n)
B 12:55
只反转行，或者列，就很简单
B 12:55
一起的话要考虑先后顺序和互相的影响…
A 12:55
顺序应该没影响吧
命运的果实 12:56
有的吧
B 12:56
我是说如果对于一行，一样的格子超过一半就反转
B 12:56
但再考虑列，就会有影响
A 12:57
对于每个点 flip 奇数偶数次不一样，顺序没关系
B 12:58
对暴力解是没关系
B 12:58
如果在考虑是否反转决策，就会有影响啦
B 13:01
要不先所有行，每一行相同超过一半反转，然后考虑列，再考虑行，直到出现循环或者无需要反转的行或者列…
B 13:01
我乱讲的
A 13:03
我错了，我误以为每行在flip了，实际是刷行或者列为一样
A 13:03
所以顺序确实重要
命运的果实 13:06
先行再列的贪心没准可行呀，能举出反例嘛…
B 13:06
还有一种思路
B 13:06
反转某一行或者某一列的时候检查是真的否导致不同格子数增加
B 13:06
如果没有就不反转