Lizq的个人博客

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

BF(Brute Force)算法

  • BF是最符合人类直觉的字符串匹配算法，但是主串的下标i经常要往回走，无法利用已匹配信息，效率不够好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int bruteForce(const string& t, const string& p) {
    int i = 0, j = 0;
    // i和j都是非负数，所以可以和无符号直接比较
    while (i < t.size() && j < p.size()) {
        if (t[i] == p[j]) {
            ++i; ++j;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == p.size())
        return i - j;
    else
        return -1;
}

KMP算法

  • 思想：“利用已部分匹配的信息，保持i指针不回溯，通过修改j指针，让模式串尽量移动到有效的位置”
  • 定义next数组： next[j] = d 表示当 t[i] != p[j] 时，j下一次匹配的位置。注意到，下标从0开始，d值实际上是下标j前的最长前后缀子串的长度
  • 求取next的过程本身就是p串与自己匹配的过程
    1. 当 p[i]==p[j] ，则 p[++i] = ++j
    2. 当 p[i]!=p[j] ，则利用前面已求得的next数组，j=next[j] ；直到无法找到，此时 j=-1 ，自动进入第一个if语句，此时i往后走一步，妙
阅读全文 »

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

功能说明

  • 实现+、-、*、/、括号的整数运算
  • 实现处理多余空格

实现1（更高效）

  • 用引用l指针的方式逐步处理
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
int core(string& s, int& l) {
    stack<int> stk;
    int n = s.size();
    int num = 0;
    char sign = '+';
    for (; l < n; ++l) {
        char c = s[l];
        if (isdigit(c)) 
            num = num * 10 + (c - '0');
        // if(c == ' ') continue是不对的，因为l=n-1时一定要最后来一次
        if ((!isdigit(c) && c != ' ') || l == n - 1) {
            if (c == '(') 
                num = core(s, ++l); // 理解这种递归思想很重要
            int prev;
            switch (sign) {
            case '+':
                stk.push(num); break;
            case '-':
                stk.push(-num); break;
            case '*':
                prev = stk.top(); stk.pop();
                stk.push(prev * num);
                break;
            case '/':
                prev = stk.top(); stk.pop();
                stk.push(prev / num);
                break;
            default: break;
            }
            sign = c;
            num = 0;
            if (c == ')') 
                break;
        }
    }
    int ret = 0;
    while (!stk.empty()) {
        ret += stk.top();
        stk.pop();
    }
    return ret;
}

int caculator(string s) {
    int tmp = 0;
    return core(s, tmp);
}
阅读全文 »

发表于 更新于 本文字数： 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;
    }
};
阅读全文 »
0%