笔试记录

2021-08-28

笔试记录

腾讯

// 第一题：往m条链表添加节点，x%m相同的处于同一链表
public ListNode[] solve (int m, ListNode a) {
    // write code here
    ListNode[] ans = new ListNode[m];		// 每条链表维护一个头节点
    ListNode[] tail = new ListNode[m];		// 维护一个尾节点
    while (a != null){
        ListNode node = new ListNode(a.val); // 获取要插入的节点
        if (ans[a.val % m] == null){		 // 如果当前链表没有节点
            ans[a.val % m] = node;			 // 这个节点=头节点=尾节点
            tail[a.val % m] = node;
        }else {
            tail[a.val % m].next = node;	// 若存在节点，插入
            tail[a.val % m] = tail[a.val % m].next;	// 尾节点后移
        }
        a = a.next;
    }
    return ans;
}


//第二题，n个魔法球，每个有不同的能量，使用一个魔法球会把能量加到所有其他魔法球上，求使用完最后能量最多为多少。共T组数据。
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    while (T-- > 0){
        int n = sc.nextInt();		// n个球
        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = sc.nextInt();
        }
        Arrays.sort(list);			// 肯定是先用大的，最后的结果最大
        int ans = 0, cur = 0, mod = 1000000007;
        // 滚动数组
        for (int i = list.length - 1; i >= 0; i--) {
            list[i] += cur;			// 当前值加上之前的累计和
            list[i] %= mod;			// 每一步都要取余
            ans += list[i];			// 答案=总计取余
            ans %= mod;
            cur += list[i];			// 当前的值加入累计和
            cur %= mod;
        }
        System.out.println(ans % mod);
    }
}

//第三题 刻舟求剑，有n个人的体重，每条船的限重w，每条船最多坐两人，如果坐两人体重之和必须是偶数，求做少需要多少条船
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 处理输入
    int n = sc.nextInt();
    int i = 0;
    while (i < n){
        int num = sc.nextInt();
        int weight = sc.nextInt();
        int[] people = new int[num];
        for (int j = 0; j < num; j++) {
            people[j] = sc.nextInt();
        }
        System.out.println(recueBoats(people, weight));
        i++;
    }
}
private static int recueBoats(int[] people, int weight) {
    if (people.length == 0 || weight == 0)
        return 0;
    // 体重之和为偶数，要么同是奇数，要么同是偶数
    List<Integer> odd = new ArrayList<>();
    List<Integer> even = new ArrayList<>();
	// 分两个List存储这些人的体重
    for (int num : people) {
        if (num % 2 == 0)
            odd.add(num);
        else
            even.add(num);
    }
    // 分别排序，然后用双指针
    Collections.sort(odd);
    Collections.sort(even);
    return count(odd, weight) + count(even, weight);
}
private static int count(List<Integer> list, int weight) {
    if (list == null || list.size() == 0) return 0;
    int count = 0;
    int l = 0;
    int r = list.size() - 1;
    while (l <= r){
        // 头+尾小于限重，且为偶数，则两个人可以同船，否则体重大的一个人一条船
        int add = list.get(l) + list.get(r);
        if (add <= weight){
            if (add % 2 == 0)
                l++;
        }
        r--;
        count++;
    }
    return count;
}

// 第四题：从n个字符的字符串中取k个字符，要使它的字典排序尽可能大
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    int n = Integer.parseInt(s.split(" ")[0]);
    int k = Integer.parseInt(s.split(" ")[1]);
    s = sc.nextLine();

    StringBuilder res = new StringBuilder();

    res.append(s.charAt(0));
    // 获取要删除的字符的数量
    int t = n - k;
    // 由于0号位置加入了res，从1号开始遍历
    for (int i = 1; i < n; i++) {
        // 三个条件：
        // 1. 还没达到要删除的字符的数量
        // 2. res中还有字符
        // 3. 当前字符比res中最后一位大
        // 逐步删除最后一位，直到不符合三个条件之一
        while (t != 0 && res.length() > 0
               && s.charAt(i) > res.charAt(res.length() - 1)){
            res.deleteCharAt(res.length() - 1);
            t--;
        }
        res.append(s.charAt(i));
    }
    // 如果没达到删除的字符的数量，从末尾逐个删除
    while (t!=0){
        res.deleteCharAt(res.length() - 1);
        t--;
    }
    System.out.println(res);
}

