备赛蓝桥杯--算法题目(2)

1. 排序数组

. - 力扣（LeetCode）

class Solution {
    void heapSort(vector<int>& nums)
    {
        for(int i=0;i<nums.size();i++)
        {
            heapInsert(nums,i);
        }
        int l=nums.size();
        while(l)
        {
            swap(nums[0],nums[l-1]);
            l--;
            heapIfy(nums,0,l);
        }
    }
    void heapInsert(vector<int>& nums,int i)
    {
        while(nums[i]>nums[(i-1)/2])
        {
            swap(nums[i],nums[(i-1)/2]);
            i=(i-1)/2;
        }
    }
    void heapIfy(vector<int>& nums,int i,int size)
    {
        int l=2*i+1;
        while(l<size)
        {
            int best=((l+1)<size)&&(nums[l+1]>nums[l])?l+1:l;
            if(nums[best]<nums[i])
            {
                best=i;
            }
            if(best==i)
            {
                break;
            }
            swap(nums[i],nums[best]);
            i=best;
            l=2*i+1;
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }
};

2. 寻找峰值

. - 力扣（LeetCode）

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        if(nums.size()==1)
        {
            return 0;
        }
        if(nums[l]>nums[l+1])
        {
            return l;
        }
        if(nums[r]>nums[r-1])
        {
            return r;
        }
        int ans=-1;
        while(l<=r)
        {
            int m=l+((r-l)>>1);
            if(nums[m+1]>nums[m])
            {
                l=m+1;
            }
            else if(nums[m-1]>nums[m]){
                r=m-1;
            }
            else{
                ans=m;
                break;
            }
        }
        return ans;
    }
};

3. 合并k个链表

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

4. 将数组和减半的最小次数

2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

class Solution {
public:
    int halveArray(vector<int>& nums) {
       priority_queue<long> q;
       long sum=0;
       for(int i=0;i<nums.size();i++)
       {
            long tmp=(long)nums[i]<<20;
            q.push(tmp);
            sum+=tmp;
       }
       long sum2=sum>>1;
       int con=0;
       while(sum2>0)
       {
            long m=q.top();
            q.pop();
            sum2-=m/2;
            q.push(m/2);
            con++;
       } 
       return con;
    }
};

5. 交换数字

面试题 16.01. 交换数字 - 力扣（LeetCode）

class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        numbers[0]=numbers[0]^numbers[1];
        numbers[1]=numbers[0]^numbers[1];
        numbers[0]=numbers[0]^numbers[1];;
        return numbers;
    }
};

6. 找到所有数组中消失的数字

448. 找到所有数组中消失的数字 - 力扣（LeetCode）

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (auto& num : nums) {
            int x = (num - 1) % n;
            if(nums[x]<=n)
            nums[x] += n;
        }
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.push_back(i + 1);
            }
        }
        return ret;
    }
};

7. 只出现一次的数字

LCR 004. 只出现一次的数字 II - 力扣（LeetCode）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> tmp(32,0);
        for(auto& m: nums)
        {
            for(int i=0;i<tmp.size();i++)
            {
                tmp[i]+=(m>>i)&1;
            }
        }
        int res=0;
        for(int i=0;i<tmp.size();i++)
        {
            if(tmp[i]%3!=0)
            {
                res|=1<<i;
            }
        }
        return res;
    }
};