DYH
关于 文章 标签 分类 随想 导航 清单 时光 CS
DYH
/images/avatar.png

^_^

hotcode

 发布于  收录于 Problemlist

912. 排序数组

题意

题解

改进版快排，针对数据重复问题，荷兰国旗问题 如果数据是有序的，直接随机洗牌就行

 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

func sortArray(nums []int) []int {
	n := len(nums)
	var quickSort func([]int, int, int)
	quickSort = func(nums []int, l int, r int) {
		if l >= r {
			return
		}
		pivot := nums[l + rand.Intn(r-l+1)]
		samel, samer := l, r
		cur := l
		for cur <= samer {
			if nums[cur] < pivot {
				nums[cur], nums[samel] = nums[samel], nums[cur]
				samel++
				cur++
			} else if nums[cur] > pivot {
				nums[cur], nums[samer] = nums[samer], nums[cur]
				samer--
			} else {
				cur++
			}
		}
		quickSort(nums, l, samel-1)
		quickSort(nums, samer+1, r)
	}
	quickSort(nums, 0, n-1)
	return nums
}

103. 二叉树的锯齿形层序遍历

题意

题解

和层序遍历差不多

阅读全文
 Problemlist

git补充2

 发布于  收录于 Note

如何更优雅地使用git，包含merge，pull，合并commit

实验工具是gitlab

pre

在gitlab上登录，只能免费试用一个月

阅读全文
 Git

C++ IPC

 发布于  收录于 Note

管道

 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

#include <iostream>
#include <unistd.h>
int main() {
    int fd[2];
    if (pipe(fd) == -1) {
        perror("pipe");
        return 1;
    }
    // create child process
    pid_t pid = fork();
    char buf[256];
    if (pid == -1) {
        perror("fork");
        return 1;
    } else if (pid > 0) { // parent process
        close(fd[0]);   // close read end
        std::string info = "hello world";
        write(fd[1], info.c_str(), info.length());
        close(fd[1]);
        wait(nullptr);  // block until one child end
    } else {    // pid == 0 is child process
        close(fd[1]);   // close write end
        read(fd[0], buf, sizeof buf);
        close(fd[0]);
        std::cout << "content is: " << buf << '\n';
    }
    return 0;
}

共享内存

 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

#include <sys/mman.h> // shm_open mmap
#include <fcntl.h> // for constants
#include <cstdio>
#include <unistd.h>
#include <iostream>

int main() {

    const int SIZE = 1024;

    // open a shared memory object which is a file located in /dev/shm/
    // "my_shm" is file name
    int fd = shm_open("my_shm", O_CREAT | O_RDWR, S_IRUSR | S_IWUSR); // -1 error

    // truncate or extend a file to a specified length
    ftruncate(fd, SIZE);    // -1 error

    int* shared_memory = static_cast<int *>(mmap(nullptr, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0)); // MAP_FAILED error

    pid_t pid = fork(); // -1 error
    if (pid > 0) {
        shared_memory[32] = 1000;
        sleep(2);
        std::cout << pid << ' ' << shared_memory[32] << '\n';
        wait(nullptr);
        munmap(shared_memory, SIZE);
        shm_unlink("my_shm");
        close(fd);
    } else if (pid == 0) {
        sleep(1);
        std::cout << pid << ' ' << shared_memory[32] << '\n';
        shared_memory[32] = 2000;
    }
    return 0;
}

to be continued

参考

https://blog.csdn.net/weixin_44014982/article/details/130241892

阅读全文
 Cpp

C++实现XXX

 发布于  收录于 Note

智能指针

 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

#include <iostream>

template <typename T>
class SmartPointer {
public:
    SmartPointer(T* ptr = nullptr) : _ptr(ptr), _cnt(ptr == nullptr ? nullptr : new int (1)){

    }

    SmartPointer(const SmartPointer<T>& other) : _ptr(other._ptr), _cnt(other._cnt) {
        if (_cnt) {
            ++(*_cnt);
        }
    }

    SmartPointer<T>& operator=(const SmartPointer<T>& other) {
        if (this != &other) {
            unpoint();
            _ptr = other._ptr;
            _cnt = other._cnt;
            if (_cnt) {
                ++(*_cnt);
            }
        }
        return *this;
    }

