腾讯4.24笔试 后台开发a4.75
# 1
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String[] strings = new String[n];
for (int i = 0; i < n; i++) {
strings[i] = in.nextLine();
}
List<Integer> list = fun(strings);
Collections.sort(list);
for (Integer integer : list) {
System.out.print(integer + " ");
}
}
private static List<Integer> fun(String[] strings) {
int n = strings.length;
int m = strings[0].length();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
StringBuilder builder = new StringBuilder();
for (String string : strings) {
builder.append(string.charAt(i));
}
list.add(Integer.parseInt(builder.toString()));
}
return list;
}
}
# 2
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a int整型一维数组
* @return int整型
*/
public int getNumber(int[] a) {
boolean[] isNotPrime = isNotPrimes(a.length + 1);
// System.out.println(Arrays.toString(isPrime));
LinkedList<Integer> list = new LinkedList<Integer>();
for (int num : a) {
list.add(num);
}
while (list.size() > 1) {
int index = 1;
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
int num = iterator.next();
if (isNotPrime[index]) {
// System.out.println(index);
iterator.remove();
}
index++;
}
// System.out.println(list);
}
return list.get(0);
}
private boolean[] isNotPrimes(int n) {
boolean[] isPrime = new boolean[n];
isPrime[1] = true;
for (int i = 2; i < n; i++) {
for (int j = 2; i * j < n; j ++) {
isPrime[i * j] = true;
}
}
return isPrime;
}
public static void main(String[] args) {
System.out.println(new Solution().getNumber(new int[]{3,1,1,4,5,6}));
}
}
# 3
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;
public class Main {
public static void main(String[] args) {
// System.out.println(Integer.MAX_VALUE / 1_000_000_000_0);
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String str = in.nextLine();
boolean[] canAttack = new boolean[n];
for (int i = 0; i < canAttack.length; i++) {
canAttack[i] = str.charAt(i) == '0';
}
long res = fun(canAttack);
System.out.println(res);
}
private static long fun(boolean[] canAttack) {
int n = canAttack.length;
// [1, i]的攻击值的和
long[] attack = new long[n + 1];
for (int i = 0; i < n; i++) {
attack[i + 1] = attack[i] + (canAttack[i] ? (i + 1) : 0);
}
// [i + 1 ,n]的防御值的和
long[] defend = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
defend[i] = defend[i + 1] + (!canAttack[i] ? (i + 1) : 0);
}
long res = Long.MAX_VALUE;
for (int i = 0; i <= n; i++) {
// [1,i], [i + 1,n]
long a = attack[i];
long d = defend[i];
res = Math.min(res, Math.abs(a - d));
}
return res;
}
}
# 4
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
Map<ListNode, ListNode> map = new HashMap<>();
Map<Integer, ListNode> int2NodeMap = new HashMap<>();
for (ListNode node : a) {
ListNode pre = int2NodeMap.computeIfAbsent(node.val, v -> new ListNode(v));
node = node.next;
while (node != null) {
ListNode mNode = int2NodeMap.computeIfAbsent(node.val, v -> new ListNode(v));
map.put(pre, mNode);
pre = mNode;
node = node.next;
}
}
for (Map.Entry<ListNode, ListNode> entry : map.entrySet()) {
entry.getKey().next = entry.getValue();
}
ListNode head = int2NodeMap.get(a[0].val);
ListNode minNode = head;
ListNode p = head.next;
while (p != head) {
if (p.val < minNode.val) {
minNode = p;
}
p = p.next;
}
// 找到minNode最后的节点
ListNode node = minNode;
while (node.next != minNode) {
node = node.next;
}
int preVal = node.val;
ListNode next = minNode.next;
if (next.val < preVal) {
node.next = null;
return minNode;
}else {
// 反转链表
minNode.next = null;
reverse(next);
return minNode;
}
}
private void reverse(ListNode head) {
ListNode pre = null;
while (head != null) {
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
}
}
# 5
过了0.75
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;
public class Main {
private static HashMap[][] maps;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
long res = fun(nums, m);
System.out.println(res);
}
private static long fun(int[] nums, int m) {
int n = nums.length;
maps = new HashMap[n + 1][n + 1];
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[i].length; j++) {
maps[i][j] = new HashMap();
}
}
return fun(nums, m, 0, 0);
}
private static long fun(int[] nums, int m, int index, int count) {
if (index == nums.length - 1) {
return m + (long) count * nums[index];
}
HashMap hashMap = maps[index][count];
Long value = (Long) hashMap.get(m);
if (value != null) {
return value;
}
// 不操作
long res = fun(nums, m, index + 1, count);
// 买入
if (m >= nums[index]) {
res = Math.max(res, fun(nums, m - nums[index], index + 1, count + 1));
}
// 卖出
if (count > 0) {
res = Math.max(res, fun(nums, m + nums[index], index + 1, count - 1));
}
hashMap.put(m, res);
return res;
}
}