华为

// 第一题：最大子矩阵和
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 获取输入矩阵
    int n = sc.nextInt();
    int m = sc.nextInt();
    int map[][] = new int[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            map[i][j] = sc.nextInt();
        }
    }

    int ans = subMaxMatrix(map);
    System.out.println(ans);

}

private static int subMaxMatrix(int[][] map) {
    int[][] total = map;
    // total[i]存储从第0行到第i行的当前列的和
    // 从而将二维最大子矩阵和问题转化为以为最大序列问题
    for (int i = 1; i < map.length; i++) {
        for (int j = 0; j < map[0].length; j++) {
            total[i][j] += total[i-1][j];
        }
    }

    int max = Integer.MIN_VALUE;
	// 从第i行到第j行
    for (int i = 0; i < map.length; i++) {
        for (int j = i; j < map.length; j++) {
            // res存储从第i行到第j行的每一列的元素和
            int[] res = new int[map[0].length];
            for (int f = 0; f < map[0].length; f++) {
                if (i == 0)
                    // 从第0行开始，便直接是total
                    res[f] = total[j][f];
                else
                    // 从第i行开始，便是第j行 - 第i行
                    res[f] = total[j][f] - total[i-1][f];
            }
            // 求最大子序列
            int maximal = maxSubsequence(res);

            if (maximal > max) max = maximal;
        }
    }
    return max;
}


private static int maxSubsequence(int[] res) {
    if (res.length == 0) return 0;
    int max = Integer.MIN_VALUE;
    int[] maxSub = new int[res.length];
    maxSub[0] = res[0];

    for (int i = 1; i < res.length; i++) {
        // 当前面的数字和大于0时，加上当前数字才有可能大于当前数字
        maxSub[i] = (maxSub[i-1] > 0 ? (maxSub[i-1] + res[i]) : res[i]);
        if (max < maxSub[i])
            max = maxSub[i];
    }
    return max;
}

// 第二题：英雄从(0,0)移动到(row-1,col-1)，地图每个地方有计时装置，每个点有剩余时间，剩余时间为0则不可通过，求最短时间。
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 处理输入
    int row = sc.nextInt();
    int col = sc.nextInt();
    int[][] map = new int[row][col];
    boolean[][] visit = new boolean[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            map[i][j] = sc.nextInt();
        }
    }
	// 准备bfs移动方向
    int[] dx = new int[]{0,0,1,-1};
    int[] dy = new int[]{1,-1,0,0};

    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node(0,0));
    // 加visit存储遍历过的节点，减少时间
    visit[0][0] = true;
    int step = 0;
	// bfs
    while (!queue.isEmpty()){
        step++;
        for (int i = queue.size(); i > 0; i--) {
            Node node = queue.poll();
            visit[node.x][node.y] = true;
            for (int j = 0; j < 4; j++) {
                int xx = node.x + dx[j];
                int yy = node.y + dy[j];
                if (xx == (row - 1) && yy == (col - 1)){
                    System.out.println(step);
                    return;
                }
                // 个人认为还可以加一个条件，(xx,yy)->(row-1,col-1)的距离
                // 是否大于(row-1,col-1)的剩余时间，大于则不加入队列
                if (xx>=0 && yy>=0 && xx<row && yy<col && map[xx][yy]>step && !visit[xx][yy]){
                    queue.offer(new Node(xx,yy));
                }
            }
        }
    }
    System.out.println(-1);
}

// 第三题：拓扑排序+dp,不会

4399

//第一题，最长公共前缀
public String longestCommonPrefix(String[] strs){
    if (strs == null || strs.length == 0) return "";
    if (strs.length == 1) return strs[0];
    int len = strs[0].length();
    for (String str : strs)
        len = Math.min(len, str.length());	// 获取最小长度
    if (len == 0) return "";
    StringBuffer res = new StringBuffer(len);
    // 逐个字符比较，有字符串该位置字符不同，直接返回
    for(j = 0 ; j < len ; j++){
        for (int t = 0 ; t < strs.length ; t++){
            if (strs[t].charAt(j) != strs[0].charAt(j)){
                return res.toString();
            }
        }
        res.append(strs[0].charAt(j));
    }
    return res.toString();
}

