shelterofly

目标

给你一个字符串 s，它由小写英文字母和特殊字符：*、# 和 % 组成。

请根据以下规则从左到右处理 s 中的字符，构造一个新的字符串 result：

• 如果字符是 小写 英文字母，则将其添加到 result 中。
• 字符 '*' 会 删除 result 中的最后一个字符（如果存在）。
• 字符 '#' 会 复制 当前的 result 并 追加 到其自身后面。
• 字符 '%' 会 反转 当前的 result。

在处理完 s 中的所有字符后，返回最终的字符串 result。

示例 1：

输入： s = "a#b%*"
输出： "ba"
解释：
i s[i] 操作 当前 result
0 'a' 添加 'a' "a"
1 '#' 复制 result "aa"
2 'b' 添加 'b' "aab"
3 '%' 反转 result "baa"
4 '*' 删除最后一个字符 "ba"
因此，最终的 result 是 "ba"。

示例 2：

输入： s = "z*#"
输出： ""
解释：
i s[i] 操作 当前 result
0 'z' 添加 'z' "z"
1 '*' 删除最后一个字符 ""
2 '#' 复制字符串 ""
因此，最终的 result 是 ""。

说明:

• 1 <= s.length <= 20
• s 只包含小写英文字母和特殊字符 *、# 和 %。

思路

根据规则从左到右处理字符串 s，如果时小写字母添加到结果 result，如果是 * 删除 result 的最后一个字符，如果是 # 将 result 追加到自身的后面，如果是 % 则反转当前的 result。

字符串长度最大为 20，可以暴力模拟。

代码

/**
 * @date 2025-07-14 9:15
 */
public class ProcessStrQ1 {

    public String processStr(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '*':
                    if (sb.length() > 0) {
                        sb.deleteCharAt(sb.length() - 1);
                    }
                    break;
                case '#':
                    sb.append(sb);
                    break;
                case '%':
                    sb.reverse();
                    break;
                default:
                    sb.append(c);
            }
        }
        return sb.toString();
    }

}

性能

目标

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。 

示例 2：

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

说明：

• 链表中节点的数目在范围 [1, 10^5] 内
• 1 <= Node.val <= 10^5

思路

删除链表的中间节点。

使用快慢指针，开始时都指向头节点，快指针每次走两步，慢指针走一步。当快指针指向最后一个节点或者 null 时，慢指针指向中间节点。因此需要在慢指针更新前将节点删除掉。

代码

/**
 * @date 2026-06-15 8:59
 */
public class DeleteMiddle2095 {

    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (true) {
            fast = fast.next.next;
            if (fast == null || fast.next == null) {
                slow.next = slow.next.next;
                break;
            }
            slow = slow.next;
        }
        return head;
    }

}

性能

目标

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

• 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

示例 1：

输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。

示例 2：

输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。

示例 3：

输入：head = [1,100000]
输出：100001
解释：
链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。

说明：

• 链表的节点数目是 [2, 10^5] 中的 偶数 。
• 1 <= Node.val <= 10^5

思路

有一个节点个数为偶数的链表，节点 A 的孪生节点 B 需满足 A 到 head 的距离等于 B 到 tail 的距离，通俗来说就是关于中轴线对称。每对孪生节点的和称为孪生和，求链表最大的孪生和。

快慢指针找到中间节点，然后反转链表后半部分，空间复杂度为 O(1)。

代码

/**
 * @date 2026-06-15 14:06
 */
public class PairSum2130 {

    public int pairSum(ListNode head) {
        int res = 0;
        ListNode slow = head;
        ListNode fast = head;
        int cnt = 0;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            cnt++;
        }
        ListNode prev = slow;
        slow = slow.next;
        prev.next = null;
        while (slow != null) {
            ListNode tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }
        for (int i = 0; i < cnt; i++) {
            res = Math.max(res, prev.val + head.val);
            prev = prev.next;
            head = head.next;
        }
        return res;
    }

}

性能

目标

给定一个长度为 n 的整数数组 nums 和一个整数 k。

你必须从 nums 中选择 恰好 k 个非空子数组 nums[l..r]。子数组可以重叠，同一个子数组（相同的 l 和 r）可以 被选择超过一次。

子数组 nums[l..r] 的 值 定义为：max(nums[l..r]) - min(nums[l..r])。

总值 是所有被选子数组的 值 之和。

返回你能实现的 最大 可能总值。

子数组 是数组中连续的 非空 元素序列。

示例 1:

输入: nums = [1,3,2], k = 2
输出: 4
解释:
一种最优的方法是：
选择 nums[0..1] = [1, 3]。最大值为 3，最小值为 1，得到的值为 3 - 1 = 2。
选择 nums[0..2] = [1, 3, 2]。最大值仍为 3，最小值仍为 1，所以值也是 3 - 1 = 2。
将它们相加得到 2 + 2 = 4。

