Linmin's Data
文章 标签 分类
Linmin's Data

Contents

ARST打卡第231周[231/521]

 included in ARST
   1185 words   3 minutes 

Algorithm

lc901_股票价格跨度

思路: 插入有序容器，然后返回upper_bound下标

结果看 题解 发现是单调递减的单调栈

真尴尬，一开始想到单调栈但没继续想下去.

正确答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class StockSpanner {
public:
    StockSpanner() {
        this->stk.emplace(-1, INT_MAX);
        this->idx = -1;
    }
    
    int next(int price) {
        idx++;
        while (price >= stk.top().second) {
            stk.pop();
        }
        int ret = idx - stk.top().first;
        stk.emplace(idx, price);
        return ret;
    }

private:
    stack<pair<int, int>> stk; 
    int idx;
};

multi_set+upper_bound探索

不过这里时间复杂度比单调栈的O(n)多，这里是O(n^2)，而且答案还是错的，具体看下面代码注释

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <bits/stdc++.h>
using namespace std;

class StockSpanner {
public:
    StockSpanner() {
        stocks.clear();
    }
    int next(int price) {
        stocks.insert(price);
        
        // 测试使用
        cout << "The multiset elements are: ";
        for (auto it = stocks.begin(); it != stocks.end(); it++)
            cout << *it << " "; 
        cout << endl;

        // 使用upper_bound查找大于target的第一个迭代器
        auto it = stocks.upper_bound(price);
        cout << "Price: " << price << " got it: " << *it << endl;
        if (it != stocks.end()) {
            // 这里distance会卡死，而且虽然 upper_bound 能O(logn), 但是这里 distance 对于multiset是O(n). 导致最终题解复杂度来到了 O(n^2) 导致超时。
            // 现在知道时间复杂度不可行，但是还不知道为啥这里distance会卡死。 
            // 看了一下: https://en.cppreference.com/w/cpp/iterator/distance  发现是 GPT 给的示例写反了...
            // return distance(it, stocks.begin()) - 1;
            return distance(stocks.begin(), it);
        }
        return 1;
    }
private:
    multiset<int> stocks;
};


int main() {
    StockSpanner* obj = new StockSpanner();
    cout << obj->next(100) << endl;
    cout << obj->next(80) << endl;
    cout << obj->next(60) << endl;
    cout << obj->next(70) << endl;
    cout << obj->next(60) << endl;
    cout << obj->next(75) << endl;
    cout << obj->next(85) << endl;
    return 0;
}

/* 
❯ g++ stock.cpp -o stock.out -std=c++11
❯ ./stock.out
The multiset elements are: 100 
Price: 100 got it: 1
1
The multiset elements are: 80 100 
Price: 80 got it: 100
1
The multiset elements are: 60 80 100 
Price: 60 got it: 80
1
The multiset elements are: 60 70 80 100 
Price: 70 got it: 80
2
############ 这里把multiset版本的思路完全证伪############
### 因为题目定以的是需要连续的几天，这里 60 70 60 ，就导致不是连续的，所以答案只能用单调栈获取。
The multiset elements are: 60 60 70 80 100 
Price: 60 got it: 70
2
The multiset elements are: 60 60 70 75 80 100 
Price: 75 got it: 80
4
The multiset elements are: 60 60 70 75 80 85 100 
Price: 85 got it: 100
6

## 正确答案如下: 
1
1
1
2
1
4
6

 */

upper_bound总结

  1. 算法库的 upper_bound 实现中是用 advance 实现的，所以对于随机访问的 vector 可以做到 logn 复杂度，而对于非随机访问的容器需要 O(n) (upper_bound(a_set)) – upper_bound默认序列有序，所以直接遍历，所以是O(n)，而不是O(nlogn)
  2. 但是红黑树实现的容器可以通过树二分获取，所以set,map类的容器自带 upper_bound 也是 logn 复杂度的。 multiset.upper_bound(val) 不了解这里的话，很容易问出这个问题: 用advance实现的lowerbound对multiset进行使用，advance是线性复杂度，那为什么lowerbound还是logn复杂度呢？ 其实用advance实现的lowerbound对multiset进行使用，时间复杂度是O(n)，要用multiset自带的upperbound实现才是红黑树分叉的logn复杂度
  3. 对于list这种链表容器，也不是树形结构，所以根本无法二分，所以使用 lower_bound, 就只有是O(n)遍历。

