D358周赛复盘：哈希表模拟⭐⭐+链表乘法翻倍运算（先反转）⭐⭐⭐

2815.数组中的最大数对和

给你一个下标从 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 。
1
2
3
4
5
6

示例 2：

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

提示：

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

思路

本题需要用哈希表来做，我们需要对应每个数位最大数字和相应的数值。

完整版

• 注意是找一对数字，也就是只找两个数字。因此哈希表里面要存储每个数位最大数字对应的那个数字的值。

class Solution {
public:
    //获取数字最大位
    int getMaxDigit(int num){
        int maxDigit =-1;
        //只要Num存在就继续
        while(num){
            maxDigit=max(maxDigit,num%10);//单个数字比较，%10得到单个数字
            num/=10;//去掉最后一位
        }
        return maxDigit;
    }
    int maxSum(vector<int>& nums) {
        //创建哈希表存储最大位和与其关联的数字最大值
        unordered_map<int,int>maxDigitMap;
        int result=-1;
        int maxD=-1;
        for(int num:nums){
            maxD=getMaxDigit(num);
            //如果这个数字已经在哈希表里面
            if(maxDigitMap.count(maxD)){
                //累积结果取最大值
                result = max(result,maxDigitMap[maxD]+num);
                //注意：目标是找到和最大的一对数字，也就是两个数字！所以哈希表要存储最大的数字
                maxDigitMap[maxD]=max(maxDigitMap[maxD],num);//更新最大位相同数字的和
            }
            else{
                maxDigitMap[maxD]=num;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2816.翻倍以链表形式表示的数字（先反转，再处理进位）

给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。

将链表 翻倍 后，返回头节点 head 。

示例 1：

输入：head = [1,8,9]
输出：[3,7,8]
解释：上图中给出的链表，表示数字 189 。返回的链表表示数字 189 * 2 = 378 。
1
2
3

示例 2：

输入：head = [9,9,9]
输出：[1,9,9,8]
解释：上图中给出的链表，表示数字 999 。返回的链表表示数字 999 * 2 = 1998 。
1
2
3

提示：

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

思路

1. 反转链表:

   为了方便计算，我们首先将链表反转。这样我们可以从数字的低位（链表的头部）开始处理，方便处理进位。例如数字 189 的链表 [1, 8, 9] 反转后会变成 [9, 8, 1]。

2. 翻倍处理:

   • 对每一个节点，翻倍它的值并加上可能的进位（carry）。例如，如果当前节点的值为9，翻倍后是18，再加上可能的进位，这样这个节点的新值就是8，进位就是1。
   • 这个进位会被加到下一个节点的值上，这样一直处理到链表的尾部。
   • 如果链表的最后一个节点有进位，就需要添加一个新的节点来存储这个进位。

3. 再次反转链表:

   在完成上述的翻倍处理后，链表仍然是反转的状态，所以我们需要再次反转它以得到正确的答案。

这种方法的好处是我们只需要遍历两次链表，一次是反转，一次是翻倍处理，所以总体的时间复杂度是 O(n)，其中 n 是链表的长度。

完整版

• 注意乘法的处理方式，先反转，再相乘，相乘完了之后更新进位。（注意相乘的时候要加上进位）
• 如果是最后一个数字且进位不为0，那么需要再加一个数值为0的空节点，用于存放carry！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
//先单独写反转链表的函数
    ListNode* reverseList(ListNode* head){
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur!=nullptr){
            ListNode* temp = cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
    ListNode* doubleIt(ListNode* head) {
        if(head==nullptr) return nullptr;
        //反转链表
        head = reverseList(head);
        //创建一个指针指向链表头部
        ListNode* cur = head;
        int carry=0;//初始化进位是0

        //遍历链表
        while(cur!=nullptr){
            int temp = cur->val *2 + carry;//加上进位，和普通乘法一样
            cur->val = temp%10;//当前节点数值是加上进位后的个位数
            carry = temp/10;//更新进位

            //注意特殊情况！如果当前节点是链表最后一个并且还有进位
            if(cur->next==nullptr&&carry){
                cur->next=new ListNode(0);//增加一个新的节点，用于存放carry
            }
            cur = cur->next;
        }
        //最后反转链表，返回
        head = reverseList(head);
        return head;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

补充：206.反转链表（双指针法）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2

示例 2：

输入：head = [1,2]
输出：[2,1]
1
2

示例 3：

输入：head = []
输出：[]
1
2

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

题解：206. 反转链表 - 力扣（LeetCode）

完整版

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;//pre是cur的前一个节点，也是反转之后当前节点需要指向的节点
        while(cur!=nullptr){
            ListNode* temp=cur->next;
            cur->next=pre;
            pre=cur;//下一个节点需要指向当前节点
            cur=temp;//cur访问下一个节点
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2817.限制条件下元素之间的最小绝对差（cpp不知道为什么超时了，java可以）

给你一个下标从 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 是最优解。
1
2
3
4
5

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= x < nums.length

本题用java解法通过，但是cpp同样的写法，不知道为啥超时了。

思路是维护前面0_{i是个有序的序列，这样就可以用二分查找0}i中和j最接近的元素。

但是java中没有既可以自动排序，又可以用下标取的数据类型。所以就自己用二分维护了一个有序列表，就是每次来一个新元素i，用二分查找它应该放在哪个位置。有序序列就是 0 ~ i 中元素排序之后的结果。

class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int n = nums.size(), ans = Integer.MAX_VALUE;
        List<Integer> ls = new ArrayList();         // 维护前面元素的有序序列（升序）
        for (int i = 0, j = x; j < n; ++i, ++j) {
            // 将nums[i]加入有序序列ls，使用二分查找寻找nums[i]应该插入的位置。
            int l = 0, r = ls.size(), v = nums.get(i);
            while (l < r) {
                int mid = l + r >> 1;
                if (ls.get(mid) <= v) l = mid + 1;
                else r = mid;
            }
            ls.add(l, v);
            
            // 使用二分查找寻找前面序列中最后一个<=nums[j]的元素
            l = 0;
            r = ls.size() - 1;
            v = nums.get(j);
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (ls.get(mid) > v) r = mid - 1;
                else l = mid;
            }
            // 使用和nums[j]最接近的元素更新答案
            ans = Math.min(ans, Math.abs(v - ls.get(l)));
            if (l + 1 < ls.size()) ans = Math.min(ans, Math.abs(ls.get(l + 1) - v));
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30