OSI 模型和 TCP/IP 模型

OSI 模型

开放式系统互联模型 七层 概念框架

• 物理层：光纤，电缆等传输信号的物理通道
• 数据链路层：通过物理层网络连接两台计算机 管理数据帧：封装在数据包中的电子信号 示例：以太网
• 网络层：多个互联网络的路由，转发和寻址 示例：IPv4, IPv6
• 传输层：传输控制，例如确保数据包以正确的顺序到达 示例：TCP，UDP
• 会话层：负责会话中两个独立应用程序之间的网络协调，管理一对一应用程序连接的开始和结束以及同步冲突。网络文件系统（NFS）和服务器消息块（SMB）是会话层的常用协议。
• 表示层：主要关注应用程序发送和使用的数据本身的语法。例如，超文本标记语言（HTML）、JavaScript 对象标记（JSON）和逗号分隔值（CSV）
• 应用层：关注应用程序本身的特定类型及其标准化通信方法。例如，浏览器可以使用超文本传输安全协议（HTTPS）进行通信，而 HTTP 和电子邮件客户端可以使用 POP3（邮局协议版本 3）和 SMTP（简单邮件传输协议）进行通信。

TCP/IP 模型

TCP/IP模型分为四个层级

• 网络接口层：该层对应OSI模型的数据链路层和物理层。它负责物理传输媒介的传输，例如以太网、Wi-Fi等，并提供错误检测和纠正的功能。此外，网络接口层还包含硬件地址（MAC地址）的管理。
• 网络层：该层对应OSI模型的网络层。主要协议是IP，它负责数据包的路由和转发，选择最佳路径将数据从源主机传输到目标主机。IP协议使用IP地址来标识主机和网络，并进行逻辑地址寻址。
  
• 传输层：对应OSI模型的传输层。服务应用。主要的传输层协议有TCP和UDP。TCP提供可靠的数据传输，确保数据的正确性和完整性；而UDP则是无连接的，适用于不要求可靠性的传输，如实时音频和视频流。
• 应用层：对应OSI模型的应用层和表示层以及会话层，面向用户，示例：电子邮件（SMTP）、网页浏览（HTTP）、文件传输（FTP）等。

从输入 URL 到页面展示到底发生了什么？

1. 输入网址，解析URL信息，准备发送HTTP请求
2. 检查浏览器缓存里是否有缓存该资源，如果有直接返回；如果没有进入下一步网络请求。
3. DNS域名解析：网络请求前，进行DNS解析，以获取请求域名的IP地址。DNS解析时会按本地浏览器缓存->本地Host文件->路由器缓存->DNS服务器->根DNS服务器的顺序查询域名对应IP，直到找到为止。
4. TCP三次握手建立连接：浏览器与服务器IP建立TCP连接。
5. 客户端发送HTTP请求：连接建立后，浏览器端会构建请求行、请求头等信息，并把和该域名相关的Cookie等数据附加到请求头中，向服务器构建请求信息。如果是HTTPS的话，还涉及到HTTPS的加解密流程。
6. 服务器处理请求并返回HTTP资源：服务器接收到请求信息，根据请求生成响应数据。
7. TCP四次挥手断开连接：浏览器与服务器IP断开TCP连接。
8. 浏览器解析响应并渲染页面：
   1. 浏览器解析响应头。若响应头状态码为301、302，会重定向到新地址；若响应数据类型是字节流类型，一般会将请求提交给下载管理器；若是HTML类型，会进入下一部渲染流程。
   2. 浏览器解析HTML文件，创建DOM树，解析CSS进行样式计算，然后将CSS和DOM合并，构建渲染树；最后布局和绘制渲染树，完成页面展示。

344.反转字符串

双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    void reverseString(vector<char>& s) {
        int h = s.size() / 2;
        int j = s.size() - 1;
        for(int i = 0;i<h;i++){
            char c = s[i];
            s[i] = s[j];
            s[j] = c;
            j--;
        }
    }
};

541. 反转字符串II

主要还是注意语法的学习

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:
    void rev(char* left, char* right){
        while(left< right){
            char c = *left;
            *left = *right;
            *right = c;
            left++;
            right--;
        }
    }
    string reverseStr(string s, int k) {
        int end = s.size() - 1;
        int p = 0;
        int n = 0;
        while(p<end){
            n = p + k - 1;
            if(n <= end){
                rev(&s[p], &s[n]);
            }else{
                rev(&s[p], &s[end]);
            }
            p = p+ 2* k;
        }
        return s;
    }
};

卡码网：54.替换数字

题目描述：

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000

主要是学习字符串输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<iostream>
#include<string>
#include<sstream>
using namespace std;
int main(){
    string line, s;
    getline(cin, line);
    for(char c: line){
        if(c >= '0' && c <= '9'){
            s.append("number");
        }else{
            s.push_back(c);
        }
    }
    cout<<s<<endl;
}

