笔记记录

[zwzhome]

STL中关于二分查找的库函数： std::upper_bound(v.begin(), v.end(), val) std::lower_bound(v.begin(), v.end(), val)

判断两个迭代器之间的距离： std::distance(iter1, iter2)

对迭代器进行+-操作的有： std::next(iter, n)和std::advance(iter, n) 区别是next返回iter+n的新迭代器，对iter不修改。advance返回void，但是对iter的引用进行了+n操作。 比如查找set中的中位数。

[zwzhome]

剪绳子 动态规划。dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))，边界条件dp[1] = 1

[zwzhome]

接雨水问题 从左往右遍历一遍，能够得到每个i对应的左侧最大值left[i] 从右往左遍历一遍，能够得到每个i对应的右侧最大值right[i] 每个点能够接的雨水量是min(left[i], right[i]) - height[i]

[zwzhome]

单调栈 求每个值和离比自己大/小的最近左侧/右侧的值差多少索引，或者具体索引是多少。 删除k个字符，使得余下的字符表示的数字最小问题。 对S进行处理，要求处理后，每个字符只出现一次（删重），且字典序最小。

[zwzhome]

动态规划 最长上升子序列问题。 最长公共子串问题。 最长公共子序列。

[zwzhome]

滑窗 无重复字符的最长子串 S中包含T所有字符的最长子串

[zwzhome]

寻找重复的子树，把树hash。

[zwzhome]

贪心算法 任务调度器 重构字符串S，要求相邻字符不同