腾讯音乐笔试
第一题：字符串
给定一个只包含小写字母字符串，每次可以选择两个相同的字符删除，并在字符串结尾新增任意一个小写字母。
请问最少多少次操作后，所有的字母都不相同？
字符串长度<1e3
input:
abab
output:
2
第一次把2个a变成f，第二次把2个b变成b。得到fb，每个字母都不相同，最少操作次数为2。
请问最少多少次操作后，所有的字母都不相同？
字符串长度<1e3
input:
abab
output:
2
第一次把2个a变成f，第二次把2个b变成b。得到fb，每个字母都不相同，最少操作次数为2。
public static int minOperations (String str) {
int[] nums = new int[26];
for (int i = 0; i < str.length(); i++) {
nums[str.charAt(i) - 'a']++;
}
int cnt = 0, kinds = 0;
for (int i = 0; i < 26; i++) {
cnt += nums[i] / 2;
kinds += nums[i] % 2;
}
if (cnt + kinds <= 26) {
return cnt;
} else {
int a = 26 - kinds;
return 2 * cnt - a;
}
} 第二题： 题目描述
已知一个二叉树的先序遍历序列和中序遍历序列，但其中一些节点的值可能相同。
请你返回所有满足条件的二叉树。二叉树在数组中的顺序是任意的。
input:
[1,1,2],[1,2,1]
output:
[{1,1,#,#,2｝,{1,#,1,2｝]
已知一个二叉树的先序遍历序列和中序遍历序列，但其中一些节点的值可能相同。
请你返回所有满足条件的二叉树。二叉树在数组中的顺序是任意的。
input:
[1,1,2],[1,2,1]
output:
[{1,1,#,#,2｝,{1,#,1,2｝]
public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
ArrayList<TreeNode> temp = dfs(preOrder, inOrder);
System.out.println(temp.size());
return temp;
}
public ArrayList<TreeNode> dfs(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
ArrayList<TreeNode> ans = new ArrayList<>();
if (inOrder.size() == 0) {
return ans;
}
int rootVal = preOrder.get(0);
for (int i = 0; i < inOrder.size(); i++) {
int k = inOrder.get(i);
if (rootVal == k) {
ArrayList<Integer> inOrderLeft = new ArrayList<>();
ArrayList<Integer> inOrderRight = new ArrayList<>();
ArrayList<Integer> preOrderLeft = new ArrayList<>();
ArrayList<Integer> preOrderRight = new ArrayList<>();
if (i > 0) {
int sum = 0;
for (int z = 0; z < i; z++) {
inOrderLeft.add(inOrder.get(z));
sum += inOrder.get(z);
}
for (int z = 1; z <= i; z++) {
preOrderLeft.add(preOrder.get(z));
sum -= preOrder.get(z);
}
if (sum != 0) {
continue;
}
}
if (i < inOrder.size()) {
for (int z = i + 1; z < inOrder.size(); z++) {
inOrderRight.add(inOrder.get(z));
preOrderRight.add(preOrder.get(z));
}
}
List<TreeNode> left = dfs(preOrderLeft, inOrderLeft);
List<TreeNode> right = dfs(preOrderRight, inOrderRight);
if (left.size() > 0 && right.size() > 0) {
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(rootVal);
root.left = l;
root.right = r;
ans.add(root);
}
}
} else if (left.size() > 0) {
for (TreeNode l : left) {
TreeNode root = new TreeNode(rootVal);
root.left = l;
ans.add(root);
}
} else if (right.size() > 0) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(rootVal);
root.right = r;
ans.add(root);
}
} else {
TreeNode root = new TreeNode(rootVal);
ans.add(root);
}
}
}
return ans;
} 
第二题没看懂大大的思路
投递美团等公司10个岗位 >