// 第二题，回文链表
public boolean isPalindrome(ListNode head){
    if (head == null || head.next == null) return true;
    // 通过快慢指针找到链表的中点
    ListNode fast = head.next.next;
    ListNode slow = head.next;
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    // 反转链表的前半部分
    ListNode pre = null;
    ListNode next = null;
    while (head != slow){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    // 如果是奇数个节点，去掉后半部分的第一个节点
    if (fast != null){
        slow = slow.next;
    }
    // 判断是否回文
    while (pre != null){
        if (pre.val != slow.val) return false;
        pre = pre.next;
        slow =slow.next;
    }
    return true;
}

// 第三题不记得了，只记得sb编译器

海康威视

// 一个数等于它所有因子的和就是“完数”，判断一个数是否是完数
// 太简单了，懒得写

// 动态地更换排序算法，只实现快排和冒泡
interface ArraysSort {
    public abstract int[] sort(int [] arr);
}

class Bubble implements ArraysSort{
    public int[] sort(int[] arr) {
        int j,temp;
        boolean flag = false;
        for (int i = 0; i <arr.length-1; i++) {
            for (j = 0; j <arr.length-1-i ; j++) {
                if(arr[j]>arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }
        }
        return arr;
    }
}

class quickSort implements ArraysSort{
    public int[] sort(int[] arr) {
        quick(arr,0,arr.length-1);
        return arr;
    }

    private void quick(int[] nums, int left, int right) {
        if(left<right) {
            int mid=partition(nums,left,right);
            //进行分割
            partition(nums,left,mid-1);
            partition(nums,mid+1,right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        // TODO Auto-generated method stub
        int x=nums[left];
        int l=left;
        int r=right;
        while(l<r) {
            // 向左找到第一个小于等于x的元素位置
            while(l<r && nums[r]>=x) r--;
            // 向右找到第一个大于等于x的元素位置
            while(l<r && nums[l]<=x) l++;
            if(l<r) {
                int tmp=nums[l];
                nums[l]=nums[r];
                nums[r]=tmp;
            }

        }
        nums[left]=nums[l];
        // 使中轴左右两边处于有序序列
        nums[l]=x;
        return l;
    }
}


class Com {
    private ArraysSort arraysSort;
    private int [] arr;

    public Com(ArraysSort arraysSort) {
        this.arraysSort = arraysSort;
    }

    public Com() {
    }

    public Com(int[] arr) {
        this.arr = arr;
    }

    public int[] getArr() {
        return arr;
    }

    public void setArr(int[] arr) {
        this.arr = arr;
    }

    public ArraysSort getArraysSort() {
        return arraysSort;
    }

    public void setArraysSort(ArraysSort arraysSort) {
        this.arraysSort = arraysSort;
    }

    public void sorts(int [] arr){
        arraysSort.sort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}



public class Main {

    public static void main(String[] args) {
        int [] arr = {3,9,4,3,96,15,72,68,16,0};
        Com com = new Com(arr);
        ArraysSort bubble = new Bubble();
        ArraysSort quickSort = new quickSort();

        com.setArraysSort(bubble);
        System.out.println("冒泡排序");
        com.sorts(arr);

        com.setArraysSort(quickSort);
        System.out.println("\n快速排序");
        com.sorts(arr);
    }

}

斗鱼

1 2	// 第一题：简单，双重for循环 // 第二题：最长公共子序列，并打印

小红书

// 第一题  最大子矩阵和
public class 最大子矩阵和 {
    static int[][] map;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        int ans = subMatrixSum();
        System.out.println(ans);

    }

    private static int subMatrixSum() {
        int[][] total = map;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                total[i][j] = total[i-1][j] + map[i][j];
            }
        }
        int mx = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int[] res = new int[n];
                for (int k = 0; k < n; k++) {
                    if (i == 0){
                        res[k] = total[j][k];
                    } else {
                        res[k] = total[j][k] - total[i-1][k];
                    }
                }
                int max = subSequenceSum(res);
                if (max > mx) mx = max;
            }
        }
        return mx;
    }

    private static int subSequenceSum(int[] res) {
        if (res.length == 0) return 0;
        int[] maxSub = new int[res.length];
        maxSub[0] = res[0];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            maxSub[i] = Math.max(maxSub[i-1], maxSub[i-1] + res[i]);
            if (max < maxSub[i]) max = maxSub[i];
        }
        return max;
    }
}

