头像

半醒的狐狸




离线:12小时前


最近来访(159)
用户头像
不会DP不改名的菜菜子
用户头像
noobcoder
用户头像
jwh
用户头像
Draper
用户头像
Unnatural
用户头像
heMing_zero
用户头像
Egbert-Lannister.
用户头像
cjyasleep
用户头像
Radualin
用户头像
Abcdefg123
用户头像
微机课
用户头像
mainkeys
用户头像
下饭
用户头像
Kole
用户头像
heavens.
用户头像
kwq
用户头像
Fool_vamp
用户头像
372_9
用户头像
KKKKKKKKKKKKKKKKKKKKKK
用户头像
L-China

活动打卡代码 LeetCode 85. 最大矩形

23.03.24 学习

319f305597b2a7384647c0378e1b1b2.png
纪念,力扣Hot100正式刷完,前前后后刷了一个多月,虽然慢但是也完事了,之前基本就刷的差不多了面试够用就没再着急刷,下一目标把算法基础课的数论部分刷完,COYG!!!

还是看wzc大佬的题解,思路非常好,而且和LeetCode84.最大的矩形 思路高度联通,把一维问题扩展到二维,或许不是最快的,但是思路很好想。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size(), res = 0;
        vector<int> heights(m, 0);
        heights.push_back(-1);

        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                if (matrix[i][j] == '0') heights[j] = 0;
                else heights[j] ++ ;
            }
            // for (auto x : heights) cout << x << ' ';
            // cout << endl;

            // 对于每一层的heights都计算一遍res,遍历完m层最大的res就出来了
            stack<int> stk;
            for (int i = 0; i <= m; i ++ ) {
                while (!stk.empty() && heights[i] < heights[stk.top()]) {
                    auto cur = stk.top();
                    stk.pop();

                    if (stk.empty()) res = max(res, heights[cur] * i);
                    else res = max(res, heights[cur] * (i - stk.top() - 1));
                }
                stk.push(i);
            }
        }

        return res;
    }
};



23.03.24 学习

这个题打断点多模拟一下吧,看大佬题解https://www.acwing.com/solution/content/140/

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), res = 0;
        heights.push_back(-1);
        stack<int> stk;

        for (int i = 0; i <= n; i ++ ) {
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                auto cur = stk.top();
                stk.pop();

                if (stk.empty()) res = max(res, heights[cur] * i);  // 左边没有比他低的柱子
                else res = max(res, heights[cur] * (i - stk.top() - 1)); 
            }
            stk.push(i);
        }

        return res;
    }
};



23.03.24 学习

题解太牛了,好难想,也不想用树状数组…,直接&O(n^2)&吧

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        if (a[0] != b[0]) return a[0] > b[0];
        return a[1] < b[1];
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);

        vector<vector<int>> res;
        for(auto p:people) res.insert(res.begin()+p[1],p);

        return res;
    }
};


活动打卡代码 LeetCode 739. 每日温度

23.03.23 学习

这个单调递减栈,有点东西

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> stk;
        vector<int> res(T.size());
        for (int i = T.size() - 1; i >= 0; i -- ) {
            while (stk.size() && T[i] >= T[stk.top()]) stk.pop();
            if (stk.size()) res[i] = stk.top() - i;
            stk.push(i);
        }
        return res;
    }
};



活动打卡代码 LeetCode 621. 任务调度器

23.03.23 学习

wzc1995大佬太强了,同样的人,向他学习

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> t(26, 0);
        for (auto c : tasks) 
            t[c - 'A'] ++ ;

        priority_queue<int> heap;
        for (auto c : t) 
            if (c != 0) 
                heap.push(c);

        int res = 0;
        int interval = n + 1;
        while (true) {
            vector<int> tmp;
            for (int i = 0; i < interval; i ++ ) {
                if (!heap.empty()) {
                    tmp.push_back(heap.top() - 1);
                    heap.pop();
                }
            }

            for (auto x : tmp) {
                if (x)
                    heap.push(x);
            }

            if (heap.empty()) {
                res += tmp.size();
                break;
            } else {
                res += n + 1;
            }
        }

        return res;
    }
};


活动打卡代码 LeetCode 647. 回文子串

23.03.22 学习

和最长回文子串一个路数,那个是取最大,这个是统计总数

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0, n = s.size();
        for (int i = 0; i < s.size(); i ++ ) {
            for (int j = i, k = i; j >= 0 && k < n; j -- , k ++ ) {
                if (s[j] != s[k]) break;
                res ++ ;
            }

            for (int j = i, k = i + 1; j >= 0 && k < n; j -- , k ++ ) {
                if (s[j] != s[k]) break;
                res ++ ;
            }
        }

        return res;
    }
};