示例 2:

输入: nums = [4,2,5,1], k = 3
输出: 12
解释:
一种最优的方法是：
选择 nums[0..3] = [4, 2, 5, 1]。最大值为 5，最小值为 1，得到的值为 5 - 1 = 4。
选择 nums[1..3] = [2, 5, 1]。最大值为 5，最小值为 1，所以值也是 4。
选择 nums[2..3] = [5, 1]。最大值为 5，最小值为 1，所以值同样是 4。
将它们相加得到 4 + 4 + 4 = 12。

说明:

• 1 <= n == nums.length <= 5 * 10^4
• 0 <= nums[i] <= 10^9
• 1 <= k <= 10^5

思路

定义子数组的值是最大值与最小值之差。已知一个长度为 n 的非负整数数组 nums，从中选择 k 个子数组（允许重复选择），求所选子数组的最大总值（即子数组值之和）。

由于可以重复选择，都选区间 [0, n - 1]，区间范围越大，最大值越大，最小值越小，差值越大。

代码

/**
 * @date 2026-06-09 9:07
 */
public class MaxTotalValue3689 {

    public long maxTotalValue(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return (long) (max - min) * k;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
  • 更正式的，考虑每一对 pi，pj ，pi 是初始时位置 i 元素的新位置，pj 是初始时位置 j 元素的新位置。如果 i < j 且两个元素 都 小于（或大于）pivot，那么 pi < pj 。

请你返回重新排列 nums 数组后的结果数组。

示例 1：

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，它们在结果数组中的相对顺序需要保留。

示例 2：

输入：nums = [-3,4,3,2], pivot = 2
输出：[-3,2,4,3]
解释：
元素 -3 小于 pivot ，所以在数组的最左边。
元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。

说明：

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot 等于 nums 中的一个元素。

思路

根据给定数字 pivot 划分数组，左边的都小于 pivot，右边的都大于 pivot，中间的等于 pivot，同一边元素的相对位置不能改变。

直接使用两个列表保存 小于 和 大于 pivot 的元素，计算等于 pivot 的元素个数，按顺序回填原数组即可。

代码

/**
 * @date 2026-06-08 9:49
 */
public class PivotArray2161 {

    public int[] pivotArray(int[] nums, int pivot) {
        int n = nums.length;
        Deque<Integer> l = new ArrayDeque<>();
        Deque<Integer> r = new ArrayDeque<>();
        for (int num : nums) {
            if (num < pivot) {
                l.offer(num);
            } else if (num > pivot) {
                r.offer(num);
            }
        }
        int equal = n - l.size() - r.size();
        int i = 0;
        while (!l.isEmpty()) {
            nums[i++] = l.poll();
        }
        while (equal > 0){
            nums[i++] = pivot;
            equal--;
        }
        while (!r.isEmpty()) {
            nums[i++] = r.poll();
        }
        return nums;
    }

}

性能

目标

给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：

• 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
• 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。

请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

测试用例会保证可以构造出 有效 的二叉树。

示例 1：

输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。

示例 2：

输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。 
结果二叉树如上图所示。 

说明：

• 1 <= descriptions.length <= 10^4
• descriptions[i].length == 3
• 1 <= parenti, childi <= 10^5
• 0 <= isLefti <= 1
• descriptions 所描述的二叉树是一棵有效二叉树

思路

有一个二维数组 descriptions，descriptions[i] = [parenti, childi, left or right] 描述了二叉树中的一对父子关系，即 parenti 是 childi 的父节点，childi 是 parenti 的左或者右孩子（取决于 1 或者 0）。重建二叉树并返回根节点。题目保证描述的是有效二叉树，且节点值不重复。

使用哈希表保存树节点，根据描述关系将节点连接起来，最终需要找出根节点，可以将孩子节点存到哈希集合中，返回不在该集合的节点即可。

代码

/**
 * @date 2026-06-08 11:34
 */
public class CreateBinaryTree2196 {

    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> map = new HashMap<>();
        Set<Integer> childKeySet = new HashSet<>();
        for (int[] description : descriptions) {
            int parentKey = description[0];
            map.putIfAbsent(parentKey, new TreeNode(parentKey));
            TreeNode parent = map.get(parentKey);
            int childKey = description[1];
            childKeySet.add(childKey);
            map.putIfAbsent(childKey, new TreeNode(childKey));
            TreeNode child = map.get(childKey);
            if (description[2] == 1) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
        for (int[] description : descriptions) {
            int parentKey = description[0];
            if (!childKeySet.contains(parentKey)) {
                return map.get(parentKey);
            }
        }
        return null;
    }
}

性能