前缀和是一种重要的预处理,能大大降低查询的时间复杂度。可以简单理解为“数列的前 项的和”。 经典例题 https://leetcode-cn.com/problems/range-sum-query-immutable/ 学习资料 https://oi-wiki.org/basic/prefix-sum/ https://leetcode-cn.com/problems/binary-subar
子序列匹配给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”ace”是”abcde”的一个子序列,而”aec”不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10 亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,
滚动数组滚动数组的思想主要是用于优化 o(n)的空间复杂 使其变为 o(1),经常在动态规划中使用。动态规划中,经常会使用到 dp[i]这个状态,这个状态经常通常用来记录某个一项的状态,如果我们在求解的过程中,发现dp[i] 只依赖dp[i-1]或者 依赖 dp[i-2],那么我们就可以用可数的变量来记录它,如 pre,cur.下面,我们具体看下示例. 斐波那契数12345678910111213
方法一:Brian Kernighan 算法 12345678function countOne(int n ){ let ones=0; while(n>0){ n=n&(n-1) ones++ } return ones;}
盛水最多的容器https://leetcode.cn/problems/container-with-most-water/ 算法实现利用双指针,计算围城的面积,这里双指针移动的方式很有趣,就是往构成面积最大的情况,来决定左右指针的方向。