Wednesday, January 5, 2022

OSCHINA 社区最新专区文章

OSCHINA 社区最新专区文章

LeetCode 560. 和为 K 的子数组

Posted: 05 Jan 2022 06:57 AM PST

基本思路： 用DP也可以，但是会超时，由于元素中存在负数，没法通过滑动窗口来解决； 最优的思路使用前缀和； 简单的版本是采用O(n^2)的方法，两个两个减自己的前缀和，得到区间和，但是该方法会导致超时，可能是10月左右力扣更新了用例； 最佳的思路是采用Hash+前缀和的思想； 其实就是把前缀和思路精简一下，如果前缀1...

LeetCode 304. 二维区域和检索 - 矩阵不可变

Posted: 05 Jan 2022 04:34 AM PST

基本思想： 恶心在坐标算不清楚，这个时候需要画图； 和303题一样，直接前缀和打表，但是要注意，如果要计算方阵(0,0)->(m,n)的值，则要计算(m+1,n+1)，也就说横纵坐标需要都加1； 具体代码： class NumMatrix { public: NumMatrix(vector<vector<int>>& matrix) { ma.resize(matrix.size()+1,vector<int...

LeetCode 303. 区域和检索 - 数组不可变

Posted: 05 Jan 2022 03:53 AM PST

基本思路： 暴力搜索比较简单，直接算区间，但是衍生出一个所谓的前缀和的思路； 前缀和有点像DP+打表； 具体思路是建立数组n，n长度为length+1，并且n[i]表示前n-1位的和； 如此，如果求i～j元素的和，只需要用前j位元素的和减去前i-1位元素的和，即为标准答案； 即：n[j+1]-n[i]，注意一下n的实际含义，就很容易理解，...
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)