#include <cctype> #include <iostream> #include <stack> using namespace std; /*栈便于解决字符串中判断顺序的问题 由栈来存放字符串，可以获得计算的顺序。如（A（BC））如果来的是左括号就忽略，是字母，就把对应矩阵的行列长度压到栈中，是右括号，就弹出最上面的两个矩阵的行列来计算,计算结果压回到栈中。 要同时存储行列两个数据，先用二维数组来分别接收每一组行列，往栈中压的时候选择pair<int,int>类型即可每次压两个一组的数据 关于如何计算乘法运算次数：A（m*n）B(n...

#include <algorithm> #include <cctype> #include <string> #include <vector> #include <iostream> using namespace std; /*用动态规划可以参考动态规划做判断是否回文子串那道题，HJ32 这道也是由bool类型的dp数组来表示是否能匹配上。 1）dp[i][j] 表示[0，i-1]的pattern串是否能和[0,j-1]的s串匹配成功 2）递推： 1>如果p[i-1]是*，s[j-1]是英语或数字，可以匹配，所以就可以选...

#include <iostream> using namespace std; //类似哈希表的思想，记下字母的频率，让最多次数的字母为26，依次递减 int main() { int n; cin >> n; string s; while (cin >> s) { int result = 0; int beauty = 26; int hash[26] = {0}; for (int i = 0; i < s.size(); i++) { hash[s[i] - 'a']++; } //插入排序 for (int i = 1; i < 2...

#include <iostream> #include <vector> using namespace std; //动态规划 0-1背包问题 //所有涉及价格的地方，由于价格全部能被10整除，全部都/10减少遍历次数，包括可供支配的总价格N、每件商品的价格price int main() { int N,m; cin>>N>>m; N/=10; int price,priority,hash;//用来输入每件物品的价格、重要度、是否是谁的附件 vector<vector<int>>data(m+1,vector&lt...

#include <iostream> #include <string> #include <stack> using namespace std; /*1)数字入一个栈，符号入一个栈。2）用函数判断符号的优先级，新来的符号优先级大于栈底的符号优先级时，3）函数：从数字栈取两个数字出来计算，并将结果再压回栈中*/ void Compute(stack<int>&num,stack<char>&op){ if(num.empty()||op.empty()) return; int b=num.top(); num.p...

#include<iostream> #include<stack> #include<vector> #include <queue> #include<algorithm> using namespace std; //找出输入数字的全排列，然后用栈来找是不是符合情况。如果出栈序列元素=入栈元素，同时弹出，不等于则入栈，最后看栈中是否为空 bool Checkstack(vector<int>& a,vector<int>& b,int n){ //分别是入栈队列、出栈队列、队列长度 que...

#include <iostream> #include <vector> #include <string> using namespace std; /*等价于动态规划的经典问题，最长递增子序列。每一个元素，正着找他的最长递增子序列长度，再倒着找他的最长递增子序列长度，想加之后-1，就是最长梯度子序列长度，保证每一侧都是梯度递增的 1) d[i]以nums[i]结尾的子序列中最长递增子序列的个数为dp[i] 2)递推公式 每一个i,用j遍历0～i,如果num[j]<num[i]说明递增关系成立，对于这个j而言，最大子序列长度dp[i]=dp[j]+...

#include <algorithm> #include <iostream> using namespace std; /*动态规划经典问题之 编辑距离 1)dp[i][j]表示word1[i-1]结尾的单词和word2[j-1]结尾的单词2之间编辑成一致所需要的最小距离（最少操作次数）（之所以是表示i-1 j-1结尾，是因为会比较容易初始化） 2）递推公式。分多种情况讨论。 1> word1[i-1]=word2[j-1]，此时两个单词的最小距离无需考虑当前位，等于word1[i-2]结尾的单词和Word2[j-2]结尾的单词的最小距离。即：dp[i][j]...

#include <iostream> #include <vector> using namespace std; //动态规划经典题目，寻找数组中的最长递增子序列元素数 /*1)dp[i]表示以nums[i]为结尾的子数组中，最长递增子序列的元素数 2）递推：i先遍历所有元素，j来遍历0～i(即j是为了找I的所有子序列)，if(nums[j]<nums[i])子序列中有递增的元素出现，则dp[i]=max(dp[j]+1,dp[i]) (dp[i]要去到i之前所有子序列中最大的数字，因为没有一个最大值就给dp[i]赋值了，再有更大的长度出现就覆盖赋值) 3）初...

#include <iostream> using namespace std; struct ListNode{ int val; ListNode* next; ListNode(int val):val(val),next(nullptr){} }; //从index插入节点的函数,再val1后面插入val2的值 ListNode* AddIndex(ListNode * dummyHead,int val1,int val2) { ListNode* cur=dummyHead; while(cur!=nullptr&&cur->val!=val1){...

#include <iostream> using namespace std; struct ListNode{ int val; ListNode* next; ListNode(int val):val(val),next(nullptr){} };//链表定义和初始化 int main() { int n,k; while(cin>>n){ int size=0; int val; ListNode* dummyHead=new ListNode(0);//在最前面定义一个虚拟头节点，这样不论是头结点还是后面的普通节点都直接用同一段代码正常插入删除即可 List...

#include <iostream> #include <string> using namespace std; //关于失败的情况有很多，要全部判断 void IsIpLeagal(string s){ string tmp; int nip,i,j; int point=0; if(s[0]=='.'||s[s.size()-1]=='.'){cout<<"NO"<<endl;return;} for(i=0,j=0;i<s.size()&&j<s.size();i++){ while(s[...

#include <iomanip> #include <iostream> using namespace std; //查找一个数是否单独目标值，二分法。由于需要答案的小数位达标，且数值正确，所以循环时可以多加上一个小数精度的条件。我们算到下一位精度，保证输出时保留一位小数结果正确 double cal(double val){ double left=-20.0,right=20.0,n; while(abs(right-left)>0.01&&left<right){ n=(right+left)/2.0; if(n*n*n>v...

#include <iostream> using namespace std; //数学题，递归，推导公式，算规律 void Calculate(long long a,long long b){ if(a==1){cout<<1<<"/"<<b<<endl;return;} else if(b%a==0){cout<<1<<"/"<<b/a<<endl;return;} else{ cout<<1<<"/&qu...