wyf 的个人博客

切割问题 一、问题特点 这类问题通常会给出一个数组（或字符串），要求列举出所有满足特定条件的划分。其特点如下： 通常不允许改变原集合中元素的相对顺序 所求答案通常是若干组满足特定条件的划分 划分中的所有元素必须在原集合中连续取值 二、相关例题 （一）分割回文串 131.分割回文串（LeetCode） 题目要求： 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串 。返回 s 所有可能的分割方案。 回文串是正着读和反着读都一样的字符串。 示例： 输入：s = “aab” 输出：[[“a”,“a”,“b”],[“aa”,“b”]] 提示： 1 <= s.length <= 16 s 仅由小写英文字母组成 解题思路： 切割问题同样是回溯算法的典型应用，其解题思路和组合问题大致相同，同样需要用for循环加递归的方法遍历搜索树查找满足条件的解，又因为切割问题中不允许重复取值，所以仍需要startIndex标明切割的起始位置。和组合问题不同的是，切割问题每次添加到路径中的往往不是单个元素s[i]，而是从[startIndex,...

全排列问题 一、问题特点 给出一个数组，返回所有可能的全排列。其中“全排列”的定义如下： 将n个元素按照一定的顺序排列起来，所有的排列情况的集合叫全排列 全排列问题的整体思路和其他回溯问题相仿，但去重操作和其他问题有所不同，这是由其自身性质决定的： 排列问题中每一条路径都必须遍历原集合中所有的元素（终止条件恒为 path.size() == nums.size() ） 排列问题中每一种状态中元素的排列顺序必须各不相同 任何一条路径都不能重复遍历同一个元素 二、遍历方法 因为不能使用startIndex修剪搜索空间，每层遍历都要从nums[0]遍历到nums[nums.size()-1]。 路径中的状态不需要记录到结果数组中，终止条件恒为 path.size() ==...

一、算法思想 在链表中寻找某一元素大多需要通过它的相邻元素才能找到该元素的地址。当我们对该元素进行删除、排序等操作时需要改变这个元素及其相邻元素的指针，但由于程序只能逐条执行，某些间接节点的地址在更改的过程中有丢失的风险，需要另设一个乃至多个指针保存这些将会丢失的地址，以免出现更改一个节点以后找不到下一节点的情况。 二、算法特性 1.适用条件 数据结构为链表 对链表中的某一元素进行删除，移位操作 2.时空复杂度 时间复杂度： O(n) 空间复杂度： O(1) 三、算法实例 206.反转链表 题目要求： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例2： 输入：head = [1,2] 输出：[2,1] 解题思路：...

一、用途 在数组中查找某一特定值的函数并获取其下标。 二、限制条件 1.有序数组 所查找的数组中的所有元素必须按照从小到大或从大到小的顺序排列。 如果所查找的数组不是有序数组，也可使用sort()库函数将其转化为升序排列的有序数组后再进行查找。其中sort()函数位于C++的algorithm库中，其具体用法如下： 123456789101112#include <iostream>#include <vector> #include <algorithm>using namespace std; vector<int> arr = {1, 3, 5, 6, 9, 12};// 默认为升序排序sort(arr, arr + n); // 降序排列sort(arr, arr + n, greater<int>()); ...

一、题目特征 给定一个整数数组 nums 和一个整数目标值 target，需要在该数组中找出并返回满足全部条件且不重复的N元组（或下标）。特别地，对于N的不同取值，N元组需要满足的附加条件也不完全相同。 二、思路 1.滑动窗口 对于要求返回N元组的题，设置四个指针使用for循环暴力求解的时间复杂度为 O(nn)O(n^n)O(nn)。由于题目不要求返回下标，因此我们可以使用sort()库函数将数组修改为有序数组，再结合滑动窗口法可以将右侧两个指针的遍历操作的时间复杂度由 O(n2)O(n^2)O(n2) 降低到 O(n)O(n)O(n)，获得更快的效率。 2.去重操作 由于原数组中可能存在具有相同值的元素，这类题还需要考虑如何实现去重操作，保证结果中的数组互不相同。由于比较并删除相同数组比较困难，最好的办法是在遍历的过程中跳过具有相同值的元素，此处注意对于for循环的变量跳过的条件一定是本次的操作数与上一次的相同(nums[i] = nums[i-1])而不是和下一次进行比较然后跳过本轮遍历。因为for循环变量的取值范围：上轮操作 > 本轮操作 >...

树状数组 拜读了大佬的讲解博文（树状数组(详细分析+应用)，看不懂打死我!），写一篇Python版的笔记巩固消化，附带蓝桥杯历年真题作为例题演示 一、作用 用于快速读取列表中 某个区间内所有元素的和 实现单点修改，区间查询 若以差分数组作为a[]则可实现 区间修改，单点查询 操作，是一个常用技巧 二、时间复杂度 传统方式 访问某个元素：O(1)O(1)O(1) 获得某区间元素和：O(n)O(n)O(n) 树状数组 访问某个元素：O(logn)O(logn)O(logn) 获得某区间元素和：O(logn)O(logn)O(logn) 三、规则 通过创建一个列表t，记录以二进制划分的区间内元素的和，其中lowbit(x)的位数决定本节点所处的层数，t[x]保存了以x为根的子树中叶节点的值（即区间的元素和） 通过观察， a数组具有以下性质： 下标索引从1开始（切记！！！） 长度为n t数组具有以下性质： t[x]t[x]t[x] 节点覆盖的长度是 lowbit(x)lowbit(x)lowbit(x) t[x]t[x]t[x] 的父节点是...

BFS BFS算法主要有洪水填充（flood fill）和最短路径两个应用。 一、洪水填充算法（Flood Fill） 例题 1：岛屿个数（第14届省赛真题） 题目描述： 小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。 在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),...,(xk−1,yk−1)，其中(x(i+1)%k,y(i+1)%k)是由(xi,yi)(x_0, y_0),(x_1, y_1), . . . ,(x_{k−1}, y_{k−1})，其中(x_{(i+1)\%k} , y_{(i+1)\%k}) 是由 (x_i , y_i)(x0​,y0​),(x1​,y1​),...,(xk−1​,yk−1​)，其中(x(i+1)%k​,y(i+1)%k​)是由(xi​,yi​) 通过上/下/左/右移动一次得来的...

