简介
该用户还未填写简介
擅长的技术栈
可提供的服务
暂无可提供的服务
最开始想的是回溯,但不是,应该用bfs。从做题角度,一般m*n矩阵不是bfs就是dfs或者二维动态规划。难点在于它不是简单的岛屿问题,或者最短路径什么的。难点在于每次向四个方向移动时,以前遍历过的位置还要遍历吗,应该要才行,因为不确定这个路径到遍历过的位置会不会跨越次数更少,但这样不会导致死循环吗,比如绕着个正方形一直死循环遍历。所以要很灵活的定义为,未遍历过或者跨越次数更少才允许往这个方向移动。
这样实现比先求出f2Left[i]表示i左边n2长子数组最大和,f2Right[i+n1]表示i+n1右边n2长最大子数组和,然后 滑动窗口迭代维护n1长的子数组的和,比较加上左边界f2Left或右边界f2Right谁更大的方法更优,因为边界情况能简化一些。然后一次遍历,left从0遍历到n-subArrN,同时记录更新最大值。具体实现上,可以先动态规划求出f1[i]表示左边界下标<= i 的n1
另外,可能有数学家已经证明V= (V-2)的情形,即此时的。那么就可以利用数学的取模mod 和除法 /,来迭代判断每次。>= V-2,这种情况不满足[-2,2]了,但是可以变成。这篇文章有答案,代码很简洁,但蛮难理解的。都必须满足[-2,2]之间。都满足,就说明YES。
(preSum[j] - preSum[i-1]) % b == 0,等价于 preSum[j] % b==preSum[i-1] % b。任意连续子数组subArr[i..j] = preSum[j] - preSum[i-1] 前缀和之差。那么subArr%b == 0即等价于。那么在遍历求前缀和时,就一边更新前缀和,一边哈希记录已有的前缀和%b的数量,一边ans+=数量。注意初始化map 有