笔记汇总

单例模式

#include <iostream>

class Singleton {
    private:
        Singleton();
        Singleton(const Singleton &other);
    public:
        static Singleton *getInstance();
        static Singleton *m_instance;
};

Singleton *Singleton::m_instance = nullptr;

//线程非安全, 懒汉，多线程情况下可能这个对象会被创建两次
Singleton* Singleton::getInstance() {
    if(m_instance == nullptr) {
        m_instance = new Singleton();
    }
    return m_instance;
}

//线程安全，但是锁的代价很高
Singleton *Singleton::getInstance() {
    Lock lock; // 加锁，treadA获取之后，threadB来了也读不了
    if(m_instance == nullptr) {
        m_instance = new Singleton();
    }
    return m_instance;
}

//双检查锁，DCL，但是会发生reorder，正常情况下最后复制给m_instance，但是reorder之后就会先赋值
//这样就出错了。因为可能还没构造就赋值了，这样返回就错了。
Singleton* Singleton::getInstance() {
    // 我们在这里不锁，如果不是nullptr直接返回就行了
    // 这样在高并发只读的情况下非常优秀，避免了上面那种直接加锁的情况
    // 很屌！
    if(m_instance == nullptr) {
        Lock lock;
        if(m_instance == nullptr) {
            m_instance = new Singleton();
        }
    }
    return m_instance;
}

建树

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

#define N 5

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
    TreeNode(): val(0), left(NULL), right(NULL) {}
};

int main() {
    // vector<TreeNode *> nodes;
    // auto root = new TreeNode(0);
    // nodes.push_back(root);
    // for (int i = 1; i <= 5; i ++) {
    //     TreeNode *a = new TreeNode(i);
    //     nodes.push_back(a);
    // }

    // int pr = 0;
    // for (int i = 1; i <= 5;) {
    //     nodes[pr]->left = nodes[i++];
    //     nodes[pr++]->right = nodes[i++];
    // }
    vector<int> node = {0, 1, 2, 5, 4, 3};
    TreeNode allnode[N + 1];
    for (int i = 1; i <= N; i++) {
        allnode[i].val = node[i];
        if (2 * i > N) {
            allnode[i].left = nullptr;
        }
        else {
            allnode[i].left = &allnode[2 * i];
        }
        if (2 * i + 1 > N) {
            allnode[i].right = nullptr;
        }
        else {
            allnode[i].right = &allnode[2 * i + 1];
        }
    }
    TreeNode *tree = &allnode[1];
    stack<TreeNode *> stk;
    stk.push(tree);
    cout << "preOrder:";
    while (!stk.empty()) {
        auto node = stk.top();
        stk.pop();
        cout << node->val << ' ';
        if (node->right)
            stk.push(node->right);
        if (node->left)
            stk.push(node->left);
    }
    cout << endl;
    cout << "inOrder:";
    stack<TreeNode *> _stk;
    auto temp = tree;
    while (temp || !stk.empty()) {
        while (temp) {
            stk.push(temp);
            temp = temp->left;
        }
        temp = stk.top();
        stk.pop();
        cout << temp->val << ' ';
        temp = temp->right;
    }

    cout << endl;
    cout << "cengxu:";
    queue<TreeNode *> q;
    q.push(tree);
    while (!q.empty()) {
        int len = q.size();
        while (len --) {
            auto _node = q.front();
            q.pop();
            cout << _node->val << ' ';
            if (_node->left)
                q.push(_node->left);
            if (_node->right)
                q.push(_node->right);
        }
    }
    cout << endl;
    return 0;
}

LRU缓存

#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>

using namespace std;

class LRUcache {
public:
    LRUcache(int capacity) {
        cap = capacity;
    }
    int get(int key) {
        auto it = _map.find(key);
        if (it == _map.end())
            return -1;
        _list.splice(_list.begin(), _list, it->second);
        return it->second->second;
    }
    void put(int key, int value) {
        auto it = _map.find(key);
        if (it != _map.end()) {
            it->second->second = value;
            _list.splice(_list.begin(), _list, it->second);
            return;
        }
        if (_list.size() == cap) {
            auto last = _list.back();
            _map.erase(last.first);
            _list.pop_back();
        }
        _list.push_front(make_pair(key, value));
        _map[key] = _list.begin();
    }
private:
    int cap;
    list<pair<int, int>> _list;
    unordered_map<int, list<pair<int, int>>::iterator> _map;
};

int main() {
    LRUcache *obj = new LRUcache(3);
    obj->put(1, 1);
    obj->put(2, 2);
    int p1 = obj->get(2);
    obj->put(2, 3);
    obj->put(3, 3);
    int p2 = obj->get(3);
    obj->put(4, 4);
    int p3 = obj->get(1);
    cout << p1 << ' ' << p2 << ' ' << p3;
    return 0;
}

链表

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

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL){}
};

