简介滑动窗口算法本质上还是基于左右指针的算法，就是用左右指针规定窗口范围，减少一些不必要的比较，提升算法的时间复杂度。该算法通常用于解决一些子串问题。 注： 子串与子序列不同，子串是要求连续的，子序列不要求连续。子串 == 子数组 框架123456789101112131415161718192021222324252627282930//滑动窗口算法框架void slidingWindow(string s, string t){ //window表示窗口里的元素当前的个数，通常我们只记录有意义的信息 //need表示不同元素所需要的个数，需要满足要求 unordered_map<char, int> need, window; //将子串所需要的，用need来表示 for(char c : t) need[c]++; //这里采用的是左闭右开的区间表示方式，目前没有任何元素 int left = 0,right = 0; int valid = 0; while(right < s.size())& ...

二分搜索套路框架二分查找是在一个有序数组中找到目标元素的一种查找方法，它的大致思想是：将区间分为两半，对比目标元素是在左半边还是右半边，然后递归地在左（右）半边区间进行查找。 二分搜索分为三类： 寻找某个数 寻找某个数的左边界 寻找某个数的右边界 虽然这三类看似差不多，主要框架也差不多，但是在细节上是有所区别的，所以本节内容是主要讲解细节上面的差异，搞懂这些细节上的差异，是我们这一节的目的。既然只有细节上有差距，那么先来看一下总的框架： 12345678910111213141516171819202122int binarySearch(int[] nums, int target){ //细节1 区间的表示形式 int left = 0; int right = nums.length - 1; //细节2 while()里是 < 还是 <= while(left <= right){ int mid = left + (right - left) / 2; //细节3 “...”中我们 ...

双指针技巧套路框架双指针技巧分为两类，一类是“快、慢指针”，一类是“左、右指针”。前者主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分搜索。 快、慢指针的常用算法1.判定链表中是否有环？设置快、慢指针解决。solution： 1234567891011boolean hasCycle(ListNode head){ ListNode fast, slow; //初始化快慢指针只像头节点 fast = slow = head; while(fast != null && fast.next != null){ fast = fsat.next.next; slow = slow.next; if(fast == slow) return true; } return false;} 2.已知链表中含有环，返回这个环的起始位置 solution： 123456789101112131415ListNo ...

BFS 问题的本质通常是让你在一副“图”中找到从起点 start 到终点 target 的最短距离。BFS的思想不多说，直接上模板。 123456789101112131415161718192021222324252627282930313233int BFS(Node start, Node target){ //初始化队列 Queue<Node> q; //集合用于去重 Set<Node> visited; //将起点加入队列 q.offer(start); //记录访问节点 visited.add(start); //记录扩散的步数 int step = 0; while(q not empty){ //当前层次的队列长度 int sz = q.size(); //遍历该层 for(int i = 0;i< sz;i++>){ Node cur = q.poll(); ...

动态规划是能够通过子问题的求解推出总问题的答案。而回溯算法的解题思路比较简单，就是不断地做选择，当走不通的时候，就回溯到上一个节点，走别的路。解决一个回溯问题，实际上就是一个多叉树的遍历问题。 基本概念1.路径：也就是已经做出的选择（已经走过的节点）。2.选择列表：也就是你当前可以做的选择（当前节点面临的多个分支）。3.结束条件：也就是到达决策树底层（叶子节点），无法再做选择的条件。 回溯算法的框架123456789101112131415result = []def backtrack(路径, 选择列表): # 出口 if 满足结束条件: result.add(路径) return for 选择 in 选择列表: # 做选择 # 将该选择从选择列表中移除 路径.add(选择) backtrack(路径,选择列表) # 撤销选择 # 将该选择恢复到选择列表 路径.remove(选择) 注： 做选择的就是将选择列表中的选择放入路径 ...

基本概念首先来介绍一下动态规划问题的基本概念。1.base case 是表示该问题最简单的形式是什么样的。 2.dp数组(函数) 中的相应变量的值（应变量的的返回值）用来表示该问题的子问题的答案。其中的变量代表着该变量所对应的子问题。 3.状态转移 是指从一个状态到另一个状态转换的方式。不同变量所对应不同的状态，它们的转换方式用状态转移方程来表示。 4.状态选择 对应状态转移中“从哪个状态转移”的问题。通常来讲，动态规划基本上是求最优值问题。所以状态选择，通常都是“从不同状态的状态转移”中选择最优值来作为选择的结果。 5.状态压缩 是指对dp数组（函数）中不同变量的数目进行压缩，以此减少状态的数量，优化算法。 动态规划的必备条件：1.重叠子问题 是指重复计算的相同状态（拥有相同变量的dp数组中的值或者dp函数所对应的返回值）的子问题。2.最优子结构 是指能够通过子问题的最优解求出整个问题的最优解。要符合“最优子结构”，子问题间必须互相独立（不同子问题之间不能有制约关系）。 自顶向下解法（递归求解）自顶向下的解法是指画出递归树的顺序，即从顶点依次画出整个递归树。求解的总问题依赖于 ...

来自深夜的叙述与思考深夜看到一些程序员学习路线指导的视频，不经感慨万分，感受到了自己肩膀上的压力，不经陷入对人生的大思考。 先来讲讲我的大学经历吧。高中不怎么努力，到了一个二本大学，大学前我还以为自己不管怎么样总归还是会上一个大学。结果来到了一个嘉兴学院，不是说学校太差，只是当时除了清北复交，其他学校一概不知，只能说自己眼界太小吧。 后来来到学校，我认为不管怎样都不能荒废学习，顺带一提，我的专业是测控技术与仪器，说来可笑，我当时选专业的时候也是这样一无所知，只是百度查了一下，工科，我应该会比较适合吧，就选了。其实专业是一个很杂的专业，可以说是电气类专业里最杂的。杂当然有杂的好处，什么都知道一点，但是什么都不精。大一虽然不能说发奋学习吧，但大一我的成绩还是班级的第二名，也只能说是不落下学习。其实现在想想我，其实还是缺少一个努力的方向，专业出来要做什么也不知道。只知道不能落下学习。为了充实自己，我加入了一个校级组织。因为班助说这个组织挺好的，挺有爱的，就没多想，反正就当作锻炼锻炼自己堪忧的情商。不过说实话，大一的时候虽然还是挺忙碌的（因为组织），就以这个理由没有参加任何竞赛，也没有加入实验 ...

PAT_刷题心得本博客记录一些关于我刷pat题目出现的一些心得(或错误)。 PAT_A1046(错误是段错误) 下面是代码： 123456789101112131415161718192021222324252627282930313233343536373839#include<cstdio>#include<iostream>using namespace std;int d[100005];int ans[2][100005];//应改为：int ans[100005][2]int sum(int a,int b,int t) { int sum = 0; while (a % (t + 1) != b) { sum += d[a]; a = a % t + 1; } return sum;}int main() { int t, r; int p1, p2; scanf("%d", &t); for (int i = 1;i <= t; i++) { sc ...