454. 四数相加II

这道题目我没什么思路，看了题解是两组两组遍历，存储和的值和出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<unordered_map>
using namespace std;
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> m1;
        for(int a: nums1){
            for(int b: nums2){
                m1[a+b]++;
            }
        }
        int count = 0;
        for(int c: nums3){
            for(int d: nums4){
                int r = 0-(c+d);
                if(m1.find(r) != m1.end()){
                    count += m1[r];
                }
            }
        }
        return count;
    }
};

383. 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> m;
        for(char c: magazine){
            m[c]++;
        }
        for(char cr: ransomNote){
            if(m.find(cr) == m.end())return false;
            m[cr]--;
            if(m[cr]<0)return false;
        }
        return true;
    }
};

15. 三数之和

这题我的思路可能就是暴力解了，看了题解发现可以在for循环里同时利用下标和双指针来解决
一开始想用set解决去重的问题，但是发现不排序的话去重还是有问题 这题的去重套路，初始化等要注意的地方还是很多的，这一遍刷题我也只是照着题解的意思敲了一遍，以后还是得多加练习

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

#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> v;
        for(int i = 0;i< nums.size();i++){
            // 遍历到第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，可以剪枝
            if(nums[i]>0)return v;
            int left = i+1, right = nums.size()-1;
            // 错误去重第一个数方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            if(i>0 && nums[i] == nums[i-1])continue;
            while(left < right && right < nums.size()){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    v.push_back({nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while(left < right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums [right-1]){
                        right--;
                    }
                    // 如果判断找到答案，双指针同时收缩
                    left++;
                    right--;
                }else if(sum < 0){
                    //否则单向收缩
                    left++;
                }else{
                    right--;
                }
            }
        }
        return v;
    }   
};

18. 四数之和

还是看题解：

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是 \(O(n^2)\) ，四数之和的时间复杂度是 \(O(n^3)\)
那么一样的道理，五数之和、六数之和等等都采用这种解法。
对于15.三数之和双指针法就是将原本暴力 \(O(n^3)\) 的解法，降为 \(O(n^2)\) 的解法，四数之和的双指针解法就是将原本暴力 \(O(n^4)\) 的解法，降为 \(O(n^3)\) 的解法

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

#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> v;
        if(nums.size()<4)return v;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] >=0 && nums[i]> target)break;
            if(i>0 && nums[i-1] == nums[i])continue;
            for(int j = (i+1);j<nums.size();j++){
                // 第二级剪枝和去重，注意表达式变化
                if((nums[i] + nums[j])>=0 &&(nums[i] + nums[j])>target)break;
                if(j>(i+1) && nums[j-1] == nums[j])continue;
                int left = j+1, right = nums.size()-1;
                while(left < right){
                    long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum == target){
                        v.push_back({nums[i],nums[j],nums[left],nums[right]});
                        //先去重，再移动指针到下一个判定位置
                        while(left<right && nums[left] == nums[left+1])left++;
                        while(right>left && nums[right] == nums[right-1])right--;
                        right--;
                        left++;
                    }else if(sum > target){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
        }
        return v;
    }
};

数据结构

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的

242.有效的字母异位词

基本上都是语法问题了，比如m[c]自动初始化（int则为0），pair的first和second都是成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<unordered_map>
#include<string>
using namespace std;
class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> m;
        for(char c: s){
            m[c]++;
        }
        for(char c: t){
            if(!m[c])return false;
            m[c]--;
            if(m[c]<0)return false;
        }
        for(pair<char, int> p: m){
            if(p.second>0)return false;
        }
        return true;
    }
};

绞尽脑汁想半天如果结果有重复数字怎么办，结果是去重的。。。以后看题要更仔细呀！
题解里使用set的特性去重也挺巧思的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include<unordered_set>
using namespace std;
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> m(nums1.begin(), nums1.end());
        unordered_set<int> r;
        for(int n: nums2){
            if(m.find(n)!=m.end()){
                r.insert(n);
            }
        }
        return vector<int>(r.begin(),r.end());
    }
};

思路差不多了，还是有代码实现的问题，例如to_string(int)的用法,如何char转int等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<unordered_set>
#include<string>
using namespace std;
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> nums;
        if(n == 1)return true;
        while(nums.find(n) == nums.end()){
            nums.insert(n);
            string s = to_string(n);
            int sum = 0;
            for(char c:s){
                int num = c - '0';
                sum += num*num;
            }
            if(sum == 1)return true;
            n = sum;
        }
        return false;
    }
};

