Algorithm
lc2779_数组的最大美丽值
思路:
这里每个数字只能选择一次来进行上下扩展k。
所以暴力方法就是遍历数组把每个范围内的值都加到一个计数数组中,出现次数最多的那个值的次数就是答案。
但是暴力方法O(n*k), 会超时。
所以可以知道把 nums[i] - k, nums[i] + k
这个范围加1,然后有重叠的最多范围。
好像线段树能解决,但是不记得怎么写线段树了…
题目转化为时间段重合最多的值。可以记录左右,然后范围排序记录维护最大重叠。
那就是 O(nlogn)。
这样应该可以,直接排序,然后再算重叠数。
进而可以优化成,滑动的 2k
窗口能装下多少数字了。
所以就是先 O(nlogn) 排序,然后遍历中二分查找维护答案。
思考了20分钟,还是太慢了,得多练。
准备写之前,看了一下tips,发现和我思路一样,开写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int ans = 1;
int gap = 2 * k;
for (auto it = nums.begin(); it != nums.end(); ++it) {
auto upper_it = std::upper_bound(it, nums.end(), *it + gap);
ans = std::max(ans, (int)std::distance(it, upper_it));
}
return ans;
}
};
|
upper有点忘了,又请教了一下gpt,然后10mins才AC…继续加油
差分复盘
题解2里面的差分数组非常精妙,复习复盘一下:
- 先前缀和再差分,可以获取区间和。
- 先差分+1,-1,再前缀和,可以获取最大区间重叠数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
int m = *max_element(nums.begin(), nums.end());
vector<int> diff(m + 2);
for (int x : nums) {
diff[max(x - k, 0)]++;
diff[min(x + k + 1, m + 1)]--;
}
int res = 0, count = 0;
for (int x : diff) {
count += x;
res = max(res, count);
}
return res;
}
};
|
Review
【TED演讲】年轻人的诉求
尝试不看字幕听的这个ted,但却被原标题误导…所以自己这里更改了标题
这个视频实际上讲的是一个 GenU 的组织,收集了很多的年轻人的诉求,
然后决定给世界上所有的年轻人提供培训和帮助,让他们更好得改善世界。
Tips
如何用 Sysbench 测试 TiDB
Share
好书分享 Designing Data-Intensive Applications
ddia
看了65小时英文中文对照版,终于看完了自己第一本英文技术书,也是自己第二本英文书(第一本是"小王子")。
本身也是从事分布式存储工作,因此对书中大量内容甚是亲切与熟悉。
这本书从数据系统基础,分布式数据,衍生数据三个方面抽象总结并详细探讨了数据密集型技术与应用。
其中观点非常有启发,对分布式存储的工作见解有极大帮助,非常推荐这本书。
并且作者在文末还提到数据系统要利于用户,利于世界,谨防大数据系统杀熟,监禁,监视。
这样才能减少世界的偏见,减少种族,性别等等各种歧视,才能让世界在大数据时代获利而不危害。
发展数据系统,但仅用于造福用户,造福世界,人人有责。
豆瓣图片展示不出
测试发现豆瓣图片无法在网页展示,F12查看得到如下:
1
|
<img class="lazyautosizes lazyloaded" src="https://img1.doubanio.com/view/subject/l/public/s29419939.jpg" data-src="https://img1.doubanio.com/view/subject/l/public/s29419939.jpg" data-srcset="https://img1.doubanio.com/view/subject/l/public/s29419939.jpg, https://img1.doubanio.com/view/subject/l/public/s29419939.jpg 1.5x, https://img1.doubanio.com/view/subject/l/public/s29419939.jpg 2x" data-sizes="auto" alt="https://img1.doubanio.com/view/subject/l/public/s29419939.jpg" title="ddia" sizes="60px" srcset="https://img1.doubanio.com/view/subject/l/public/s29419939.jpg, https://img1.doubanio.com/view/subject/l/public/s29419939.jpg 1.5x, https://img1.doubanio.com/view/subject/l/public/s29419939.jpg 2x">
|
所以应该是豆瓣的这个图片链接是自动适应功能,但是却没在网页展示…
1
|
![ddia](https://img1.doubanio.com/view/subject/l/public/s29419939.jpg)
|
所以尝试用单独的 html 试试先。
还是不行,然后就网上找了一下,原来要这样:
使用图片缓存方法,使用https://images.weserv.nl/?url=再加上原来豆瓣图片地址去掉https://的链接,即可访问。
1
2
|
- https://img3.doubanio.com/view/subject/l/public/s2955123.jpg
+ https://images.weserv.nl/?url=img3.doubanio.com/view/subject/l/public/s2955123.jpg
|