// 第二题，段式回文串
public class 段式回文 {
    public static void main(String[] args) {
        int n = longestDecomposition("abcbabc");
        System.out.println(n);
    }

    private static int longestDecomposition(String text) {
        return divide(text, 0);
    }

    private static int divide(String text, int n) {
        int m = text.length();              // 字符串长度
        if (text.equals("")) return n;      // 字符串空了，返回当前长度
        for (int i = 0; i < m/2; i++) {     // i=0-字符串长度的一半，查看能否回文
            if (text.substring(0, i +1).equals(text.substring(m - i - 1, m))){
                return divide(text.substring(i+1, m-i-1), n+2);
            }
        }
        return n+1;                         // 如果中间还剩一段   + 1
    }
}

// 第三题，全源最短路径
// 只想到弗洛伊德 9%

美团

// ab串
// ab组成的串，即不包含aba，也不包含bab
// dfs方法模拟， 后发现答案为斐波那契数列
public class t1 {
    static int res = 0;
    static char[] path;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        path = new char[n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                path[0] = (char) ('a' + i);
                path[1] = (char) ('a' + j);
                dfs(n, 2);
            }
        }
        int ans = res % 998244353;
        System.out.println(ans);
    }

    private static void dfs(int n, int k) {
        if (n == k) {
            res++;
            return;
        }
        if (path[k-2] == 'a' && path[k-1] == 'b'){
            path[k] = 'b';
            dfs(n, k+1);
        } else if (path[k-2] == 'b' && path[k-1] == 'a'){
            path[k] = 'a';
            dfs(n, k+1);
        } else if (path[k-2] == 'a' && path[k-1] == 'a'){
            for (int i = 0; i < 2; i++) {
                path[k] = (char) ('a' + i);
                dfs(n, k+1);
            }
        } else {
            for (int i = 0; i < 2; i++) {
                path[k] = (char) ('a' + i);
                dfs(n, k+1);
            }
        }
    }
}

// 坐公交，先把输入条件(稍微有点麻烦，不写了)转换为坐公交(leetcode)，然后BFS
public class 公交路线 {
    public static void main(String[] args) {
        System.out.println(numBusesToDestination(new int[][]{{1,2,7},{3,6,7}}, 1 ,6));
    }

    public static int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        int n = routes.length;
        boolean edge[][] = new boolean[n][n];                   // 记录节点之间的边
        Map<Integer, List<Integer>> map = new HashMap<>();      // 记录当前节点能到哪些节点
        for (int i = 0; i < n; i++) {                           // 节点1-n
            for (int site : routes[i]) {                        // 对于当球节点能到的所有节点
                List<Integer> list = map.getOrDefault(site, new ArrayList<>());
                for (int j : list) {
                    edge[i][j] = edge[j][i] = true;
                }
                list.add(i);                                    // 修改list
                map.put(site, list);                            // 将修改后的list放入map
            }
        }

        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        Queue<Integer> queue = new LinkedList<>();
        for (int bus : map.getOrDefault(source, new ArrayList<>())) {   // 第一步能到的节点
            dis[bus] = 1;
            queue.offer(bus);
        }

        while (!queue.isEmpty()){
            int x = queue.poll();
            for (int i = 0; i < n; i++) {
                if (edge[x][i] && dis[i] == -1){
                    dis[i] = dis[x] + 1;                        // 第x+1步能到的节点
                    queue.offer(i);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int bus : map.getOrDefault(target, new ArrayList<>())) {
            if (dis[bus] != -1)
                res = Math.min(res, dis[bus]);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

//不许ac，一个只包含a和c的字符串，移动最少次数使得不包含ac    不会

//一个无向图，里面能组成多少四边形，dfs答案不对