头像

贺谦

NPU




离线:4天前


分享 AL面试题

贺谦
4天前

题目

按层遍历一棵多叉树,输出层号和节点

代码

#include <iostream>
#include <vector>
#include <memory>
#include <queue>

class TreeNode 
{
public:
    TreeNode(int num) : num_(num) {};
    TreeNode(const TreeNode& rhs) = default;
    ~TreeNode() = default;

    int getNum() const { return num_; }
    void addChild(std::shared_ptr<TreeNode>& child) { children.push_back(child); }
    void addChild(std::shared_ptr<TreeNode>&& child) { children.push_back(child); }
    auto getChild() const { return children; }

private:
    int num_;
    std::vector<std::shared_ptr<TreeNode>> children;
};

void layer(std::shared_ptr<TreeNode>& root) 
{
    typedef std::pair<int, std::shared_ptr<TreeNode>> PIT;
    std::queue<PIT> qe;
    qe.push({1, root});
    while (qe.size()) 
    {
        auto ele = qe.front();
        qe.pop();
        std::cout << ele.first << ' ' << ele.second->getNum() << '\n';

        for (auto &cld : ele.second->getChild()) 
        {
            qe.push({ele.first + 1, cld});
        }
    }
}

int main() 
{
    auto root = std::make_shared<TreeNode>(1);

    root->addChild(std::make_shared<TreeNode>(2));
    root->addChild(std::make_shared<TreeNode>(3));
    root->addChild(std::make_shared<TreeNode>(4));
    layer(root);

    return 0;

}


分享 MARK

贺谦
22天前



贺谦
24天前

原理

  • 优先队列:基于完全二叉树的二叉堆
  • 时间片与线程
  • 线程池的好处1:精准地控制我们申请到的线程的数量
  • 函数就是【待处理的计算任务】
  • 任务队列:如果同时有100个任务,但是只有3个线程

    等任务来了后,任务会先进入任务队列,然后【线程池】中的工作线程会从【任务队列】中依次获取【需要计算的任务】进行操作
    让有限的线程处理更多的任务

  • 延时执行

原理-代码

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <thread>

using namespace std;

class Task
{
public :
    template<typename Func_T, typename ...ARGS>
    Task(Func_T f, ARGS ...args)
    {
        this->func = bind(f, forward<ARGS>(args)...);
    }

    void run()
    {
        this->func();
        return ;
    }

    function<void()> func;
};

void func(int a, int b)
{
    cout << a << "+" << b << "=" << a + b << endl;
    return ;
}

template<typename QueueType = queue<Task*>>
class ThreadPool
{
public :
    ThreadPool(size_t n)
    {
        is_running = true;
        for (int i = 0; i < n; i++)
        {
            threads.push_back(new thread(&ThreadPool::thread_worker, this));
        }
    }

    void thread_worker()
    {
        while (is_running)
        {
            Task* t = this->getOneTask();
            if (t == nullptr) break;
            t->run();
        }
        return ;
    }

    Task* getOneTask()
    {
        // 进入临界区加锁
        unique_lock<mutex> lock(_mtx);

        // 等待任务
        while (is_running && tasks.empty())
        {
            _cdv.wait(lock);
        }

        // 取任务
        Task* t = nullptr;
        if (is_running)
        {
            t = tasks.front();
            tasks.pop();
        }

        return t;
    }

    void addOneTask(Task* t)
    {
        unique_lock<mutex> lock(_mtx);
        tasks.push(t);
        _cdv.notify_one();
        return;
    }

    ~ThreadPool()
    {
        do
        {
            is_running = false;
            unique_lock<mutex> lock(_mtx);
            _cdv.notify_all();
        }while (0);

        for (int i = 0; i < threads.size(); i++)
        {
            threads[i]->join();
            delete threads[i];
        }
        return ;
    }

private:
    vector<thread *> threads;

    bool is_running;

    QueueType tasks;

    mutex _mtx;

    condition_variable _cdv;
};

template
<
    typename T,
    typename Array=vector<T>,
    typename compare_T=less<T>
>
class HeapQueue
{
public:

private:
    Array elements;
    compare_T compare;

    // up
    void up_update()
    {
        int ind = elements.size();
        while (ind > 1 && compare(elements[ind / 2 - 1], elements[ind - 1]))
        {
            swap(elements[ind / 2 - 1], elements[ind - 1]);
            ind /= 2;
        }
        return;
    }

    // down
    void down_update()
    {
        int ind = 0, n = elements.size();
        while (ind * 2 + 1 < n)
        {
            int tind = ind;
            if (compare(elements[tind], elements[ind * 2 + 1]))
            {
                tind = ind * 2 + 1;
            }

            if (ind * 2 + 2 < n && compare(elements[tind], elements[ind * 2 + 2]))
            {
                tind = ind * 2 + 2;
            }

            if (ind == tind) break;

            swap(elements[ind], elements[tind]);
            ind = tind;
        }
    }
};

int main()
{
    Task t1(func, 3, 4);
    Task t2(func, 5, 6);

    t2.run();
    t1.run();

    return 0;
}


分享 手撸strcmp

贺谦
1个月前
  • 字符的本质是【ASCII码】
  • char* s1 = "China"; char* s2 = "China";

    s1 == s2比较的【两个地址】是否相等,而不是【地址指向的内容】是否相等

#include <stdio.h>

int my_strcmp(char* s1, char* s2)
{
    while (*s1 != '\0' && *s2 != '\0')
    {
        if (*s1 > *s2) return 1;
        else if (*s1 < *s2) return -1;
        else
        {
            s1 ++;
            s2 ++;
        }
    }

    if (*s1 == '\0' && *s2 != '\0') return -1;
    else if (*s1 != '\0' && *s2 == '\0') return 1;
    else return 0;
}

