写出完整的c++代码
时间: 2023-08-07 18:15:13 浏览: 48
好的,以下是完整的C++代码:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int longest_increasing_subsequence(string s) {
int n = s.length();
int dp[n];
fill(dp, dp + n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (s[j] < s[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp, dp + n);
}
int main() {
int n;
cin >> n;
while (n--) {
string s;
cin >> s;
cout << longest_increasing_subsequence(s) << endl;
}
return 0;
}
```
输入示例:
```
3
aaa
ababc
abklmncdefg
```
输出示例:
```
1
3
7
```
相关问题
请写出相关C++代码
六度空间理论是一个社交网络理论,与C++语言本身没有直接关系。不过,我们可以通过C++代码来实现一些类似的算法,比如图论中的最短路径算法,用于求解两个人之间的最短路径,从而验证六度空间理论。以下是一个简单的实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int INF = 1e9;
vector<int> G[10000];
int d[10000];
bool used[10000];
void bfs(int s) {
queue<int> q;
q.push(s);
d[s] = 0;
used[s] = true;
while(!q.empty()) {
int v = q.front(); q.pop();
for(int i=0; i<G[v].size(); i++) {
int u = G[v][i];
if(!used[u]) {
used[u] = true;
d[u] = d[v] + 1;
q.push(u);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
// 构建无向图
for(int i=0; i<m; i++) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
// 求解最短路径
bfs(1);
// 输出结果
int cnt = 0;
for(int i=1; i<=n; i++) {
if(d[i] == 6) cnt++;
}
cout << cnt << endl;
return 0;
}
```
这段代码中,我们使用了广度优先搜索算法来求解最短路径。具体来说,我们从起点开始,不断向外扩展,直到找到目标节点或者遍历完整个图。最终,我们可以得到每个节点到起点的最短距离,从而验证六度空间理论。
写出c++代码
以下是使用递归方式实现求结点X在二叉树中的双亲结点算法的C++代码:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* findParent(TreeNode* root, TreeNode* node) {
if (!root || root == node) {
return NULL;
}
if (root->left == node || root->right == node) {
return root;
}
TreeNode* left = findParent(root->left, node);
if (left) {
return left;
}
return findParent(root->right, node);
}
```
在上面的代码中,我们使用了TreeNode结构体表示二叉树的节点,其中包含节点的值、左右子树指针。函数findParent接收二叉树的根节点和要查找的节点作为参数,并返回查找的节点的双亲节点。在函数中,我们首先判断当前节点是否为空或者是否为要查找的节点,如果是,返回空指针NULL;然后判断当前节点的左右子树是否为要查找的节点,如果是,返回当前节点;否则,递归查找左子树和右子树,直到找到要查找的节点或者遍历完整个树为止。