力扣刷题记录10.16

k

2024/10/16

测评*n，剪秋我的头好痛

（1）链表

1、 合并两个有序链表

• 递归

重点：考虑当前应该做的事，不要深究下一次、再下一次递归如何。

考虑当前时刻，后面的链表已经合并，现在到了list1和list2节点。那就是哪个节点的值比较小，就将这个节点合并到后面链接的节点上。然后是结束递归的条件：节点遍历完之后直接return 该节点。这样还不用分情况讨论两个链表是否为空。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {      
        if(list1==nullptr) return list2;
        if(list2==nullptr) return list1;
        if(list1->val<=list2->val) {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        list2->next=mergeTwoLists(list2->next,list1);
        return list2;    
    }
};

• 迭代

设置哨兵节点，方便最后返回连接好的链表。

pre节点负责每次去连接下一个节点，所以注意每次循环后pre=pre->next。

最后最多只剩下一个链表有剩余节点未连接，直接把pre接过去即可。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {      
        ListNode *prehead=new ListNode(-1);
        ListNode *pre=prehead;
        while(list1&&list2){
            if(list1->val<=list2->val){
                pre->next=list1;
                list1=list1->next;
            }
            else{
                pre->next=list2;
                list2=list2->next;
            }
            pre=pre->next;
        }
        pre->next=list2?list2:list1;
        return prehead->next;
    }
};

（2）数组

1、最小元素和最大元素的最小平均值

你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。

你需要重复以下步骤 n / 2 次：

• 从 nums 中移除 最小 的元素 minElement 和 最大 的元素 maxElement。
• 将 (minElement + maxElement) / 2 加入到 averages 中。

返回 averages 中的 最小 元素。

这道题很简单，主要的点在于整型和浮点数的转化。以及除法运算在最后才做，避免每次循环都要做一次。

class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int i=0；
        int n=nums.size();
        int ans=INT_MAX;
        while(i<n/2){
            ans=min(ans,nums[i]+nums[n-1-i]);
            i++;
        }
        return ans/2.0;
    }
};