1.题目:给一个只有小写字母的字符串,每次可以选择两个相同的字符删去我,并在字符串结尾新增一个小写字母。
请问多少次操作后,所有字母都不相同
思路:尽可能的把变的字母变成不存在的字母。?如果26个字母都有了的话就把答案加上多余字符的个数。
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int n,a[30]={0};
cin>>s;
n=s.length();
for(int i=0;i<n;i++) a[s[i]-'a']++;
int k=0,sum=0,ans=0;
for(int i=0;i<26;i++){
if(a[i]==0 || a[i]%2==0) k++;
if(a[i]) sum+=a[i]/2;
}
if(sum<=k) ans=sum;
else
{
sum-=k;
ans+=sum;
sum++;
ans+=sum-1;
}
cout<<ans<<endl;
return 0;
}
2.重建二叉树之存在相同节点
这个题虽然说改了条件,但是题目好像也就很难了哎
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// vector<TreeNode*> ans;
// TreeNode* p;
// TreeNode* dfs1(TreeNode* x) {
// if(x == NULL) return NULL;
// TreeNode* ret = new TreeNode(x->val);
// ret->left = dfs1(x->left);
// ret->right = dfs1(x->right);
// return ret;
// }
// void makeAns() {
// // TreeNode* rt = new TreeNode(p->val);
// // rt->left = dfs1(p->left);
// // rt->right = dfs1(p->right);
// TreeNode rt = new
// ans.push_back(rt);
// }
// bool dfs(vector<int>& v1, vector<int>& v2, int l, int r, TreeNode* y) {
// if(l > r) return true;
// y = new TreeNode(v1[x]);
// if(l == r) {
// if(v1[x] == v2[l]) {
// y->val = v1[x];
// if(x == (int)v1.size() - 1) makeAns();
// return true;
// }
// return false;
// }
// for(int i = l; i <= r; i ++) {
// int t = x;
// if(v1[x] == v2[i]) {
// x ++;
// if(dfs(v1, v2, l, i - 1, y->left)) {
// x ++;
// dfs(v1, v2, i + 1, r, y->right);
// }
// }
// x = t;
// y->left = NULL;
// y->right = NULL;
// }
// return true;
// }
int x = 0;
vector<TreeNode*> dfs(vector<int>& v1, vector<int>& v2, int l, int r) {
vector<TreeNode*> ret;
if(l > r) {
ret.push_back(NULL);
return ret;
}
if(l == r) {
if(v1[x] != v2[l]) return ret;
ret.push_back(new TreeNode(v1[x]));
return ret;
}
vector<TreeNode*> ve[2];
TreeNode* p = new TreeNode(v1[x]);
for(int i = l; i <= r; i ++) {
int t = x;
if(v1[x] == v2[i]) {
if(l <= i - 1) x ++;
ve[0] = dfs(v1, v2, l, i - 1);
if(i + 1 <= r) x ++;
ve[1] = dfs(v1, v2, i + 1, r);
for(int j = 0; j < ve[0].size(); j ++) {
for(int k = 0; k < ve[1].size(); k ++) {
p->left = ve[0][j];
p->right = ve[1][k];
TreeNode* q = p;
ret.push_back(q); /// q是局部变量,会被回收吗?
}
}
ve[0].clear();
ve[1].clear();
}
x = t;
}
return ret;
}
vector<TreeNode*> getBinary(vector<int>& preOrder, vector<int>& inOrder) {
vector<TreeNode*> ans;
if(preOrder.size() != inOrder.size()) return ans;
return dfs(preOrder, inOrder, 0, (int)inOrder.size() - 1);
}
int main() {
vector<int> v1, v2;
int n, m, x;
cin >> n >> m;
while(n --) {
cin >> x;
v1.push_back(x);
}
while(m --) {
cin >> x;
v2.push_back(x);
}
vector<TreeNode*> ans = getBinary(v1, v2);
cout << ans.size() << endl;
return 0;
}
3.xx的平衡树
题意:给一个二叉树,每个二叉树只有0个或者两个孩子
现在需要对每个结点赋值一个正整数,使得每个结点的左右子树权值和相等
解题:思维题,结论是每个结点赋值为1,那么整棵树的节点和其实取决于树的高度,求树高相同的完全二叉树的节点个数就ok了,发现dfs暴力就是求出左右子树中更大的那一个,把另一个子树变得一样就好。大小与深度有关。
int dfs(TreeNode*x)
{
if(!x) return 0;
return max(dfs(x->left),dfs(x->right))+1;
}
int getTree(TreeNode* tree)
{
if(!tree) return 0;
int x=dfs(tree);
int ans=0;
while(x--)
{
ans=(ans*2+1)%(int)(1e9+7);
}
return ans;
}
做的很烂,待会再说吧哈哈哈哈