Skip to content

Files

Latest commit

 

History

History
678 lines (552 loc) · 15.5 KB

常见题.md

File metadata and controls

678 lines (552 loc) · 15.5 KB

排序

class Solution {
public:
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; j++) {
            if (nums[j] < pivot) {
                swap(nums[++i], nums[j]);
            }
        }
        swap(nums[++i], nums[r]);
        return i;
    }
    int random_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; 
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void quick_sort(vector<int>& nums, int l, int r) {
        int flag = true;
        for(int i = l ; i < r ; i++){
            if(nums[i] != nums[i+1])
                flag = false;
        }
        if (l < r && !flag) {
            int pos = random_partition(nums, l, r);
            quick_sort(nums, l, pos - 1);
            quick_sort(nums, pos + 1, r);
        }
    }
    void shiftDown(vector<int>& nums, int i, int len){
        for(; (i<<1) + 1 <= len;){
            int lson = (i<<1) + 1;
            int rson = (i<<1) + 2;
            int large = i;
            if (lson <= len && nums[lson] > nums[large]) {
                large = lson;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            if(large != i){
                swap(nums[i], nums[large]);
                i = large;
            }
            else{
                break;
            }
        }
    }
    void makeHeap(vector<int>& nums, int len){
        for(int i = len/2 ; i >= 0 ; i--){
            shiftDown(nums, i, len);
        }
    }

    void heapSort(vector<int>& nums){
        int len = (int)nums.size()-1;
        makeHeap(nums, i , len);
        for(int i = len ; i >= 1 ; --i){
            swap(nums[i], nums[0]);
            len -= 1;
            shiftDown(nums, 0, len);
        }
    }

    void mergeSort(vector<int>& nums, int l, int r){
        if(l >= r) return;
        int mid = (l+r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid+1 , r);
        int i = l ,j = mid+1;
        int cnt = 0;
        while(i <= mid && j  <= r){
            if(nums[i] <= nums[j]){
                tmp[cnt++] = nums[i++];
            }
            else{
                tmp[cnt++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[cnt++] = nums[i++];
        }
        while(j  <= r){
            tmp[cnt++] = nums[j++];
        }
        for(int i = 0 ; i < cnt ; i++){
            nums[i+l] = tmp[i];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quick_sort(nums, 0, nums.size()-1);
        return nums;
    }
};

合并K个有序列表

class Solution {
public:
    struct cmp{
	bool operator()(const ListNode* a,const ListNode* b) const{
		return a->val>b->val;
	}
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* hair = new ListNode(0);
        ListNode* ans = hair;
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for(auto& list : lists){
            if(list)
                pq.push(list);
        }
        while(!pq.empty()){
            ListNode* cur = pq.top();
            pq.pop();
            if(cur->next){
                pq.push(cur->next);
            }
            hair->next = cur;
            hair = cur;
        }
        return ans->next;
    }
};

反转链表区间

image.png

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode *pre = hair;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next = nullptr;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return hair->next;
    }
};

设计一个hashmap

怎么说呢,题解是用list写的,但是手撕的时候要求用不能用list,让写线性探测

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;
    static const int base = 769;
    static int hash(int key) {
        return key % base;
    }
public:
    /** Initialize your data structure here. */
    MyHashMap(): data(base) {}
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        }
        data[h].push_back(make_pair(key, value));
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }
};

这里给出一个比较满意的解

#include <iostream>
#include <vector>
#include <string>
#include <functional>

template <typename KeyType, typename ValueType>
class HashMap {
private:
    static const int INITIAL_SIZE = 10;
    static const double LOAD_FACTOR_THRESHOLD;
    
    std::vector<std::pair<KeyType, ValueType>> table;
    int size;

    int hash(const KeyType& key) {
        return std::hash<KeyType>{}(key) % table.size();
    }

    void resize() {
        int newSize = table.size() * 2;
        std::vector<std::pair<KeyType, ValueType>> newTable(newSize);
        
        for (const auto& entry : table) {
            int index = hash(entry.first);
            while (!newTable[index].first.empty()) {
                index = (index + 1) % newSize;
            }
            newTable[index] = entry;
        }

        table = newTable;
    }

public:
    HashMap() : table(INITIAL_SIZE), size(0) {}

