LeetCode
34 分钟 读完 (大约 5132 个字)

2020-04 LeetCode每日一题做题记录

Apr.30 快乐数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isHappy(self, n: int) -> bool:
        def change(x: int) -> int:
            ret = 0
            while x:
                x, digit = divmod(x, 10)
                ret += digit * digit
            return ret
        
        st = set()
        while n not in st:
            if n == 1:
                return True
            st.add(n)
            n = change(n)
        return False

Apr.29 山脉数组中查找目标值

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
// 4 ms, 7.2 MB
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    template<typename Func>
    int binary_search(MountainArray& mountainArr, int target, int l, int r, Func func) {
        target = func(target);
        while (l <= r) {
            int mid = (l + r) / 2;
            int cur = func(mountainArr.get(mid));
            if (cur == target) return mid;
            if (cur < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }

    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0, r = mountainArr.length() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int peak = l;
        int index = binary_search(mountainArr, target, 0, peak, [](int x) {
            return x;
        });
        if (index != -1) return index;
        index = binary_search(mountainArr, target, peak + 1, mountainArr.length() - 1, [](int x) {
            return -x;
        });
        return index;
    }
};

Apr.28 数组中数字出现的次数

分组异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 40 ms, 16.1 MB
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xor_all = 0;
        for (int val : nums) xor_all ^= val;
        // xor_all 中 1 的位表示两个只出现过一次的数中这一位不同
        int bit = xor_all & -xor_all; // 以 lowbit(xor_all) 区分两个组别
        int a = 0, b = 0; // 对这两个组别分别做异或
        for (int val : nums) {
            if (val & bit) a ^= val;
            else b ^= val;
        }
        return {a, b};
    }
};

Apr.27 搜索旋转排序数组

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
// 0 ms, 6.4 MB
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return -1;
        }

        int p = 0, q = 1;
        while (q) {
            if (p + q >= nums.size() || nums[p + q] < nums[p]) {
                q >>= 1;
            } else {
                p += q;
                q <<= 1;
            }
        }

        // nums[p] is the biggest value in nums.
        int l, r;
        if (target >= nums[0]) { // the target's index is in [0, p].
            l = -1;
            r = p + 1;
        } else { // the target's index is in [p+1, nums.size()-1].
            l = p;
            r = nums.size();
        }
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l >= 0 && nums[l] == target ? l : -1;
    }
};

Apr.26 合并K个排序链表

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
// 60 ms, 10.4 MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct Cmp {
        bool operator()(const ListNode* a, const ListNode* b) const {
            return a->val > b->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        
        for (ListNode* listHead : lists) {
            if (listHead) heap.push(listHead);
        }
        
        ListNode dummy;
        ListNode* last = &dummy;
        while (!heap.empty()) {
            ListNode* now = heap.top();
            heap.pop();
            
            if (now->next) heap.push(now->next);
            
            last->next = now;
            last = now;
        }
        
        return dummy.next;
    }
};

