zkkKillua's Blog
0%

发表于 更新于 分类于

本篇博客全文转载自https://blog.twofei.com/496/

前言

大家都应该知道C++的精髓是虚函数吧? 虚函数带来的好处就是: 可以定义一个基类的指针, 其指向一个继承类, 当通过基类的指针去调用函数时, 可以在运行时决定该调用基类的函数还是继承类的函数. 虚函数是实现多态(动态绑定)/接口函数的基础. 可以说: 没有虚函数, C++将变得一无是处!

既然是C++的精髓, 那么我们有必要了解一下她的实现方式吗? 有必要! 既然C++是从C语言的基础上发展而来的, 那么我们可以尝试用C语言来模拟实现吗? 有可能! 接下来, 就是我一步一步地来解析C++的虚函数的实现方式, 以及用C语言对其进行的模拟.

C++对象的内存布局

阅读全文 »

发表于 更新于 分类于

先说结论：

当函数的返回值类型未规定时，默认为int类型，并且此时的函数可以通过return返回值，返回值的类型需要能够转换到int。这个规则适用于普通函数和成员函数。

写代码的时候发现了一个很有意思的事情，当我没有规定函数返回值类型的时候，编译和运行都是不会出错的。

1
2
3
4
5
6
7
8
9
func () {
    cout << "This is a func()" << endl;
}

int main () {
    cout << typeid(func()).name();        // #include <typeinfo>
    
    return 0;
}

同时可以获得func()的返回值是一个i，即int类型。

阅读全文 »

发表于 分类于

1. 中序遍历

看到二叉搜索树优先考虑“二叉搜索树的中序序列是递增的”。
获取中序序列后两两比较差值。
时间O(n)，空间O(n)。 

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        stack<TreeNode*> st;

        while (root != nullptr || !st.empty()) {
            if (root == nullptr) {
                TreeNode* temp = st.top();
                st.pop();
                nums.push_back(temp->val);
                root = temp->right;
            } else {
                st.push(root);
                root = root->left;
            }
        }

        int ans = INT_MAX, n = nums.size();
        for (int i = 1; i < n; i++)
            ans = min(ans, nums[i] - nums[i - 1]);
        
        return ans;
    }
};

发表于 分类于

1. 递归+回溯

第一反应是“40. 组合总和 II”，有重复数字，不能重复选择。
首先求出数组总和，然后就变成了找是否存在目标为sum/2的组合问题。
时间复杂度O(2^n)（每个元素选或不选），空间复杂度O(1)。
超时

“40. 组合总和 II”用dfs是因为它需要记录所有的方案，而这道题目只需要方案数，所以不需要在dfs过程中隐式包含的路径。 

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
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        bool ans = false;
        for (int i = 0; i < n; i++) 
            sum += nums[i];
        
        if (sum % 2 == 0) {
            sort(nums.begin(), nums.end());
            ans = dfs(nums, 0, sum / 2);
        }

        return ans;
    }
private:
    bool dfs(vector<int>& nums, int beg, int target) {
        if (target < 0)
            return false;
        if (target == 0)
            return true;
        
        bool ans = false;
        for (int i = beg; i < nums.size(); ++i) {
            if (nums[i] > target)
                break;
            ans = dfs(nums, i + 1, target - nums[i]);
            if (ans)
                break;
        }

        return ans;
    }
};

2. 背包

阅读全文 »

发表于 分类于

1. hash表

遍历链表，使用hash表记录途中的节点，直到到达链表尾或者出现hash表中储存的节点，该节点即为环的入口。
时间O(n)，空间O(n)。 

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> table;
        ListNode* ans = nullptr;

        while (head != nullptr) {
            if (table.count(head)) {
                ans = head;
                break;
            }
            table.insert(head);
            head = head->next;
        }

        return ans;
    }
};

2. 双指针

参考“关于环形链表的一切”。
设置快指针速度为2，慢指针速度为1，首先获得二者的相遇点（如果有环的话），然后另设一个速度为1的指针从起点出发，与慢指针同步前进，二者的相遇位置即为环的入口。
时间O(n)，空间O(1)。