class Solution{
public:
    ListNode* reverseListnode(ListNode* head) {
        ListNode *pre = head;
        ListNode *cur = NULL;
        ListNode *temp = NULL;

        while(pre) {
            temp = pre->next;

            pre->next = cur;
            cur = pre;
            pre = temp;
        }
        return cur;
    }
};

ListNode* buildListnode(vector<int>& res, int begin, int end) {
    if(begin > end)
        return NULL;
    ListNode *root = new ListNode(res[begin]);
    root->next = buildListnode(res, begin + 1, end);
    return root;
}

int main() {
    int node;
    vector<int> res;
    while(cin >> node) {
        res.push_back(node);
    }
    ListNode *head = buildListnode(res, 0, res.size() - 1);
    Solution solution;
    ListNode *ans = solution.reverseListnode(head);
    while(ans->next) {
        cout << ans->val << ' ';
        ans = ans->next;
    }
    cout << ans->val << endl;
    return 0;
}

string类

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

//基本类方法
class String {
    public:
        String(const char *str = NULL);//普通的构造函数, 注意=NULL
        String(const String &other);//拷贝构造函数
        ~String();
        String &operator=(const String &rhs);//=运算符构造，赋值构造函数
        void Show();
    private:
        char *m_data; //保存字符串
};
//方法实现
String::String(const char* str) {
    if(str == NULL) {
        m_data = new char[1];
        *m_data = '\0';
    }
    else {
        int num = strlen(str);
        m_data = new char[num + 1];
        strcpy(m_data, str);
    }
}
String::~String() {
    delete[] m_data;
    m_data = NULL;
    cout << this << "析构" << endl;
}
String::String(const String& other) {
    int len = strlen(other.m_data);
    m_data = new char[len + 1];
    strcpy(m_data, other.m_data);
    cout << "拷贝构造" << endl;
}
//等号运算符重载
//赋值构造函数，将=右边的本类对象的值复制给等号左边的的对象，它不属于构造函数，等号左右两边的对象必须已经被创建
//若没有显示写=运算符重载，系统也会创建一个默认的=运算符重载，只做一个简单的拷贝工作
String & String::operator=(const String &rhs) {
    //首先检测等号右边的是否就是左边的对象本身，如果是，则返回就行
    if(&rhs == this) {
        return *this;
    }
    delete[] m_data;
    int len = strlen(rhs.m_data);
    m_data = new char[len + 1];
    strcpy(m_data, rhs.m_data);
    cout << "=运算符重载，赋值构造函数" << endl;
    return *this;
}
void String::Show() {
    cout << m_data << endl;
}

//测试
int main() {
    //拷贝构造
    String str = "str";
    String str1 = str;
    str1.Show();
    //等号运算符重载构造函数
    // String s1 = "str";
    // String s2;
    // s2 = s1;
    // s2.Show();
    return 0;
}

快排

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

// void quickSort(int *arr, int l, int r) {
//     int left = l;
//     int right = r;
//     if(left >= right)
//         return;//这一步很重要的。。
//     int pivot = arr[left];
//     while(left < right) {
//         while(left < right && arr[right] >= pivot) {//是while不是if,因为一旦当arr[right]>=pivot时候，我们希望right一直减小，而不是只减少一次
//             right--;
//         }
//         if(left < right && arr[right] < pivot) {//这里也要注意&&后面的可以省略，因为一旦跳出上面的while就肯定满足这里的条件，但是left<right不可以省略
//             arr[left] = arr[right];
//         }
//         while(left < right && arr[left] <= pivot) {
//             left++;
//         }
//         if(left < right && arr[left] > pivot) {
//             arr[right] = arr[left];
//         }
//         if(left >= right) {
//             arr[left] = pivot;
//         }
//     }
//     quickSort(arr, l, right - 1);
//     quickSort(arr, left + 1, r);
// }

// int main() {
//     int arr[] = {19, 97, 9, 17, 1, 8, 0};
//     int l = 0;
//     int r = sizeof(arr) / sizeof(arr[0]) - 1;
//     quickSort(arr, l, r);
//     cout << "排序后：" << endl;
//     for (int i = 0; i <= r; ++i) {
//         cout << arr[i] << endl;
//     }
// }

// void quickSort(vector<int> &res, int l, int r) {
//     int left = l, right = r;
//     if(left >= right)
//         return;
//     int pivot = res[left];
//     while(left < right) {
//         while(left < right && res[right] >= pivot) {//是while不是if而且一定注意判断right在判断left前面
//             right--;//一定注意如果是升序：pivot为左边,那么应该是high->low!!!!!!!!!!!!!!!!!!!!!!!
//         }//否则导致基准值错误的情况发生https://blog.csdn.net/lengyishanasme/article/details/99256796
//         if(left < right && res[right] < pivot) {
//             res[left] = res[right];
//         }
//         while(left < right && res[left] <= pivot) {
//             left++;
//         }
//         if(left < right && res[left] > pivot) {
//             res[right] = res[left];
//         }
        
