东莞营销型网站建设公司,html网页制作平台,毕业设计做网站要求,深圳市宝安区中心医院文章目录 1. 双指针1.1 两数之和1.2 三数之和1.3 盛最多水的容器1.4 接雨水 2. 字串2.1 滑动窗口最大值 3. 动态规划4. 多维动态规划4.1 最长回文字串 1. 双指针
1.1 两数之和 思路#xff1a;因为是有序数组#xff0c;
1.2 三数之和 题目要求不能重复 思路#xff1a;三… 文章目录 1. 双指针1.1 两数之和1.2 三数之和1.3 盛最多水的容器1.4 接雨水 2. 字串2.1 滑动窗口最大值 3. 动态规划4. 多维动态规划4.1 最长回文字串 1. 双指针
1.1 两数之和 思路因为是有序数组
1.2 三数之和 题目要求不能重复 思路三数之和可以变为两数之和固定一个数字看两数之和此时target变为target-固定的数字要先对数组排序然后依次固定一个数求两数之和。
避免重复解 重复解有两种情况
固定数字的时候 【-1-1】已经固定过-1得出了一组解又有一个-1得出得还是同一组解重复----- 解决在固定数字的时候判断前一个是不是和自己一样一样就跳过这样做是因为数组已经有序两数之和双指针寻找的时候【-10011】 ------- 解决在双指针移动的时候当左指针和它前面元素一样时i当右指针和它后面一个元素一样时j–
1.3 盛最多水的容器 思路双指针解决两个指针分别指向最左和最右计算容量因为最左和最右宽度是最大的每次都是移动较低的那一边这样宽度减小了但是高度增加了才有可能容量变大每次移动后计算容量做max取大的。
1.4 接雨水 思路单调栈解决将柱子依次入栈要入栈的柱子小于栈顶柱子高度时可以入栈当要入栈的柱子高度大于栈顶柱子的高度时此时表示形成凹陷可以接水此时计算凹陷将栈顶的这个柱子出栈该出栈柱子的左边也就是现在的栈顶就是凹陷的左边入栈的这个柱子就是凹陷的右边取左右的最小高度该最小高度减去出栈柱子的高度就是凹陷的高左右之差就是凹陷的宽算盛水量。这样依次尝试将所有柱子加入单调栈中有凹陷就出栈并计算容量最后sum得到总容量。
2. 字串
2.1 滑动窗口最大值 思路单调队列解决对头就是最大值遍历数组将每个元素入队当窗口大小都充满元素时出队。
3. 动态规划
4. 多维动态规划
4.1 最长回文字串 思路不用动态规格用中心开发的思想 两种情况
回文子串是奇数中点有一个字符 aba依次遍历字符串并认为该字符是中心判断中心的前后字符是否一样一样再判断前面的前面和后面的后面是否一样并且用两个变量记录回文的left 和 right回文字串是偶数中点两个字符 abba:依次遍历字符串每次取两个字符并且要相等再以中心扩展一样则记录回文的left 和 right
