Lizq的个人博客

发表于 更新于 本文字数： 758 阅读时长 ≈ 3 分钟

Map和Set

  • Map是<key, value>结构；Set是<key>结构，天然具有去重功能
  • 自定义类放入Map或Set需要实现bool operator<(const MyClass& ano) const，注意里面的两个const是必备的，不能漏
  • 不用实现operator=，因为a<b == false && a>b == false会自动推断出等于

0、示范图

1
2
3
4
5
6
7
8
9
         0
         |
        (1)
         |
2 —(1)—  1  —(1)— 3
   \           /
   (3)       (2)
      \     /
         4

1、错误代码示例

阅读全文 »

发表于 更新于 本文字数： 743 阅读时长 ≈ 3 分钟

单例模式

0、静态函数变量版本

利用C++特性

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
template <class T>
class SingleTon {
public:
    static T& GetInstance() {
        static T ins;
        return ins;
    }
    SingleTon(const SingleTon&) = delete;
    SingleTon& operator=(const SingleTon&) = delete;
    virtual ~SingleTon() {}
protected:
    SingleTon() {}
};

class Apple : public SingleTon<Apple> {
    friend SingleTon<Apple>; // 友元
public:
    void show() {
        cout << __FUNCTION__ << endl;
    }
    ~Apple() {
        cout << __FUNCTION__ << endl;
    }
protected:
    Apple() {}
};

class Orange : public SingleTon<Orange> {
    friend SingleTon<Orange>; // 友元
public:
    ~Orange() {
        cout << __FUNCTION__ << endl;
    }
    void show() {
        cout << __FUNCTION__ << endl;
    }
protected:
    Orange() {}
};

int main() {
    Apple::GetInstance().show();
    cout << &Apple::GetInstance() << endl;
    Apple::GetInstance().show();
    cout << &Apple::GetInstance() << endl;
    Orange::GetInstance().show();
    Orange::GetInstance().show();
    return 0;
}

1、普通版本（高并发效率不足）（安全）

阅读全文 »

发表于 更新于 本文字数： 235 阅读时长 ≈ 1 分钟

线程安全的share指针

1. 代码部分

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <mutex>
using namespace std;

class Counter{
public:
    Counter(): m_Counter(0) {}
    Counter(const Counter&) = delete;
    Counter& operator=(const Counter&) = delete;
    ~Counter() {}
    void reset() { m_Counter = 0; }
    unsigned int get() const { return m_Counter; }
    void operator++() { m_Counter++; }
    void operator++(int) { m_Counter++; }
    void operator--() { m_Counter--; }
    void operator--(int) { m_Counter--; }

private:
    unsigned int m_Counter{}; // 花括号也可以初始化
};

template<typename T>
class SharedPtr{
public:
    explicit SharedPtr(T *ptr = nullptr): // explicit
        pData(ptr),
        pCounter(new Counter()),
        pMutex(new std::mutex)
    {
        if (ptr) {
            addCount();
        }
    }

    SharedPtr(const SharedPtr<T>& sp) {
        pData = sp.pData;
        pCounter = sp.pCounter;
        pMutex = sp.pMutex;
        addCount();
    }

    SharedPtr<T>& operator=(const SharedPtr<T>& sp) {
        if (pData != sp.pData) {
            subCount();
            pData = sp.pData;
            pCounter = sp.pCounter;
            pMutex = sp.pMutex;
            addCount();
        }
    }

    T* operator->() { return pData; }

    T& operator*() { return *pData; }

    T* get() { return pData; }

    unsigned int getCount() { return pCounter->get(); }

    ~SharedPtr() { subCount(); }

private:
    void addCount() {
        pMutex->lock();
        ++(*pCounter);
        pMutex->unlock();
    }

    void subCount() {
        bool deleteflag = false;
        pMutex->lock();
        --(*pCounter);
        if (pCounter->get() == 0) {
            delete pCounter;
            delete pData;
            deleteflag = true;
        }
        pMutex->unlock();
        if (deleteflag == true) delete pMutex;
    }

private:
    T *pData;
    std::mutex *pMutex;
    Counter *pCounter;
};

class MyClass {
public:
    MyClass() {
        cout << "Constructor" << endl;
    }
    ~MyClass() {
        cout << "Destructor" << endl;
    }
};

int main() {
    SharedPtr<MyClass> p(new MyClass());
    SharedPtr<MyClass> p2 = p;
    cout << "END" << endl;
    return 0;
}

2. 参考资料

阅读全文 »

发表于 更新于 本文字数： 547 阅读时长 ≈ 2 分钟

540 有序数组中的单一元素

我的二分

  • 与右侧配对失败:
    • 右侧是奇数: l = m + 1
    • 右侧是偶数: r = m
  • 与右侧配对成功:
    • 右侧是奇数: l = m + 2
    • 右侧是偶数: r = m - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l < r){ // 这样可以放心取m+1不越界
            int m = (l + r) >> 1;
            if(nums[m] != nums[m+1]){
                if((r-m) & 1) l = m + 1;
                else r = m;
            }else{
                if((r-m-1) & 1) l = m + 2;
                else r = m - 1;
            }
        }
        return nums[l];
    }
};

官方的全数组二分查找

阅读全文 »

发表于 更新于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

1 寻找峰值

