迪士尼在逃米老鼠

题解

/ 注册

全部文章 / 题解（共16篇）

查找两个字符串a,b中的最长公共子串

这道题考的是常见的最长公共子串问题，这类问题需要用动态规划解决。 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；题解 ...

2020-02-23

4 2140

公共字串计算

这道题考的是常见的最长公共子串问题，这类问题需要用动态规划解决。 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； #in...

2020-02-23

13 2361

计算字符串的相似度

这题考的是levenshtein距离的计算，需要运用动态规划去解决该类问题。传递公式： lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离；插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a；如果a[i] == b[...

2020-02-23

8 936

计算字符串的距离

这题考的是levenshtein距离的计算，需要运用动态规划去解决该类问题。传递公式： lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离；插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a；如果a[i] == b[...

2020-02-23

66 7637

称砝码

怎么去重，用set集合。首先根据输入顺序，将砝码用数字序列表示，例如2个1g和1个2g，就用 1 1 2的序列表示； set序列用来表示加入当前砝码之前能产生的重量种类； set初始化为{0}；当第一个1g砝码放入时，则set中需要插入原先set中的所有元素+1g后的结果；即{0, 0+1}; ...

2020-02-23

187 7116

火车进站

每次操作只有两种选项，输入的元素压栈；栈顶的元素出栈；后一次操作不受前一次操作影响。故可以使用递归实现。递归终止条件即输入序列用完。 #include <iostream> #include <queue> #include <algorithm> #i...

2020-02-18

20 2652

四则运算

问题：如何判断'+'或'-'是加减还是正负？解答：用一个变量来判断：数字和运算符是交替出现的（括号的出现不会影响这种交替关系）。思路用两个栈分别压数字和运算符；如果当前运算符优先级('*/')高于栈顶运算符('+-')优先级，则将运算符入栈；反之，从数字栈中弹出两个数，从运算符栈中弹出栈顶运...

2020-02-16

82 7132

24点运算

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

2020-02-14

6 1877

24点游戏算法

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

2020-02-14

10 2380

扑克牌大小

思路分析（分成两种情况讨论）：问题1：如何分辨两组牌是否为同一个类型？答案1：可以通过输入字符串的间隔符（空格数）是否相同判断。问题2：如何判断单个牌的大小顺序？答案2：组一个字符串“345678910JQKA2jokerJOKER”，通过判断对应单个字符或字符串在该字符串的位置进行大小比较。手...

2020-02-12

64 2937