大内高手

题解

前端(1)

/ 注册

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

0-1背包变形

代码和0-1背包非常之像，只是由原来的容量固定，求最大价值，最小邮票数是每个邮票的价值(权重)一样，都为1(枚)，在背包大小固定的情况，求最少的邮票数。 // runtime: 4ms // space: 496K #include <iostream> #include <alg...

CPP 背包问题 DP

2020-03-23

1 841

0-1背包问题

经典的0-1背包问题。代码中的backtracking部分是输出组成最大价值的编号。 // runtime: 4ms // space: 728K #include <iostream> #include <algorithm> #include <stack> ...

背包问题 DP

2020-03-18

0 806

最长公共子序列

状态转移方程为：当s1[i] = s2[j]时: 当s1[i] != s2[j]时: // runtime: 4ms // space: 504K // complexity: O(m*n) #include <iostream> #include <cstring&...

CPP DP

2020-03-18

5 765

合唱队形

两次DP求最长递增子序列，然后，结果是 // runtime: 3ms // space: 496K #include <iostream> #include <algorithm> using namespace std; const int MAX = 100; i...

CPP DP

2020-03-17

0 597

最大上升子序列和

最长递增子序列的变形问题。 // runtime: 4ms // space; 496K #include <iostream> #include <cstdio> using namespace std; const int MAX = 1000; int arr[MAX...

CPP DP

2020-03-17

3 823

最长递增(减)子序列

// runtime: 4ms // space: 504K #include <iostream> #include <cstdio> using namespace std; const int MAX = 25; int arr[MAX]; int dp[MAX]; ...

CPP DP

2020-03-17

3 814

二叉排序树

本题考察的是二叉树的建立，并且输出父节点的值。所以函数Insert的参数里多了一个int型的变量father，记录的是父节点的值。因为二叉排序树的新增节点都是在叶子处，所以root == NULL时，新建一个结点BTree(x)。 // runtime: 5ms // space: 504K #in...

CPP 二叉树

2020-03-15

11 928

二叉树的遍历

此题考察最基本的二叉树的构造和中序遍历。 // runtime: 3ms // space: 488K #include <iostream> #include <string> using namespace std; // 二叉树结构体 struct BTree { ...

CPP 二叉树

2020-03-14

0 723

2的幂次方

此题的题意是给定一个数n，先分解成二进制和的形势2的i次方的和。比如：，而系数，直到2上面的系数i全为0或者1为止。2直接输出为2，输出为2(0),所以输入为9，输出为2(2+2(0))+2(0),即。所以此题非常适合使用递归策略。 // runtime: 4ms // space: 4...

递归 CPP

2020-03-12

6 823

递归&分治

分治：即把一个复杂的问题分成两个或多个子问题，子问题之间相互独立且与原问题相同或相似，持续分解，直到最后的子问题可以简单的求解。原问题即子问题解的合并。由于反复利用分治手段，这就为使用递归策略提供了条件。解法：采用递归策略，根据二叉树的性质：左子树编号为2m,右子树为2m+1，不断的去计算节点...

递归 CPP

2020-03-12

13 761