[email protected]同城笔试

文章目录

1.调整队形 AC

需要将男同学排到一起，女同学排到一起；男生用’B’表示，女生用’G’表示
计算出最少需要多少次调换才能将男同学和女同学分开？

思路：只有两种情况，一种情况下男生在左边，一种情况下男生在右边；
分别统计男生和女生的个数，以及男生和女生各自在数组(字符串)中的下标和，分别进行相减就可以知道要调整的次数

public class Main {

    public static void main(String[] args) {
        String str = "GGBBG";
        System.out.println(lineup(str));  //2
    }

    public static int lineup (String peoples) {
        // write code here
        char[] peoplesChars = peoples.toCharArray();
        int boyTotal = 0;
        int girlTotal = 0;
        int boyCount = 0;
        int girlCount = 0;

        for(int i = 0; i < peoplesChars.length; i++){
            if(peoplesChars[i] == 'B'){
                boyCount++;
                boyTotal+=i;
            }
            if(peoplesChars[i] == 'G'){
                girlCount++;
                girlTotal+=i;
            }
        }

        boyTotal = boyTotal -(boyCount-1)*boyCount /2;
        girlTotal = girlTotal -(girlCount-1)*girlCount /2;
        return Math.min(boyTotal, girlTotal);
    }
}

2.删除数组中的重复项(87%)

删除数组中的重复项，只保留最后一次出现的重复元素，使得每个元素只出现一次，返回新数组，并且要保证数组元素的顺序和之前一致

思路：新建一个map，从后向前遍历数组，每次都查看map中是否有该元素，如果没有的话，就加到list里(从头加)，有的话，就不加了
但是没有AC，不知道错哪了

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //int[] array = {};
        //int[] array = {1,1,1,1,1};
        int[] array = {3,5,8,2,3,8};

        System.out.println(Arrays.toString(removeDuplicate(array)));
    }

    public static int[] removeDuplicate (int[] array) {
        if(array.length == 0) return new int[0];
        // write code here
        Map<Integer, Integer> map = new HashMap<>();

        List<Integer> list = new ArrayList<>();
        for(int i = array.length-1; i >= 0; i--){
            if(!map.containsKey(array[i])){
                map.put(array[i], 1);
                list.add(0, array[i]);
            }
        }

        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }

        return res;
    }
}

3.二叉树遍历:数组存储 前序中序后序(AC)

输入一个数组，-1表示空节点，要求输出二叉树的前序中序后序遍历结果

输入：[1,7,2,6,-1,4,8]
输出：[[1,7,6,2,4,8], [6,7,1,4,2,8], [6,7,4,8,2,1]]

import java.util.ArrayList;

public class Main {
    static ArrayList<Integer> pre = new ArrayList<Integer>();
    static ArrayList<Integer> in = new ArrayList<Integer>();
    static ArrayList<Integer> post = new ArrayList<Integer>();

    public static void main(String[] args) {
        int[] input = {1,7,2,6,-1,4,8};
        binaryTreeScan(input);
    }

    public static ArrayList<ArrayList<Integer>> binaryTreeScan (int[] input) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        dfs1(input, 0);
        dfs2(input, 0);
        dfs3(input, 0);
        res.add(pre);
        res.add(in);
        res.add(post);

        //System.out.println(res);
        return res;

    }

    public static void dfs1(int[] input, int index){
        if(index >= input.length || input[index] == -1){
            return ;
        }
        pre.add(input[index]);
        dfs1(input, index*2+1);
        dfs1(input, index*2+2);
    }

    public static void dfs2(int[] input, int index){
        if(index >= input.length || input[index] == -1){
            return ;
        }
        dfs2(input, index*2+1);
        in.add(input[index]);
        dfs2(input, index*2+2);

    }

    public static void dfs3(int[] input, int index){
        if(index >= input.length || input[index] == -1){
            return ;
        }
        dfs3(input, index*2+1);
        dfs3(input, index*2+2);
        post.add(input[index]);
    }
}