看到题目例子的时候我就觉得数组如果有两个一样的值，用哈希表就比较麻烦。先存数组所有值再判断会出现索引相等的问题。使用一个循环，先判断是否已有互补值，再存当前值进map，可以避免配对同一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<unordered_map>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> r;
        for(int i = 0; i< nums.size();i++){
            int v = target - nums[i];
            if(m.find(v) != m.end()){
                r.push_back(i);
                r.push_back(m[v]);
                return r;
            }
            m[nums[i]] = i;
        }
        return r;
    }
};

24. 两两交换链表中的节点

翻转链表加强版

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)return head;
        ListNode* d = new ListNode(-1, head);
        ListNode* n = swapPairs(head->next->next);
        ListNode* r_pair = head->next;
        d->next = r_pair;
        r_pair->next = head;
        head->next = n;
        return d->next;
    }
};

还是那个当整个链表删除时不能直接返回head的问题，多复制几个dummy head就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* d = dummy;
        ListNode* d2 = dummy;
        int len = 0;
        while(d->next){
            d = d->next;
            len++;
        }
        cout<<"len: "<<len<<endl;
        int rm = len - n-1;
        while(rm>=0){
            cout<<"rm: "<<rm<<"d2 val"<<d2->val<<endl;
            d2 = d2->next;
            rm--;
        }
        d2->next = d2->next->next;
        return dummy->next;
    }
};

本来想着可能需要挨个遍历节点是否相等找到相交节点，看了题解发现可以从共同长度同时往后搜索

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:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur_a = headA;
        ListNode* cur_b = headB;
        int len_a = 0, len_b = 0, e = 0;
        while(cur_a){
            len_a++;
            cur_a = cur_a->next;
        }
        while(cur_b){
            len_b++;
            cur_b = cur_b->next;
        }
        cur_a = headA;
        cur_b = headB;
        cout<<"len_a:"<<len_a<<"len_b"<<len_b<<endl;
        if(len_a > len_b){
            e = len_a - len_b;
            cout<<"e:"<<e<<endl;
            while(e>0){
                e--;
                cur_a = cur_a->next;
            }
        }else{
            e = len_b - len_a;
            cout<<"e:"<<e<<endl;
            while(e>0){
                e--;
                cout<<"whiling"<<endl;
                cur_b = cur_b->next;
            }
        }
        cout<<"caval:"<<cur_a->val<<"cbval:"<<cur_b->val<<endl;
        while(cur_a || cur_b){
            if(cur_a == cur_b)return cur_a;
            cur_a = cur_a->next;
            cur_b = cur_b->next;
        }
        return NULL;
    }
};

模糊记得俩指针相遇的地方有一些特性，还是得确定地记下来： 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。 两个指针都从head开始如何避免判断一开始这个点？看题解发现可以循环内先走next再判断,错误的初始化容易错过相遇点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* h = head;
        if(!head || !head->next)return NULL;
        ListNode* fast = head;
        while(slow && fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                ListNode* b = slow;
                while(b != h){
                    b = b->next;
                    h = h->next;
                }
                return h;
            }
            
        }
        return NULL;
    }
};

203.移除链表元素

这回刷题的思路总算对了，但是一开始直接返回head,没有考虑到万一整个链表全部需要删除，原有的链表相当于没动。设置了dummy head就解决了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* n = new ListNode(0, head);
        ListNode* dum = n;
        while(n && n->next){
            if(n->next->val == val){
                // cout<<"next val eq. cur val: "<<n->val<<endl;
                ListNode* link = n->next->next;
                n->next = link;
            }else{
                n = n->next;
            }
            
        }
        return dum->next;
    }
};

设计了一个单链表
首先是结构体命名总是写错，应该注意检查这种问题。
dummy node 也需要在构造函数外声明才可以在其它函数中调用；
然后是尾部插入节点不需要再声明一个尾节点，直接插入即可，定义尾dummy code需要考虑的边界条件太多。

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

class MyLinkedList {
private:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int v): val(v),next(nullptr){}
        ListNode(int v, ListNode* n): val(v), next(n){}
    };
    ListNode* dummy;
public:
    MyLinkedList() {
        dummy = new ListNode(-1);
    }
    
    int get(int index) {
        if(!dummy->next) return -1;
        ListNode* d = dummy;
        cout<<"get ind:"<<index<<endl;
        for(;index>=0;index--){
            d = d->next;
            if(!d)return -1;
            cout<<"index:"<<index<<"getfor+1";
        }
        cout<<endl;
        // if(d->val == -1)return -1;
        return d->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        // if(dummy->next)
        ListNode* d = dummy;
        while(d->next){
            d = d->next;
        }
        d->next = new ListNode(val);
    }
    
    void addAtIndex(int index, int val) {
        ListNode* d = dummy;
        for(int i = index - 1;i>=0;i--){
            d = d->next;
            if(!d)return;
        }
        // if(!d || !d->next)return;
        ListNode* n = new ListNode(val);
        ListNode* link = d->next;
        d->next = n;
        n->next = link;
    }
    
    void deleteAtIndex(int index) {
        ListNode* d = dummy;
        for(int i = index - 1;i>=0;i--){
            d = d->next;
            if(!d)return;
        }
        if(!d->next)return;
        d->next = d->next->next;
    }
};

