Maxw的小站

Maxw学习记录

发表于 更新于 分类于

151.翻转字符串里的单词

需要注意反转的过程，不能想当然 

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
class Solution {
public:
    void rev(char* left, char* right){
        while(left < right){
            char c = *left;
            *left = *right;
            *right = c;
            left++;
            right--;
        }
    }
    string reverseWords(string s) {
        string ss;
        string res;
        for(int i = s.size() - 1; i>=0;i--){
            if(s[i] != ' '){
                // cout<<"s[i]:"<<s[i]<<endl;
                ss.push_back(s[i]);
            }else{
                if(!ss.empty()){
                    rev(&ss[0], &ss[ss.size() - 1]);
                    res.append(ss);
                    res.push_back(' ');
                    ss = "";
                }
            }
        }
        if(!ss.empty() && ss[ss.size()-1] != ' '){
            rev(&ss[0], &ss[ss.size() - 1]);
            res.append(ss);
        }
        if(res[res.size() - 1] == ' ')res.pop_back();
        return res;
    }
};

卡码网：55.右旋转字符串

一步一步输出看结果，总算是做对了 贴一下题目：

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

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
#include<iostream>
#include<string>
using namespace std;
int main(){
    int k;
    cin>>k;
    string s;
    cin.ignore();
    getline(cin, s);
    // cout<<"k:"<<k<<" s:"<<s<<endl;
    string ss;
    int len = s.size();
    for(int i = (len - 1); i>=(len-k);i--){
        ss.push_back(s[i]);
        s.pop_back();
    }
    // cout<<"ss:"<<ss<<" s:"<<s<<endl;
    char* left = &ss[0];
    char* right = &ss[ss.size() - 1];
    while(left < right){
        char c = *left;
        *left = *right;
        *right = c;
        left++;
        right--;
    }
    ss.append(s);
    cout<<ss;
}

28. 实现 strStr()

使用KMP算法求最长相等前后缀的过程，实际上是在：

  • 后缀指针是外层循环
  • 若前后缀判断不相等，前缀指针可以一直往前跳跃至上一个判断不相等的位置，直到长度计数归零或者找到相等位置。如果找到相等位置，则参考下一条将计数加一
  • 重复利用之前已经判断相等的前后缀，如果一直相等，则长度每次都加一
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
class Solution {
public:
    void getNext(vector<int> &nextTable, string s){
        nextTable.push_back(0);
        int j = 0;
        for(int i = 1;i<s.size();i++){
            while(j > 0 && s[i] != s[j]){
                j = nextTable[j - 1];
            }
            if(s[i] == s[j]){
                j++;
            }
            nextTable.push_back(j);
        }
    }
    int strStr(string haystack, string needle) {
        vector<int> n;
        getNext(n, needle);
        for(int i:n){
            cout<<i;
        }
        cout<<endl;
        int j = 0;
        for(int i = 0;i<haystack.size();i++){
            while(j>0 && haystack[i] != needle[j]){
                j = n[j-1];
            }
            if(haystack[i] == needle[j]){
                if(j == needle.size() - 1)return i-j;
                j++;
            }
        }
        return -1;
    }
};

459.重复的子字符串

关键是数学证明：最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，那么不包含的子串 就是s的最小重复子串 

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
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        vector<int> nextT;
        nextT.push_back(0);
        int j= 0;
        for(int i = 1;i<s.size();i++){
            while(j>0 && s[i] != s[j]){
                j = nextT[j-1];
            }
            if(s[i] == s[j]){
                j++;
            }
            nextT.push_back(j);
        }
        int cnt = 0;
        for(int k = 0;k<nextT.size();k++){
            if(nextT[k] == 0){
                cnt++;
            }else{
                break;
            }
        }
        int len = s.size();
        if(nextT.back()!=0 && (len % (len - j) == 0))return true;
        return false;
    }
};

发表于 分类于

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::set 红黑树 有序 否 否 O(log n) O(log n)
std::multiset 红黑树 有序 是 否 O(logn) O(logn)
std::unordered_set 哈希表 无序 否 否 O(1) O(1)

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

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

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;
    }
};
### 349. 两个数组的交集

绞尽脑汁想半天如果结果有重复数字怎么办，结果是去重的。。。以后看题要更仔细呀！
题解里使用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());
    }
};
### 202. 快乐数

思路差不多了，还是有代码实现的问题，例如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;
    }
};
### 1. 两数之和

看到题目例子的时候我就觉得数组如果有两个一样的值，用哈希表就比较麻烦。先存数组所有值再判断会出现索引相等的问题。使用一个循环，先判断是否已有互补值，再存当前值进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;
    }
};
### 19.删除链表的倒数第N个节点

还是那个当整个链表删除时不能直接返回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;
    }
};
### 面试题 02.07. 链表相交 (leetcode 160)

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

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;
    }
};
### 142.环形链表II

模糊记得俩指针相遇的地方有一些特性，还是得确定地记下来： 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。 两个指针都从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;
    }
};
### 707.设计链表

设计了一个单链表
首先是结构体命名总是写错，应该注意检查这种问题。
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;
    }
};
### 206.反转链表

稀里糊涂地写对了...看了题解，发现这种做法相当于从后往前反转列表，结合以前的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;
    }
};
### 59.螺旋矩阵II

看到这道题目我的第一想法是整理出移动方向和当前数字所在位置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++常见数据类型长度

数据类型 长度（字节） 备注
char 1
short 2
int 4
long 4或8 取决于编译器和操作系统
long long 8
float 4
double 8
long double 8或16 取决于编译器和操作系统
bool 1 实际只使用1位
指针类型 4或8 取决于编译器和操作系统

在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}};

关键区别

特性 数组 向量
大小 固定（编译时确定） 动态（运行时可调整）
内存管理 栈或静态内存 堆内存（自动管理）
作为参数传递 退化为指针 可安全传递（保持大小信息）
越界访问 未定义行为（可能崩溃） 使用at()会抛出异常
功能扩展 无内置方法 支持push_back()、size()等方法

示例代码

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.

0%