又一波笔试题（雅虎，搜狐，创新工场，微软）
本帖最后由 longzuo 于 2010-10-21 14:30:10 编辑 雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
搜狐：
3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
创新工场：
4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
[解决办法]
1. 有2个弱判断准则,不过不知道3个加起来是不是和题目等价
1) 讲矩阵分成黑白棋盘格, 所有黑色格子的数字和等于白色格子的.
2)对任意一个位置, 他的值不大于周围(上下左右)4个临格的数值的和.
[解决办法]
2. 背包问题, 当然有些条件可以预先判断,比如(所有元素的和%m)!=0, 那么就不需要处理了.
[解决办法]
4. 直接遍历, O(n)
[解决办法]
5. 二分法查找分界点, 再二分法查找O(ln(n))
[解决办法]
1.第一反应是广搜，因为以前遇过一个这样类似的问题，应该是变式之类的。。
2.第一反应有数学方法，结合爆搜吧。一定是可以解的不过搜索量不小，可能用深搜好点。
3.第一反应是排列组合。因为规则给的很多
4.第一反应就是动归，没说的，经典问题。
5.第一反应是因为有局部的递减性质，那就找到断点，不要恢复（因为恐怕有阴人的地方，不是一次能够恢复得了的）。局部用二分查找。