稀里糊涂地写对了...看了题解，发现这种做法相当于从后往前反转列表，结合以前的debug经验推导了一下这段代码会如何运行，有些理解了

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)return head;
        ListNode* n = head->next;
        ListNode* h = reverseList(n);
        head->next = nullptr;
        n->next = head;
        return h;
    }
};

209.长度最小的子数组

不看题解的时候我的想法是在一个大循环里使用三个循环，先移动两个指针里右边指针的位置到和大于等于target，然后移动左指针到小于等于target,再开始移动右边指针。看了题解了解到可以在两个循环里操作两个指针完成上述操作，避免到处找边界条件。 实际写的时候还是犯了一些小错误，例如sum的累加初始值，sum应该在何时减少等等，今后在更改代码的时候还是要注意细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <climits>
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0, k = INT_MAX;
        for(;right<nums.size();right++){
            sum += nums[right];
            int len;
            while(sum >= target){
                len = right - left + 1;
                if(len < k)k = len;
                sum -= nums[left];
                left++;
            }
            // printf("left: %d, right: %d, len: %d, k:%d\n", left, right,len, k);
        }
        return k == INT_MAX ? 0 : k;
    }
};

看到这道题目我的第一想法是整理出移动方向和当前数字所在位置i，j的关系。尝试写了一下感觉太复杂了，看了题解发现是每圈一次循环，每次循环处理四条边 自己尝试着写了一下发现被每次循环加减的边界绕进去了，还是题解的方式比较清晰。题解强调的区间问题也要注意，不仅仅是每条边的循环条件，每次循环终止如何过渡到下次循环开始也是问题。

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

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mat;
        for(int i = 0; i<n;i++){
            vector<int> row(n, 0);
            mat.push_back(row);
        }
        int row = 0, col = 0, p = 1, c = n / 2;
        int startx = 0, starty = 0, offset = 1;
        while(c--){
            row = starty;
            col = startx;
            for(;col<(n-offset);col++){
                mat[row][col] = p;
                p++;
            }
            for(;row<(n-offset);row++){
                mat[row][col] = p;
                p++;
            }
            for(;col>startx;col--){
                mat[row][col] = p;
                p++;
            }
            for(;row>starty;row--){
                mat[row][col] = p;
                p++;
            }
            startx++;
            starty++;
            offset++;
        }
        if(n % 2 == 1)mat[n/2][n/2] = p;
        return mat;
    }
};

数组基础与算法实现

数组基本特性

• 数组下标从0开始
• 数组内存空间的地址是连续的
• 在C++中，二维数组在内存的空间地址是连续的

C++常见数据类型长度

在C++中，声明数组和向量（vector）有多种方式。以下分别详细说明：

数组声明

数组（Array）的声明方式

数组是固定大小的连续内存序列，大小在编译时确定。

1. 指定大小（不初始化）
   元素值未定义（随机值）：

   1	int arr1[5]; // 5个int类型元素，值未初始化

2. 指定大小并完全初始化
   显式初始化所有元素：

   1	int arr2[3] = {10, 20, 30}; // 初始化所有元素

3. 指定大小并部分初始化
   未显式初始化的元素设为0：

   1	int arr3[5] = {1, 2}; // [1, 2, 0, 0, 0]

4. 自动推断大小
   编译器根据初始化列表确定数组大小：

   1	int arr4[] = {1, 2, 3}; // 大小自动推断为3

5. 统一初始化（C++11）
   省略等号，使用花括号：

   1	int arr5[]{4, 5, 6}; // 大小推断为3

6. 多维数组
   声明二维/三维数组：

   1	int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};

向量（Vector）的声明方式

向量是动态数组（标准库容器），大小可在运行时改变，需包含头文件 <vector>。

1. 空向量
   创建不含元素的空向量：

   1	std::vector<int> vec1; // 空向量

2. 指定大小
   创建含 n 个默认初始化元素的向量（如 int 初始化为0）：

   1	std::vector<int> vec2(5); // 5个0: [0, 0, 0, 0, 0]

3. 指定大小和初始值
   创建含 n 个指定值的元素：

   1	std::vector<int> vec3(4, 100); // 4个100: [100, 100, 100, 100]

4. 通过初始化列表（C++11）
   直接初始化元素值：

   1 2	std::vector<int> vec4 = {7, 8, 9}; // 列表初始化 std::vector<int> vec5{10, 20, 30}; // 直接花括号初始化