活动打卡代码 LeetCode 617. 合并二叉树

23.03.22 学习

简单遍历第一棵树,不用dfs也蛮好想的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
        if (!r1 && !r2) return NULL;
        if (r1 && !r2) return r1;
        if (!r1 && r2) return r2;

        r1->val += r2->val;
        r1->left = mergeTrees(r1->left, r2->left);
        r1->right = mergeTrees(r1->right, r2->right);
        return r1;
    }
};



23.03.22 学习

$O(n)$线性扫描

区间分三段,维护两个指针下标,具体看题解https://www.acwing.com/solution/content/5823/

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < nums.size() - 1 && nums[l] <= nums[l + 1]) l ++ ;
        while (r > l && nums[r - 1] <= nums[r]) r -- ;
        cout << l << ' ' << r << endl;
        if (l == r) return 0;

        for (int i = l + 1; i < nums.size(); i ++ ) 
            while (l >= 0 && nums[i] < nums[l]) 
                l -- ;
        for (int i = r - 1; i >= 0; i -- )
            while (r < nums.size() && nums[i] > nums[r])
                r ++ ;

        return r - l - 1;
    }
};

$O(nlogn)$排序

简单好想

    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> temp;
        temp.assign(nums.begin(),nums.end());
        sort(temp.begin(),temp.end());
        int n = nums.size(),left = 0,right = n - 1;
        while(left < n && nums[left] == temp[left]) left ++;
        while(right >= left && nums[right] == temp[right]) right --;
        return right - left + 1;
    }



23.03.22 学习

ChatGPT版代码,CSDN什么垃圾???

在下面的代码中,我们定义了一个 ThreadPool 类表示线程池。在ThreadPool类的构造函数中,我们创建了指定数量的线程,并将一个 lambda 函数作为线程函数,该 lambda函数不断从任务队列中取出任务并执行。在任务队列为空时,线程将阻塞并等待条件变量 cv的通知。如果线程池被停止且任务队列为空,则线程函数退出,线程被回收。

ThreadPool类的析构函数中,我们将布尔型变量exit设为true,并通知所有线程结束其任务。然后,我们等待所有线程结束并回收其资源。

ThreadPool类还提供了一个add_task()成员函数,用于添加一个新的任务到任务队列中。该函数使用了可变参数模板和lambda函数,将待执行的函数和其参数封装为一个std::function<void()>对象,并将该对象添加到任务队列中。然后,该函数通知一个等待在条件变量cv上的线程以便执行新的任务。

main()函数中,我们创建了一个ThreadPool对象,并向其中添加了8

#include <iostream>
#include <vector>
#include <queue>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>

class ThreadPool {
public:
    ThreadPool(size_t num_threads) : exit(false) {
        for (size_t i = 0; i < num_threads; ++i) {
            threads.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock<std::mutex> lock(mtx);
                        cv.wait(lock, [this] { return exit || !mQueue.empty(); });
                        if (exit && mQueue.empty()) {
                            return;
                        }
                        task = std::move(mQueue.front());
                        mQueue.pop();
                    }
                    task();
                }
                });
        }
    }

    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(mtx);
            exit = true;
        }
        cv.notify_all();
        for (auto& thread : threads) {
            thread.join();
        }
    }

    template<class F>
    void add_task(F&& f)
    {
        {
            std::unique_lock<std::mutex> lock(mtx);
            tasks.emplace(std::forward<F>(f));
        }
        cv.notify_one();
    }

private:
    std::vector<std::thread> threads;
    std::queue<std::function<void()>> mQueue;
    std::mutex mtx;
    std::condition_variable cv;
    bool exit;
};

void foo(int i) {
    std::cout << "begin" << i << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "end " << i << std::endl;
}

int main() {
    ThreadPool pool(4);

    for (int i = 0; i < 8; ++i) {
        pool.add_task([i] { foo(i); });
    }

    return 0;
}




23.03.21 学习

ChatGPT真好用!!!!!

String类

#include <iostream>
#include <cstring>
using namespace std;

