【一级讲解】是0还是1,这是个问题
程序员文章站
2022-03-15 11:09:52
...
是0还是1,这是个问题
题意:
一个n*m方阵,我们可以选择其中任意个元素,使其值+1.执行该操作后,要求方阵中相邻的元素不相等.
例如方阵
3 2 2 1 3 3 2 3 2 3
2 3 1 1 2 -----> 2 3 2 1 2
3 3 2 1 2 3 4 3 2 3
问题分析:
由于这道题的原题没有公开出来,我记得原题还有一个说明是每个数最多只能操作一次。当时我就挺头疼的,因为如果没有这个限制这道题就会变得很简单,只要一行行的检验是否符合条件,若否则一直加一直到符合条件。
因为我一开始想的就是没有这个条件的解法,所以再加上这个条件后我的思维就彻底被锁死了,一直想要如何去优化之前想的那个算法来**这个条件。
事实上这个算法是根本解决不了的,因为动一发牵全身,你没有办法保证下一行检索时符合条件。
现在看完ACM的题解,再回过头看,还是要从题目入手,
其值+1
这个能干什么?当矩阵中的数都很相近的时候,它对是否符合题目条件有很大影响,但当矩阵中的数相差很大时,作用就微乎其微了。
我们再回到数的本身去看,既然我们没有办法通过直接比较再做选择(因为这次做出的选择可能等其他数字做出选择时就不符合条件了甚至可能出现两种选择都会无效的情况)+1可以改变这个数的什么性质?是的,奇偶性!
这里采用ACM协会技术部林振杰在公开课上的PPT
只要我们控制每一个数字它本身的奇偶性即可,由于题目具体范围条件以及样例的缺失,本次题解就不写代码啦~。
主要是想提醒下,千万不要让自己陷入思维定势,一旦锁死在错误的算法就很难脱身了,当卡住的时候,不妨退一步,看看有无其他的思维方式,试着换一下关注的重点。