9.6 腾讯后台开发笔试
第一题 数组公共子序列，，数组下标异步挪动就行
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len1 = sc.nextInt();
int[] nums1 = new int[len1];
for(int i = 0; i < len1; ++i) {
nums1[i] = sc.nextInt();
}
int len2 = sc.nextInt();
int[] nums2 = new int[len2];
for(int i = 0; i < len2; ++i) {
nums2[i] = sc.nextInt();
}
sc.close();
int[] ans = solution(nums1, nums2);
if(ans.length >= 1) {
for(int i = 0; i < ans.length - 1; ++i) {
System.out.print(ans[i] + " ");
}
System.out.print(ans[ans.length - 1]);
}
}
static int[] solution(int[] arr1, int[] arr2) {
if(arr1.length == 0 || arr2.length == 0) {
return new int[0];
}
int index1 = 0, index2 = 0, len1 = arr1.length, len2 = arr2.length;
ArrayList<Integer> temp = new ArrayList<>();
while(index1 < len1 && index2 < len2) {
if(arr1[index1] == arr2[index2]) {
temp.add(arr1[index1]);
++index1;
++index2;
}
else if(arr1[index1] > arr2[index2]) {
++index1;
}
else {
++index2;
}
}
int[] ans = new int[temp.size()];
for(int i = 0; i < temp.size(); ++i) {
ans[i] = temp.get(i);
}
return ans;
}
} 第二题 字符串次数前k个，后k个，哈希表排序 public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
HashMap<String, Integer> map = new HashMap<>();
String temp;
for(int i = 0; i < N; ++i) {
temp = sc.next();
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
list.sort((o1, o2) -> !o1.getValue().equals(o2.getValue()) ? o2.getValue() - o1.getValue() :
o1.getKey().compareTo(o2.getKey()));
for(int i = 0; i < K; ++i) {
System.out.println(list.get(i).getKey() + " " + list.get(i).getValue());
}
list = new ArrayList<>(map.entrySet());
list.sort((o1, o2) -> !o1.getValue().equals(o2.getValue()) ? o1.getValue() - o2.getValue() :
o1.getKey().compareTo(o2.getKey()));
for(int i = 0; i < K; ++i) {
System.out.println(list.get(i).getKey() + " " + list.get(i).getValue());
}
}
} 第三题。第四题顺序记不住了， 寻找中位数，还是哈希表排序，记住中位数以及中位数前一个数的下标就行
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] nums = new int[N];
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < N; ++i) {
nums[i] = sc.nextInt();
map.put(i, nums[i]);
}
sc.close();
ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
list.sort(Comparator.comparingInt(Map.Entry::getValue));
int mid = list.get(N / 2).getKey();
int subMid = list.get(N / 2 - 1).getKey();
if(nums[mid] == nums[subMid]) {
for(int i = 0; i < N; ++i) {
System.out.println(nums[mid]);
}
}
else {
for(int i = 0; i < N; ++i) {
if(nums[i] >= nums[mid]) {
System.out.println(nums[subMid]);
}
else {
System.out.println(nums[mid]);
}
}
}
}
} 通知人数，典型的图的遍历，我采用的是BFS，将第一个包含0的团队加进双端队列queue，设置visited集合标记以通知过的编号，对应queue中的每一个元素循环遍历其他团队中的编号，public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
ArrayList<HashSet<Integer>> list = new ArrayList<>();
HashSet<Integer> temp;
int flag = -1, num, len;
for(int i = 0; i < M; ++i) {
len = sc.nextInt();
temp = new HashSet<>();
for(int j = 0; j < len; ++j) {
num = sc.nextInt();
if(num == 0 && flag == -1) {
flag = i;
}
temp.add(num);
}
list.add(temp);
}
sc.close();
if(flag == -1) {
System.out.println(0);
}
else {
LinkedList<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
temp = list.remove(flag);
for(Integer integer : temp) {
queue.addLast(integer);
visited.add(integer);
}
int size;
while(!queue.isEmpty()) {
size = queue.size();
for(int i = 0; i < size; ++i) {
num = queue.removeFirst();
for(HashSet<Integer> set : list) {
if(set.contains(num)) {
for(Integer integer : set) {
if(!visited.contains(integer)) {
queue.addLast(integer);
visited.add(integer);
}
}
}
}
}
}
System.out.println(visited.size());
}
}
} 
我c++ 还手写了 struct NodeList * oj 怎么知道我用的 list 还是 vector
汤臣倍健公司氛围 434人发布