找到任意一个峰值，你可以假设 nums[-1] = nums[n] = -∞ 。

1.1 二分法（不怎么优雅）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l <= r){
            int m = (l + r) / 2;
            if(m-1>=0 && nums[m-1]>nums[m])
                r = m - 1;
            else if(m+1<nums.size() && nums[m+1]>nums[m])
                l = m + 1;
            else
                return m;
        }
        return 0; // 永远不会走
    }
};

1.2 二分法（优雅）

阅读全文 »

发表于 更新于 本文字数： 468 阅读时长 ≈ 2 分钟

83 删除排序链表中重复元素

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode* ptr = head->next;
        while(ptr && head->val == ptr->val) ptr = ptr->next;

        // 下面俩方式效果一样
        head->next = deleteDuplicates(ptr);
        // head->next = ptr;
        // deleteDuplicates(ptr);
        return head;
    }
};

后续遍历

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        // 有点像并查集里的路径压缩
        head->next = deleteDuplicates(head->next);
        if(head->next && head->val == head->next->val)
            return head->next;
        return head;
    }
};
阅读全文 »

发表于 更新于 本文字数： 665 阅读时长 ≈ 2 分钟

1143 最长公共子序列

  • 子序列是可以不连续的
  • dp[i][j]的含义是text1[:i]和text2[:j]最长公共子序列，这个最长公共子序列不一定包含text1[i]和text2[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 多一行一列
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; // 别忘了坐标偏移
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

718 最长重复子数组

  • 子数组是连续的
  • dp[i][j]的含义是以nums1[i]结尾的nums1[:i]和以nums2[j]结尾的nums2[:j]的最长重复子数组
阅读全文 »

发表于 更新于 本文字数： 1.6k 阅读时长 ≈ 6 分钟

零. 子集、组合和排列问题汇总

  • 组合问题和子集问题是等价的
  • 参考labuladong和优秀题解

一. 子集问题

78 子集划分

1.1 子集扩张

阅读全文 »

发表于 更新于 本文字数： 472 阅读时长 ≈ 2 分钟

43 字符串相乘

两数A位和B位，相加后位数最大为max(A, B)+1；相乘后最大位数为A+B

1.1 常规法

将两个串的指针位置m和n、进位c统一放入while循环，代码就会很优美。 代码可以继续优化速度存储：addtion函数改为原地相加，但是会破坏代码的逻辑性，就不改了。

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
class Solution {
public:
    string addtion(string& num1, string& num2){
        int m = num1.size()-1, n = num2.size()-1;
        int c = 0;
        string ret;
        while(m>=0 || n>=0 || c){
            int a = m>=0 ? num1[m]-'0' : 0; // 越界定0技巧
            int b = n>=0 ? num2[n]-'0' : 0; // 越界定0技巧
            int s = a + b + c;
            ret.push_back('0' + s % 10);
            c = s / 10;
            --m, --n;
        }
        reverse(ret.begin(), ret.end()); // 反转
        return ret;
    }
    
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0") return "0";
        string res = "0";
        int cnt = 0; // 记录表示每次乘完左移的0的个数
        int m = num2.size()-1;
        while(m >= 0){
            int n = num1.size()-1;
            int b = num2[m] - '0';
            int c = 0;
            string ret(cnt, '0'); // 初始化"左移"0
            while(n>=0 || c){
                int a = n>=0 ? num1[n]-'0' : 0; // 越界定0技巧
                int s = a * b + c;
                ret.push_back('0' + s % 10);
                c = s / 10;
                --n;
            }
            reverse(ret.begin(), ret.end()); // 反转
            res = addtion(res, ret);
            --m, ++cnt;
        }
        return res;
    }
};
阅读全文 »

发表于 更新于 本文字数： 543 阅读时长 ≈ 2 分钟

1. 124 二叉树中的最大路径和

1.1 两个递归的笨方法

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
class Solution {
public:
    int ans = INT_MIN;
    int core(TreeNode* root) { // 找到以root为起点，深入向下的最大路径一条线（分叉只走一条）
        if(!root) return 0;
        int lv = core(root->left);
        int rv = core(root->right);
        int res = max(max(lv, rv), 0) + root->val;
        return res;
    }
    
    void recursion(TreeNode* root){ // 遍历树中每个结点，尝试寻找本题答案的“起点根”
        if(!root) return;
        recursion(root->left);
        recursion(root->right);
        int lv = core(root->left); // 以左孩子为起点的“线”
        int rv = core(root->right); // 以右孩子为起点的“线”
        if(lv < 0) lv = 0;
        if(rv < 0) rv = 0;
        ans = max(ans, lv + rv + root->val);
    }
    
    int maxPathSum(TreeNode* root) {
        recursion(root);
        return ans;
    }
};

1.2 一个递归的好方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int ans = INT_MIN;
    int core(TreeNode* root) {
        if(!root) return 0;
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int lv = max(core(root->left), 0);
        int rv = max(core(root->right), 0);
        
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int ifAnsRoot = root->val + lv + rv;
        ans = max(ans, ifAnsRoot);
        
        // 返回
        return max(lv, rv) + root->val;
    }
    
    int maxPathSum(TreeNode* root) {
        core(root);
        return ans;
    }
};
阅读全文 »
0%