全排列 全排列主要结合DFS求出一个数组中所有数字的排列结果，这个结果往往需要从小到大排列。 此外，全排列还经常要求出某一个排列的前一个排列或后一个排列，此时需要用到 pre_permutation() 和 next_permutation() 算法模板 123456789101112131415161718192021222324252627282930def next_permutation(nums): n = len(nums) # traversal the list from its end # if find the first pair of numbers that is not inverse,begin to change its positon for i in range(n-2,-1,-1): if nums[i] < nums[i+1]: # begin to find the first number that are bigger than it for...

前缀和 & 差分 前缀和与差分是常用的区间优化方式，其中前缀和数组可以将区间查询的时间复杂度降为常数，而差分数组则可以将区间修改的时间复杂度降为常数。 一、前缀和 前缀和知识点简单易理解，但出题难度较大，需要根据题意挖掘出潜在的前缀和关系，建立辅助数组求解问题。 （1）一维前缀和 定义： 对数组 x0,x1,x2,...,xnx_0,x_1,x_2,...,x_nx0​,x1​,x2​,...,xn​，对其进行区间查询的时间复杂度是 O(n)O(n)O(n) 为了提高区间查询的效率，可以引入前缀和数组 y0,y1,...yny_0,y_1,...y_ny0​,y1​,...yn​，前缀和数组有以下定义： y0=x0y1=x0+x1y2=x0+x1+x2...y_0 = x_0\\ y_1 = x_0 + x_1\\ y_2 = x_0 + x_1 + x_2...y0​=x0​y1​=x0​+x1​y2​=x0​+x1​+x2​... 创建方式： 由定义可知，前缀和数组有递推生成公式：yi=yi−1+xi(i>0)y_i = y_{i-1} +...

滑动窗口（尺取法） 算法含义： 在解决关于区间特性的题目时保存搜索区间左右端点，然后根据实际要求不断更新左右端点位置的算法 时间复杂度： O(n)O(n)O(n) 空间复杂度： O(1)O(1)O(1) 在历年真题中，滑动窗口主要有求追偿不重复子串和模拟优先队列求区间最值两个作用 一、求最长不重复字串 不重复子串：字符串的字串中不包含重复字符的字串 123456789101112131415161718from collections import defaultdicts = input()n = len(s)# 建立一个字典存储各个元素在窗口中出现的次数d = defaultdict(int)ans = 0# 确定窗口左端left = 0for right in range(n): # 如果发现窗口中已经有s[right]，将left右移直到窗口中不存在s[right] while d[s[right]] > 0: # 更新字典 d[s[left]] -= 1 left += 1 ans =...