    void insert(const KeyType& key, const ValueType& value) {
        if ((double)size / table.size() >= LOAD_FACTOR_THRESHOLD) {
            resize();
        }

        int index = hash(key);
        while (!table[index].first.empty()) {
            index = (index + 1) % table.size();
        }
        table[index] = {key, value};
        size++;
    }

    ValueType get(const KeyType& key) {
        int index = hash(key);
        while (!table[index].first.empty()) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = (index + 1) % table.size();
        }
        return ValueType{};
    }

    void remove(const KeyType& key) {
        int index = hash(key);
        while (!table[index].first.empty()) {
            if (table[index].first == key) {
                table[index].first = KeyType{}; // Mark as deleted 使用花括号 {} 是C++11以后的语法,用于直接创建一个临时对象而无需显式指定构造函数参数。
                size--;
                return;
            }
            index = (index + 1) % table.size();
        }
    }
};

template <typename KeyType, typename ValueType>
const double HashMap<KeyType, ValueType>::LOAD_FACTOR_THRESHOLD = 0.7;

int main() {
    HashMap<std::string, int> intHashMap;
    intHashMap.insert("apple", 5);
    intHashMap.insert("banana", 8);
    intHashMap.insert("orange", 12);

    std::cout << "Value for 'apple': " << intHashMap.get("apple") << std::endl;
    std::cout << "Value for 'banana': " << intHashMap.get("banana") << std::endl;
    std::cout << "Value for 'grape': " << intHashMap.get("grape") << std::endl;

    HashMap<std::string, std::string> stringHashMap;
    stringHashMap.insert("name", "Alice");
    stringHashMap.insert("city", "Wonderland");

    std::cout << "Value for 'name': " << stringHashMap.get("name") << std::endl;
    std::cout << "Value for 'city': " << stringHashMap.get("city") << std::endl;

    return 0;
}

相交链表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

设计一个读取返回topn的结构

// 在线面试平台。将链接分享给你的朋友以加入相同的房间。
// Author: tdzl2003<[email protected]>
// QQ-Group: 839088532


class Solution{
private:
  struct Data{
  	string name;
    float score;
    int line;
    // 大顶堆维护 小顶堆需要反转小于号
    bool operater < (const& Data data) const{
      if(abs(score - data.score) < 0.01){
        return score < data.score;
      }
      if(strcmp(data.name, name)!=0){
      	return strcmp(data.name, name);
      }
      return line > data.line;
    }
    bool operater == (const & Data data) const{
    	return abs(score - data.score) < 0.01;
    }
    Data(const Data& data){
    	name = data.name;
      score = data.score;
      line = data.line;
    }
  };
  priority_queue<Data> pq;
  
  vector<Data> solve(int topn){
    csvReader<2> reader;
    int currline = 0;
    Data data;
    vector<int> hash(1001, 0); 
    while(reader.read_line(data.name, data.score)){
      data.line = currline; 
      if(pq.size() < topn || pq.top() == data){
      		hash[int(data.score*10)]++;
        	pq.push(data);
      }
      else if(data < pq.top()){ //小于号是反的
        int pos = pq.top().score*10;
        if(hash[pos] + topn >= pq.size()){
          	while(hash[pos]--){
            	pq.pop();
          }
        }
        hash[int(data.score*10)]++;
        pq.push(data);
      }
      currline++;
    }
    int size = pq.size();
    vector<Data> ans(size);
    for(int i = size-1 ; i >= 0 ; i++){
    	ans[i] = pq.top();
      pq.pop();
    }
    return ans;
  }
  
};

3、5、7的第k个合数

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<int> dp(k + 1);
        dp[1] = 1;
        int p3 = 1, p5 = 1, p7 = 1;
        for (int i = 2; i <= k; i++) {
            int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
            dp[i] = min(min(num3, num5), num7);
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
            if (dp[i] == num7) {
                p7++;
            }
        }
        return dp[k];
    }
};