// 优化后
int myStrcmp(char* s1, char* s2)
{
    for (; *s1 && *s2; s1 ++, s2 ++)
        if (*s1 != *s2)
            break;
    return *s1 - *s2;
}

int main()
{
    char* s1 = "ahina";
    char* s2 = "zhina";

    int ret = myStrcmp(s1, s2);

    if (ret == 0) printf("s1 == s2\n");
    else if (ret > 0)printf("s1 > s2\n");
    else printf("s1 < s2\n");

    return 0;
}


分享 手撸strcpy

贺谦
1个月前
  • 【数组名】是一个常量
  • strcpy:被拷贝的区域,必须有【足够的空间】容纳
  • strcpy的逻辑:先拷贝,再判断,再++
#include <stdio.h>

char* my_strcpy(char* dest, const char* src)
{
    char* res = dest;
    while (*dest ++ = *src ++);
    return res;
}

int main()
{
    char name[200];
    char name2[200];
    char *pName = "China";

//    strcpy(name, pName);
//    printf("name = %s\n", name);

    my_strcpy(name, my_strcpy(name2, pName));
    printf("name = %s\n", name);

    return 0;
}


分享 手撸strcat

贺谦
1个月前
char* my_strcat(char* dest, char* src)
{
    char* res = dest;
    while (*dest) dest ++;
    while (*dest ++ = *src ++);
    return res;
}

int main()
{
    char firstName[30] = "Jim";
    char middleName[30] = "---";
    char lastName[30] = "Green";

    my_strcat(my_strcat(firstName, middleName), lastName);
    printf("%s\n", firstName);

//    char* p = firstName;
//    char* q = lastName;

//    while (*p) p ++;
//    while (1)
//    {
//        *p = *q;
//        if (*p == '\0') break;
//        p ++;
//        q ++;
//    }
//    printf("%s\n", firstName);

//    while (*p ++ = *q ++);
//    printf("%s\n", firstName);

    return 0;
}


分享 手撸strlen

贺谦
1个月前

一、字符串长度和大小的区别

  • 大小:包括\0
  • 长度:不包括\0

【数组名】是数组【首元素的地址】

#include <stdio.h>
#include <string.h>

int main1()
{
    char *p = "china";    // 将指针赋给了p
    char arr[] = "china"; // 将指针指向的内容赋给了arr指向的一段内存

//    printf("sizeof p = %d\n", sizeof(p));
//    printf("sizeof arr = %d\n", sizeof(arr));

    // char* q = p;
    char* q = arr;
    int cnt = 0;
    while (*q != '\0')
    {
        cnt ++;
        q ++;
    }
    printf("cnt = %d\n", cnt);

    int count = 0;
    char* sq = p;
    for (; *sq ++; count ++);
    printf("count = %d\n", count);

    return 0;
}

int my_strlen(char * q)
{
    int cnt = 0;
    for (; *q ++; cnt ++ );
    return cnt;
}

int main()
{
    char arr[] = "China";
    int res = my_strlen(arr);
    printf("res = %d\n", res);

    return 0;
}



贺谦
1个月前

一、智能指针




贺谦
1个月前
#include <iostream>
#include <string>

using namespace std;

class istream_line_reader 
{
public:
    class iterator
    {
    public:
        typedef ptrdiff_t               difference_type; 
        typedef string                  value_type;
        typedef const value_type*       pointer;
        typedef const value_type&       reference; 
        typedef input_iterator_tag      iterator_category;

        iterator() noexcept : stream_(nullptr) {}

        explicit iterator(istream& is) : stream_(&is)
        {
            ++* this;
        }

        reference operator*() const noexcept
        {
            return line_;
        }

        pointer operator->() const noexcept
        {
            return &line_;
        }

        iterator& operator++()
        {
            getline(*stream_, line_);

            if (!*stream_) 
            {
                stream_ = nullptr;
            }

            return *this;
        }

        iterator operator++(int)
        {
            iterator temp(*this);

            ++* this;

            return temp;
        }

        bool operator==(const iterator& rhs) const noexcept
        {
            return stream_ == rhs.stream_;
        }

        bool operator!=(const iterator& rhs) const noexcept
        {
            return !operator==(rhs);
        }
    private:
        istream* stream_;
        string line_;
    };

    istream_line_reader() noexcept : stream_(nullptr) {}

    explicit istream_line_reader(istream& is) noexcept : stream_(&is) {}

    iterator begin()
    {
        return iterator(*stream_);
    }

    iterator end() const noexcept
    {
        return iterator();
    }

private:
    istream* stream_;
};



贺谦
1个月前

一、写者优先的原则

  • 【读者】与【写者】都等待的时候,【写者】优先访问【缓冲区】

二、进程优先级互斥的实现

  • 【互斥信号量】—— rw_sem用于读者写者之间的互斥,rw_sem的初值为1
  • 【读者】对rw_sem的操作——读者申请到rw_sem后,在读操作前立即释放
  • 【写者】对rw_sem的操作——写者申请到rw_sem后,占用rw_sem直到阻塞在【等待队列】的写者都完成工作

三、共享数据(临界资源)的互斥

  • 【信号量file_src_sem

四、读者写者等待进程数量

  • rc——当前在读的读者进程数
  • wc——当前阻塞排队的写者进程数

    rc, wc也是多个读者/写者访问的临界资源,所以也需要【信号量】进行保护——
    rc_sem(多个读者之间互斥), wc_sem(多个写者之间互斥)