    ~SmartPointer() {
        unpoint();
    }

    T& operator*() const {
        return *_ptr;
    }

    T* operator->() const {
        return _ptr;
    }

    int getCnt() const {
        return _cnt ? *_cnt : 0;
    }

private:
    void unpoint() {
        if (_cnt and --(*_cnt) == 0) {
            delete _ptr;
            delete _cnt;
        }
    }
    T* _ptr;
    int* _cnt;
};

int main() {
    SmartPointer<int> ptr(new int(3));
    std::cout << ptr.getCnt() << '\n';
    SmartPointer<int> ptr2(ptr);
    std::cout << ptr.getCnt() << '\n';
    std::cout << ptr2.getCnt() << '\n';
    {SmartPointer<int> ptr3 ;
    ptr3 = ptr2;
    std::cout << ptr.getCnt() << '\n';
    std::cout << ptr2.getCnt() << '\n';
    std::cout << ptr3.getCnt() << '\n';}
    std::cout << ptr.getCnt() << '\n';
    std::cout << ptr2.getCnt() << '\n';

}

单例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Singleton {
private:
    Singleton() = default;
    static Singleton* instance;
public:
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
    static Singleton* getInstance() {
        if (instance == nullptr) {
            instance = new Singleton();
        } 
        return instance;
    }
};
Singleton* Singleton::instance = nullptr;

String

 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

#include <iostream>

class String {
public:
    String() = default;
    // 构造函数
    String(const char* str) {
        m_size = strlen(str);
        m_data = new char[m_size + 1];
        memcpy(m_data, str, m_size + 1);
    }

    // 拷贝构造函数
    String(const String& s) {
        m_size = s.m_size;
        m_data = new char[m_size + 1];
        memcpy(m_data, s.m_data, m_size + 1);
    }

    // 移动构造函数
    String(String&& s) {
        m_size = s.m_size;
        m_data = s.m_data;
        s.m_size = 0;
        s.m_data = nullptr;
    }

    // 赋值函数
    String& operator=(const String& s) {
        if (this != &s) {
            delete m_data;
            m_size = s.m_size;
            m_data = new char[m_size + 1];
            memcpy(m_data, s.m_data, m_size + 1);
        }
        return *this;
    }

    // 析构函数
    ~String() {
        m_size = 0;
        delete[] m_data;
        m_data = nullptr;
    }

    char& operator[](size_t id) {
        return m_data[id];
    }

private:
    char* m_data = nullptr;
    size_t m_size;
    friend std::ostream& operator<<(std::ostream& os, const String& s);
};


// 重载输出流
std::ostream& operator<<(std::ostream& os, const String& s) {
    os << s.m_data;
    return os;
}


int main() {
    String a = "abc";
    std::cout << a << '\n';
    String b = a;
    b[0] = 'q';
    std::cout << b << '\n';
    String c ;
    c = b;
    c[1] = 'w';
    std::cout << b << '\n';
    std::cout << c << '\n';

    return 0;
}

线程池

 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

#include <iostream>
#include <queue>
#include <thread>
class ThreadPool {
public:

    ThreadPool(size_t num_thread = std::thread::hardware_concurrency()) {
        for (size_t i = 0; i < num_thread; i++) {
            threads_.emplace_back([this] () -> void {
                while (true) {

                    std::function<void()> task;

                    // 查看tasks有没有task，或者是否为stop_
                    {
                        std::unique_lock<std::mutex> lock(mutex_tasks_);
                        cv_.wait(lock, [this](){
                            return this->stop_ || !this->tasks_.empty();
                        });
                        if (stop_ && tasks_.empty()) {
                            return;
                        }

                        // 走到这步，队列中一定有任务
                        task = std::move(tasks_.front());
                        tasks_.pop();
                    }

                    task();

                }
            });
        }
    }

    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(mutex_tasks_);
            stop_ = true;
        }
        cv_.notify_all();
        for (auto& thread : threads_) {
            thread.join();
        }
    }

    void enqueue(std::function<void()> task) {
        {
            std::unique_lock<std::mutex> lock(mutex_tasks_);
            tasks_.emplace(std::move(task));
        }
        cv_.notify_one();
    }
