ARTS Week 30

Algorithm

This week’s LeetCode problem is 162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Because the problem requires that the algorithm complexity is O(log n), then it cannot be traversed, and a binary search is required. In order to avoid peak elements on the left and right boundaries, add a negative infinity to the left and right boundaries of the original array. Next, perform a binary search to determine whether the mid meets the requirements of the question. If so, update the result. Next, search for the qualified numbers in the range of left ~ mid and mid ~ right respectively. If the number found is greater than the result found before , then update the result.

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        if (nums.length == 2) {
            return nums[0] > nums[1]? 0: 1;
        }
        int length = nums.length;
        float[] arr = new float[length+2];
        arr[0] = Float.NEGATIVE_INFINITY;
        for (int i = 0; i < length; i++) {
            arr[i+1] = nums[i];
        }
        arr[length+1] = Float.NEGATIVE_INFINITY;
        int ans = binarySearchPeak(arr, 1, length) - 1;
        return ans;
    }
    public int binarySearchPeak(float[] arr, int left, int right) {
        if (left > right) {
            return 0;
        }
        if (left == right) {
            return left;
        }
        int mid = left + (right - left) / 2;
        int ans = 0;
        if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {
            ans = mid;
        }
        int leftAns = binarySearchPeak(arr, left, mid-1);
        int rightAns = binarySearchPeak(arr, mid+1, right);
        if (arr[ans] < arr[leftAns]) {
            ans = leftAns;
        } if (arr[ans] < arr[rightAns]) {
            ans = rightAns;
        }
        return ans;
    }
}

Review

This week’s Review is for the following article: Everything Must Be Paid for Twice

The author’s point may sound strange at first, we pay once for everything, why pay twice? For example, if you spend 20 yuan to buy a book, but when you read it, it may take 10 hours to read it, which is the second price; for example, mobile phones, furniture, etc., when you spend money to buy them, It also takes time to learn to use them so they can work to their effect, and these are second prices.

The author believes this is one of the reasons why we sometimes feel self-delusional in our modern life. We are constantly paying the first price and incurring huge second-price debts accordingly, but buying anything to get a return requires two All prices are paid. Among the second-price debts, cell phone apps, streaming services, and processed foods, etc., they require very little effort to enjoy them, so it’s easy to get addicted to them, but it doesn’t help us grow.

The only solution that comes to the author’s mind is to avoid paying unnecessarily the first price, so you don’t add debt to the second price, and you’ll have time to enjoy a good book, learn a musical instrument, etc.

It’s not difficult to figure out what a second price is, the important thing is that you can stick with it and pay the second price, and slowly, the rewards will come at unfamiliar times.

Tip

In C language, sizeof is calculated at compile time, so for pointer p, sizeof(p) gets the size of the pointer, and sizeof(*p) gets the type of the pointer the size of. An example is as follows:

#include <stdio.h>
 
int main()
{
    // printf("%d\n", sizeof(tmp1));
    // printf("%d\n", sizeof(p_tmp));
    // printf("%d\n", p_tmp[2].x);
    int a[10];
    int *p = a;
    printf("sizeof(a) = %d\n", sizeof(a));
    printf("sizeof(p) = %d\n", sizeof(p));
    printf("sizeof(*p) = %d\n", sizeof(*p));
}

The result of execution is:

sizeof(a) = 40
sizeof(p) = 8
sizeof(*p) = 4

Share

I stayed in the dormitory for a week in isolation (it is estimated that I will stay in the dormitory for a while in the future). At first, I was not quite used to the life in the dormitory. I couldn’t find the status, and the efficiency was relatively low. In the future, it is necessary to gradually adapt to the life in the dormitory and get back to the original state.