腾讯笔试记录
1题 重排链表。通过90%，超时了
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param m int整型
* @param a ListNode类 指向彩带的起点，val表示当前节点的val，next指向下一个节点
* @return ListNode类一维数组
*/
public ListNode[] solve (int m, ListNode a) {
ListNode[] ret = new ListNode[m];
ListNode[] ps = new ListNode[m];
ListNode p = a;
while (p != null) {
int idx = p.val % m;
if (ret[idx] == null) {
ret[idx] = ps[idx] = p;
} else {
ps[idx].next = p;
ps[idx] = ps[idx].next;
}
p = p.next;
}
for (int i = 0; i < m; ++i) {
if (ps[i] != null) {
ps[i].next = null;
}
}
return ret;
}
}
2 题 获取最大能量值
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int MOD = (int)1e9 + 7;
int T = sc.nextInt();
StringBuilder cache = new StringBuilder();
while(T-- > 0) {
int n = sc.nextInt();
long[] arr = new long[n];
for (int i = 0; i < n; ++i) {
arr[i] = sc.nextInt();
}
long sum = 0;
long delta = 0;
Arrays.sort(arr);
for (int i = n - 1; i >= 0; --i) {
sum = (sum + arr[i] + delta) % MOD;
delta = (delta + delta + arr[i]) % MOD;
}
cache.append(sum).append("
");
}
System.out.print(cache);
}
}
3 题 最少船只数。奇偶体重分开算import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
StringBuilder cache = new StringBuilder();
while(T-- > 0) {
int n = sc.nextInt();
int w = sc.nextInt();
List<Integer> oddList = new ArrayList<>();
List<Integer> evenList = new ArrayList<>();
for (int i = 0; i < n; ++i) {
int wi = sc.nextInt();
if ((wi & 1) == 1) {
oddList.add(wi);
} else {
evenList.add(wi);
}
}
oddList.sort(null);
evenList.sort(null);
int sum = getCount(oddList, w);
sum += getCount(evenList, w);
cache.append(sum).append("
");
}
System.out.print(cache);
}
private static int getCount(List<Integer> list, int w) {
int count = 0;
int i = 0, j = list.size() - 1;
while(i < j) {
if (list.get(i) + list.get(j) <= w) {
++i;
}
--j;
count++;
}
if (i == j) {
count++;
}
return count;
}
}
4 题 长度为n的字符串，选取k个，约束是选取结果的字典序最大。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
String s = sc.next();
StringBuilder buf = new StringBuilder();
int st = 0;
while(k > 0) {
st = getFirst(s, st, n, k, buf);
k--;
}
System.out.println(buf);
}
private static int getFirst(String s, int st, int n, int k, StringBuilder buf) {
int idx = n - k;
char first = s.charAt(idx);
for (int i = idx -1; i >= st; --i) {
if (s.charAt(i) >= first) {
first = s.charAt(i);
idx = i;
}
}
buf.append(s.charAt(idx));
return idx + 1;
}
}
5 最小变换数的和。暴力骗分，过55%import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = sc.nextInt();
}
long minSum = Long.MAX_VALUE;
for (int i = 0; i < n; ++i) {
minSum = Math.min(minSum, work(arr, i));
}
System.out.println(minSum);
}
private static int work(int[] arr, int st) {
int i = st - 1, j = st + 1;
int sum = 0;
long magic = arr[st];
while(i >= 0 || j <= arr.length -1) {
while(i >= 0 && arr[i] == magic) --i;
while(j < arr.length && arr[j] == magic) ++j;
if (i < 0 && j == arr.length) break;
long newMagic = 0;
if (i < 0) {
newMagic = arr[j];
} else if (j == arr.length) {
newMagic = arr[i];
} else {
if (Math.abs(arr[i] - magic) <= Math.abs(arr[j] - magic)) {
newMagic = arr[i];
} else {
newMagic = arr[j];
}
}
sum += Math.abs(newMagic - magic);
magic = newMagic;
}
return sum;
}
}