//         if(left >= right) {
//             res[left] = pivot;
//         }
//     }
//     quickSort(res, l, right - 1);
//     quickSort(res, left + 1, r);
// }
void quickSort(vector<int> &res, int l, int r) {
    int left = l, right = r;
    if(left >= right)
        return;
    int pivot = res[left];
    while(left < right) {
        while(left < right && res[right] >= pivot) {
            right--;
        }
        if(left < right && res[right] < pivot) {
            res[left] = res[right];
        }
        while(left < right && res[left] <= pivot) {
            left++;
        }
        if(left < right && res[left] > pivot) {
            res[right] = res[left];
        }
        if(left >= right) {
            res[left] = pivot;
        }
    }
    quickSort(res, l, right - 1);
    quickSort(res, left + 1, r);
}
int main() {
    int n;
    cin >> n;
    vector<int> res;
    while(n--) {
        int temp;
        cin >> temp;
        res.push_back(temp);
    }
    int r = res.size()-1;
    int l = 0;
    quickSort(res, l, r);
    for (int i = 0; i <= r; i++) {
        cout << res[i] << ' ';
    }

    return 0;
}

归并

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

// void merge(vector<int> &nums, int l, int m, int r)
// {
//     int leftsize = m - l;
//     int rightsize = r - m + 1;
//     vector<int> leftnums(leftsize, 0);
//     vector<int> rightnums(rightsize, 0);
//     for (int i = l; i < m; ++i)
//     {
//         leftnums[i - l] = nums[i];
//     }
//     for (int i = m; i <= r; ++i)
//     {
//         rightnums[i - m] = nums[i];
//     }
//     int i = 0, j = 0, k = l;
//     while (i < leftsize && j < rightsize)
//     {
//         if (leftnums[i] < rightnums[j])
//         {
//             nums[k] = leftnums[i];
//             i++;
//             k++;
//         }
//         else
//         {
//             nums[k] = rightnums[j];
//             j++;
//             k++;
//             //count += m - i + 1;
//         }
//     }
//     while (i < leftsize)
//     {
//         nums[k] = leftnums[i];
//         i++;
//         k++;
//     }
//     while (j < rightsize)
//     {
//         nums[k] = rightnums[j];
//         j++;
//         k++;
//     }
// }

// void mergeSort(vector<int> &nums, int l, int r)
// {
//     if (l == r)
//         return;
//     int mid = l + (r - l) / 2;
//     mergeSort(nums, l, mid);
//     mergeSort(nums, mid + 1, r);
//     merge(nums, l, mid + 1, r);
// }
void merge(vector<int> &nums, int l, int m, int r) {
    int leftSize = m - l;
    int rightSize = r - m + 1;
    vector<int> leftNums(leftSize);
    vector<int> rightNums(rightSize);
    for (int i = l; i < m; i++) {
        leftNums[i-l] = nums[i];
    }
    for (int i = m; i <= r; i++) {
        rightNums[i - m] = nums[i];
    }
    int i = 0, j = 0, k = l;
    while(i < leftSize && j < rightSize) {
        if(leftNums[i] < rightNums[j]) {
            nums[k++] = leftNums[i++];
        }
        else {
            nums[k++] = rightNums[j++];
        }
    }
    while(i < leftSize) {
        nums[k++] = leftNums[i++];
    }
    while(j < rightSize) {
        nums[k++] = rightNums[j++];
    }
}
void mergeSort(vector<int> &nums, int l, int r) {
    if(l >= r)
        return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    merge(nums, l, mid+1, r);
}

int main() {
    vector<int> nums = {8, 7, 2, 11, 4, 15, 36, 48, 1, 10, 123, 23, 14, 5};
    int l = 0;
    int r = 13;
    mergeSort(nums, l, r);
    for (int i = 0; i <= r; ++i) {
        cout << nums[i] << endl;
    }
    return 0;
}

冒泡

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

// void maopao(int *arr, int length) {
//     int temp;
//     for (int i = 0; i < length - 1; ++i) {
//         for (int j = 0; j < length - i - 1; ++j) {
//             if(arr[j+1] < arr[j]) {
//                 temp = arr[j];
//                 arr[j] = arr[j+1];
//                 arr[j+1] = temp;
//             }
//         }
//     }
// }

// int main() {
//     int arr[] = {3,2,6,13,12,42,12,5,1,7};
//     int length = sizeof(arr) / sizeof(arr[0]);
//     maopao(arr, length);
//     cout << endl
//          << "排序后：" << endl;
//     for (int i = 0; i < length; ++i) {
//         cout << arr[i] << endl;
//     }
// }

void maopao(vector<int>& res) {
    int len = res.size();
    int t;
    for (int i = 0; i < len-1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if(res[j+1] < res[j]) {
                t = res[j];
                res[j] = res[j+1];
                res[j+1] = t;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> res;
    while(n--) {
        int temp;
        cin >> temp;
        res.push_back(temp);
    }
    maopao(res);
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << ' ';
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,245评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,749评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,960评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,575评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,668评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,670评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,664评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,422评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,864评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,178评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,340评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,015评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,646评论 3赞 323
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,265评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,494评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,261评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,206评论 2赞 352