天天日报丨刷题疑惑3

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

天天日报丨刷题疑惑3

2023-04-10 15:56:12 来源：博客园

(资料图片)

1、等值距离和（340周赛B）：有时间复杂度的要求，采用前缀和策略，保存在一个前缀和数组中，序列是从左往右递增的，所以可以将其分为左侧和右侧分开计算，模板题；同有序数组中差绝对值之和；

既然数组是非递减有序的，那么a[i]左边的元素一定不大于它本身，右边的元素一定不小于它本身；我们先计算出i位置（包含i）的前缀和pre[i]；a[i]与它左侧的所有元素绝对值差的和，等于i * a[i] - pre[i-1];；a[i]与它右侧的所有元素绝对值差的和，等于pre[a.length-1] - pre[i] - (a.length-1-i) * nums[i]；

2、判断是否是质数：采用平方根方法，1不是质数，所以从2开始计算；

bool isPrime(int num){    if(num <= 1) return false;    for(int i = 2;i*i <= num; ++i){        if(num % i == 0) return false;    }    return true;}

3、最小化数对的最大差值：二分思想+贪心；周赛常考的知识点；看到最大值最小的问题就想二分方法；先排序，相邻的元素差值一定最小，所以转化为最多选几个数对使得最大差值不超过x，x就是我们要枚举的元素；如果我们选了大于等于p个数对，那么该答案就通过检验；多写写类似题目，若将排序后相邻元素的差值记录下来，该题还可以转化为打家劫舍；

4、跳跃游戏Ⅱ：动规做时间复杂度高；贪心好一些；起始时只能跳一次，将能跳到的范围内的值挨个枚举，更新最大值；

5、

关键词：