Review

【TED演讲】你感到如此忙碌的原因

忙碌的三个原因： 1.不知道该做什么，让自己自己忙碌起来 2.让自己觉得自己很重要 3.麻痹自己

实际上，我们需要更多的时间思考自己真正想要做什么，然后不要在乎他人的眼光，然后自由选择自己想做的事情，自由掌控自己的事情，过自己想要的生活才是重要的。

Tips

hexo博客迁移-从一台PC到另一台PC

Share-修改照片文件时间为拍摄时间

因为时光相册下线了，所以时光相册的照片需要下载下来上传到其他云盘，但是下载后的照片文件创建时间是下载时的时间，导致上传到其他网盘时时间错乱。

所以我们可以先用脚本把照片文件的创建时间和修改时间改成照片的拍摄时间，然后再去上传。

以下是操作的 python 代码脚本。

需要自行下载一下 exiftool。 apt-get install exiftool / yum install exiftool / pkg install exiftool

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import os
import subprocess

## 指定要处理的目录
directory_path = "./Everphoto"  ## 替换为实际的目录路径

## 获取目录中所有的照片文件（假定为.jpg格式，可根据需要扩展）
photo_files = [os.path.join(directory_path, filename) for filename in os.listdir(directory_path) if filename.lower().endswith((".jpg", ".jpeg", ".png"))]

## 遍历照片文件并设置创建时间和修改时间为拍摄时间
for photo_file in photo_files:
    ## 使用 exiftool 获取拍摄时间
    result = subprocess.run(["exiftool", "-DateTimeOriginal", photo_file], capture_output=True, text=True)
    datetime_original = result.stdout.strip().splitlines()

    ## 如果成功获取拍摄时间，则设置文件的创建时间和修改时间为拍摄时间
    if datetime_original:
        ## 设置文件的创建时间和修改时间
        ## subprocess.run(["exiftool", f"-FileModifyDate={datetime_original}", f"-FileCreateDate={datetime_original}", photo_file])
        ## Android 不支持修改创建时间...
        subprocess.run(["exiftool", f"-FileModifyDate={datetime_original}", photo_file])

print("已成功将照片文件的修改时间设置为拍摄时间。")

悲伤的背后故事

因为作者本人是先把时光相册的照片下载到了手机，并且照片已经备份到了其他云盘，并且照片数据量很大，所以最终只修改了一下文件修改时间。(可能看不懂这句话，下面对这句话分解)

  • 手机上的照片文件如果不root，是无法修改创建时间的。(Termux 用python脚本尝试失败后得知. :(
    • 所以必须把文件移动到电脑上，删除掉手机文件，然后在电脑上修改好时间再上传网盘。然后再在手机上更新。
    • 上面方法理论上是完全可行的，所以数据量不大的兄弟们可以试试
  • 已经上传到了网盘，并且数据量巨大。
    • 所以上面步骤成本太大。
    • 折中方案就是在手机上使用 Termux 修改照片文件的修改时间
    • 然后发现小米相册排序并没有文件修改时间的排序 :(
      • 小米的相册创建时间排序其实就是拍摄时间排序…
        • 所以这种排序相册是正常了，但是默认排序是相册文件创建时间排序…
      • 小米相册的修改时间排序其实就是照片文件的创建时间排序…(而且mac的小米云是默认按拍摄时间排序，nice)

Termux 安装python，exiftool网上很多教程，应该没人感兴趣吧，如果有，可以评论或联系作者再出一篇文章

Updated on 2023-12-16
Read Markdown
 ARST
Back | Home