/* string类
* 构造函数:
* string(const char* s);        
* string(const string& str);    //拷贝构造,使用一个string对象初始化另一个string对象
* string(string &&str);         //移动构造,使用一个string对象初始化另一个string对象并删掉原对象指针
* 析构函数:
* ~string();
* 重载运算符:
* string & operator=(const string &str);  // 拷贝赋值运算符=,已有对象再赋值
* string & operator=(string & str)        // 移动赋值运算符=,已有对象再赋值,区别类似
* string operator+(const string &str) const;  // 重新+,返回新字符串
* 成员函数:
* size_t size() const;          //获取字符串长度
* 输入输出:
* friend istream& operator>>(istream &is, string &str);
* friend ostream& operator<<(ostream &os, string &str);
*/

class String {
public:
    String() {
        m_size = 0;
        m_data = new char[1];
        *m_data = '\0';
    }

    String(const char* str) {  //通用构造,使用字符串s初始化
        m_size = strlen(str);
        m_data = new char[m_size + 1];
        strcpy(m_data, str);
    }
    String(const String& str) {  //拷贝构造,使用一个string对象初始化另一个string对象
        m_size = str.m_size;
        m_data = new char[m_size + 1];
        strcpy(m_data, str.m_data);
    }
    String(String&& str) : m_data(str.m_data), m_size(str.m_size) {   //移动构造,使用一个string对象初始化另一个string对象并删掉原对象指针
        str.m_data = nullptr;
        str.m_size = 0;
    }

    String& operator=(const String& str) {  // 拷贝赋值运算符=,已有对象再赋值
        if (this != &str) {
            delete[] m_data;
            m_size = str.m_size;
            m_data = new char[m_size + 1];
            strcpy(m_data, str.m_data);
        }
        return *this;
    }
    String& operator=(String&& str) {  // 移动赋值运算符=,已有对象再赋值,区别类似
        if (this != &str) {
            delete[] m_data;
            m_size = str.m_size;
            m_data = str.m_data;
            str.m_data = nullptr;
            str.m_size = 0;
        }
        return *this;
    }
    String operator+(const String& str) const {  // 重新+,返回新字符串
        String newStr;
        newStr.m_size = m_size + str.m_size;
        newStr.m_data = new char[newStr.m_size + 1];
        strcpy(newStr.m_data, m_data);
        strcat(newStr.m_data, str.m_data);
        return newStr;
    }

    size_t size() const {
        return m_size;
    }

    friend istream& operator>>(istream& is, String& str) {  // 重载>>,先申请一块足够大的内存
        char tem[1000];  //简单的申请一块内存
        is >> tem;
        str.m_size = strlen(tem);
        str.m_data = new char[str.m_size + 1];
        strcpy(str.m_data, tem);
        return is;
    }
    friend ostream& operator<<(ostream& os, String& str) {  // 重载<<
        os << str.m_data;
        return os;
    }

    ~String() {
        if (m_data)
            delete[] m_data;
    }

private:
    char* m_data;
    size_t m_size;
};

int main()
{
    String s1 = "123";
    cout << s1 << endl;
    String s2(move(s1));
    cout << s2 << endl;

    return 0;
}

Vector类

#include <iostream>
using namespace std;

template<typename T>
class Vector {
private:
    T* data;
    int size;
    int capacity;
public:
    typedef T* iterator; 

    // 构造函数
    Vector() {
        size = 0;
        capacity = 4;
        data = new T[capacity];
    }
    // 复制构造函数
    Vector(const Vector& other) {
        size = other.size;
        capacity = other.capacity;
        data = new T[capacity];
        for (int i = 0; i < size; i++) {
            data[i] = other.data[i];
        }
    }
    // 析构函数
    ~Vector() {
        delete[] data;
    }
    // 在尾部添加元素
    void push_back(T val) {
        if (size == capacity) {
            reserve(capacity * 2);
        }
        data[size++] = val;
    }
    // 删除尾部元素
    void pop_back() {
        if (size > 0) {
            size--;
        }
    }
    // 重置大小
    void resize(int n) {
        if (n > capacity) {
            reserve(n);
        }
        size = n;
    }
    // 重置容量
    void reserve(int n) {
        if (n > capacity) {
            T* newData = new T[n];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            delete[] data;
            data = newData;
            capacity = n;
        }
    }
    // 获取元素个数
    int getSize() {
        return size;
    }
    // 获取元素容量
    int getCapacity() {
        return capacity;
    }
    // 重载下标运算符
    T& operator[](int i) {
        return data[i];
    }
    // 迭代器
    iterator begin() { return data; }
    iterator end() { return data + size; }
};

int main() {
    Vector<int> v;
    /*
    测试代码
    */

    return 0;
}