阅读全文 »

发表于 更新于 分类于

首先可以得到的结论是：

只要快慢指针从同一起点出发，则一定能相遇（从起点出发，在环长度的倍数倍位置上一定能相遇，不论快慢指针步长如何。但首次相遇位置不一定在此处），并且当快指针速度是慢指针的整数倍时，相遇时慢指针在圆环中移动的距离不足一周。

原因是，设圆环外链表长度为k，圆环长度为n，快指针速度是慢指针的r倍。

先考虑r为整数的情况：

令慢指针前进S（S为n的倍数，并且满足k<=S<k+n）距离，保证慢指针能够位移进入圆环，此时，快指针移动的距离为rS，可以看作先前进了S到达慢指针前进S到达的地点，又前进了(r-1)S，这部分为n的倍数，相当于转圈。因此便证明了上述结论。

阅读全文 »

发表于 更新于 分类于

一. 输入和输出运算符

1
2
3
4
5
6
7
8
9
10
11
class A {
    friend ostream& operator << (ostream& os, const A& item) {
        os << "something";        // without `endl`
        return os;
    }
    
    friend istream& operator >> (istream& is, A& item) {
        in >> item.something;
        return is;
    }
};

1. 输出运算符

第一个形参使用非常量的ostream对象的引用，第二个形参使用常量的引用。

ostream非常量是因为向流写入内容会改变其状态；第二个形参使用常量是为了避免修改对象内容，引用是为了避免调用复制构造函数。

阅读全文 »

发表于 更新于 分类于

1. 复制构造函数被调用的三种情况

  1. 使用已有的对象创建新的对象。

    1
    2
    A a1(a);
    A a2 = a;

  2. 函数的参数类型是对象。

    1
    void func(A a);

  3. 函数返回值的类型是对象。

    1
    A func();

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
#include <iostream>

using namespace std;

class A {
public:
    A() { cout << "constructor" << endl; }
    ~A() { cout << "destructor" << endl; }
    A(const A& a) { cout << "copy constructor" << endl; }
};

A func() {
    A a;
    cout << "func()" << endl;
    return a;
}

int main()
{
    A a = func();
    
    cout << "return" << endl;
    return 0;
}

运行结果为：

阅读全文 »

发表于 更新于 分类于

1. const常量

1
2
3
4
const int a = 10;
int const a = 10;

const int a;    // error 需要在创建时初始化

当以编译时初始化的方式定义一个const 对象时，编译器将在编译过程中把用到该变量的地方都替换成对应的值。
为了执行上述替换，编译器必须知道变量的初始值。

默认情况下， const 对象被设定为仅在文件内有效。
如果想只在一个文件中定义const，而在其他多个文件中声明并使用它。

1
2
3
4
// file_l.cc 定义并初始化了一个常量，该常量能被其他文件访问
extern const int bufSize =fcn ();
// file_l.h 头文件
extern const int bufSize; // 与file_l.cc中定义的bufSize是同一个

2. const引用

const修饰引用表示不能通过引用修改值，如果引用的是常量，则引用必须也是const。

阅读全文 »

发表于 分类于

1. 层次遍历

层次遍历获得同一层的节点，然后依次让next指向右侧的节点。
时间O(n)，空间O(n)。 

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr)
            return nullptr;

        queue<Node*> q;
        Node* cur = root;
        q.push(cur);
        while (!q.empty()) {
            int n = q.size();
            while (n-- > 0) {
                cur = q.front();
                q.pop();
                if (cur->left != nullptr)
                    q.push(cur->left);
                if (cur->right != nullptr)
                    q.push(cur->right);
                if (n > 0)
                    cur->next = q.front();
            }
        }

        return root;
    }
};

2. 迭代

通过上一层已经构造好的next指针获取下一层新的节点，并不断修改下一层节点的next值。
时间O(n)，空间O(1)。

阅读全文 »