2022-01-02 swipe questions and punch in every day

Flying book - daily question

42. Rainwater connection

Given n non negative integers to represent the height diagram of each column with width 1, calculate how much rain the columns arranged according to this can receive after rain.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: the above is the height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rainwater can be connected (the blue part represents rainwater).

First of all, we know that only when the height in the middle is less than the height on the left and right sides can we receive rainwater. In this case, we can use the head and tail double pointers to move and traverse to the middle. Prepare two values l_max and r_max to save the maximum height on the left and right sides. Start traversing. Compare the size of height[l] and height[r] each time. If l is large, you can know that a place greater than the current height has appeared on the left. As long as you find a place greater than the current height on the right, let's update the maximum height to see that it is r_max is bigger or height[r]. If height[r] is bigger, update r_max, we calculate R_ The value of Max height[r] is the value that we can receive rainwater. If the column we traverse is the highest column, naturally there will be no higher column on the right to let us receive rainwater, so it is 0. If r_max greater than height[r] indicates that there are also high columns on the right, which meets the conditions of small in the middle and large on both sides. At this time, the capacity that can receive rainwater is r_max height[r], then R –. If l is small, the above operation can be changed.

class Solution {
public:
    int trap(vector<int>& height) {
        int l=0,r=height.size()-1,l_max=0,r_max=0,ans=0;
        while(l<r)
        {
            if(height[l]<height[r])
            {
                l_max=max(l_max,height[l]);
                ans+=l_max-height[l];
                l++;
            }
            else
            {
                r_max=max(r_max,height[r]);
                ans+=r_max-height[r];
                r--;
            }
        }
        return ans;
    }
};

Force deduction - one question per day

390. Eliminate games

The list arr consists of all integers in the range [1, n] and is sorted strictly incrementally. Please apply the following algorithm to arr:

From left to right, delete the first number, and then delete every other number until you reach the end of the list.
Repeat the above steps, but this time from right to left. That is, delete the rightmost number, and then delete every other number.
Repeat these two steps from left to right and from right to left until there is only one number left.
Give you the integer n and return the last remaining number of arr.

Example 1:

Input: n = 9
Output: 6
Explanation:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

We can see that each deletion will delete half of the numbers (if it is an odd number, the deleted number will be rounded up). Moreover, each deletion is the number in the middle of the two numbers, that is, each deletion will double the difference between the two adjacent numbers. For example, the difference between the two numbers is 1 2 3 4 5 6 at the beginning, and the difference between the two numbers is 1. After the first deletion, it becomes 2 4 6, The difference becomes 2. We can see a rule that every time you delete, one of the numbers at the beginning and end will change (be deleted). If the existing number is odd, the numbers at the beginning and end will change. If the existing number is even, it is related to the number of times you delete. If the number of times you delete is odd, The number at the beginning will change (if the number of deletes is odd, the deletion will start from the head). If the number of deletes is even, the deletion will start from the tail, that is, the number at the tail will change, and the change size is 2 ^ (the number of deletes). We start the cycle and delete half of the number in each cycle. When the remaining number is less than or equal to 2, it ends. Each deletion modifies the number at the beginning and end according to the number of deletes and the parity of the remaining numbers. After the cycle ends, judge whether to return the first number or the last number according to the parity of the number of cycles.

class Solution {
public:
    int lastRemaining(int n) {
        int num=n,l=1,r=n,loop=0,d=1;
        while(num>2)
        {
            loop++;
            if((num%2==1)||(num%2==0&&loop%2==1))l+=d;
            if((num%2==1)||(num%2==0&&loop%2==0))r-=d;
            num/=2;
            d*=2;
        }
        return loop%2==1?l:r;
    }
};

Acwing

838. Heap sorting - AcWing question bank

Enter an integer sequence with length n, and output the number of the first m from small to large.

Input format

The first line contains integers n and m.

The second row contains n integers, representing the integer sequence.

Output format

A total of one line, including M integers, representing the number of the first m in the integer sequence.

Data range

1≤m≤n≤10^5
1 ≤ elements in sequence ≤ 10 ^ 9

Input example:

5 3
4 5 1 3 2

Output example:

1 2 3

Just remember the template.

#include<iostream>
using namespace std;
const int N = 100010;
int arr[N], n, m, len;

void down(int u)
{
    int t = u;
    if (u * 2 <= len && arr[2 * u] < arr[t])t = 2 * u;
    if (u * 2 + 1 <= len && arr[2 * u + 1] < arr[t])t = 2 * u + 1;
    if (u != t)
    {
        swap(arr[t], arr[u]);
        down(t);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%d", &arr[i]);
    len = n;
    for (int i = n / 2; i; i--)down(i);
    while (m--)
    {
        cout << arr[1] << " ";
        arr[1] = arr[len];
        len--;
        down(1);
    }
    return 0;
}