腾讯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();
        }
    }
}

#腾讯笔试##笔经##腾讯#