小米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;
        }
    }
}