设计一个生产者消费者模型

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

class Task {
public:
    Task(int id) : id(id) {}

    void execute() {
        std::cout << "Executing task " << id << std::endl;
        // Simulate task execution
        std::this_thread::sleep_for(std::chrono::seconds(1));
    }

    int getId() const {
        return id;
    }

private:
    int id;
};

class ProducerConsumer {
public:
    ProducerConsumer() : buffer_size(5) {}

    void start(int num_producers, int num_consumers) {
        for (int i = 1; i <= num_producers; ++i) {
            producers.emplace_back(&ProducerConsumer::producer, this, i);
        }

        for (int i = 1; i <= num_consumers; ++i) {
            consumers.emplace_back(&ProducerConsumer::consumer, this, i);
        }

        for (auto& producerThread : producers) {
            producerThread.join();
        }

        for (auto& consumerThread : consumers) {
            consumerThread.join();
        }
    }

    void producer(int id) {
        for (int i = 1; i <= 10; ++i) {
            Task task(i);
            std::unique_lock<std::mutex> lock(mtx);
            bufferNotFull.wait(lock, [this] { return buffer.size() < buffer_size; });

            buffer.push(task);
            std::cout << "Producer " << id << " produced task " << task.getId() << std::endl;

            lock.unlock();
            bufferNotEmpty.notify_all();
        }
    }

    void consumer(int id) {
        for (int i = 1; i <= 10; ++i) {
            std::unique_lock<std::mutex> lock(mtx);
            bufferNotEmpty.wait(lock, [this] { return !buffer.empty(); });

            Task task = buffer.front();
            buffer.pop();
            lock.unlock();

            task.execute();
            std::cout << "Consumer " << id << " completed task " << task.getId() << std::endl;

            lock.lock();
            bufferNotFull.notify_all();
        }
    }
    
private:
    int buffer_size;
    std::queue<Task> buffer;
    std::mutex mtx;
    std::condition_variable bufferNotEmpty;
    std::condition_variable bufferNotFull;
    std::vector<std::thread> producers;
    std::vector<std::thread> consumers;
};

int main() {
    ProducerConsumer pc;
    pc.start(3, 2);

    return 0;
}

手写一个简单的线程池

#include <vector>
#include <iostream>
#include <queue>
#include <atomic>
#include <future>

using namespace std;

class threadpool{
private:
    int _size;
    using Task = function<void()>;
    vector<thread> _pool;
    queue<Task> _task;
    mutex _mtx;
    condition_variable _task_cv;
    atomic<bool> _run{true};
    atomic<int> _idleCount{0};
public:
    threadpool(int poolSize):_size(poolSize){
        addThread(poolSize);
    }
    ~threadpool(){
        _run = false;
        _task_cv.notify_all();
        for(auto& thread: _pool){
            if(thread.joinable()){
                thread.join();
            }
        }
    }
    template<typename F, typename... Args>
    auto commit(F&& f,Args&& ...args)->future<decltype(f(args...))>{
        if(!_run){
            throw runtime_error("崩了");
        }
        using RetType = decltype(f(args...));
        auto task = make_shared<packaged_task<RetType>>(
            bind(forward<F>(f), forward<Args>(args)...)
        );
        auto future = task->get_futrue();
        {
            std::lock_guard<std::mutex> lock(_mtx);
            _task.emplace([task](){
                (*task)();
            });

        }
        _task_cv.notify_one();
        return future;
    }
    void addThread(int num){
        if(!_run){
            return;
        }
        while(num--){
            _pool.emplace_back([this]{
                while(true){
                    Task task;
                    unique_lock<mutex> lock(_mtx);
                    _task_cv.wait(lock, [this]{
                        return !_run|| !_task.empty();
                    });
                    _idleCount--;
                    task = move(_task.front());
                    _task.pop();
                    lock.unlock();

                    task();
                    _idleCount++;
                }
            });
            _idleCount++;
        }

    }


};


int main()
{
    cout << "Hello world!" << endl;
    return 0;
}