当前位置 : 主页 > 编程语言 > 其它开发 >

ARTS Week 30

来源:互联网 收集:自由互联 发布时间:2022-05-30
Algorithm 本周的 LeetCode 题目为 162. 寻找峰值 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums ,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下
Algorithm

本周的 LeetCode 题目为 162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。

因为题目要求算法复杂度是 O(log n),那么不能进行遍历,则需要进行二分查找。为了避免峰值元素在左右边界上,那么在原数组左右边界上分别增加一个负无穷数。接下來进行二分查找,判断mid是否符合题目要求,若符合则更新结果,接下來分别寻找 left ~ midmid ~ right 范围中符合条件的数,如找到的数大于之前找到的结果,则更新结果。

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

本周 Review 的英文文章为:一切东西都必须支付两次

作者的观点乍听起来很奇怪,我们买任何东西都是一次付费即可,为什么要支付两次呢?例如,花20元买了一本书,但是当你阅读它时,可能需要花费10小时来阅读它,这便是第二个价格;再比如手机、家具等、当你花钱购买它们后,还需要花时间来学习使用他们,这样它们才能发挥其效果,这些都是第二价格。

作者认为这是我们现代生活的有时感到自欺欺人的原因之一,我们不断地在支付着第一个价格,相应地也产生了巨额的第二价格债务,但购买任何物品想要取得回报,需要两个价格都被支付才行。在第二价格债务中,手机应用程序、流媒体服务和加工食品等,它们仅需要付出很少的努力便可享受他们,于是我们很容易沉迷于它们,但这并不能帮助我们成长。

作者想到的唯一解决办法是避免支付不必要的第一价格,这样你就不会新增第二价格的债务,你就会有时间来享受一本好书,学习一种乐器等。

弄清楚什么是第二价格并不难,重要的是你可以坚持下去支付第二价格,慢慢地,奖励将会在陌生的时刻出现。

Tip

C 语言中 sizeof 是在编译时就计算得到结果,因此对于指针p来说,sizeof(p) 得到的是指针的大小,而 sizeof(*p) 得到的是指向类型的大小。示例如下:

#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));
}

运行结果是:

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

隔离了在宿舍呆了一周(未来估计还要呆一段时间),最开始还不太适应在宿舍的生活,找不到状态,效率比较低。未来需要逐步适应在宿舍的生活,找回原本的状态。

网友评论