第358场周赛

小鱼儿 2024-03-23 22:23 66阅读 0赞

## 1. 数组中的最大数对和 ##

### 题目描述： ###

给你一个下标从 **0** 开始的整数数组 nums 。请你从 nums 中找出和 **最大** 的一对数，且这两个数数位上最大的数字相等。  
返回最大和，如果不存在满足题意的数字对，返回 -1。

**示例 1：**

> **输入**： nums = \[51,71,17,24,42\]  
> **输出**：88  
> **解释**： i = 1 和 j = 2 ，nums\[i\] 和 nums\[j\] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。 i = 3 和 j = 4 ，nums\[i\] 和 nums\[j\] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。 可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。

**示例 2：**

> **输入**： nums = \[1,2,3,4\]  
> **输出**：-1  
> **解释**：不存在数对满足数位上最大的数字相等。

**提示：**

*  `2 <= nums.length <= 100`
 *  `1 <= nums[i] <= 104`

### 解题思路： ###

1.  使用双重for循环遍历数组中的元素
2.  如果两数的数位最大值相同则，使用result变量记录当前两数和的最大值nums\[i\] + nums\[j\]

### 代码实现： ###

class Solution {
        
        public int maxSum(int[] nums) {
        
            // 双指针
            int result = -1;
            for (int i = 0; i < nums.length; i++) {
        
                for (int j = i + 1; j < nums.length; j++) {
        
                    int sum = nums[i] + nums[j];
                    if (sum > result && check(nums[i], nums[j])) {
        
                        result = sum;
                    }
                }
            }
            return result;
        }
    
        /**
         * 判断两数之和的最大值是否相同
         */
        private boolean check(int num1, int num2) {
        
            // 找最大数字
            return getMaxNum(num1) == getMaxNum(num2);
        }
    
        /**
         * 获取当前数的最大值
         */
        private int getMaxNum(int num) {
        
            int result = 0;
            while (num != 0) {
        
                result = Math.max(result, num % 10);
                num /= 10;
            }
            return result;
        }
    }

![image.png][]

## 2. 翻倍以链表形式表示的数字 ##

### 题目描述： ###

给你一个 **非空** 链表的头节点 `head`，表示一个不含前导零的非负数整数。  
将链表 **翻倍** 后，返回头节点`head`。

**示例 1：**

> ![956e3963bfa7172969a39dffb50ddbbe.png_averageHue_f6f6f6_clientId_u1e07c647-3567-4_from_paste_id_u01d046e9_originHeight_81_originWidth_401_originalType_url_ratio_2_rotation_0_showTitle_false_status_done_style_none_taskId_ue0ab55b0-78c8-4378-8d83-95c88512564_title][]  
> **输入**：head = \[1,8,9\]  
> **输出**：\[3,7,8\]  
> **解释**：上图中给出的链表，表示数字 189 。返回的链表表示数字 189 \* 2 = 378 。

**示例 2：**

> ![eb4788d2411bcc039bc8979198e34a51.png_averageHue_f6f6f6_clientId_u1e07c647-3567-4_from_paste_id_uff71b763_originHeight_81_originWidth_401_originalType_url_ratio_2_rotation_0_showTitle_false_status_done_style_none_taskId_u156c1618-e4fc-4e36-b6d1-0fff99dbf2e_title][]  
> **输入**：head = \[9,9,9\]  
> **输出**：\[1,9,9,8\]  
> **解释**：上图中给出的链表，表示数字 999 。返回的链表表示数字 999 \* 2 = 1998 。

**提示：**

*  链表中节点的数目在范围 `[1, 104]` 内
 *  `0 <= Node.val <= 9`
 *  生成的输入满足：链表表示一个不含前导零的数字，除了数字 0 本身。

### 解题思路： ###

1.  先将链表遍历一次，使用ArrayList存储每个节点值，同时定义**int类型**变量flag**判断当前节点值是否需要进位**以及**进位值为多少**
2.  **逆序遍历**存储链表节点值的List，将每一个节点值都进行**乘2操作并与flag节点值相加**计算翻倍后并且增加了进位的值sum
3.  判断此时sum值
    
    1.  `sum >= 10`，更新flag的值为`sum / 10`，此时将`sum - flag * 10`值添加到ArrayList中
    2.  `sum < 10`，**说明没有需要进位的操作**，将`sum`添加到ArrayList中，并将flag进位值赋值为0，防止对后续节点值的计算产生影响
