这道题考的是常见的最长公共子串问题，这类问题需要用动态规划解决。 dp[i][j] 表示字符串a[1...i]和字符串b[1...j]的最大公共字串长度。 递推公式：如果a[i] == a[j]， 那么dp[i][j] = dp[i-1][j-1] + 1; 否则 dp[i][j] = 0； #include <iostream> using namespace std; int lcs(string a, string b) { int maxLen = 0; a.insert(0, 1, ' '); b.insert(0, 1, ' '); i...

这题考的是levenshtein距离的计算，需要运用动态规划去解决该类问题。 传递公式： lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离； 插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a； 如果a[i] == b[j]，则说明a[i]和b[j]分别加入a，b之后不会影响levenshtein距离，lev[i][j] = lev[i-1][j-1] + 0; 如果a[i] != b[j]，则需要考虑3种情况的可能： a中插入字符，即lev[i][j] = lev[i-1][j] + 1; b中插入字符，即lev...

这题考的是levenshtein距离的计算，需要运用动态规划去解决该类问题。 传递公式： lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离； 插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a； 如果a[i] == b[j]，则说明a[i]和b[j]分别加入a，b之后不会影响levenshtein距离，lev[i][j] = lev[i-1][j-1] + 0; 如果a[i] != b[j]，则需要考虑3种情况的可能： a中插入字符，即lev[i][j] = lev[i-1][j] + 1; b中插入字符，即lev...

怎么去重，用set集合。 首先根据输入顺序，将砝码用数字序列表示，例如2个1g和1个2g，就用 1 1 2的序列表示； set序列用来表示加入当前砝码之前能产生的重量种类； set初始化为{0}；当第一个1g砝码放入时，则set中需要插入原先set中的所有元素+1g后的结果；即{0, 0+1}; 当第二个1g加入时，则set会插入{0+1, 1+1},就变成了{0, 1, 2}; 重复上述步骤加入所有砝码；则最后set的大小即为能产生的重量种类。 #include <iostream> #include <vector> #include <set> u...

每次操作只有两种选项， 输入的元素压栈； 栈顶的元素出栈； 后一次操作不受前一次操作影响。故可以使用递归实现。递归终止条件即输入序列用完。 #include <iostream> #include <queue> #include <algorithm> #include <stack> using namespace std; vector<string> v; void print_queue(queue<int> q) { string s; while ( !q.empty() ) ...

问题：如何判断'+'或'-'是加减还是正负？解答：用一个变量来判断：数字和运算符是交替出现的（括号的出现不会影响这种交替关系）。 思路 用两个栈分别压数字和运算符； 如果当前运算符优先级('*/')高于栈顶运算符('+-')优先级，则将运算符入栈；反之，从数字栈中弹出两个数，从运算符栈中弹出栈顶运算符，进行运算，数字栈压入运算结果，符号栈压入当前运算符。重复该操作直到不满足条件。 出现左括号，则直接压入；出现右括号，则从数字栈中弹出两个数，从运算符栈中弹出栈顶运算符，进行运算，数字栈压入运算结果，重复该操作直到栈顶弹出右括号位置。 题解 #include <iostream> ...

对于测试用例乱来的题目，以下方法百分百AC。 #include <iostream> #include <vector> using namespace std; vector<string> qu = {"4 2 K A", "3 2 3 8", "5 7 3 9", "8 3 9 7", "A 2 J 3", "A A A A", "A K J 8", "K Q 6 K", "A 8 8 4", "Q 3 J 8", "4 4 2 7", "A J K 6", "J ...

穷举法实现（未做剪枝） 四个数进行全排列（共 a = 4*3*2种情况），全排列可以使用next_permutation实现； 每两个数之间插一个运算符，共三个运算符（共 b = 4*4*4种情况）； 考虑括号对优先级影响（共c=3*2种情况）。 #include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; double op(double a, double b, int opera) { if(op...

思路分析（分成两种情况讨论）： 问题1：如何分辨两组牌是否为同一个类型？答案1：可以通过输入字符串的间隔符（空格数）是否相同判断。问题2：如何判断单个牌的大小顺序？答案2：组一个字符串“345678910JQKA2jokerJOKER”，通过判断对应单个字符或字符串在该字符串的位置进行大小比较。 手牌比较过程： 手牌的类型相同（单对单，对对对，三对三，四对四，顺子对顺子）： a. 直接比较第一张手牌的大小即可； 手牌的类型不同（分为三种情况）： a. 存在王炸，输出王炸； b. 存在炸弹，输出炸弹； c. 否则输出ERROR； 题解 #include <iostream> #i...

把输入的double数看成string类型，先读整数部分后读小数部分； 整数部分的长度j减去当前字符所在位置i即当前数所在的权重位；即每一位可以读作ge[s[i]-'0'] + ot[j-i-1]；（遵循从高位往低位读） 对应位碰上0则不读，但如果该权重位在万，亿，万亿，万万亿上，则无需读零，但需输出权重位的读法（万，亿）；这样才能保证100000读成拾万，而不是读成拾。例外：100000000应读成壹亿，而非壹亿万。 对应位不为0，但前一位为0，则补读零。 例外：10应读成拾元而非壹拾元。 #include <iostream> using namespace std; st...

这道题考的是常见的最长上升子序列问题。 #include <iostream> using namespace std; int main() { int n; int m[10000], dp1[10000], dp2[10000]; while(cin >> n) { for(int i = 0; i < n; i++) { cin >> m[i]; dp1[i] = 1; for(int j = 0; j &l...

这道题考的是常见的最长上升子序列问题。 #include <iostream> using namespace std; int main() { int n, m = 0; int a[10000], dp[10000]; while(cin >> n) { m = 0; for(int i = 0; i < n; i++) { cin >> a[i]; dp[i] = 1; for (int j ...

合理使用递归 #include <iostream> using namespace std; bool match(string a, string b) { // 可以做一下剪枝 for(int i = 0, j = 0; i < a.size(); i++, j++) { if (a[i] == '*') { bool f = false; string s = a.substr(i+1); for (int k = j; k < b.size(); ...

这道题很简单，其实可以简化成树的层序遍历（或图的广度优先遍历），唯一难点就是记录路径。把迷宫抽象成一个起点为根的树。 #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; int main(){ int n, m; int t[4][2] = {{-1,0}, {0,-1}, {1,0},{0,1}}; int v[12][12]; while(cin >> n ...