腾讯0424开发岗笔试题代码

第一题

给n个数字字符串,每个字符串长度为m,然后从上到下对齐,从上到下构建数字,排序输出。
思路:暴力
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Q1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        String strs[] = new String[n];
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            strs[i] = sc.nextLine();
        }

        int m = strs[0].length();
        List<Integer> nums = new ArrayList();
        for (int i = 0; i < m; i++) {
            int num = 0;
            for (int j = 0; j < n; j++) {
                num = num * 10 + (strs[j].charAt(i)-'0');
            }
            nums.add(num);
        }
        nums.sort((o1,o2)->{return o1-o2;});
        for (int i = 0; i < nums.size(); i++) {
            System.out.print(nums.get(i)+" ");
        }

    }
}

第二题

给一个数组,下标从1-n,每次淘汰下标非质数的数字,然后重新组成数组,问最后剩下的数字为何数?
思路:暴力
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
       // int a[] = new int[]{1,2,3,4};
        int a[] = new int[]{3,1,1,4,5,6};
        Main main = new Main();
        System.out.println(main.getNumber(a));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * @param a int整型一维数组
     * @return int整型
     */
    public int getNumber (int[] a) {
        // write code here
        int n = a.length;
        List<Integer> pnums = getZ(n);
        while (n!=1){
            int k = 0;
            for (int i = 0; i < pnums.size() && pnums.get(i)<n; i++) {
                a[k++] = a[pnums.get(i)];
            }
            n = k;
        }
        return a[0];
    }

    public List<Integer> getZ(int n){
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if(isP(i)){
                list.add(i-1);
            }
        }
      /*  System.out.print("{");
        for (int i = 0; i < list.size()-1; i++) {
            System.out.print(list.get(i)+",");
        }
        System.out.println(list.get(list.size()-1)+"}");*/
        return list;
    }

    public boolean isP(int x){
        for(int i = 2;i < (int)(Math.sqrt(x)+1);i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}


第三题

给一堆字符串代表一排士兵,士兵编号1~n,字符串中‘0’的士兵代表进攻性的,‘1’的代表防御性的,每个士兵的攻击力或守备力为其下标值。将士兵分组,0~pos的是进攻组,只算攻击力,pos+1~n的是防御组,只算防御力。pos可以取0~n。求攻击组的攻击力和防御组的防御力的差的绝对值的最小值。
思路:使用前缀和记录攻击力和防御力,并逐一求差值的绝对值的最小值。
import java.util.Scanner;

public class Q3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String str = sc.nextLine();
        long attack[] = new long[n + 1];
        long defend[] = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            attack[i] = attack[i - 1];
            defend[i] = defend[i - 1];
            //只会进攻
            if (str.charAt(i - 1) == '0') {
                attack[i] += i;
            } else {
                //只会防守
                defend[i] += i;
            }
         //   System.out.println(i + "\t前缀和进攻值:" + attack[i]);
         //   System.out.println(i + "\t前缀和防御值:" + attack[i]);
        }
        //1-pos是进攻的 为1的 pos+1到n是防守
        //考虑全进攻和全防守的形式
        long ans = Math.min(attack[n], defend[n]);
   //     System.out.println("全进攻:" + attack[n]);
     //   System.out.println("全防守:" + defend[n]);
        for (int i = 1; i < n; i++) {
          //  System.out.println("坐标:\t" + i);
          //  System.out.println("\t\t进攻值:" + attack[i] + "\t防御值:" +(defend[n]-defend[i]));
          //  System.out.println("\t\t绝对值:" + Math.abs(attack[i] - (defend[n]-defend[i])));
            ans = Math.min(ans,  Math.abs(attack[i] - (defend[n]-defend[i])));
        }
        System.out.println(ans);
    }
}

第四题

给一个链表数组,数组中的每个链表是一个循环链表中的破碎的部分,且每个链表结点的值唯一且为数值类型,求将这个循环链表复原以后,从链表中任意一个结点正序或逆序遍历 字典序 最小的那个链表,并返回。
思路:链表中结点的值唯一,使用字典记录结点的前驱和后继,并记录最小值,然后从最小值开始遍历,并判断最小值的前驱和后继哪个更小,从更小的开始顺序遍历。
import java.util.*;


class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * @param a ListNode类一维数组 指向每段碎片的开头
     * @return ListNode类
     */
    public ListNode solve(ListNode[] a) {
        // write code here
        HashMap<Integer, ListNode> nodeMap = new HashMap<>();
        HashMap<Integer, Integer> preMap = new HashMap<>();
        HashMap<Integer, Integer> nextMap = new HashMap<>();
        HashMap<Integer, Boolean> visitedMap = new HashMap<>();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            printList(a[i]);
            for (ListNode p = a[i]; p != null; p = p.next) {
                nodeMap.put(p.val, p);
                if (p.next != null) {
                    preMap.put(p.next.val, p.val);
                    nextMap.put(p.val, p.next.val);
                }
                min = Math.min(min, p.val);
            }
        }
        ListNode head = new ListNode(0);
        head.next = null;
        ListNode rear = head;
        rear.next = nodeMap.get(min);
        rear = rear.next;
        rear.next = null;
        visitedMap.put(min, true);
        if (preMap.get(min) < nextMap.get(min)) {
            //前驱小 从前驱走
            while (!visitedMap.getOrDefault(preMap.get(min), false)) {
                min = preMap.get(min);
                rear.next = nodeMap.get(min);
                rear = rear.next;
                rear.next = null;
                visitedMap.put(min, true);
            }

        } else {
            //后继小 从后继走
            //前驱小 从前驱走
            while (!visitedMap.getOrDefault(nextMap.get(min), false)) {
                min = nextMap.get(min);
                rear.next = nodeMap.get(min);
                rear = rear.next;
                rear.next = null;
                visitedMap.put(min, true);
            }
        }
        printList(head);
        return head.next;
    }

    public void printList(ListNode head) {
        System.out.print("链表->{");
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val+" ");
        }
        System.out.println("}");
    }
}

