可以写代码的网站有哪些问题,网络营销课程大概学什么内容,做网站建网站公司,wordpress搭建商城滑动窗口和双指针 一、循环不变量1.1 定义1.2 总结 二、使用循环不变量写对代码2.1 注意2.2 总结 三、滑动窗口3.1 固定长度的滑动窗口#xff08;同向交替移动的两个变量#xff09;3.2 不定长度的滑动窗口3.2.1 定义3.2.2 总结 3.3 计数问题3.3.1 标准3.3.2 总结 3.4 使用数… 滑动窗口和双指针 一、循环不变量1.1 定义1.2 总结 二、使用循环不变量写对代码2.1 注意2.2 总结 三、滑动窗口3.1 固定长度的滑动窗口同向交替移动的两个变量3.2 不定长度的滑动窗口3.2.1 定义3.2.2 总结 3.3 计数问题3.3.1 标准3.3.2 总结 3.4 使用数据结构维护窗口性质 四、链表中的双指针问题五、双指针相向交替移动的两个变量5.1 定义 六、小结 一、循环不变量
1.1 定义
循环前、中、后保持不变。循环不变量是指我们在编写代码的过程中要一直循序不变的性质这样的性质是根据要解决的问题由我们自己定义的。循环不变量是我们写对一个问题的基础保证了在初始化、循环遍历、结束这三个阶段相同的性质使得一个问题能够被正确解决。
1.2 总结
区间不同的定义决定了不同的初始化逻辑、遍历过程中的逻辑。
二、使用循环不变量写对代码
2.1 注意
在写代码时一定要明确自己对变量以及区间的定义是什么并且在编写代码的过程中保持定义不变。
2.2 总结
循环不变量是人为定义的无需记忆。只要我们在编码的开始明确了我们对变量和区间的定义写对代码就是水到渠成的事情了。
三、滑动窗口
3.1 固定长度的滑动窗口同向交替移动的两个变量
3.2 不定长度的滑动窗口
3.2.1 定义
1、有一类数组上的问题需要使用两个指针变量我们称为左指针和右指针同向、交替向右移动完成任务。这样的过程像极了一个窗口在平面上滑动的过程因此我们将解决这一类问题的算法称为滑动窗口问题。 2、掌握好这一类滑动窗口的问题需要先从暴力解法开始分析滑动窗口利用了问题本身的特点在两个指针同向、交替向右移动的过程中少考虑了很多暴力解法需要考察的情况将时间复杂度降到了线性级别O(N)这里N是数组的长度。
3.2.2 总结
滑动窗口是一类通过使用两个变量在数组上同向交替移动解决问题的算法。这一类问题的思考路径通常是先思考暴力解法分析暴力解法的缺点一般而言暴力解法的缺点是重复计算然后结合问题的特点使用双指针技巧对暴力解法进行剪枝。因此思考算法设计的合理性是更关键的这一点适用于所有算法问题。 1left 和 right 同方向移动 2定义条件即我们需要时刻检测的一件事情 3原理充分利用本题本身的特点以减少不必要的计算 4利用循环不变量保证代码边界正确 5不要记忆代码模板应该结合具体问题分析出什么时候滑动窗口最长什么时候滑动窗口最短 6掌握处理字符串的技巧。
3.3 计数问题
3.3.1 标准
写对计数问题的标准不重不漏。
3.3.2 总结
计数问题需要统一计数的标准。这一类问题需要仔细计算一些代码的细节如果想不明白可以在草稿纸上写出具体的例子帮助总结规律。
3.4 使用数据结构维护窗口性质
四、链表中的双指针问题
五、双指针相向交替移动的两个变量
5.1 定义
双指针是指通过两个变量交替相向移动完成任务的算法具体来说可以使用两个变量 i 和 j 初始的时候i 和 j 分别指向数组的第一个元素和最后一个元素然后指针 i 不断向右移动 指针 j 不断向左移动直到它们相遇。这样设计的算法少考虑了很多暴力解法需要考虑的情况如下图所示。
六、小结
不管是滑动窗口还是双指针问题其实都是在完成任务的过程中使用了一些变量帮助我们以线性时间复杂度完成题目交给的任务理解它们基于对问题本身的理解大家在做题的过程中需要体会这两种算法都是对暴力解法的优化。这一专题的内容并不难但是掌握好它们需要一定量的练习最好的办法也是看起来最笨的办法。我们给出一些学习过程中的建议 1画图分析 2通过具体的、恰当的例子归纳解题思路 3遇到问题的时候一定不能急躁在代码中打印出变量的值观察变量的值是不是按照我们设计的逻辑进行的这样的办法也是最有效的办法 4理解循环不变量并利用好循环不变量这个非常朴素的、在写对代码的过程中一定需要保证的性质
