小红书9.4后端AK代码
最近难得的一次AK，记录一下。
1、镜像复制
问题描述：给定n，m，k（n>=1,m>=1,k<=1e18）
根据n得到[1, 2, 3, …, n]，进行m次镜像复制
每次镜像复制，例如：[1, 2, 3]->[1,2,3,3,2,1]
求m次镜像复制后第k个数
解题思路：找规律，最少镜像复制一次，从第2次开始，数组每2n个元素一次循环，即[1, 2, 3, 3, 2, 1][1, 2, 3, 3, 2, 1]。
代码：
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long k = sc.nextLong();
int[] arr = new int[2 * n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
arr[2 * n - i - 1] = arr[i];
}
System.out.println(arr[(int)((k - 1) % (2 * n))]);
}
} 2、n个数，乘积为7 问题描述：给定n个数，每个数每次操作可以+1，或-1。求最少的操作次数使得这n个数乘积为7.
解题思路：7是质数，所以最终数组会出现一个7或-7，其他均为1或-1.
首先可以把问题划分为两个问题：
1、记录每个数，正数转化为1，负数转化为-1，所需要操作数，累加的a。
2、记录每个数，正数转化为7，负数转化为-7，比1或-1少的次数，取最大值b。
3、结果=a-b。
4、特殊情况考虑，数组存在0，则不考虑负数个数的奇偶性（0变为-1和1次数相同）。
5、数组不存在0，负数为偶数也不考虑，负数为正数需要将其中一个从-1变为1，即多进行2次操作，结果为res+2.
代码：
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int under = 0;
int zero = 0;
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
if(arr[i] < 0) {
under++;
}else if(arr[i] == 0){
zero++;
}
}
long res = 0;
int[] nums = new int[n];
int minV = Integer.MAX_VALUE;
for(int i = 0; i < n; i++) {
nums[i] = Math.min(Math.abs(arr[i] - 1), Math.abs(arr[i] + 1));
int temp = Math.min(Math.abs(arr[i] - 7), Math.abs(arr[i] + 7));
minV = Math.min(minV, temp - nums[i]);
}
for(int i = 0; i < n; i++) {
res += nums[i];
}
res += minV;
if(zero == 0 && under % 2 == 1) {
System.out.println(res + 2);
}else {
System.out.println(res);
}
}
} 3、旅游，一个国家由1，2，…，n这些城市，从1出发，目的地为n。边的长度为1，花费为cost。现有一张特权卡M，花费小于M的边可以通过。求深度不超过k的情况下，M的最小值。 解题思路：深度优先搜索，城市数据量很大，使用邻接表存储。
class Node {
int id;
Map<Integer, Integer> next;
public Node(int id) {
this.id = id;
next = new HashMap<>();
}
}
public class Main {
private static Map<Integer, Node> nodes;
private static int k;
private static int n;
private static int minVal = Integer.MAX_VALUE;
private static Set<Integer> visited = new HashSet<>();
public static void dfs(Node loc, int maxCost, int depth) {
if(depth > k) {
return ;
}
if(loc.id == n) {
minVal = Math.min(minVal, maxCost);
}
for(Map.Entry<Integer, Integer> entry: loc.next.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
if(!visited.contains(key)) {
visited.add(key);
dfs(nodes.get(key), Math.max(maxCost, value), depth + 1);
visited.remove(key);
}
}
}
public static void main(String[] args) {
nodes = new HashMap<>();
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int m = sc.nextInt();
k = sc.nextInt();
int[][] edges = new int[m][3];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < m; j++) {
edges[j][i] = sc.nextInt();
}
}
for(int i = 1; i <= n; i++) {
nodes.put(i, new Node(i));
}
for(int i = 0; i < m; i++) {
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
nodes.get(u).next.put(v, w);
nodes.get(v).next.put(u, w);
}
if(n == 1) {
System.out.println(0);
}else {
dfs(nodes.get(1), Integer.MIN_VALUE, 0);
System.out.println(minVal);
}
}
}
类似资料：