第一题：在字符串中每次删除两个相同的字母可以增加一个任意字母，问最少多少次操作可以使得整个字符串的所有字母都只出现一次
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回满足题意的最小操作数
* @param str string字符串 给定字符串
* @return int整型
*/
public int minOperations (String str) {
// write code here
int[] cnt = new int[26];
int n = str.length();
for(int i=0;i<n;++i){
int x = str.charAt(i) - 'a';
cnt[x]++;
}
int ans = 0;
for(;;){
int tot1 = 0;
int tot2 = 0;
for(int i=0;i<26;++i){
tot1 += cnt[i] / 2;
cnt[i] %= 2;
tot2 += cnt[i];
}
ans += tot1;
if(tot1 + tot2 <= 26) break;
tot1 -= 26 - tot2;
for(int i=0;i<26;++i){
if(cnt[i] == 0) cnt[i] = 1;
}
while(true){
boolean flag = true;
for(int i=0;i<26;++i){
if(tot1 > 0) {
cnt[i]++;
tot1--;
}else {
flag = false;
break;
}
}
if(!flag) break;
}
}
return ans;
}
} 第二题：根据给定的先序和中序能构造出的所有二叉树
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型ArrayList
* @param inOrder int整型ArrayList
* @return TreeNode类ArrayList
*/
ArrayList<TreeNode> ans = new ArrayList<>();
int n;
ArrayList<TreeNode> dfs(ArrayList<Integer>pre,int l1,int r1,ArrayList<Integer>in,int l2,int r2){
if(l1 > r1 || l2 > r2) return null;
int rt = pre.get(l1);
ArrayList<TreeNode> res = new ArrayList<>();
for(int i=l2;i<=r2;++i){
if(rt == in.get(i)){
int lnum = i - l2;
int rnum = r2 - i;
ArrayList<TreeNode> list1 = dfs(pre,l1+1,l1+lnum,in,l2,i-1);
ArrayList<TreeNode> list2 = dfs(pre,l1+lnum+1,r1,in,i+1,r2);
if(list1 == null && list2 != null){
int n2 = list2.size();
for(int j=0;j<n2;++j){
TreeNode u = new TreeNode(rt);
u.right = list2.get(j);
res.add(u);
}
}else if(list1 != null && list2 == null){
int n1 = list1.size();
for(int j=0;j<n1;++j){
TreeNode u = new TreeNode(rt);
u.left = list1.get(j);
res.add(u);
}
}else if(list1 == null && list2 == null){
TreeNode u = new TreeNode(rt);
res.add(u);
}else{
int n1 = list1.size();
int n2 = list2.size();
for(int k=0;k<n1;++k){
for(int j=0;j<n2;++j){
TreeNode u = new TreeNode(rt);
u.left = list1.get(k);
u.right = list2.get(j);
res.add(u);
}
}
}
}
}
return res;
}
public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> pre, ArrayList<Integer> in) {
// write code here
n = pre.size();
ans = dfs(pre,0,n-1,in,0,n-1);
return ans;
}
} 第三题：二叉树的每个结点只有0个子结点或者2个子结点，要求给每个结点填入正整数，且左右子树的和相等，问整棵树最小的和是多少（答案要对1e9+7取模）
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tree TreeNode类
* @return int整型
*/
final long mod = (int)(1e9 + 7);
long dfs(TreeNode u){
if(u.left == null && u.right == null) return 0;
long res = 0;
long num1 = dfs(u.left);
long num2 = dfs(u.right);
res = 2L * (Math.max(num1,num2) + 1L);
return res;
}
public int getTreeSum (TreeNode tree) {
// write code here
long ans = dfs(tree);
ans++;
ans %= mod;
return (int)ans;
}
}
#腾讯音乐2023秋招笔试心得体会#
