腾讯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();
}
}
}
投递华为等公司10个岗位