4.  结束遍历后再次判断flag的值，**判断最后一个节点值是否有进位操作**，如果flag不为0则在ArrayList后再添加1
5.  逆序遍历ArrayList，根据每一个值来构建链表节点。因为此时存储进位后节点值的ArrayList中的值都是倒序的，**例如：**\[9,9,9\]中，在经过步骤1,2,3后，得到的List为\[8,9,9,1\]
6.  返回链表

### 代码实现： ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode doubleIt(ListNode head) {
        
            // 存储链表节点值
            List<Integer> nodes = new ArrayList<>();
            while (head != null) {
        
                nodes.add(head.val);
                head = head.next;
            }
            // 进位值，初值为0
            int flag = 0;
            // 存储节点值进行翻倍处理后的值
            List<Integer> list = new ArrayList<>();
            // 逆序遍历节点值
            for (int i = nodes.size() - 1; i >= 0; i--) {
        
                // 计算当前节点值
                int sum = nodes.get(i) * 2 + flag;
                if (sum >= 10) {
        
                    // 更新进位值
                    flag = sum / 10;
                    // 添加节点值
                    list.add(sum - flag * 10);
                } else {
        
                    // 更新进位值
                    flag = 0;
                    list.add(sum);
                }
            }
            // 判断最后一个元素是否有进位操作
            if (flag != 0) {
        
                list.add(1);
            }
            // 构造新链表
            ListNode result = new ListNode(0), temp = result;
            // 逆序遍历存储节点值
            for (int i = list.size() - 1; i >= 0; i--) {
        
                // 添加链表节点
                ListNode node = new ListNode(list.get(i));
                temp.next = node;
                temp = temp.next;
            }
    
            return result.next;
        }
    }

![image.png][image.png 1]

## 3. 限制条件下元素之间的最小绝对差 ##

### 题目描述： ###

给你一个下标从 **0** 开始的整数数组 nums 和一个整数 x 。  
请你找到数组中下标距离至少为 x 的两个元素的 **差值绝对值** 的 **最小值** 。  
换言之，请你找到两个下标 i 和 j ，满足 `abs(i - j) >= x` 且 `abs(nums[i] - nums[j])` 的值最小。  
请你返回一个整数，表示下标距离至少为 x 的两个元素之间的差值绝对值的 **最小值** 。

**示例 1：**

> **输入**：nums = \[4,3,2,4\], x = 2  
> **输出**：0  
> **解释**：我们选择 nums\[0\] = 4 和 nums\[3\] = 4 。 它们下标距离满足至少为 2 ，差值绝对值为最小值 0 。 0 是最优解。

**示例 2：**

> **输入**：nums = \[5,3,2,10,15\], x = 1  
> **输出**：1  
> **解释**：我们选择 nums\[1\] = 3 和 nums\[2\] = 2 。 它们下标距离满足至少为 1 ，差值绝对值为最小值 1 。 1 是最优解。

**示例 3：**

> **输入**：nums = \[1,2,3,4\], x = 3  
> **输出**：3  
> **解释**：我们选择 nums\[0\] = 1 和 nums\[3\] = 4 。 它们下标距离满足至少为 3 ，差值绝对值为最小值 3 。 3 是最优解。

**提示：**

*  `1 <= nums.length <= 105`
 *  `1 <= nums[i] <= 109`
 *  `0 <= x < nums.length`

### 解题思路： ###

本题思路较为简单，但是在做题时需要注意双重for循环会出现超时情，因此需要借助`TreeSet`数据结构  
首先需要先知道使用到的两个核心方法：  
`floor(E e)`**：返回此集合中最大的元素小于或等于给定元素，如果没有这样的元素，则返回 null**  
`ceiliing(E e)`：**返回此集合中最小元素大于或等于给定元素，如果没有此元素，则返回 null**

1.  首先定义TreeSet集合用于维护符合条件的节点
2.  遍历当前数组，遍历的索引初值为x
    
    1.  添加数组中第`x - i`个元素到TreeSet中，在本次遍历过程中，第`x - i` 个元素是符合条件的元素，在随后的遍历过程中，每一个符合条件的元素都会添加到TreeSet中
    2.  分别获取当前集合中 **小于当前遍历值的最大值** 和 **大于当前遍历值的最小值** 并分别获取到它们与当前遍历值的差值
    3.  记录当前最小差值
3.  返回最小差值

### 代码实现： ###

class Solution {
        
