实习+秋招刷题009-0010（牛客刷题）

腾讯音乐娱乐集团2023校园招聘技术类岗位编程题合集

009字符串操作
题目描述

给定一个只包含小写字母字符串，每次可以选择两个相同的字符删除，并在字符串结尾新增任意一个小写字母。
请问最少多少次操作后，所有的字母都不相同？
输入例子：
"abab"
输出例子：
2
例子说明：
第一次操作将两个'a'变成一个'f'，字符串变成"bbf"。
第二次操作将两个'b'变成一个'b'，字符串变成"fb"。
操作方式不是唯一的，但可以证明，最少操作次数为2。

关键解题思路
每次的操作看成是一次消除新增操作，消除两个一样的字符，优先新增字符串中没出现过的字母。
获取str中存在能两两配对（类似aa,aa,bb,cc）的数量count。
上面的操作看成第一次操作，当第一次所有消除新增操作结束以后，count大于26，那么字符串中一定有重复字母，继续进行新增消除操作。
那么操作次数 = 第一次操作次数（count）+ 第一次操作结束后的字符串长度能两两消除的数量（即第一次操作结束后的字符串中所有字母都不同所需要进行的最少操作次数） = count + （len(str)-count-26）

Solution

import java.util.*;


public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回满足题意的最小操作数 * @param str string字符串 给定字符串 * @return int整型 */
    public int minOperations (String str) {
   
        Set<Character> strarr = new HashSet<Character>();
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
   
            if (!strarr.add(str.charAt(i))) {
   
                char c = str.charAt(i);
                strarr.remove(c);
                // while (strarr.add(c++)) {
   

                // }
                count++;
            }

        }
        if(str.length()-count>26){
   
            count=count+(str.length()-count-26);
        }
        return count;
        // write code here
    }
}

0010带重复节点的前序中序二叉树
题目描述

已知一个二叉树的先序遍历序列和中序遍历序列，但其中一些节点的值可能相同。请你返回所有满足条件的二叉树。二叉树在数组中的顺序是任意的。    
输入例子：
[1,1,2],[1,2,1]
输出例子：
[{
   1,1,#,#,2},{
   1,#,1,2}]

关键解题思路
通过函数边界参数递归构造左子树和右子树,preorder[pl]为根节点
如果左边界大于右边界，需要add(null),然后return；
递归视野要宏观，此时left和right表示左子树和右子树，需要把他们拼接到一个子树上,left、right是由node组成，抛出这些node拼接树

Solution

import java.util.*;
public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param preOrder int整型ArrayList * @param inOrder int整型ArrayList * @return TreeNode类ArrayList */
    public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
   
        // write code here

        ArrayList<TreeNode>  arr = new ArrayList<TreeNode>();
        arr = getTree(preOrder, 0 ,preOrder.size()-1, inOrder,0 ,inOrder.size()-1);

        return arr ;
    }
    public ArrayList<TreeNode> getTree(ArrayList<Integer> preOrder,int pl,int pr, ArrayList<Integer> inOrder,int il,int ir){
   
         ArrayList<TreeNode>  arr = new ArrayList<TreeNode>();
         //通过函数边界参数构造左子树和右子树,preorder[pl]为根节点
         //如果左边界大于右边界，需要结束
         if(pl>pr || il>ir){
   
            arr.add(null);
            return arr;
         }
         for(int i =il; i<=ir; i++){
   
            if(inOrder.get(i)==preOrder.get(pl)){
   
                
                ArrayList<TreeNode> left= getTree(preOrder,pl+1,pl+i-il,inOrder,il,i-1);
                ArrayList<TreeNode> right= getTree(preOrder,pl+i-il+1,pr,inOrder,i+1,ir);
                //递归视野要宏观，此时left和right表示左子树和右子树，需要把他们拼接到一个子树上,left、right是由node组成，抛出这些node拼接树
                for (TreeNode leftnode: left){
   
                    for(TreeNode rightnode: right){
   
                        TreeNode root= new TreeNode(preOrder.get(pl));
                        root.left = leftnode;
                        root.right = rightnode;
                        arr.add(root);
                        // System.out.println(root);

                        }
                    }
                }
            }
        return arr;
    }
}

这两题花了我3个小时，我真的无语，第二题node不好debug，所以很痛苦。
求职小吐槽：
海康的软件开发工程师岗位笔试代码读写都是C语言，真的不会了呀，上次写C还是大一。好多年以前了。