先给一个二叉树节点结构：
class Node2 {
public:
Node2(int val){
left = nullptr;
right = nullptr;
this->val = val;
}
Node2* left;
Node2* right;
int val;
};
1.给定一个非负整数n，代表二叉树的节点个数，返回能形成多少种不同的二叉树结构
int test02(int n) {
if (n < 0) return 0;
if (n <= 1) return 1;
if (n == 2) return 2;
int res = 0;
for (int i = 0; i < n - 1; i++) {
int leftNum = test02(i);
int right = test02(n - 1 - i);
res += leftNum * right;
}
return res;
}
2.完整的字符串需要添加的字符
int test03(string& s) {
int count = 0;
int ans = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
count++;
}
else {
if (count == 0) {
ans++;
}
else {
count--;
}
}
}
return count + ans;
}
3.给定一个arr,求差值为k的去重数字对
vector<vector<int>> test04(vector<int>& vec, int k) {
vector<vector<int>> res;
unordered_map<int, int> map;
for (const auto& n : vec) {
map[n]++;
}
for (const auto& n : map) {
if (map.find(n.first + k) != map.end()) {
res.push_back(vector<int>{n.first, n.first + k});
}
else if (map.find(n.first - k) != map.end()) {
res.push_back(vector<int>{n.first, n.first - k});
}
}
return res;
}
4.给一个包含n个整数元素的集合a，一个包含m个整数元素的集合b，定义magic操作为，从一个集合中取出一个元素，放到另一个集合中，且操作过后每个集合的平均值都大于操作前。不可以把一个集合的元素区孔，这样就没有平均值了，值为x的元素从集合b取出放入集合a，但集合a中已经有值为x的元素，则a的平均值不变，b的平均值可能会改变，最多进行多少次magic操作。
int test05(vector<int>& a, vector<int>& b) {
double sum1 = 0;
for (const auto& n : a) {
sum1 += n;
}
double sum2 = 0;
for (const auto& n : b) {
sum2 += n;
}
if ((sum1 / a.size()) == (sum2 / a.size())) {
return 0;
}
vector<int> arrMore;
vector<int> arrLess;
double sumMore = 0;
double sumLess = 0;
if ((sum1 / a.size()) > (sum2 / b.size())) {
arrMore = a;
sumMore = sum1;
arrLess = b;
sumLess = sum2;
}
else {
arrMore = b;
sumMore = sum2;
arrLess = a;
sumLess = sum1;
}
sort(arrMore.begin(), arrMore.end());
std::set<int> setLess;
for (const auto& n : arrLess) {
setLess.insert(n);
}
int moreSize = arrMore.size();
int lessSize = arrLess.size();
int ops = 0;
for (int i = 0; i < arrMore.size(); i++) {
double cur = (double)arrMore[i];
if (cur < (sumMore / moreSize) && cur >(sumLess / lessSize) && setLess.find(arrMore[i]) != setLess.end()) {
sumMore -= cur;
moreSize--;
sumLess += cur;
lessSize++;
setLess.insert(arrMore[i]);
ops++;
}
}
return ops;
}
5.求一个合法括号字符串的深度，合法字符串的定义“（）（）（）”，合法字符串的深度："()()()“深度为1”((()))"深度为3
int test06(string& s) {
if (s.size() == 0) return 0;
int count = 0;
int res = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
count++;
}
else {
count--;
}
res = max(count, res);
}
return res;
}
6.给定一个合法字符串，找出其有效的最长括号子串长度，"())()(())()))(())"的最长括号子串为“()(())()”
int test07(string& s) {
if (s.size() == 0) return 0;
vector<int> dp(s.size());
int pre = 0, res = 0;
for (int i = 1; i < s.size(); i++) {
if (s[i] == ')') {
pre = i - dp[i - 1] - 1;
if (pre >= 0 && s[pre] == '(') {
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
res = max(res, dp[i]);
}
return res;
}
7.给定一个栈 按升序进行排序 最多只能使用一个额外的栈存放临时数据
void test08(stack<int>& s) {
stack<int> sta;
while (!s.empty()) {
int top = s.top();
s.pop();
if (sta.empty() || top < sta.top()) {
sta.push(top);
}
else {
while (top < sta.top()) {
int tmp = sta.top();
sta.pop();
s.push(tmp);
}
sta.push(top);
}
}
s = sta;
}
8.给定一个字符串，1对应a, 2d对应b,…,26对应z,例如12258可以转化为"abbeh", “aveh”,“abyh”,“lbeh”，“lyh”，给出可以转化的不同字符串的个数
int test09_1(string s, int n) {
if (n == s.size()) {
return 1;
}
if (s[n] == '0') {
return 0;
}
int res = test09_1(s, n + 1);
if (n == s.size() - 1) {
return res;
}
if (((s[n] - '0') * 10 + s[n + 1] - '0') < 27) {
res += test09_1(s, n + 2);
}
return res;
}
9.二叉树每个节点都有一个权重，求一颗二叉树从根到叶子的所有路径中权重和最大的一条路
int max10 = INT_MIN;
void test10(Node2* head, int pre) {
if (head->left == nullptr && head->right == nullptr) {
max10 = max(max10, pre + head->val);
}
if (head->left) {
test10(head->left, pre + head->val);
}
if (head->right) {
test10(head->right, pre + head->val);
}
}
10.查找二维数组中的一个数字，该二维数组中数字每行每列都是有序的从小到大
bool test11(vector<vector<int>> vec, int num) {
int left = 0;
int right = vec[0].size();
while (left < vec.size() && right >= 0) {
if (vec[left][right] == num) return true;
if (vec[left][right] > num) {
right--;
}
else {
++left;
}
}
return false;
}
| 