        public int minAbsoluteDifference(List<Integer> nums, int x) {
        
            // 定义返回值
            int result = Integer.MAX_VALUE;
            TreeSet<Integer> treeSet = new TreeSet<>();
            // 一次遍历寻找
            for (int i = x; i < nums.size(); i++) {
        
                // 存储当前符合条件的节点值
                treeSet.add(nums.get(i - x));
                // 获取当前值
                int num = nums.get(i);
    
                // 获取小于当前值的最大值
                Integer floor = treeSet.floor(num);
                // 获取大于当前值的最小值
                Integer ceil = treeSet.ceiling(num);
    
                // 比较大于当前值的最小节点值 与 小于当前值的最大节点值 和当前值的差
                if (floor != null) {
        
                    result = Math.min(Math.abs(floor - num), result);
                }
                if (ceil != null) {
        
                    result = Math.min(Math.abs(ceil - num), result);
                }
            }
            return result;
        }
    }

![image.png][image.png 2]

## 4. 操作使得分最大 ##

### 题目描述： ###

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。  
一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：

*  选择一个之前没有选过的 **非空** 子数组 nums\[l, …, r\] 。
 *  从 nums\[l, …, r\] 里面选择一个 **质数分数** 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
 *  将你的分数乘以 x 。

nums\[l, …, r\] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。  
一个整数的 **质数分数** 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 \* 2 \* 3 \* 5 \* 5 。  
请你返回进行至多 k 次操作后，可以得到的 **最大分数** 。  
由于答案可能很大，请你将结果对 109 + 7 取余后返回

**示例 1**：

> **输入**：nums = \[8,3,9,3,8\], k = 2  
> **输出**：81  
> **解释**：进行以下操作可以得到分数 81 ：

*  选择子数组 nums\[2, …, 2\] 。nums\[2\] 是子数组中唯一的元素。所以我们将分数乘以 nums\[2\] ，分数变为 1 \* 9 = 9 。
 *  选择子数组 nums\[2, …, 3\] 。nums\[2\] 和 nums\[3\] 质数分数都为 1 ，但是 nums\[2\] 下标更小。所以我们将分数乘以 nums\[2\] ，分数变为 9 \* 9 = 81 。  
    81 是可以得到的最高得分。  
    示例 2：

**示例 2：**

> **输入**：nums = \[19,12,14,6,10,18\], k = 3  
> **输出**：4788  
> **解释**：进行以下操作可以得到分数 4788 ：

*  选择子数组 nums\[0, …, 0\] 。nums\[0\] 是子数组中唯一的元素。所以我们将分数乘以 nums\[0\] ，分数变为 1 \* 19 = 19 。
 *  选择子数组 nums\[5, …, 5\] 。nums\[5\] 是子数组中唯一的元素。所以我们将分数乘以 nums\[5\] ，分数变为 19 \* 18 = 342 。
 *  选择子数组 nums\[2, …, 3\] 。nums\[2\] 和 nums\[3\] 质数分数都为 2，但是 nums\[2\] 下标更小。所以我们将分数乘以 nums\[2\] ，分数变为 342 \* 14 = 4788 。  
    4788 是可以得到的最高的分。

**提示**：

*  `1 <= nums.length == n <= 105`
 *  `1 <= nums[i] <= 105`
 *  `1 <= k <= min(n * (n + 1) / 2, 109)`

> 暂时还没有想到怎么AC这道。。。

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a0e8c14f1b4643f6985bad09e5420f05.png
[956e3963bfa7172969a39dffb50ddbbe.png_averageHue_f6f6f6_clientId_u1e07c647-3567-4_from_paste_id_u01d046e9_originHeight_81_originWidth_401_originalType_url_ratio_2_rotation_0_showTitle_false_status_done_style_none_taskId_ue0ab55b0-78c8-4378-8d83-95c88512564_title]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7da1d931088e421bb2ec08008a0030ef.png
[eb4788d2411bcc039bc8979198e34a51.png_averageHue_f6f6f6_clientId_u1e07c647-3567-4_from_paste_id_uff71b763_originHeight_81_originWidth_401_originalType_url_ratio_2_rotation_0_showTitle_false_status_done_style_none_taskId_u156c1618-e4fc-4e36-b6d1-0fff99dbf2e_title]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4849c71ab3d344f7a2be2c0fbae5d224.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8e0f48200c4b444eb59135f708edd0b1.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9c8df43ff17e408391d321bd261a4cbf.png