小米10.12笔试编程题
1：给你一个长度为n的数组，你可以对0~(n-1)内任意位置 i 进行取相反数操作，但arr[i]取反后，arr[i+1]也会跟着取反。你可以进行任意次这样的操作。请返回反转后arr数组之和的最大值。
思路
一道dp题（本人菜鸡只会用记忆化搜索）
定义dp【i】【0】为i位置 未被上一个数取反时 i~(n-1)任意选择反转。
定义dp【i】【1】为i位置 被上一个数取反时 i~(n-1)任意选择反转。
dp【i】【0】= max ( dp【i+1】【0】+arr[i] , dp【i+1】【1】-arr[i] );
dp【i】【1】= max ( dp【i+1】【0】-arr[i] , dp【i+1】【1】+arr[i] );
那么结果为dp【0】【0】
上代码：
import java.util.Scanner;
public class Main {
static int maxn = 30000 + 10;
static long maxi = (int) (1e9 + 10);
static long[] arr = new long[maxn];
// 定义动态规划 dp 数组，dp[i][0] 表示第 i 个元素不取反的最大和，dp[i][1] 表示第 i 个元素取反的最大和
static Long[][] dp = new Long[maxn][2];
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++) {
arr[i] = sc.nextLong();
}
System.out.println(dfs(0, 0));
}
// 定义 dfs 函数，cur 表示当前遍历到的数组下标，not 表示当前元素是否取反（0 表示不取反，1 表示取反）
public static long dfs(int cur, int not) {
// 如果 dp[cur][not] 已经计算过，直接返回结果
if (dp[cur][not] != null) {
return dp[cur][not];
}
// 根据 not 值决定当前元素是否取反
long currValue = not == 0 ? arr[cur] : -arr[cur];
// 如果当前是最后一个元素，则返回其值（处理边界情况）
if (cur == n - 1) return currValue;
// 递归计算当前元素不取反的情况下，后续元素的最大和
long noNot = dfs(cur + 1, 0) + currValue;
// 递归计算当前元素取反的情况下，后续元素的最大和
long isNot = dfs(cur + 1, 1) - currValue;
// 取不取反两种情况中的较大值作为 dp[cur][not] 的值
dp[cur][not] = Math.max(noNot, isNot);
return dp[cur][not];
}
}
附带一句：笔者笔试的时候第一眼以为是翻硬币 模板，以为自己模板记错了，疯狂想怎么递推。笔试完突然想到应该dp的😭😭😭。
再加一道网友的思路：如果负数个数为偶数，那么最终可以把全部反转成正数，如果是奇数，最后则只会剩下一个负数。并且这个负数可以是任意一个位置。那么最终结果为：负数个数==偶数？ sum( arr) : sum( arr ) - 2*绝对值最小的数。
public static long ans(int n, long[] arr) {
int cnt = 0, min = Integer.MAX_VALUE;
long sum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) cnt++;
long abs = Math.abs(arr[i]);
min = (int) Math.min(min, abs);
sum += abs;
}
if (cnt % 2 == 0) {
return sum;
} else {
return sum - min * 2L;
}
}
题目2：给你一个一串长度为 n的 手链（不是环），手链上的珠子编号从1到n。
它可能有多次如下操作：将 a位置的珠子取出来放到 b位置的前面或后面。
问操作q次后，这串手链的最终编号。
lru缓存算法翻版：如果不了解这个算法的话可以先去了解下。
ac代码：注释是找ai加的
import java.util.Scanner;
public class Main {
static int maxn = (int) (1e5 + 10);
// 定义一个 Node 数组，表示手链上的每个珠子（节点）
static Node[] nodes = new Node[maxn];
static int n, q;
/**
* lru算法，使用双向链表来模拟手链的操作，使用map集合来快速查找珠子。（珠子的值很小所以我用数组代替了（nodes））
*
* @param args
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
q = sc.nextInt();
// 初始化头节点 h 和尾节点 t，h 和 t 是哨兵节点，方便操作
Node h = new Node(-1); // 头节点（不属于手链上的珠子）
Node t = new Node(-1); // 尾节点（不属于手链上的珠子）
h.next = t;
t.pre = h;
// 初始化手链中的每个珠子，构建一个双向链表
for (int i = 1; i <= n; i++) {
Node node = new Node(i); // 创建第 i 个珠子
node.pre = t.pre; // 珠子的 pre 指向尾节点的前一个节点
node.next = t; // 珠子的 next 指向尾节点
t.pre.next = node; // 尾节点的前一个节点的 next 指向该珠子
t.pre = node; // 尾节点的 pre 更新为该珠子
nodes[i] = node; // 将珠子存入 nodes 数组
}
// 处理 q 次操作
for (int i = 0; i < q; i++) {
int a = sc.nextInt(); // 珠子 a 的编号
int b = sc.nextInt(); // 珠子 b 的编号
int op = sc.nextInt(); // 操作类型，0 表示将 a 插入到 b 前面，1 表示将 a 插入到 b 后面
Node nodeA = nodes[a]; // 获取珠子 a 的节点
Node nodeB = nodes[b]; // 获取珠子 b 的节点
// 从链表中移除珠子 a
nodeA.pre.next = nodeA.next; // 珠子 a 的前一个节点的 next 指向珠子 a 的下一个节点
nodeA.next.pre = nodeA.pre; // 珠子 a 的下一个节点的 pre 指向珠子 a 的前一个节点
// 根据 op 的值，选择将珠子 a 插入到 b 的前面或后面
if (op == 0) { // 将 a 插入到 b 的前面
nodeA.next = nodeB; // 珠子 a 的 next 指向珠子 b
nodeA.pre = nodeB.pre; // 珠子 a 的 pre 指向珠子 b 的前一个节点
nodeB.pre.next = nodeA; // 珠子 b 的前一个节点的 next 指向珠子 a
nodeB.pre = nodeA; // 珠子 b 的 pre 更新为珠子 a
} else { // 将 a 插入到 b 的后面
nodeA.next = nodeB.next; // 珠子 a 的 next 指向珠子 b 的下一个节点
nodeA.pre = nodeB; // 珠子 a 的 pre 指向珠子 b
nodeB.next.pre = nodeA; // 珠子 b 的下一个节点的 pre 指向珠子 a
nodeB.next = nodeA; // 珠子 b 的 next 更新为珠子 a
}
}
// 输出操作后的手链
Node curr = h.next; // 从头节点 h 的下一个节点开始遍历
while (curr != t) { // 遍历到尾节点 t 停止
System.out.print(curr.v + " "); // 输出当前珠子的编号
curr = curr.next; // 移动到下一个珠子
}
}
// 定义双向链表节点类 Node
static class Node {
int v; // 珠子的编号
Node pre; // 指向前一个节点的指针
Node next; // 指向下一个节点的指针
// 构造函数，初始化编号 v
public Node(int v) {
this.v = v;
}
// 构造函数，初始化编号 v 以及前一个节点和下一个节点的指针
public Node(int v, Node pre, Node next) {
this.v = v;
this.pre = pre;
this.next = next;
}
}
}
#小米笔试#
投递小米集团等公司10个岗位 >