5. 通过迭代器范围
   复制另一个容器的部分或全部元素：

   1 2 3

   std::vector<int> src = {1, 2, 3, 4}; std::vector<int> vec6(src.begin(), src.end()); // 复制整个src std::vector<int> vec7(src.begin(), src.begin() + 2); // 复制前2个元素: [1, 2]

6. 拷贝构造
   复制另一个向量的内容：

   1 2	std::vector<int> original = {5, 6, 7}; std::vector<int> vec8(original); // 拷贝: [5, 6, 7]

7. 移动构造（C++11）
   高效转移另一个向量的资源（原向量被置空）：

   1 2	std::vector<int> temp = {9, 10}; std::vector<int> vec9(std::move(temp)); // vec9接管资源，temp变为空

8. 多维向量
   声明二维向量（向量嵌套）：

   1	std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}, {5, 6}};

关键区别

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
#include <vector>

int main() {
    // 数组示例
    int arr[] = {1, 2, 3};  // 自动推断大小
    std::cout << "数组大小: " << sizeof(arr)/sizeof(arr[0]) << "\n"; // 输出3

    // 向量示例
    std::vector<int> vec = {4, 5, 6};
    vec.push_back(7);  // 动态添加元素
    std::cout << "向量大小: " << vec.size();  // 输出4
    return 0;
}

根据需求选择：数组适用于固定大小且性能敏感的场景；向量则提供灵活性和安全性，适合大多数动态需求。

算法实现

704. 二分查找

左闭右闭区间实现

原本仅判断left == right，后来发现在处理仅两个元素，且target小于最小元素的数组时，这样写会导致left = 0同时right= -1,陷入死循环，更改判断条件后就解决了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return searchid(0, nums.size()-1, target, nums);
    }
   
    int searchid(int left, int right, int target, vector<int>& nums) {
        int mid = (left + right) / 2;
        if(nums[mid] == target) {
            return mid;
        } else if(nums[mid] > target) {
            if(left >= right) return -1;
            return searchid(left, mid - 1, target, nums);
        } else {
            if(left >= right) return -1;
            return searchid(mid + 1, right, target, nums);
        }
    }
};

左闭右开区间实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return searchid(0, nums.size(), target, nums);
    }
   
    int searchid(int left, int right, int target, vector<int>& nums) {
        int mid = (left + right - 1) / 2;
        if(nums[mid] == target) {
            return mid;
        } else if(nums[mid] > target) {
            if(left >= right) return -1;
            return searchid(left, mid, target, nums);
        } else {
            if(left >= right) return -1;
            return searchid(mid + 1, right, target, nums);
        }
    }
};

27. 移除元素

当target小于所有数时，right不断左移，left不变等于0，刚好结果应该是0。当target大于所有数时，right不会动，left不断右移直到nums.length，刚好等于结果。所以未找到时应返回left

我的方法从数组的两端向中间遍历，虽然也是双指针方法，但是需要不少额外判断。下一次要定义快慢指针去解题，因为实际上不用把所有查找的元素移动到数组最后，所以直接跳过这些元素复制即可： 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组 慢指针：指向更新 新数组下标的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.empty()) return 0;
        int left = 0, right = nums.size()-1;
        while(left < right) {
            while(nums[left] != val && left < right) left++;
            while(nums[left] == val && left < right) {
                nums[left] = nums[right];
                nums[right] = val;
                right--;
            }
        }
        if(nums[left] != val) return left + 1;
        return left == 0 ? 0 : left;
    }
};

977. 有序数组的平方

这题我一开始总是想着在原数组中修改，于是想不出什么来。看了题解是新开一个数组，再左右指针遍历原数组，思路正确很快就做出来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size(), 0);
        int left = 0, right = nums.size()-1;
        int res_p = nums.size()-1;
        while(res_p >= 0) {
            if(abs(nums[left]) < abs(nums[right])) {
                res[res_p] = pow(nums[right], 2);
                right--;
            } else {
                res[res_p] = pow(nums[left], 2);
                left++;
            }
            res_p--;
        }
        return res;
    }
};

C++常用数学函数

• pow(x, y)：计算x的y次方
• sqrt(x)：计算平方根
• abs(x)：计算绝对值
• ceil(x)：向上取整
• floor(x)：向下取整
• round(x)：四舍五入
• max(x, y)/min(x, y)：返回较大/较小值

I've been working on LeetCode problems for almost a week now, and I feel like my progress with algorithms is pretty slow—managing just one or two problems a day seems like my limit.

I'm focusing on problems from the "Beginner Algorithms" section on LeetCode. Sometimes, I feel my memory is terrible; I realized I had encountered some of these problems before in an introductory algorithms book but couldn't recall the solutions. I ended up solving them with the most inefficient methods...

I can foresee that learning techniques like two-pointers will take some getting used to. It's tough! But I'll take it one step at a time.