Apr.25 全排列

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 4 ms, 7.4 MB
class Solution {
public:
    void dfs(vector<vector<int>>& ans, vector<int>& now, const vector<int>& nums, int visit) {
        if (visit == (1 << nums.size()) - 1) {
            ans.emplace_back(now);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!((visit >> i) & 1)) {
                now.push_back(nums[i]);
                dfs(ans, now, nums, visit ^ (1 << i));
                now.pop_back();
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tmp;
        dfs(ans, tmp, nums, 0);
        return ans;
    }
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 4 ms, 7.2 MB
class Solution {
public:
    void solve(vector<vector<int>>& res, vector<int>& nums, int pos) {
        if (pos == nums.size()) {
            res.emplace_back(nums);
            return;
        }
        for (int i = pos; i < nums.size(); i++) {
            swap(nums[pos], nums[i]);
            solve(res, nums, pos + 1);
            swap(nums[pos], nums[i]);
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        solve(ans, nums, 0);
        return ans;
    }
};
阅读更多
C++
3 分钟 读完 (大约 381 个字)

C++右值引用

Rvalue references

在C++0x中介绍了一种新的引用类型：右值引用，它帮助解决了不必要的拷贝问题和允许了完美转发的存在。当赋值的右手边（right-hand side）是一个右值时，左手边（left-hand side）的对象就可以偷走右手边对象的资源，而不是进行一次独立的分配，也就诞生了”移动语义“。

左值：可以出现在 operator= 左侧者。

右值：只能出现在 operator= 右侧者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
using namespace std;

int main() {
    int a = 9;
    int b = 4;
    // a + b = 42; // error: lvalue required as left operand of assignment

    string s1("Hello ");
    string s2("World");
    s1 + s2 = s2; // s1 + s2 可以当做左值！
    cout << s1 << endl;
    cout << s2 << endl;
    string() = "World"; // 可以对临时对象赋值！
}

C++在用户自定义类型中会产生一些细微的问题，这些问题有关于修改或赋值动作。这种问题就导致上面的定义不正确。

（但是仍然应把临时对象认为是右值。）

当右值出现在 operator= （拷贝赋值，copy assignment）的右侧，我们认为对资源进行偷取/搬移（move）而非拷贝（copy）是合理的。则

  1. 必须有语法让我们在调用端告诉编译器“这是个右值”
  2. 必须有语法让我们在被调用端写出一个专门处理右值的所谓移动赋值（move assignment）函数
C++
34 分钟 读完 (大约 5115 个字)

C++的4种类型转换

static_cast

用隐式和用户定义转换的组合在类型间转换。

语法

static_cast <new_type> (expression) 返回 new_type 类型的值。

解释

唯有下列转换能用 static_cast 执行，但若转换会转型走常量性或易变性则亦不允许。

  1. 若存在从 expression 到 new_type 的隐式转换序列，或者若针对以 expression 到 new_type 类型的对象或引用所进行的直接初始化的重载决议，找到至少一个可行函数，则 static_cast <new_type> (expression) 返回如同以 new_type Temp(expression); 所初始化的一个虚构变量 Temp，它可能涉及隐式转换，对 new_type 的构造函数的调用，或对用户定义转换运算符的调用。对于非引用的 new_type，static_cast 纯右值表达式的结果对象是其直接初始化的对象。 (C++17 起)

  2. 若 new_type 是某类类型 D 的左值或指向它的指针纯右值，而 expression 的类型是到其非虚基类 B 的指针或引用，则 static_cast 进行向下转型（downcast）。若 B 是 D 的有歧义、不可访问或虚的基类（或虚基类的基类），则此向下转型非良构。这种 static_cast 并不进行用以确保该对象的运行时类型确实是 D 的运行时检查，而且仅当这项前提条件由其他方法所保证时才能安全使用，例如在实现静多态时。可以用 dynamic_cast 执行安全的向下转型。

    1
    2
    3
    4
    5
    struct B { };
    struct D : B { };
    D d;
    B& br = d;
    static_cast<D&>(br); // 左值指代原初的 d 对象

  3. (本条自C++11起) 若 new_type 是右值引用类型，则 static_cast 将泛左值、类纯右值或数组纯右值 (C++17 前) 任何左值 (C++17 起) expression 的值转换为与该表达式指代相同对象，或指代其基类子对象（取决于 new_type）的亡值。若目标类型是表达式的不可访问或有歧义基类，则程序非良构。若表达式是位域左值，则它首先被转换成底层类型的纯右值。这种 static_cast 用于在 std::move 中实现移动语义。

  4. 若 new_type 是（可为 cv 限定的）void 类型，则 static_cast 在求值 expression 后舍弃其值。

  5. 若存在从 new_type 到 expression 类型的标准转换序列，且它不包含左值到右值、数组到指针、函数到指针、空指针、空成员指针、函数指针 (C++17 起)或布尔转换，则 static_cast 能进行该隐式转换的逆转换。

  6. 若从 expression 到 new_type 涉及左值到右值、数组到指针或函数到指针转换，则能显式用 static_cast 进行。

  7. 有作用域枚举类型(C++11)能转换成整数或浮点类型。

    1. 当目标类型为 cv bool 时，若原值为零则结果为 false，而对所有其他值结果为 true。对于其余整型类型，若该枚举的值能以目标类型表示，则结果为其值，否则结果未指明。(C++20前)
    2. 其结果与从枚举的底层类型隐式转换成目标类型的结果相同。 (C++20 起)

  8. 整数或枚举类型值可转换为任何完整枚举类型。

    • 若底层类型不固定，则当 expression 的值落在范围（范围是大到足以保有目标枚举的所有枚举项的最小位域的所有可能值）外时，结果未指明 (C++17 前) 或 为未定义行为 (C++17 起)。

    • 若底层类型固定，则其结果与转换原值到枚举的底层类型再到该枚举类型的结果相同。

      浮点类型的值也可转换为任何完整枚举类型。

    • 其结果与转换原值到枚举的底层类型再到该枚举类型的结果相同。

  9. 指向某类 D 的成员的指针可以向上转型（upcast）为指向其无歧义、可访问的基类 B 的成员。这种 static_cast 不进行用以确保成员实际存在于所指向对象的运行时类型的检查。

  10. 指向（可有 cv 限定）void 的指针类型的纯右值可转换到指向任何对象的指针类型。若原指针值所表示的内存中字节地址不满足目标类型的对齐要求，则结果指针值未指明。否则，若原指针值指向对象 a，且存在与 a 指针可互转换（定义于下文）的目标类型的（忽略 cv 限定）对象 *b，则结果为指向 *b 的指针。否则指针值不改变。任何指针转换到 void 指针，再转换回原（或更为 cv 限定的）类型的指针，都保持其原值。

同所有转型表达式，结果是：

  • 左值，若 new_type 是左值引用或到函数类型的右值引用；
  • 亡值，若 new_type 是到对象类型的右值引用；
  • 否则为纯右值。

满足以下条件时，两个对象 a 与 b 指针可互转换（pointer-interconvertible）：

  • 它们为同一对象，或
  • 一个是 union 对象而另一个是该对象的非静态数据成员，或
  • 一个是标准布局类对象，而另一个是该对象的首个非静态数据成员，或若该对象无非静态数据成员，则为该对象的任何基类子对象，或
  • 存在对象 c 使得 a 与 c 指针可互转换，而 c 与 b 指针可互转换。
1
2
3
4
union U { int a; double b; } u;
void* x = &u;                        // x 的值为“指向 u 的指针”
double* y = static_cast<double*>(x); // y 的值为“指向 u.b 的指针”
char* z = static_cast<char*>(x);     // z 的值为“指向 u 的指针”

注

static_cast 亦可用于通过进行到指定类型的函数到指针转换，来消解函数重载的歧义。如

1
2
std::for_each(files.begin(), files.end(),
              static_cast<std::ostream&(*)(std::ostream&)>(std::flush));
阅读更多
C++
3 分钟 读完 (大约 443 个字)

C++构造函数的优化

下面这段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

class A {
   public:
    A() { cout << "default ctor\n"; }
    A(const A& b) { cout << "copy ctor\n"; }
    ~A() { cout << "dtor\n"; }
};

A foo() {
    A b;
    return b;
}

int main() {
    A a = foo();
    return 0;
}

理论上，它的运行结果应为

1
2
3
4
5
6
default ctor // foo函数第一行的对象b的构造
copy ctor    // 对象b拷贝到返回值临时对象
dtor         // 对象b析构
copy ctor    // 返回值临时对象拷贝到main中对象a
dtor         // 返回值临时对象析构
dtor         // main对象析构

然而，当我们实际编译并运行它时，运行结果为

1
2
default ctor
dtor

发现所有的拷贝构造和临时对象的析构都被优化掉了。这就是NRV优化带来的性能上的好处。

阅读更多
TCP/IP
11 分钟 读完 (大约 1659 个字)

TCP/IP学习笔记：DNS

概述

DNS：Domain Name System，域名系统。它是：

  1. 一个由分层的DNS服务器（DNS Server）实现的分布式数据库；
  2. 一个使得主机能够查询分布式数据库的应用层协议。

它运行在UDP之上，使用53号端口。

它提供的服务：

  1. 主机名到IP地址转换的目录服务。
  2. 主机别名。有着复杂主机名的主机能拥有一个或多个别名。复杂主机名也称为规范主机名。如果存在主机别名，主机别名比规范主机名更加容易记忆。应用程序可以调用DNS来获得主机别名对应的规范主机名以及主机的IP地址。
  3. 邮件服务器别名。电子邮件应用程序可以调用DNS，对提供的主机名别名（如yahoo.com）进行解析，已获得该主机的规范主机名（如relay1.west-coast.hotmail.com）及其IP地址。
  4. 负载分配。DNS也用在冗余的服务器（如冗余的Web服务器）之间进行负载分配。繁忙的站点被冗余分布在多台服务器上，每台服务器均运行在不同的端系统上，每个都有着不同的IP地址。由于这些冗余的Web服务器，一个IP地址集合因此与同一个规范主机名相联系。DNS数据库中存储着这些IP地址集合。当客户对映射到某地址集合的名字发出一个DNS请求时，该服务器用IP地址的整个集合进行响应，但在每个回答中循环这些地址次序。因为客户通常总是向IP地址排在最前面的服务器发送HTTP请求报文，所以DNS就在所有这些冗余的Web服务器之间循环分配了负载。

域名空间


图源：《TCP/IP详解 卷1：协议》

DNS的分布式、层次数据库

大致说来，在DNS服务器的层次结构中有3种类型的DNS服务器：

  • 根DNS服务器：提供TLD服务器的IP地址。
  • 顶级域名（Top-Level-Domain, TLD）DNS服务器：提供权威DNS服务器的IP地址。
  • 权威DNS服务器：在因特网上具有公共可访问主机（如Web服务器和邮件服务器）的每个组织机构必须提供公共可访问的DNS记录，这些记录将这些主机的名字映射为IP地址。一个组织机构的权威DNS服务器收藏了这些DNS记录。

还有一类重要的DNS服务器，严格而言它不属于DNS服务器的层次结构，但它对DNS层次结构至关重要。这一类DNS服务器是本地DNS服务器。每个ISP（如一个居民区的ISP或一个机构的ISP）都有一台本地DNS服务器（也叫默认名字服务器）。当主机与某个ISP连接时，该ISP提供一台主机的IP地址，该主机具有一台或多台其本地DNS服务器的IP地址（通常通过DHCP）。主机的本地DNS服务器通常“临近”本主机：对某机构ISP而言，本地DNS服务器可能就与主机在同一局域网中；对于某居民区ISP来说，本地DNS服务器通常与主机相隔不超过几台路由器。当主机发出DNS请求时，该请求被发往本地DNS服务器，它起着代理的作用，并将该请求转发到DNS服务器层次结构中。

查询分为递归查询与迭代查询。

（具体例子见 《计算机网络：自顶向下方法（原书第7版）》P86-88）

DNS缓存

在一个请求链中，当某DNS服务器接收一个DNS回答（如包含某主机名到IP地址的映射）时，它能将映射缓存在本地存储器中。由于主机和主机名与IP地址间的映射不是永久的，所以DNS服务器在一段时间后（通常设置为两天）将丢弃缓存的信息。

本地DNS服务器也能够缓存TLD服务器的IP地址，因而允许本地DNS绕过查询链中的根DNS服务器。事实上，因为缓存，除了少数DNS查询以外，根服务器基本都被绕过了。

DNS记录

共同实现DNS分布式数据库的所有DNS服务器存储了资源记录（Resource Record，RR），RR提供了主机名到IP地址的映射。资源记录是一个包含了以下字段的4元组：

(Name, Value, Type, TTL)

  • TTL

    该记录的生存时间，它决定了资源记录应当从缓存中删除的时间。

  • Name、Value、Type

    • 若Type=A，则Name是主机名，Value是该主机名对应的IP地址。该类型的资源记录提供了标准的主机名到IP地址的映射。如(relay1.bar.foo.com, 145.37.93.126, A)。
    • 若Type=NS，则Name是个域（如foo.com），而Value是个知道如何获得该域中主机IP地址的权威DNS服务器的主机名。这个记录用于沿着查询链来路由DNS查询。如(foo.com, dns.foo.com, NS)。
    • 若Type=CNAME，则Value是别名为Name的主机对应的规范主机名。该记录能够向查询的主机提供一个主机名对应的规范主机名，例如(foo.com, relay1.bar.foo.com, CNAME)。
    • 若Type=MX，则Value是个别名为Name的邮件服务器的规范主机名。如(foo.com, mail.bar.foo.com, MX)。通过使用MX记录，一个公司的邮件服务器和其他服务器（如Web服务器）可以使用相同的别名。为了获得邮件服务器的规范主机名，DNS客户应当请求一条MX记录；而为了获得其他服务器的规范主机名，DNS客户应当请求CNAME记录。

参考资料

《计算机网络：自顶向下方法（原书第7版）》P83-92

分类

标签云

ACM C++ C++11 Linux MySQL Navicat Python STL VMware Valgrind memcheck 数据结构

最新文章

文章

标签

ACM 2
C++ 1
C++11 3
Linux 2
MySQL 1
Navicat 1
Python 1
STL 7
VMware 1
Valgrind 1
memcheck 1
数据结构 7
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×