第五题

股票问题,一开始有初始资金m,和一个长度为n的股票价格数组,每天可以进行买入股票或者卖出股票其中的一种操作,或不操作。可以同时持有多个股票,问最后一天的最大总资产是多少?(最大总资产为持有现金+持有的股票价格)
思路:动态规划,设dp[i][j]为第i天持有j个股票能拥有的最大现金额度,dp[i][j]  = Math.min(dp[i-1][j] , dp[i][j+1] +prices[i] , dp[i][j-1]-prices[i])
import java.util.Arrays;
import java.util.Scanner;

public class Q5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int prices[] = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = sc.nextInt();
        }
        long dp[][] = new long[n][n];//dp[i][j] 表示在第i天拥有j注股票的最大资产 ,n天最多n-1支股票
        Arrays.fill(dp[0], -1);
        dp[0][0] = m;//第0天 0注股票拥有m元
        if (m >= prices[0]) {
            dp[0][1] = m - prices[0];
        }
        for (int i = 1; i < n; i++) {
            //两种情况
            //一是买入一注
            //一是卖出一注
            //一个是啥也不干
            for (int j = 0; j < n; j++) {
                //啥也不干
                dp[i][j] = dp[i - 1][j];
                //买入一注 并且金额足够
                if (j > 0) {
                    if (dp[i - 1][j - 1] != -1 && dp[i - 1][j - 1] >= prices[i]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] - prices[i]);
                    }
                }
                //卖出一注
                if (j < n - 1) {
                    if (dp[i - 1][j + 1] != -1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + prices[i]);
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (dp[n - 1][i] == -1) continue;
            ans = Math.max(ans, dp[n - 1][i] + i * prices[n - 1]);
        }
       // print(dp);
        System.out.println(ans);
    }

    public static void print(int dp[][]) {
        int n = dp.length;
        System.out.print("\t\t");
        for (int i = 0; i < n; i++) {
            System.out.print("d" + i + "\t");
        }
        System.out.println();
        for (int i = 0; i < n; i++) {
            System.out.print(i + "注股票\t");
            for (int j = 0; j < n; j++) {
                System.out.print(dp[j][i] + "\t");
            }
            System.out.println();
        }
    }
}


#腾讯笔试##笔经##腾讯#
全部评论
https://tans.fun/archives/tecent-2022-exam C++写了一篇题解,欢迎评论😀
3
送花
回复 分享
发布于 2022-04-24 22:25
不明白了,第一题我也是这样写的循环,也是str[j].charAt(i) ,一直说我这里数组越界,本地IDE都没问题
3
送花
回复 分享
发布于 2022-04-24 22:31
OPPO
校招火热招聘中
官网直投
我直接反手就是一个关注!😘
2
送花
回复 分享
发布于 2022-04-24 22:32
第五题dp了半天没想出来,后来写了个dfs暴力居然能过60%
2
送花
回复 分享
发布于 2022-04-24 22:40
感谢大佬的题解
1
送花
回复 分享
发布于 2022-04-24 22:22
兄弟,我最后一题跟你一样的思路,该用long也用了,为啥只能95%啊
1
送花
回复 分享
发布于 2022-04-24 23:07
第四题原来存前后节点,我傻了,存的第一个节点,结果有问题,还想了半天😰
1
送花
回复 分享
发布于 2022-04-25 00:09
喜欢你的代码风格,学习了
1
送花
回复 分享
发布于 2022-04-27 09:29
牛逼哇
点赞
送花
回复 分享
发布于 2022-04-24 22:24
太强了
点赞
送花
回复 分享
发布于 2022-04-24 22:25
第三题只过了70%,是因为少排除了什么特殊情况吗,我思路是一样的
点赞
送花
回复 分享
发布于 2022-04-24 22:26
大佬、请问笔试还要自己写scanner吗
点赞
送花
回复 分享
发布于 2022-04-24 22:38
点赞
送花
回复 分享
发布于 2022-04-25 14:48
老哥有空帮我看看我第一题的写法哪有问题吗,输出一直是0,自己测没啥问题。
点赞
送花
回复 分享
发布于 2022-04-25 14:53
楼主,为啥n天最多只能是n - 1支股票啊?最多不是n支股票吗
点赞
送花
回复 分享
发布于 2022-04-26 17:08
第五题的dp为什么打印不出来 只有ans能打印出来
点赞
送花
回复 分享
发布于 2022-04-26 22:35
楼主太强了!但是第五题那个大于100万的条件不用考虑吗?
点赞
送花
回复 分享
发布于 2022-04-27 09:42

相关推荐

24 105 评论
分享
牛客网
牛客企业服务