- 博客(53)
- 收藏
- 关注
RSS订阅原创 二维数组中修改代价最小问题【转换题意+最短路径】(Dijkstra+01BFS)
题目规律：在二维数组上给定起始点和终止点，且二维数组中有一些限定走法的障碍，可以将障碍消除/修改，需要我们找到从起始点到终止点的最小的修改次数。考虑每个点都是一个节点，在任意位置都可以任意移动，但是不能走出边界，如果移动符合要求，则移动的代价为0，否则移动的代价为1。这样就可以把二维数组转换为一个包含mn个点的图，每个节点都和最多相邻的4个节点相连，边的权值要么为0，要么为1（符合移动要求）。在图G上运用任意的最短路算法，求解出从起始点到终止点的最短路。关于Dijkstra的朴素算法和小根堆优化可以.
2022-05-29 20:41:44
618
原创 巫师的总力量和【单调栈+前缀和的前缀和】
搞懂这个题需要先搞懂P1856子数组最小乘积的最大值，关于P1856和单调栈的知识可以见上一篇关于单调栈的文章寻找下一个最大/小问题【单调栈】此题目是leetcode294场周赛T4，题目在巫师的总力量和分析题目，相比于枚举区间，我们更倾向于枚举每一个数字，然后求以他为最小值的区间的总力量值。为了知道遍历到iii时左右端点的值，我们采用单调栈记录每一个点的左边第一个小于他的位置left[i]left[i]left[i]、右边第一个小于他的位置right[i]right[i]right[i]。那么需要计
2022-05-22 17:46:58
404
原创 第K小/大问题【二分法】
对于第K小、第K大的问题，通常使用的解法是优先队列，优先队列的求解方法可以查看我的文章：优先队列解决多个升序列表的第K小但是对于优先队列枚举会超时的情况，我们一般采用二分法来求解。我们考虑题目如果要求：求出数组/二维数组中的第k小的数/数对，我们可以考虑另一个相同的解法：对于数组/二维数组中的数/数组 x，他是第几小的数字？上面的描述可以看出是很明显的二分的问法，可以防止对数组的全部遍历，对于二分查找有疑惑的可以查看我的文章：二分法题解合集以及模板【第一部分】目录乘法表中第k小的数找出第k小的距离.
2022-05-18 15:26:41
881
原创 寻找下一个最大/小问题【单调栈】
单调栈实际上就是栈，只是运用了一些巧妙的逻辑使得每次新元素入栈之后，栈内的元素都保持有序状态单调栈一般用来解决寻找下一个最大/小问题(Next Greater Element)例如，给定一个数组[2,1,2,4,3]，需要返回的数组是[4,2,4,-1,-1]，即每一位的值是从这一位向后的最大的元素的值，如果不存在比当前元素大的值，返回-1我们可以想象是具有数字大小身高的人按照顺序排队，从前往后看，看到的第一个高个子的人，就是此位置的答案具体代码见模板：vector<int> ne.
2022-05-14 15:45:10
395
原创 状态dfs/bfs+剪枝优化
首先看状态dfs，题目是检查是否有合法括号字符串用c表示字符串的状态(平衡度)：遇到左括号就+1，遇到右括号就-1，那么合法的字符串即为任意时刻c≥0c≥0c≥0且最后c=0从左上角到右下角，往右走m-1次，往下走n-1次因此路径长度是固定的，为(m-1)+(n-1)+1=m+n-1；极限的情况下左半边全为左括号，右半边全为右括号，因此c的最大值为(m+n-1)/2当遍历到(x,y)结点时，后面还剩下(m-1-x)+(n–1-y)+1=m-x+n-y-1，如果此时c大于这个值，后面就算全为右括号
2022-05-09 21:29:36
439
原创 约瑟夫环经典问题【数学公式法】
约瑟夫经典问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。题目可见：找出游戏的胜利者首先考虑常规解法：队列模拟。用一个队列模拟环，报到M的数字移除队列，其余的数字添加到队列末尾，直到队列中的数字个数只有一个为止，时间复杂度是O(nm)，每m次离开一个，一共进行n次，空间复杂度是O(n)。代码如下：int findTheWinner(int n, int k) { k%=n; //取余 if(k==0) k=n;;
2022-05-04 10:40:41
2499
原创 结点序列的最大得分【三元组类问题】
题目是leetcode第76场双周赛T4结点序列的最大得分数据范围较大，暴力枚举dfs的话会超时，题目需要我们构造一个序列，由四个结点三条边组成，对于这种“三元组类”的问题，我们一般是选择枚举中间元素，在这个题中我们枚举三条边的中间那条边。假设序列为a-x-y-b(-表示为一条边)，我们枚举edges中的每条边作为序列的中间那条边，即x-y，需要注意的是由于不能出现重复的元素，因此与x相邻的点中，不能选择与y和b相同的点，因此我们保留分数最大的三个点，a必定在这三个点中，同理，保留y相邻的最大的三
2022-04-28 11:33:38
196
原创 验证有向图是否是二叉树
给定一个有向图，需要我们判断其是否是一颗二叉树，如下，题目在验证二叉树对于包含n个结点m条边无向图，如果他是一颗树，那么必须满足以下三个条件中的两个：m=n-1该无向图连通该无向图无环对于连通性的判断，我们可以采用广度优先搜索，从根结点出发，将遍历到的结点放入一个set中，当一次广度优先搜索结束之后，set中的元素应该是所有元素的个数，如果存在在遍历过程中，访问到了已经放进set中的元素，说明有环存在。因为二叉树的遍历中，每个元素只会遍历一次，因此遍历到他之后可以直接将其放进set中。同时
2022-04-27 15:01:31
1054
原创 判断二分图【bfs】
题目是判断二分图给定一个可能不是连通的无向图，我们需要判断此图是不是一个二分图。在一个连通的无向图内，判断二分图的方法为：初始化所有结点都未染色，染色数组color初始化全未0从任意一个结点开始，将其染为颜色1，并从该结点开始遍历整个图如果我们通过u结点和v结点之间的边遍历到了v结点有以下两种情况：如果v未被染色，那么我们将其染成于u不同的颜色，并从v继续往下遍历如果v被染色，v的颜色如果于u相同的话，则说明不是一个二分图，返回false当遍历结束的时候，返回true由于题目给
2022-04-26 10:42:46
798
原创 单源最短路径算法【朴素Dijkstra+小根堆优化】
给定结点K和一个有向图edges，我们需要求出K结点到所有结点的最短路径，采用Dijkstra算法，核心思想是贪心，其算法步骤主要为以下：将结点分为两类[未确定结点]以及[已确定结点]，需要从当前全部[未确定结点]中，找到距离K结点最短的点x通过点x更新其他所有点距离源点的最短距离，更新的含义是：用起点到某个点y的距离，和起点到x的最短距离加上x到y的距离，更新为两者中的最小值当全部其他点都遍历完成后，一次循环结束，将x标记为[已确定结点]，进入下一轮循环，直到所有点都被标记上。实现的一些细节如
2022-04-25 15:42:25
592
原创 花期内花的数目【离散化+前缀和+差分】
题目是290场周赛T4花期内花的数目一般讲出生、上下车这种一上一下的情况，很大可能是使用差分数组，关于差分数组的使用，建议去看以下链接：差分 --算法竞赛专题解析本题具体思路如下：离散化思想：对于花期在[start,end]的花朵，我们看成是将区间[start,end]上的每个时间点都增加一朵花。对于第i个人，我们只需要计算出在personi时间结点的花朵数量即可差分：构建差分数组map<int,int>m，对于每个区间[start,end]，我们想要将区间里面所有的值加1，因此修改
2022-04-25 11:25:01
386
原创 并查集简单模版
并查集基础知识：并(Union):代表合并查(Find):代表查找集(Set):代表这是一个以字典为基础的数据结构，基本功能是合并集合中的元素，查找集合中的元素并查集的应用是解决有关连通分量的问题实现如下：int parent[200] //放元素的数量void Init(int n){ //初始化函数 for(int i=0;i<n;i++){ parent[i]=i; //每个结点的父亲都是自己 }}int find(int x){ //查找结点x的根结点 if(
2022-04-23 15:12:18
1124
原创 归并排序【求逆序对】
给定一个数组，需要求出数组的逆序对的个数：归并排序包含以下三个步骤：**分解：**待排序的区间为[l,r]，令mid=(l+r)>>1；我们把[l,r]分解为[l,mid]和[mid+1,r]；**解决：**使用归并排序递归的排序两个子序列**合并：**把两个已经排好序的子序列合并起来而求逆序对和归并排序的关系就是[并]的过程，在合并的过程中，如果找到了左指针指示的数比右指针指示的数大的情况，那么就可以算出他对逆序对的贡献度。int ans=0;vector<int>
2022-04-20 10:48:21
515
原创 拓扑排序(判断是否是有向无环图DAG)【dfs+bfs】
拓扑排序原理：对有向无环图DAG的顶点进行排序，使得对于每一条有向边(u,v)，均有u(在排序记录中)比v先出现，亦可理解为对某点v而言，只有当v的所有源点均出现了v才能出现根据定义，可以得到以下两个结论：如果图G中存在环(即G不是有向无环图)，那么G不存在拓扑排序，反之如果G存在拓扑排序，则G中没有环如果G是有向无环图，那么他的拓扑排序可能不止一种我们用两种方法来求解拓扑排序：dfs和bfs方法一 ：深度优先搜索我们用一个栈来存储所有已经搜索完成的结点，对于某个结点，他在搜索过程..
2022-04-18 20:45:56
2404
原创 第n个丑数【动态规划、堆、二分】
题目是丑数丑数是能被2，3，5整除的数，我们可以从1开始构造丑数，某个数a是丑数，那么2a、3a、5a都是丑数方法一：使用堆实现：使用最小堆，初始堆为空，将最小的丑数1加入堆，每次取出堆中的最小的元素x，并将2x、3x、5x加入堆中。但是可能会出现重复的情况，因此我们多建立一个set集合来去重，只有在set中没有出现的元素才加入到堆中。代码如下：int nthUglyNumber(int n) { vector<int>f={2,3,5}; unordered_se
2022-04-18 11:42:34
737
原创 二叉搜索树的后序遍历【分治+递归】
给定一个序列，我们需要判断此序列是否为某个二叉搜索树的后序遍历序列，题目在二叉搜索树的后序遍历二叉搜索树的特点：中序遍历(左->根->右)是一个递增的序列，因此在后序遍历(左->右->根)，我们可以判断根的位置，并判断左是否全部小于根，右是否全部大于根，一直判断直到整个序列被遍历使用left和right指向需要判断的序列的左端点和右端点，根结点就是right指向的值bool isPost(vector<int>& postorder,int left,
2022-04-10 15:51:36
1543
原创 二叉树与二叉搜索树【回溯与递归】
本篇包含的题目有：平衡二叉树、二叉搜索树的第K大结点、二叉树中和为某一值的路径采用自底向顶的递归，类似于后序遍历，对于当前遍历到的结点，先递归的判断其左右子树是否是平衡的，再判断当前结点是否是平衡的，如果此结点是平衡的，返回其高度，否则返回-1，最后判断整个二叉树的所有结点的高度都要是正整数即可int height(TreeNode* root){ if(root==nullptr) return 0; int leftHeight=height(root->left); /
2022-04-08 11:09:07
179
原创 K次翻转后字符串中最大连续字符【滑动窗口】
给定一个字符串，有K次机会将某个字符变成另一个字符，我们需要找到通过K次转换后，此字符串中最长的连续子字符串，将其分为两种类型只有特定字符的字符串没有规律字符的字符串类型一：有特定字符的字符串例如题目考试最大困扰度，给定字符串中只包含特定的字母T和F，给定改变的次数K，我们需要找到经过K次改变字符后最长的子字符串，可以知道，最长的相等子字符串一定是全由T组成的或全由F组成的，因此我们自定义函数，功能是找到由字符X组成的，经过K次改变字符的，最长相等子字符串，我们采用滑动窗口的思想去解决问题从
2022-04-01 14:52:23
728
原创 对称二叉树&&二叉树镜像&&树的子结构【递归】
三个题的题目分别见对称二叉树和二叉树的镜像以及树的子结构对称二叉树：做递归思考三步：1.递归函数要做什么？函数的作用是判断两个数是否镜像输入的是TreeNode left和TreeNode right输出的是true或者false2.递归的停止条件是什么？左右结点都为空 -> 到底了长的都一样 -> true一个结点为空的时候另一个结点不为空 -> false左右结点的值不相等 -> false3.从某层到下一层的关系是什么？左节点的左子树要和右节
2022-03-28 10:35:20
552
原创 二叉树的最近公共祖先
假设我们需要找到结点p，q的最近公共祖先，我们可以发现二叉树的最近公共祖先满足：此结点的左结点和右节点分别存在p，q或者此节点恰好是p，q之一并且他的左右结点之一恰好是另一结点。我们假设fleft==true表示左节点或左节点的子节点中存在其中一个元素，fleft == false则表示左节点或左节点的子节点中不存在元素，fright同理，则判断一个结点是否最近公共祖先结点的判断条件是：(fleft(fleft(fleft&&fright)∣∣((x=p)∣∣(x=q)frigh..
2022-03-26 16:24:58
2601
原创 【字节跳动面试】考频top10题目【普通难度】（1）
文章目录TOP1 无重复字符的最长子串top2 LRU 缓存TOP1 无重复字符的最长子串题目在P3无重复字符的最长子串对于字符串abcbcbb而言，我们从头遍历，查找以遍历处开始往后的最长不重复子串，如下：以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；以a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；以ab( c )abcbb 开始的最长字符串为 ab(cab)cbb；以abc(a)bcbb 开始的最长字符串为 abc(abc)bb；以abca(
2022-03-25 21:17:57
859
原创 价格范围内最高排名的 K 样物品【经典BFS】
题目是价格范围内最高排名的 K 样物品解题思路：从start坐标开始遍历整张图，遍历时将当前坐标价值在合法区间的值保存下来，需要记录横、纵坐标，价格和距离四个维度因素，我们可以用一个结构体来保存遍历完后自定义优先级排序，排序优先级分别为：距离、价格、横坐标、纵坐标，从小到大排序如果结果数组长度小于k则全部输出，否则输出前k个代码如下：typedef struct node{ //自定义结构体，记录位置x，y和价格pricing和距离dist int x; int y;
2022-01-24 13:17:51
515
原创 统计元音字母序列的数目【经典动态规划】
题目是P1220统计元音字母序列的数目通过分析我们可以得知：a前面只能接e、i、ue前面只能接a或ii前面只能接e、oo前面只能接iu前面只能接o、i我们用dp[i]表示长度为i的字符串的个数，其中dp[i][j]表示dp[i]的5种状态，0≤j≤4。分别是以5个元音字母结尾的字符串。因此最终答案就是dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]+dp[n][4]dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]+dp[n][4]dp[n][0
2022-01-17 12:51:18
519
原创 实现Trie【前缀树(字典树)】
Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：指向子节点的指针数组children。对于小写字母而言，数组长度为26，即小写英文字母的数量。此时children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，[25]children[25] 对应小写字母 z。布尔字段isEnd，表示该节点是否为字符串的结尾。插入字符串我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：子节点存在。沿着指针移动到子节点，继续处理下一个字符。子
2021-12-28 14:13:56
180
原创 买卖股票的时期含冷冻期【动态规划】
题目是P309最佳买卖股票时机含冷冻期对于股票类的题目，我们常用方法是将“买入”和“卖出”分开进行考虑，买入时为负收益，而卖出时为正收益，在买入之后才有卖出的权力。我们用dp[i]表示第i天结束之后的累计最大收益，根据题目的描述，由于我们最多只能同时买入一支股票，且卖出之后有冷冻期的限制，因此对于每一天，有以下三种状态：dp[i][0]：今天结束后持有一支股票dp[i][1]：今天结束后不持有任何股票且处于冷冻期中，即刚卖出股票dp[i][2]：今天结束后不持有任何股票且不处于冷冻期内对于d
2021-12-25 20:23:50
419
原创 吃苹果的最大数目【优先队列+贪心】
题目是P1705吃苹果的最大数目分析，对于每个已经收获的苹果，我们的决策总是先吃腐烂时间早的，因此我们用优先队列存储二元组[苹果数量，腐烂时间]，同时每次吃的时候我们考虑优先队列的头部，如果头部的苹果不满足要求，我们就直接丢掉，继续查看头部，直到满足要求的苹果出现或者队列为空，代码如下：struct cmp{ bool operator()(const pair<int,int>&a,const pair<int,int>&b){ re
2021-12-24 09:30:23
576
原创 贪心+二分查找求解LIS问题
求解最长上升子序列通常做法都是直接dp，很容易得到dp状态转移方程：dp[i]=max(dp[j])+1dp[i]=max(dp[j])+1dp[i]=max(dp[j])+1，其中0≤j<i且num[j]<num[i]0≤j<i且num[j]<num[i]0≤j<i且num[j]<num[i]用两个循环遍历原数组，维护dp数组，遍历结束之后找到dp数组中的最大值就是最长上升子序列。代码如下：int lengthOfLIS(vector<int>&a
2021-12-19 15:05:36
350
原创 多源广度优先搜索
我们知道用队列实现广度优先搜索有三个步骤：初始化队列将起始点入队列循环：当队列不为空时，先弹出首个元素，然后将这个元素能够处理的其他点全部入队列而多源广度优先搜索就是起始点入队列时，我们让多个点进入队列。重点在于：如何记录广度优先搜索的最短时间，如下题：P994腐烂的橘子初始我们将腐烂的橘子都入队列，并记录新鲜的橘子的个数，如果最后还剩余新鲜的橘子我们就返回-1。如何处理这一时刻遍历的腐烂的橘子的最小时间呢，因为我们是让所有最初腐烂的橘子同一时刻开始传递腐烂，因此我们可以借助动态规划的思想
2021-12-17 09:59:11
604
原创 无重复字符的最长子串【滑动窗口】
题目是P3无重复字符的最长子串对于字符串abcbcbb而言，我们从头遍历，查找以遍历处开始往后的最长不重复子串，如下：以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；以a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；以ab( c )abcbb 开始的最长字符串为 ab(cab)cbb；以abc(a)bcbb 开始的最长字符串为 abc(abc)bb；以abca(b)cbb 开始的最长字符串为 abca(bc)bb；以abcab( c )bb 开始的最长字
2021-12-14 11:09:40
679
原创 优先队列解决贪心问题
题目是P630课程表 III由于我们不能同时选择两门课程，因此选课需要步步是最优解，我们考虑两个课程[t1t_1t1，d1d_1d1]和[t2t_2t2，d2d_2d2]。不妨令d1d_1d1≤d2d_2d2，我们可以得到结论：先学习结束时间小的(d1d_1d1)，总是最优的。可以证明如下：假设当前时刻为x，则若先选择一号课程，再选择二号课程，有：t1t_1t1+xxx≤d1d_1d1t2t_2t2+t1t_1t1+xxx≤d2d_2d2若先选择二号课程，再选择一号课程
2021-12-14 09:46:57
1323
原创 无重叠子数组的最大和【滑动窗口】
题目是力扣P689三个无重叠子数组的最大和首先我们考虑解决长度为k的单个子数组的最大和问题：假设sum1sum_1sum1是大小为k的窗口的元素和，当窗口从[i-k+1，i]向右滑动一个元素后，sum1sum_1sum1增加了nums[i+1]，减少了nums[i-k+1]。我们从0开始，增大窗口直至窗口大小为k，然后不断向右滑动窗口，直到窗口的右端点到达数组末尾时结束，统计这以过程中的sum1sum_1sum1最大值(记作maxsum1)及其位置就行。vector<int> ma
2021-12-08 15:20:33
470
原创 边框着色&&岛屿数量【经典搜索问题】
首先看P1034边界着色问题。题目意思就是说给定一个位置，要求把这个位置和这个位置属于同一连通分量的网格块染成给定的颜色(color)，是一道很经典的搜索问题，我们从给定位置出发开始搜索，可以用dfs以及bfs，本文都采用的是dfs方式。搜索的方向我们用一个4×2的二维数组来决定，4个方向，每个方向代表x轴和y轴的变化量。是否搜索过我们用visit二维数组来记录，起始值除了起始点都是false，搜索的过程中每搜索一个点就将此点置为true意为已经搜索过了。在搜索过程中我们定义变量isBorder，
2021-12-07 15:45:33
238
原创 二叉树路径问题【寻找最近公共祖先(lca)】
题目见力扣270场周赛第三题从二叉树一个节点到另一个节点每一步的方向很明显这个题需要我们求解两个节点的最近公共祖先，这样才是最短路径，在求得他们的最近公共祖先后，从这个结点T到出发结点startValue的路径记录在ans1中，从T到目的结点destValue的路径记录在ans2中，我们可以很明显的发现最后的答案就是将ans1中的‘L’和‘R’全部转换成‘U’，然后拼接在ans2之前，就是整个的最短路径。在求解最近公共祖先时，我们可以采用以下方法：从头节点出发，到起始结点s的路径记录在ans1中，从头
2021-12-05 15:26:01
707
2
原创 快速幂求模
我们需要求ab模上一个数的值，例如P372超级次方我们首先直到模运算的的乘法律(a * b) % p = (a % p * b % p) % p，因此只要每一步乘法运算都取模运算，最后的结果也是取模的结果。我们考虑ab，当b是奇数时，可以分解为a * a(b-1)，而(b-1)是偶数，我们可以直接带到b是偶数的情形，当b是偶数时，ab=（a*a）b/2，这样我们就可以继续分解，记录结果，并在每一步乘法中对p取模，从而达到计算ab对p取模的结果。递归解法：int fastpawer(int a,int
2021-12-05 10:19:19
452
原创 二分法题解合集以及模板【第一部分】
自己平时写二分全靠运气，运气好的时候就能水过二分，究其原因还是自己对二分的过程不了解清楚，因此专门写一个BLOG来记录刷爆二分的过程。首先贴一个究极好用模板：https://www.pianshen.com/article/90471307044/用二分法求解寻找有序序列中“第一个”满足某条件的元素的位置的模板：//二分区间为左闭右闭的[left,right]//解决“寻找有序序列第一个满足某条件A的元素的位置”int solve(int left,int right){ int mid; w
2021-12-03 22:09:42
1635
原创 分治解至少有K个重复字符的最长子串
题目是力扣P395至少有K个重复字符的最长子串类似于这样字符串求特定规则下的子串的长度的题目一般都可以用滑动窗口解决，但是这个题我没想到怎么滑，换一种思路，对于一段字符串[left,right]，我们要判断他是否满足条件，就是判断这一段字符串内的每一个字符，出现的次数是否都大于等于K即可，因此可以想到用map存储每个字符出现的次数，当再一次遍历的时候，发现此时遍历的字符出现的次数比K小，那么我们记录此时的位置，举个例子，我们先记录left-1，当出现某个字符不满足条件的时候，记录此时的位置j，假设只有一
2021-12-03 15:43:08
892
原创 优先队列解决多个升序列表的第K小
题目是力扣P786.第K个最小的素数分数第一眼看数据范围只有103，直接想暴力搜索排序，每一对数据可以用到pair，用vector储存每一对pair，自定义函数cmp重载<符，比较两个分数大小的时候直接比较a的分子乘b的分母和b的分子乘a的分母的大小即可。class Solution {public:static bool cmp(const pair<int,int>&a,const pair<int,int>&b){ return (a.f
2021-11-29 15:40:07
449
原创 并查集模板
力扣269周赛的最后一题：题目描述关于0到n-1，连通性的关键字的问题，很大可能是并查集模板。定义全局变量：vector<int> parent; //储存结点的祖先vector<int> size; //储存以x为祖先的团体的大小union_set(int n){ //初始化 parent.resize(n); ranker.resize(n); for(int i = 0; i < n;++i){ parent[i] =
2021-11-28 15:17:57
573
原创 位运算异或查找单一元素
我们需要在线性的时间复杂度和不使用额外的空间的条件下实现。题目需要求解两两数字相同出现的数组中有一个数字是单独出现，因此我们考虑异或运算，异或运算具有以下性质：交换律，a ^ b = b ^ a；结合律，a ^ b ^ c = a ^ (b ^ c)；任何数和0做异或，结果为本身，即a ^ 0 = a；任何数异或本身，结果为0，即a ^ a =0；由以上可知，我们只需要异或数组中的所有数，用交换律和结合律把相同的数异或，结果为0，最后异或唯一出现的数，得到的结果就是唯一只出现一次的数。c.
2021-11-26 09:51:25
342
原创 压状、前缀和与子字符串
题目P1542找出最长的超赞子字符串首先分析题目，我们需要找到他的子字符串，且能通过任意次数的交换变成一个回文字符串。不考虑顺序仅仅考虑回文字符串的性质：任意一个回文字符串最多有一个数字出现的次数为奇数，其余数字出现的次数必定为偶数。因此我们在判断一个子字符串是否是超赞字符串，仅仅只需要指导各个数字出现的次数的奇偶性就可以，因此我们考虑用到状态压缩，我们用0-1表示数字出现的奇偶，0表示出现奇数次，1表示出现的偶数次。用不大于1024的10位二进制数来表示0-9这10个数字。例如：举个例子，对于子
2021-11-24 18:25:24
292
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人