(All problems below are from LeetCode's official website.)

2/25-3/1

LC26. Remove Duplicates from Sorted Array

You are given an array nums sorted in non-decreasing order. Remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. After removing the duplicates, return the new length of the array.

Since some languages cannot change the size of the array, the final result must be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with \(O(1)\) extra memory.

\[ \begin{aligned} &\text{class Solution \{} \\ &\quad \text{public:} \\ &\quad \quad \text{int removeDuplicates(vector<int>\& nums) \{} \\ &\quad \quad \quad \text{int a = 0;} \\ &\quad \quad \quad \text{int b = nums.size();} \\ &\quad \quad \quad \text{if (b <= 1) return b;} \\ &\quad \quad \quad \text{for (int i = 0; i < (b - 1); i++) \{} \\ &\quad \quad \quad \quad \text{if (nums[i] != nums[i + 1]) \{} \\ &\quad \quad \quad \quad \quad \text{nums[a] = nums[i];} \\ &\quad \quad \quad \quad \quad \text{a++;} \\ &\quad \quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{nums[a] = nums[b - 1];} \\ &\quad \quad \quad \text{return a + 1;} \\ &\quad \quad \text{\}} \\ &\text{\};} \end{aligned} \]

Here, I learned (again) about the two-pointer technique and refreshed my long-unused C++ knowledge. I chose C++ mainly because many of the algorithm and OpenCV books I previously studied use C++. Although I've heard C++ interviews focus heavily on language features, it feels more suitable than Python for understanding internal mechanisms. Python seems to hide a lot of details, which might not be ideal for my coding style later.

This problem was manageable, but for problems involving in-place modifications, it's essential to use vector<int>& nums to pass by reference.

While solving this, I realized I had forgotten basic functions like .size(), memset(), and .length(). Sigh.

LC122. Best Time to Buy and Sell Stock II

You are given an array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can hold at most one share of the stock at any time. However, you can buy it and then sell it on the same day. Return the maximum profit you can achieve.

\[ \begin{aligned} &\text{class Solution \{} \\ &\quad \text{public:} \\ &\quad \quad \text{int maxProfit(vector<int>\& prices) \{} \\ &\quad \quad \quad \text{int day = 0;} \\ &\quad \quad \quad \text{int count = 0;} \\ &\quad \quad \quad \text{bool st = false;} \\ &\quad \quad \quad \text{if (prices.size() == 1) return 0;} \\ &\quad \quad \quad \text{for (int i = 0; i < prices.size() - 1; i++) \{} \\ &\quad \quad \quad \quad \text{if (prices[i] < prices[i + 1] && st == false) \{} \\ &\quad \quad \quad \quad \quad \text{day = i; st = true;} \\ &\quad \quad \quad \quad \text{\}} \\ &\quad \quad \quad \quad \text{if (prices[i] > prices[i + 1] && st == true) \{} \\ &\quad \quad \quad \quad \quad \text{count += prices[i] - prices[day]; st = false;} \\ &\quad \quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{return count;} \\ &\quad \quad \text{\}} \\ &\text{\};} \end{aligned} \]

The above solution attempts to track local minima and maxima but led to overly complex if conditions. A simpler approach is summing positive differences between consecutive days:

\[ \begin{aligned} &\text{class Solution \{} \\ &\quad \text{public:} \\ &\quad \quad \text{int maxProfit(vector<int>\& prices) \{} \\ &\quad \quad \quad \text{int pf = 0;} \\ &\quad \quad \quad \text{for (int i = 0; i < prices.size() - 1; i++) \{} \\ &\quad \quad \quad \quad \text{if (prices[i] < prices[i + 1]) \{} \\ &\quad \quad \quad \quad \quad \text{pf += prices[i + 1] - prices[i];} \\ &\quad \quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{return pf;} \\ &\quad \quad \text{\}} \\ &\text{\};} \end{aligned} \]

This solution is concise and easier to understand, summing up profits whenever prices go up.

LC48. Rotate Image

You are given an \(n \times n\) 2D matrix representing an image. Rotate the image by 90 degrees clockwise.

\[ \begin{aligned} &\text{class Solution \{} \\ &\quad \text{public:} \\ &\quad \quad \text{void rotate(vector<vector<int>>\& matrix) \{} \\ &\quad \quad \quad \text{int n = matrix.size();} \\ &\quad \quad \quad \text{for (int i = 0; i < n; i++) \{} \\ &\quad \quad \quad \quad \text{for (int j = i; j < n; j++) \{} \\ &\quad \quad \quad \quad \quad \text{swap(matrix[i][j], matrix[j][i]);} \\ &\quad \quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{for (auto\& row : matrix) \{ reverse(row.begin(), row.end()); \}} \\ &\quad \quad \text{\}} \\ &\text{\};} \end{aligned} \]

First, transpose the matrix, then reverse each row to achieve the 90-degree rotation.

After solving the problem using the approach of transposing the matrix followed by reversing the rows, I thought of an alternative way: reversing the rows first and then transposing the matrix.

This approach also works effectively and provides the same result. Here's how it looks:

\[ \begin{aligned} &\text{class Solution \{} \\ &\quad \text{public:} \\ &\quad \quad \text{void rotate(vector<vector<int>>\& matrix) \{} \\ &\quad \quad \quad \text{reverse(matrix.begin(), matrix.end());} \\ &\quad \quad \quad \text{for (int i = 0; i < matrix.size(); i++) \{} \\ &\quad \quad \quad \quad \text{for (int j = i; j < matrix[i].size(); j++) \{} \\ &\quad \quad \quad \quad \quad \text{swap(matrix[i][j], matrix[j][i]);} \\ &\quad \quad \quad \quad \text{\}} \\ &\quad \quad \quad \text{\}} \\ &\quad \quad \text{\}} \\ &\text{\};} \end{aligned} \]

This version simplifies the triangle iteration by starting the inner loop at j = i. It reduces the code's complexity while maintaining clarity. However, I noticed that the memory usage was slightly higher compared to my earlier implementation where I explicitly managed the triangular region with an additional variable. To investigate further, I experimented with both versions on LeetCode's submission platform. Interestingly, I found that memory usage sometimes fluctuated slightly for reasons I couldn't fully understand, possibly due to internal optimizations in the runtime environment.

Ultimately, both methods provide the correct result, and the choice depends on your preference for readability versus strict memory management.

摘录一下Marion的论文要点，方便查阅

任务模型

每个任务 \(\tau_i\) 由一组子任务 \(\tau_{i,j}\) 组成，并在其间具有优先关系 \(<\)。每个子任务 \(\tau_{i,j}\) 的特征为： - 工作量 \(c_{i,j} \in \mathbb{N}\)，表示其最坏情况下的执行时间。

子任务必须顺序执行，即它是一组必须按顺序完成的指令的集合，执行时间最长为 \(c_{i,j}\)。假设子任务执行是可重入的：执行可以被其他子任务抢占，且无需在系统中同一个核心上恢复。

优先关系限制了子任务的执行顺序，例如 \(\tau_{i,a} < \tau_{i,b}\)，则 \(\tau_{i,a}\) 必须在 \(\tau_{i,b}\) 之前完全执行。我们说，当任务 \(\tau_{i,a}\) 的所有前驱任务 \(\tau_{i,a'}\) 完成时，\(\tau_{i,a}\) 变为“可用”（available）。

根据 [26]，我们将任务分为两类： 1. 轻量任务（light tasks）：满足 \(C_i < D_i\)； 2. 重量任务（heavy tasks）：满足 \(C_i \geq D_i\)，此类任务必须利用其潜在的并行性才能满足调度要求。

本文的重点是联合调度（federated scheduling），对于每个重量任务，其被分配到一个专用核心集上并独占执行。我们仅考虑截止时间 \(D_i\) 和子任务工作量 \(c_{i,j}\) 为正整数的任务，称为整数值任务（integer-valued tasks）。

优先关系的DAG表示

子任务执行的优先关系可表示为一个有向无环图（DAG）。对于每个并行任务 \(\tau_i\)，存在一个DAG \(G_i\)，其包含的顶点集合为 \(v_{i,j}\)，对应于任务 \(\tau_i\) 的子任务 \(\tau_{i,j}\)： - 每个顶点 \(v_{i,j}\) 的属性为子任务的工作量 \(c_{i,j}\)； - 边 \(v_{i,a} \to v_{i,b}\) 存在当且仅当 \(\tau_{i,a} < \tau_{i,b}\) 且不存在 \(v_{i,c}\) 满足 \(\tau_{i,a} < \tau_{i,c} < \tau_{i,b}\)，即 \(v_{i,b}\) 直接继承 \(v_{i,a}\)。

关键路径长度的定义

对于每个图顶点 \(v_{i,j}\)，我们定义其关键路径长度或跨度 \(l_{i,j} \in \mathbb{N}\) 为从该顶点起始的最长路径的长度，该路径由沿路径每个顶点的执行时间（包括起始顶点的权重 \(c_{i,j}\)）加权。

对于相应的任务 \(\tau_i\)，跨度 \(L_i \in \mathbb{N}\) 是所有顶点的跨度中的最大值，即整个DAG的关键路径长度。跨度对应于任务在给定无限数量核心时相对于其激活时间的最早完成时间。

显然，为使任务可调度，必须满足： \[ L_i \leq D_i \]

适用于整数值任务的联合调度

对于一个重量任务 \(\tau_i\)，其特征为工作量 \(C_i\)、跨度 \(L_i\) 和截止时间 \(D_i\)，在提供足够核心的情况下，任何工作保留型（work-conserving，即贪婪型）调度器均可调度该任务。分配给任务 \(\tau_i\) 的核心数可以表示为： \[ n_i = \left\lceil \frac{C_i - L_i}{D_i - L_i} \right\rceil \tag{1} \]

我们在此证明，对于一个并行任务，如果其截止时间和所有子任务的工作量均为整数，则分配的核心数可以改进为： \[ n_i' = \left\lceil \frac{C_i - L_i + 1}{D_i - L_i + 1} \right\rceil \]

这一公式比方程 (1) 在限制重量任务的核心数方面提供了实际且直观的优势。

单工作量表调度（Unit-Workload List Scheduling）

第4节中提出的联合调度方法为高利用率的整数值任务分配了足够的处理器，以保证任何工作保留型调度器的可行性，前提是给定每个任务的工作量、关键路径长度和截止时间。然而，这种常量时间的分配方法可能会导致对重量任务的处理器过度分配，进而造成资源浪费。

在 [3] 中，Graham 的表调度方法（list scheduling）被应用于重量任务；通过使用多种启发式方法为子任务排序，可以在更少的处理器上生成可行的调度。表调度以非抢占式方式将可用子任务分配给空闲处理器；如 [14] 所述，这可能导致对重量任务的处理器分配过多。然而，允许空闲子任务进行抢占可能会引入切换问题。

方法改进

为了解决这个问题，我们提出了单工作量子任务的表调度。
- 一个整数值并行任务 \(\tau_i\)，由DAG \(G_i\) 表示，可以被分解为一个包含单工作量顶点的DAG \(G_i^*\)。
- 在 \(G_i\) 中具有工作量 \(c\) 的顶点 \(v_{i,j}\) 被映射为一个完全有序的顶点序列，在 \(G_i^*\) 中形成从起点到终点的路径。

对于 \(G_i^*\) 中的任何边 \(v_{i,j}\)，其连接方式如下： 1. \(G_i^*\) 中进入 \(v_{i,j}\) 的任何边连接到其分解后路径中的第一个顶点； 2. 在 \(G_i\) 中离开 \(v_j\) 的任何边，现在连接到 \(v_{i,j}\) 的分解路径中的最后一个顶点。

优势

对于这样的DAG，表调度方法可以为每个单位工作量分配一个优先级；
这使得原始DAG \(G_i\) 中的相应子任务能够在单位时间步边界内被抢占。

5.1 常见的表调度启发式方法

关键路径规则（Critical Path Rule, CP）

关键路径规则用于表调度时，以最长跨度的顺序选择可用子任务进行执行。
- 子任务跨度的分配可以以深度优先搜索的方式完成；当为每个顶点分配跨度后，图的总跨度 \(L\) 会被更新。 - 该过程的时间复杂度为 \(O(|V| + |E|)\)。

DAG分解

DAG \(G\) 分解为单位工作量的 DAG \(G^*\) 的过程表示为函数 Convert_Unit_DAG： 1. 初始化 \(G^*\) 为 \(G\) 的副本。 2. 建立一个顶点集合 \(V^*\)，其由 \(G^*\) 中的顶点（实际代码中可能为指向顶点的指针）组成。 3. 对于 \(V^*\) 中的每个顶点 \(v_i\)： - 将 \(v_i\) 的工作量 \(c_i\) 转化为单位工作量顶点序列，这些顶点在 \(G^*\) 中形成路径： - 路径中的每个顶点之间用边连接，第一个顶点的跨度等于 \(v_i\) 的跨度 \(l_i\)； - 每个后续顶点的跨度比前一个顶点小1。 - 删除原始顶点 \(v_i\)。

4. 处理完成后，\(G^*\) 中仅包含单位工作量的顶点：
   • 通过分解，生成了 \(C - |V|\) 个额外顶点，以及 \(C - |V|\) 条额外边。
   • 因此，总运行时间为 \(O(|V| + C - |V| + |E| + C - |V|)\)，简化为 \(O(C + |E|)\)。

后继数量规则（Largest Number of Successors Rule, LNS）

LNS规则以后继任务的总工作量为顺序，选择可用子任务进行执行： - 子任务 \(v_i \in G\) 的后继工作量由与 \(v_i\) 通过路径相连的所有顶点的工作量之和定义。 - 可以通过动态规划在整个图上实现这一过程，其时间复杂度为 \(O(|V| + |E|)\)。

LNS规则也可以应用于单位工作量子任务的表调度，并保持伪多项式时间复杂度。

注意

将整数值任务的 DAG \(G\) 分解为单位工作量的 DAG \(G^*\) 时，还需要为每个单位工作量顶点分配一个子图工作量。这与跨度的分配类似，不会影响算法的时间复杂度。