private:

    std::vector<std::thread> threads_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mutex_tasks_;
    std::condition_variable cv_;
    bool stop_ = false;
};


int main() {
    ThreadPool tp(3);
    for (int i = 0; i < 5; ++i) {
        tp.enqueue([i]() {
            std::cout << i << ' ' << std::this_thread::get_id() << '\n';
            std::this_thread::sleep_for(std::chrono::microseconds(1000));
        });
    }
    return 0;
}

快排

 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

#include <bits/stdc++.h>

using namespace std;


void quickSort(vector<int>& a, int l, int r) {
    if (l < r) {
        int ptrl = l, ptrr = r;
        int x = a[ptrl];
        while (ptrl < ptrr) {
            while (a[ptrl] <= x and ptrl < r) { // 注意这里是 < r 不是 < ptrr
                ptrl++;
            }
            while (a[ptrr] >= x and ptrr > l) {
                ptrr--;
            }
            if (ptrl < ptrr) {
                swap(a[ptrl], a[ptrr]);
            }
        }
        swap(a[l], a[ptrr]);
        quickSort(a, l, ptrr - 1);
        quickSort(a, ptrr + 1, r);
    }
}

int main() {


    vector<int> a = {3, 5, 1, 8, 9, 4, 2, 6, 0, 1};
    quickSort(a, 1, (int) a.size() - 1);
    for (int i : a) {
        cout << i << ' ';
    }
    return 0;
}

对于顺序的数组，可以先随机洗牌

阅读全文
 Cpp

redis

 发布于  收录于 Database

基础篇

redis命令

通用命令

https://img-blog.csdnimg.cn/direct/7edb39be80224fc9af908caed7424446.png

String类型

https://img-blog.csdnimg.cn/direct/45adff8cd4e54929b431927cfd224774.png

https://img-blog.csdnimg.cn/direct/c1a84a0c6c8c4bc6a300c69d860098b2.png

key的层级结构

e.g.

douyin:user:1

douyin:user:2

douyin:product:1

Hash类型

https://img-blog.csdnimg.cn/direct/d10bc7faa57a4f27ae3131160f40b94d.png

https://img-blog.csdnimg.cn/direct/1d4c3b239ae04cdd987adc882196a78e.png

List类型

https://img-blog.csdnimg.cn/direct/417482b2339e48578d434c83d4302d3f.png

https://img-blog.csdnimg.cn/direct/3d19d9990b5948dab3d83d889018dba1.png

阅读全文
 Redis

docker2

 发布于  收录于 Note

参考链接

Containerize an application

构建应用的镜像

编写Dockerfile，构建镜像（假设镜像名叫getting-started）

1

docker build -t getting-started .

根据镜像创建容器

阅读全文
 Docker

C++中继承和虚函数的关系汇总

 发布于  收录于 Note

类C 继承 类B 继承 类A

基类指针指向派生类对象

如果是C->A, B->A，那么操作A和C时，不会触碰到B

析构函数和成员函数之间互不干扰

如果是像这样 B* b = new B 或者 C* c = new C 这种，那构造函数一定会调用基类的，析构函数一定会调用基类的

阅读全文
 Cpp

C++互斥锁

 发布于  收录于 Note

std::mutex

最简单的互斥锁

 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

// mutex example
#include <iostream>       // std::cout
#include <thread>         // std::thread
#include <mutex>          // std::mutex

std::mutex mtx;           // mutex for critical section

void print_block (int n, char c) {
    // critical section (exclusive access to std::cout signaled by locking mtx):
    // mtx.lock();
    for (int i=0; i<n; ++i) { std::cout << c; }
    std::cout << '\n';
    // mtx.unlock();
}

int main ()
{
    std::thread th1 (print_block,50,'*');
    std::thread th2 (print_block,50,'$');

    th1.join();
    th2.join();

    return 0;
}

输出

阅读全文
 Cpp

C++类继承和可见性

 发布于  收录于 Note

三种继承方式，是否真正继承了，子类可访问吗，外部可访问吗

三种可见性，类自己可访问吗，外部可访问吗

继承默认是private继承

继承和可见性问题

private、protected、public

阅读全文
 Cpp