Lizq的个人博客

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

1. 插入排序

  • 只要注意每次判断比前面的大那就不需要回头
  • 否则需要从头找合适的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* insertSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode dummy; dummy.next = head;
    ListNode* prev = head;
    ListNode* curr = head->next;
    while (curr) {
        if (prev->val <= curr->val) {
            prev = curr;
            curr = curr->next;
        } else {
            ListNode* t = &dummy;
            while (t->next && t->next->val <= curr->val) t = t->next;
            prev->next = curr->next;
            curr->next = t->next;
            t->next = curr;
            curr = prev->next;
        }
    }
    return dummy.next;
}

2. 归并排序

  • 不论是主递归还是merge都要求两个链表以nullptr结尾
  • 也就是在合适的地方断开
阅读全文 »

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

一、简单排序

  • 定义：对于下标$i<j$，如果$A[i]>A[j]$，则称$(i,j)$是一对逆序对（inversion）
  • 定理：任意$N$个不同元素组成的序列平均具有$N(N-1)/4$个逆序对。
  • 定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为$Ω(N^2)$

1. 冒泡排序

  • 时间复杂度：$O(N^2)$
  • 最好情况下的时间复杂度，有序$O(N)$
  • 空间复杂度：$O(1)$
  • 稳定（比较相等时，是不做交换的）
  • end标记可以提前结束
  • 链表也可用
  • 每次交换都会消除一对逆序对
    • 如果$I$是逆序对的个数，时间复杂度是$O(N+I)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int end = 1;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                end = 0;
            }
        }
        if (end)
            break;
    }
}
阅读全文 »

发表于 更新于 本文字数： 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 子集扩张

阅读全文 »
0%