- 博客(68)
- 收藏
- 关注
RSS订阅原创 704.二分查找
根据题意class Solution { public int search(int[] nums, int target) { if(target<nums[0]||target>nums[nums.length-1])return-1; int n=nums.length; int left=0,right=n-1; while(left<=right) { int mid
2021-09-08 22:03:52
79
原创 Codeforces 1490.C. Sum of Cubes
我们可以直接把1到10000之间的3次方都打表，然后遍历1到10000#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int maxn = 15e4 + 10;using na
2021-05-31 23:17:06
109
原创 Codeforces 1527.A. And Then There Were K
这道题的意思是找到比n小的最大k#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int maxn = 1e5 + 10;using namespace std;typedef
2021-05-30 14:49:09
207
原创 Codeforces 1521.A. Nastia and Nearly Good Numbers
好数我们可以直接使用A*B，次好数我们可以用A，然后输出它们的和就可以了#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int maxn = 2e5 + 10;using na
2021-05-30 13:36:33
99
原创 Codeforces.1526.B. I Hate 1111
这道题中，1111 及以上的是可以被11或111整除 的因此，我们可以使用11尝试整除x，如果不行，那么就让x减去111,10次以内可以得出结果#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>
2021-05-29 10:30:26
223
原创 Codeforces.1526.A. Mean Inequality
如果把整个数组分成左右两个子数组，左数组的最大值小于右数组的最小值，交替输出，那么答案可以成立#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int maxn = 2e5 + 1
2021-05-29 10:10:35
104
原创 Codeforces.1430.C. Numbers on Whiteboard
根据题意，只需要取最大的两个数字，使他们相加减半，就可以得到答案如果n=2，那么答案是2如果n大于等于2，那么答案也是2，不过答案的格式不等于n=2的情况由此写出以下代码：#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#in
2021-05-28 19:52:10
59
原创 Codeforces.1506.B. Partial Replacement
题目的意思是让我们去找在K范围内的能够变成X的*数量我们可以用两个指针标记头和尾的位置，然后对其用贪心算法进行求解#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int max
2021-05-28 11:17:15
93
原创 Codeforces1509.B. TMT Document
根据题意，对于每个数组中的M，如果它左侧的T大于等于且右侧的T大于等于，并且，T的数量应该是M数量的两倍#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int maxn = 2e
2021-05-27 23:54:21
69
原创 Codeforces 1506.D.Epic Transformation
这道题的思路是找到数组中出现次数最多的数字，然后比较它和数组的大小，如果出现的次数达到了数组大小的1/2，那么就输出2*大小-1；否则输出n%2#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>
2021-05-27 23:00:30
105
原创 Codeforces 1428.B. Belted Rooms
有两种情况：第一种，可以完成一个大回旋，即全为逆时针或顺时针第二种，中间夹杂着反向的传送带，这种情况下，如果这个房间连接着任何一个双向传送带，那么这个传送带也可以完成退房#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#incl
2021-05-27 17:05:28
116
原创 Codeforces 1428.C. ABBB
从题目的描述中可以看出这道题可以用栈来解答如果是A，就压入栈；如果是B，在满足消除的情况下把前面的弹出，不满足就压入。因此，最终结果一定为BAAAAA……或AAAAAAA……使用上面的这种维护手段可以得到答案#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#includ
2021-05-27 16:20:07
255
原创 Codeforces 1525.B. Permutation Sort
简单分析一下，如果是完全逆序，需要三次；如果头段或尾端符合，那么需要一次，完全有序，则需要0次。#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<map>const int maxn = 3e5 +
2021-05-26 22:35:41
90
原创 Codeforces 1529.B. Sifid and Strange Subsequences
因为题目要求任意两个数相减的绝对值不小于最大值，根据数学分析，如果所有数字都为正，那么不能满足要求，所以，答案的初值赋予数组中非正整数的个数，如果多出的那个正数满足题意，那么答案加1#include<iostream>#include<cmath>#include<cstring>#include<cmath>#include<algorithm>#include<stack>#include<queue>#
2021-05-25 21:53:06
128
原创 474. 一和零
https://leetcode-cn.com/problems/ones-and-zeroes/本题中的字符串可以看作是一个物品，每个物品只能拿取一次，所以这道题可以用01背包做出来，只不过需要二维的背包来存储dp数组那么按照dp五步来1.dp[i] /[j]表示，最多有i个0和j个1的strs的最大子集的大小为dp[i] /[j]2.确定递推公式dp[i] /[j]可以由前一个strs的前一个字符串推导出来，strs的字符串里有num1个1，num个0，因此，dp可以是dp[i - num0]
2021-05-20 22:07:34
61
原创 416. 分割等和子集
https://leetcode-cn.com/problems/partition-equal-subset-sum/这道题要我们判断这个数组能否分割为2个子集，使得两个子集的元素和相等因此，只要找到元素和为总和的一半的子集，就找到了两个子集因为元素和我们只能用一次，所以在这道题中我们需要使用01背包的思想我们可以确定的条件：1.背包的大小为所有元素之和的一半2.背包需要放入的商品的价值为元素的数值，重量也是3.背包正好装满的时候，说明找到了总和为元素之和一半的子集4.背包中每一个元素不可
2021-05-18 15:41:20
39
原创 1049. 最后一块石头的重量 II
https://leetcode-cn.com/problems/last-stone-weight-ii/其实这道题的意思就是把数组分成尽量相等的两份，然后输出剩下的值我们可以直接根据动归五步来做1.确定dp数组及其下标的含义dp[j]表示，容量为j的背包最大可以容纳价值为dp[j]的物品2.确定递推公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])3.dp数组的初始化根据题目中的意思，把数组大小规定为20000左右就可以了，初值按0来赋
2021-05-18 15:40:34
49
原创 96. 不同的二叉搜索树
https://leetcode-cn.com/problems/unique-binary-search-trees/如果n=1，那么一共有1棵搜索树如果n=2，那么一共有2棵搜索树如果n=3，那么一共有5棵搜索树如果n=4，那么一共有14棵搜索树我们大致推出，n每增加一，答案都需要再原来的基础上增加如果以双层循环作为标准，那么我们大致可以推出状态转移方程为dp[i] += dp[j - 1] * dp[i - j]我们可以判断推理的顺序是从1到n，循环两层class Solution {
2021-05-12 22:14:18
59
原创 343. 整数拆分
https://leetcode-cn.com/problems/integer-break/从2开始，拆分的数字从两个增加，所以，我们采用动态规划对该问题进行求解class Solution {public: int integerBreak(int n) { vector<int>dp(n+1); dp[2]=1; for(int i=3;i<=n;i++) { for(int j=1
2021-05-12 13:54:31
43
原创 63. 不同路径 II
https://leetcode-cn.com/problems/unique-paths-ii/利用动态规划，从1开始存储每个节点的道路数状态转移方程是dp[i][j]=do[i][j-1]+dp[i-1][j]但是，题目中有一个重要的点，障碍物该怎么跨越假设路径只要一条，那么障碍物后面的都是不可以到达的，我们标记为0class Solution {public: int uniquePathsWithObstacles(vector<vector<int>>&
2021-05-11 21:04:42
32
原创 746. 使用最小花费爬楼梯
https://leetcode-cn.com/problems/min-cost-climbing-stairs/这是一道动态规划的题目既然是动态规划，那么就应该写出状态转移方程根据题目 的意思，我们可以判断dp[i]=dp[i-1]+dp[i-2]+cost[i]然后，我们只需要从前到后遍历数组就可以了class Solution {public: int minCostClimbingStairs(vector<int>& cost) { int
2021-05-11 18:03:27
32
原创 Max Sum Plus Plus
Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.Given a consecutive number sequence S1, S2, S3, S4 … Sx, … Sn
2021-05-09 15:48:43
57
原创 Codeforces1517C.Fillomino 2
https://codeforces.com/problemset/problem/1517/C题目大意是说给我们一个长度为n的数组表示一个n*n的矩阵的主对角线能否让每个数字的值输出相应个数的元素因为题目的输入是从1到n，所以不需要考虑溢出的情况我们可以模拟一下这个过程，可以发现，只要输入合法，那么就一定会有答案因此，我们可以采用从左到右的方法来进行输出，使数据尽量贴近左侧，这样输出就可以实现题目的目标了#include<iostream>#include<algorith
2021-04-29 16:13:45
328
原创 Codeforces1514B.AND 0, Sum Big
题目大意是给两个变量n和k，n表示数组的大小，数组中的元素值不能超过2的k次方。同时，它还要求满足其他两个条件首先，使用元素按位和等于0这个好理解，比如4的二进制是10，1的二进制是01，它们的和为0而在这个数组中，只要取一个数为0，那么位和就一定为0它还要求元素之和应该尽量大所以，我们除了0之外只能取，2的k次方减1到2的k次方减n-1的数，总共是k个，而每个元素都有这么多取法因此，这道题的最终输出就是，n的k次方#include<iostream>#include<a
2021-04-27 19:44:10
88
原创 102.二叉树的层序遍历
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*>que; if(root!=NULL)que.push(root); vector<vector&
2021-04-26 23:37:58
49
原创 codeforces1513F.Swapping Problem
https://codeforces.ml/problemset/problem/1513/F题解是抄的，磨了几个小时还是不会#include<iostream>#include<algorithm>#include<cmath>#include<stack>#include<map>#include<cstring>#include<vector>using namespace std;#defin
2021-04-26 16:27:28
204
原创 二叉树的前序中序后序遍历（递归法）
void recursion(Treenode* cur, vector<int>& vec){//前序遍历 if (cur == NULL)return; vec.push_back(cur->val); recursion(cur->left, vec); recursion(cur->right, vec);}void recursion(Treenode* cur, vector<int>& vec){//中序遍历 if
2021-04-25 21:49:34
40
原创 145.二叉树的后序遍历(迭代法）
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/在前序遍历的基础上改进class Solution {public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*>st; vector<int>result; st.push(root);
2021-04-25 16:19:09
40
原创 94.二叉树的中序遍历（迭代法）
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/根前序遍历的题类似，就是输出顺序但是，这次我们需要一个指针用来遍历节点同样是一个栈来处理节点上的元素class Solution {public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*>st; vector<int&g
2021-04-25 15:55:34
42
原创 144.二叉树的前序遍历（迭代法）
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/这道题的目的是让我们输出二叉树的前序遍历前序遍历，即根据 中 左 右 的顺序输出二叉树的结点class Solution {public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*>st;//创建一个栈来做中转站 vector
2021-04-25 15:18:02
39
原创 347.前k个高频元素
https://leetcode-cn.com/problems/top-k-frequent-elements/给定一个整数集和一个数返回频率第k高的数如果用暴力的方法去做也可以完成，统计每个数的频率然后逐个输出但是，题目中的进阶要求我们必须使用时间复杂度为O(nlogn)级别的算法因此，我们可以采用优先级队列不过，还有一个问题，是用大顶堆还是小顶堆呢？如果使用大顶堆的话，在每次更新的时候，都会弹出最大的元素，因此，我们使用小顶堆因为我们需要统计前k频率的数，小顶堆每次弹出最小元素，最后小
2021-04-24 20:39:09
38
原创 239.滑动窗口最大值
https://leetcode-cn.com/problems/sliding-window-maximum/又是一道滑动窗口题这道题的暴力解法是在每次移动时比较产生最大值，但因为数据是整体移动的，用max来标记最大值不容易实现因此，我们定义一个双向队列来实现这一目的...
2021-04-24 15:12:13
43
原创 150.逆波兰表达式
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/根据题目的意思，我们需要把原先的中缀表达式改写为后缀表达式也就是原本a+b改写为ab+我们也是运用stack来进行解答stack<int>st; for(int i=0;i<tokens.size();i++) { if(tokens[i]=="+"||tokens[i]=="-"||tokens
2021-04-23 12:35:09
42
原创 KMP算法的简单运用
https://leetcode-cn.com/problems/repeated-substring-pattern/根据KMP算法的原理，这道题可以很方便地用KMP算法实现我们只需要观察next数组的最后一个元素，如果它可以整除原字符串的长度并且不等于-1，那么它就满足题意void getnext(int *next,string &s){ int j=-1; next[0]=-1; for(int i=1;i<s.size();i++) {
2021-04-21 21:51:55
46
原创 KMP算法笔记
https://leetcode-cn.com/problems/implement-strstr/该题需要我们匹配一个与子字符串相同的字符串，如果没有就返回-1看起来只要暴力就可以破除，但是，暴力的解法需要的时间复杂度非常大，一旦字符串的长度开得很大，时间限制更加严格，暴力很可能冲不过去所以，我们可以采用一种比较相同字符串非常著名的方法，KMP算法KMP算法的一个核心就是next数组，如next[i]表示两个值：首先，这个下标 i 表示的是字符的下标，注意，是子串的下标而这个next[i]的值表
2021-04-20 23:33:18
33
原创 向左旋转字符串
https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/在只学习了C语言的时候，向左旋转字符串是非常麻烦的，需要注意各种条件而在stl库中，reverse函数可以方便地旋转字符串 reverse(s.begin(),s.begin()+n); reverse(s.begin()+n,s.end()); reverse(s.begin(),s.end()); return s;
2021-04-19 23:53:35
70
原创 翻转字符串中的单词
https://leetcode-cn.com/problems/reverse-words-in-a-string/该题需要我们翻转字符串中的单词因为题目中建议我们采用n（1）复杂度的方法，所以我们就不能使用stl库中的一些函数了首先，我们反转整个字符串我们设计让指针只读入非空格字符，除了第一个单词，之后每遇到一个单词都在前面加上空格，这样就达到了去空格的目的然后，我们只需要对每个单词进行翻转就完成了字符串中单词的翻转 reverse(s.begin(),s.end()); i
2021-04-19 19:30:13
95
原创 字符串替换空格
https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/在之前，如果需要替换空格并且替换的长度不等于空格大小，可以采用边判断边输出的方法，但这道题我们需要返回一个string类型，所以需要采取新方法首先，我们遍历一次字符串，获得空格的数目然后我们把原数组的大小扩充空格的两倍（（3-1）/1=2）之后我们定义两个指针，一个指向原字符串末尾，一个指向新字符串末尾，让它们同时向头部移动，如果遇到非空格那么就从前指针输入字符到后指针，否则，就把空格转化为%
2021-04-19 18:50:59
138
原创 从第k个字符开始反转字符串
https://leetcode-cn.com/problems/reverse-string-ii/submissions/因为如果用双指针法进行反转字符串代码量会比较大，所以，我们采用stl库中的reserve函数它的功能是反转字符串，具体是reserve（开始位置，结束位置）int n=s.size(); for(int i=0;i<n;i+=2*k) { //如果剩余字符数大于K if(i+k<=n) reve
2021-04-19 18:32:28
214
原创 四数相加
https://leetcode-cn.com/problems/4sum-ii/该题大意是说给我们四个数组，判断从每个数组中各取一个数相加能否等于零，因为是四数相加，所以采用暴力解法的复杂度会非常大因此，我们采用哈希表法因为数组不需要有序，为了读入数据更加快捷，我们采用unordered_map来存储哈希表首先，遍历前两个数组，获得每两个元素相加的和存储到哈希表中然后，遍历后两个数组，前两个数组与后两个数组的和即a+b+c+d，即前两个数组的和在等于-c-d 时四数之和为零，当满足条件时，将结果
2021-04-19 16:17:53
124
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人