logo
publist
写文章

简介

该用户还未填写简介

擅长的技术栈

可提供的服务

暂无可提供的服务

Marscode小M的星球时代冒险——灵活bfs或dfs

最开始想的是回溯,但不是,应该用bfs。从做题角度,一般m*n矩阵不是bfs就是dfs或者二维动态规划。难点在于它不是简单的岛屿问题,或者最短路径什么的。难点在于每次向四个方向移动时,以前遍历过的位置还要遍历吗,应该要才行,因为不确定这个路径到遍历过的位置会不会跨越次数更少,但这样不会导致死循环吗,比如绕着个正方形一直死循环遍历。所以要很灵活的定义为,未遍历过或者跨越次数更少才允许往这个方向移动。

文章图片
#宽度优先#算法
MarsCode非重叠子数组的最大和——滑动窗口

这样实现比先求出f2Left[i]表示i左边n2长子数组最大和,f2Right[i+n1]表示i+n1右边n2长最大子数组和,然后 滑动窗口迭代维护n1长的子数组的和,比较加上左边界f2Left或右边界f2Right谁更大的方法更优,因为边界情况能简化一些。然后一次遍历,left从0遍历到n-subArrN,同时记录更新最大值。具体实现上,可以先动态规划求出f1[i]表示左边界下标<= i 的n1

文章图片
#算法#数据结构
MarsCode奇妙货币交易问题——数学

另外,可能有数学家已经证明V= (V-2)的情形,即此时的。那么就可以利用数学的取模mod 和除法 /,来迭代判断每次。>= V-2,这种情况不满足[-2,2]了,但是可以变成。这篇文章有答案,代码很简洁,但蛮难理解的。都必须满足[-2,2]之间。都满足,就说明YES。

#算法
Marscode连续子串和的整除问题——前缀和+哈希表

(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 有

文章图片
#散列表#数据结构
到底了