cm456

这个屌丝很懒，什么也没留下！

热门标签

代码随想录刷题学习笔记——初级篇C++/Python_c++ 代码随想录

作者：cm456 | 2024-02-06 13:22:22

踩

c++ 代码随想录

C++算法题学习笔记

高阶C++基本知识点笔记
C++编程题笔记
数组
链表专题
哈希表专题
字符串专题
栈和队列专题

高阶C++基本知识点笔记

该部分截图来自黑马程序员C++课程戳这里，因为感觉重新打字写的也是一样的东西，不如截图方便
在这里插入图片描述

，

如果有设定值，按照设定值填充。

deque的结构

###########################

C++编程题笔记

题目截图来自LeetCode官网，编程刷题跟着代码随想录学的，主要记录自己刷题过程中的学习结果和查漏补缺的笔记。

数组

一、二分法

1.数组简单应用

题目难度：简单
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
关键点：边界值设定和查找法

//Cpp写法
class Solution {
public:
    int search(vector<int>& nums, int target) {//使用vector大概是可以保证默认升序排序
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int middle=(left + right )/ 2;//除法直接保留整数部分
            //代码随想录中给出的是left+((right-left)/2)防止溢出，等价于我写的语句，我没有反应过来啥意思
            if(nums[middle]<target){
                left=middle+1;   
            }
            else if(nums[middle]>target){
                right=middle-1;
            }
            else{
                return middle;
            }
                
        }
        //遍历所有元素都未找出结果
        return -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

#python写法
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right + left) // 2 
            #python中/表示浮点数 //表示结果为整数
            num = nums[mid]
            if num == target:
                return mid
            elif num > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
OS：显然暴力遍历的算法是不能满足要求的，虽然不知道系统如何辨识出来
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position

//cpp运行速度快，代码量高，考察严密的逻辑
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int middle=(left+right)/2;
            if(nums[middle]<target){
                left=middle+1;
            }
            else if(nums[middle]>target){
                right=middle-1;
            }
            else{
                return middle;
            }
        }
        return left;

    }
};

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

#python写起来就是好看
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums.sort()
            return nums.index(target)

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

3. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
思路：

时间复杂度要求—>二分法查找
返回两个坐标位置—>二分法分别查找左右边界
分析返回的状态：1) [-1,-1] ；2) [数组中的左右下标]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    //write code............
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 情况二
        return {-1, -1};
    }
private:
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
};
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

4. x的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sqrtx
考点：变量类型存储空间也是代码逻辑完备性考察的因素，编程系统中会给出所有可能的案例，用案例通过率检验你的方法

class Solution {
public:
    int mySqrt(int x) {
        int i;
        for(i=0;i<x;i++){
            if((i*i<=x))
            {
                if(i==46340)
                break;
                else if((i!=46340)&&((i+1)*(i+1)>x))
                break;
            }
        }
        return i;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、移除元素

双指针法
题目有时间复杂度和空间复杂度的要求

三、有序数组的平方

活用容器时间复杂度不一定满足要求
题目：给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
PS：这道题对非递减含义的理解很重要，下面给个例子
1,2,3,4,5：递增排列，
9,8,7,6,5：递减排列。
1，2，3，3，4，5，8，8：非递减排列，
9，8，7，7，6，5，5，2，1 : 非递增排列。
即，非递减序列中允许有重复值数据

四、螺旋矩阵II

数组总结

数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）。
C++中vector和array的区别一定要弄清楚，vector的底层实现是array，封装后使用更友好。严格来讲vector是容器，不是数组。
数组的元素是不能删的，只能覆盖。
常用方法回顾：
二分法：
快慢指针：
滑动窗口：
模拟行为：

摘自代码随想录网页版的分享

链表专题

链表与数组的区别：

数组在内存中的连续地址存储的，而链表是靠指针联系在一起的，存储地址可以不连续，具体的地址分配要看系统的管理机制。
在LeetCode中如果使用节点，会提供已经定义好的ListNode，我们需要知道的是这是编译网站提供的内置结构体不是C/C++编译器的内置内容，因此我们在平时不要以为这是个默认存在的东西，要有自己构建结构体的意识，这样才能应对面试中的编程环节。
删除节点时，C++中需要手动释放不需要的指针，而Python中已经自动处理好了，不占用空间。

一、移除链表元素

题目： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

方法一：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //删除头结点
        while(head!=NULL&& head->val==val){
            //用if不能通过所有的测试用例
            //假设链表中所有的元素都是val，那么删除第一个head之后
            //更新的head仍然需要看作头结点删除
            //第二个板块只能解决从head->next开始的val值
            //编程题会给出所有可能的测试用例，测试通过的覆盖率不达100%是无法提交通过的
            //因此想法一定要全面
            ListNode *temp=head;
            head=head->next;
            delete temp;

        } 
        //删除链表中的非头结点val
        ListNode *cur=head;
        while(cur!=NULL&&cur->next!=NULL){
            //因为遍历链表中的非头结点元素，如果cur代表最后一个元素，那么需要借助前一个元素完成指针指向的改变
            //因此，判断是否为val，其实目标对象是cur->next
            //类似于for(int i=0;i<n-1;i++)的过程
            if(cur->next->val==val){
                ListNode *temp=cur->next;
                cur->next=cur->next->next;
                delete temp;

            }
            else
            {
                cur=cur->next;//完成遍历动作
            }
        }   
        
        return head;//经常忘记写return啦
    }
};


方法二：构造虚拟头结点
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;//最后记住要把虚拟节点删掉
        return head;
    }
};
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

二、设计链表

题目来自LeetCode

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        size = 0;
    }
    
    int get(int index) {//获取链表下index对应的数值
        if (index > (size - 1)|| index < 0) {
            return -1;
        }
        LinkedNode* cur=dummyHead->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {//插入成为头节点
        LinkedNode* head=new LinkedNode(val);
        head->next=dummyHead->next;
        dummyHead->next=head;//这个虚拟头节点仍然存在
        size++;

    }
    
    void addAtTail(int val) {//插入成为尾节点
        LinkedNode* tail=new LinkedNode(val);
        LinkedNode* cur = dummyHead;
        while(cur->next!=nullptr){
            cur = cur->next;
        }
        cur->next = tail;
        size++;//一直保持对size的计数是因为整个类内的操作可能是相互关联的
    }
    
    void addAtIndex(int index, int val) {//插入指定位置，不包括尾节点
        if(index>size){
            return;
        }
        LinkedNode* addNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead;
        while(index--){
            cur=cur->next;
        }
        addNode->next=cur->next;
        cur->next=addNode;
        size++;

    }
    
    void deleteAtIndex(int index) {//删除指定位置的节点
        if(index<0||index>=size){
            return;
        }
        LinkedNode* cur=dummyHead;//在上一道题目中解释了虚节点的好处
        while(index--){
            cur=cur->next;
        }
        LinkedNode* tmp=cur->next;
        cur->next=cur->next->next;
        delete tmp;
        size--;
    }

    // void printNodeList(){
    //     LinkedNode* cur = dummyHead;
    //     while(cur->next!=nullptr){
    //         cout<<cur->next->val<<" ";
    //         cur=cur->next;
    //     }
    //     cout<<endl;
    // }
private:
    int size;
    LinkedNode* dummyHead;


};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
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

三、翻转链表

四、两两交换链表中的节点

在这里插入图片描述

知识点补充：null可以用来代表数值为0，nullptr专指空指针
null和nullptr的区别

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };在实际的笔试题目中可能这种的结构体定义，以及前面的库函数的调用都要自己写，否则会执行报错
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* virnode=new ListNode(0);
        virnode->next = head;
        ListNode* cur = virnode;
        while(cur->next!=nullptr && cur->next->next!=nullptr)
        //确保不是最后一个结点，它包括值不为0，后继存在
        {
            ListNode* temp=cur->next;//两两一组中的第一个节点
            ListNode* temp1=cur->next->next->next;//下一个两两一组的第一个节点
            cur->next=cur->next->next;//让虚拟节点指向第二个节点
            cur->next->next=temp;//让第二个节点指向第一个节点
            cur->next->next->next=temp1;//让第一个节点指向下一组的第一个节点
            //到此一组交换完毕，虚拟头节点需要进入下一组互换，即往前走两步,
            //此时不用管指向的到底是哪个节点，反正跨国当前这一组的两个节点即可
            cur = cur->next->next;
        
        }
        return virnode->next;
        //其实这个链表已经实现了两两互换，但是虚拟头节点不能真实参与，
        //所以返回的头节点应当是实际链表中的第一个节点，因此返回virnode->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

五、删除链表的倒数第N个节点

在这里插入图片描述
这里面的规律要记住

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int count=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //两种结题看法：1. 真正改变链表的结构 2. 保证输出符合题目的要求
        //递归法解决问题
        if(!head) return NULL;//nullptr关键字是小写，null关键字是大写
        head->next = removeNthFromEnd(head->next, n); //明明是倒数第n个为什么感觉都是正向走了n步呢？
        count++;
        if(n==count) return head->next;

        return head;

    }
};
//这里其实有一个前景规律没有人解释，对于一个序列长L，要找到倒数第n个数并删除
//在有虚拟节点的情况下
//快慢指针方法中，慢指针需要走到倒数第n个数的前一个数的位置处，即该数在L-n+1处，
//慢指针需要走L-n步
//慢指针行走时，快指针与其同步，因此快指针走到null的剩下步伐为L+1-(L-n)=n+1
//因此，为了后续操作，快指针需要先走出(n+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

在这里插入图片描述

六、链表相交

在这里插入图片描述
代码随想录和我想的方案一样，但是在帖子里看见一个更巧妙好玩的方法，我将分别写在方案一和方案二中。方法二太好玩了，我把帖子提供给大家。戳这里

方法一，灵感来源于双指针法删除倒数第N个节点。两个链表如果有长度差，必定在开头，先让长的链表将差异走完，剩下的两人同步进行，同步比较即可获得结果。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};
方法二，偏重于一种运动策略设计，抓住两路的共性，构建策略方程，完成比较
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A=headA;
        ListNode* B=headB;
        while (A != B) {//感觉换做我自己，会想到把两个指针进行比较是不太可能的
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};
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

七、环形链表 II

在这里插入图片描述
思路整理戳这里

/**
 * 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) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};


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

哈希表专题

哈希表的基本定义：经过映射方法的处理，将数据以索引和对应的键值成对存储，数据查找时找出key就可以得到相应的value。如果发生键值冲突，即不满足一一对应的关系，哈希表将重新构建。
哈希碰撞解决办法：拉链法和线性探测法。

拉链法：将索引对应的键值存放空间扩容。
线性探测法：保证索引空间大于数据存储空间，便于随时改变索引关系，腾出空位。
常用对象：数组、set、map

一、有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-anagram
著作权归领扣网络所有。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
    //这种方法没有直接使用哈希容器，但是借助了容器的思想，并且巧用++和--，减少了变量的定义
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
在这里插入图片描述
这道题需要去重找元素，数组是无法做到的，于是用哈希结构来解决，势必要用到STL容器，这也是本题的收获要点。
关于STL-set的具体内容介绍戳这里

在这里插入图片描述
常见用法：if(nums_set.find(num)!=nums_set.end())

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int num : nums2)
        //for(数据类型 A:B)：叫做for each循环，是在B中遍历A的意思

        {
            // set.find()判断在set容器中是否存在某值为x的元素
            //set.find()返回一个指向被查找到元素的迭代器；如果没有找到，返回指向集合最后一个元素的迭代器。
            //所以当返回值与set.end()不相等时候说明遇见了已经存储过的数据，对于本题而言，也就是找到了nums1和nums2交集中的元素，需要记录在result_set容器中
            if(nums_set.find(num)!=nums_set.end()){
                //set.end()为set容器中最后一个元素后面的迭代器
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、快乐数

在这里插入图片描述

class Solution {
public:
    int getSum(int n){
        int sum=0;//定义的变量要赋初值，否则编译错误，我想是因为此函数内外定义了同名变量
        while(n){//分解各位数求和
            sum +=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1)
        {
            int sum=getSum(n);//对当前数的各位按要求求和，尚未形成循环
            if(sum==1)
            {
                return true;//跳出循环
            }
            if(set.find(sum)!=set.end())
            {
                return false;//跳出循环
            }
            else
            {
                set.insert(sum);
            }
            n=sum;//循环形成了

        }



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

四、两数之和

在这里插入图片描述
因为要返回元素的下标，所以用带有key-value结构的map是最合适的。我们当然可以用暴力循环的方式来解决该问题，但是这样的算法时间复杂度很高。

在这里插入图片描述

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>hashtable;    // 建立哈希表
        for(int i=0;i<nums.size();++i){     //nums.size后面要带括号()
        // for(auto i:nums)  错误，因为只有知道i的类型才可以用auto
            auto it=hashtable.find(target-nums[i]); //返回类型是iterator迭代器
            if(it!=hashtable.end()){     // 查找it是否在hashtable里
                return{it->second,i};   //first是键(key)，second是值(value)
                                        //hashtable[nums[i]]=i,first就是nums[i],second就是i
            }
            hashtable[nums[i]]=i;   //存入键值对。 hashtable(nums[i])=i;错误，是[]不是()
        }
        return{};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五、四数相加II

在这里插入图片描述

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap;
        //key-value结构中各自存放数值的含义我们是可以自己定的
        for(int a : A){
            for(int b:B){
                umap[a+b]++;
            }
           
        }
        int count =0;
        for(int c: C){
            for(int d:D){
                if(umap.find(0-(c+d))!=umap.end()){
                    count+=umap[0-(c+d)];
                }
            }
        }
        return count;//这道题意思明白但是逻辑没搞懂，明明nums4已经确定使用下表为1对应的数值了，为什么还要遍历D
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

六、赎金信

在这里插入图片描述

方案一：
//代码随想录说对于海量数据使用数组会比使用map更快，不过数组实现的方式相当于在构造哈希
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
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

方案二：用暴力算法
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for(int i=0;i<ransomNote.length();i++){
            for(int j=0;j<magazine.length();j++)
            {
                if(ransomNote[i]==magazine[j]){
                    ransomNote.erase(ransomNote[i]);//这个函数在学习基础知识的时候并不知道
                    //感觉在课本中也不常见，需要积累
                    break;
                }
            }
        }
        if(ransomNote.length()==0){
            return true;
        }
        return false;
    }
};
//我按照上述方式写的时候编译没有问题，但是测试用例没有百分百通过
//目前还不明白为什么，在我看来也不过就是和下面代码随想录给的示例遍历的先后顺序不一样
//我有想到过，当先遍历ransomNode的时候，在后续删除其重复元素后回到循环语句，
//此时起点相对于原来的定义发生了变化，但好像还是不能证明什么。
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};
相比较这个逻辑我觉得还是方案一数组给的更加简单直接
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

七、三数之和

在这里插入图片描述
有个基础知识必须先解决：C++各容器之间的区别
 vector使用方法详解

使用双指针的概念解使用双指针的概念解题。需要注意的是，对于这里的“指针”这个概念，它并不是指编程语言中的指针，而是指两个引导针，便于理清逻辑，当然也不排除真的有需要指针才能实现的题目。双指针法要根据具体的任务和概念选择具象化的方式。
这个办法我想到了，我的设计是：首先对给定的整数数组进行去重和排序，得到一个整理后的数组A。对于A，用for循环给定一个起点数字，剩下的两个数用指针指向他们，模仿冒泡排序的遍历方式，两个指针接着给定的起点，在后面间隔0-n个进行位置移动，找到一个符合条件的元组就记录下来，这样获得的元组一定不会有重读的内容，能够符合条件。但是指针移动的描述条件每次都是判断是否==0，似乎还不够简洁，除此以外，在给定的起点之后，可能的结果要在剩下的元素中两两配对都遍历一遍，我觉得这个思路是行得通的，但是这种思路的缺点就在于，你不是去“找”解析解而是去判断所有可能的配对情况，这样仍然会产生加高的时间复杂度。
代码随想录中给出的思路也是使用双指针，有种逐步代入，找到最优解的感觉。当我确定一个起始点的数值，我要做的是抓住数组已经排序的特性，给指针剩余数据中的最大值和最小值，搭配大了，最大值就要减小，搭配小了，最小值就要增大，这样在基于已经排序的基础之上每一个给定起始点的遍历是唯一的，不需要去测试所有可能的搭配案例。接下来，就需要解决防止元组内容重复的问题。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //根据函数名定义中提供的返回值类型可以给出如下设定
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());//这里的sort函数并不能去重
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0){//经过排序的数组如果起始点大于0,那后面就不用看了
                return result;
            }
            if(i>0 && nums[i]==nums[i-1]){//这里其实是在给数组去重，重复的元素为起点会产生重复的元组
            //这里为什么是nums[i]==nums[i-1]而不是nums[i]==nums[i+1]，代码随想录里有解释，我觉得这个代码很多细节是在不同条件下根据测试用例才可以想完整的，哈哈
                continue;
            }
            int left=i+1;
            int right=nums.size()-1;
            while(right>left){
                if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                }
                else{
                    
                    //到这里还不能去除所有重复的元组
                    //举个例子：[2,-1,-1,-1,-1],此时(left,right)的坐标不同有两种情况，但是元组元素是相同的，题目判定为重复元组
                    //所以，接下来要对剩下两个位置的数去重
                    while(right>left && nums[right]==nums[right-1]) right--;
                    while(right>left && nums[left]==nums[left+1]) left++;
                    //这里必须要使用while循环，如果使用if，只能去除一次重复
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    //找到答案并去重以后，双指针需要同时收缩
                    //下面这两句话是为了实现while循环里找到一个答案后
                    //可以在第一个元素起点相同的情况下找到其它符合条件的方案
                    //也只有找到了一个答案后才会在这个基础之上继续寻找
                    right--;
                    left++;
                }

            }

        }
        return result;
        //不得不说这道题考虑还是要非常周全非常细致才行

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

七、四数之和

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // vector<vector<int>>二维动态数组，用于存储所有的元组答案
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        //在做完三数之和之后，这道题的难点在于target不再是0，而可能是任意一种情况
        //要知道不断改变起始点的时候，即使起始点大于target，不能就直接跳过，因为负数只会越加越小
        for(int k=0;k<nums.size();k++){
            if(nums[k]>target && nums[k]>=0){//这其实是分情况讨论之起点以后所有的数字都是自然数
                break;//跳出循环
            }
            if(k>0 && nums[k]==nums[k-1]){
                continue;//跳过某次迭代
            }
            //先把全是正数的情况完成？
            for(int i=k+1;i<nums.size();i++){//二级排除
            //需要排除(N数-指针数)级
                if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0){
                    break;
                }
                if(i>k+1 && nums[i]==nums[i-1]){
                    continue;
                }
                int left=i+1;
                int right = nums.size()-1;
                while(right>left){
                    if((long)nums[k]+nums[i]+nums[left]+nums[right]==target){
                        //不添加这个long会报错，无法通过测试用例
                        // result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
                        result.insert(result.end(), {nums[k], nums[i], nums[left], nums[right]});
                        while(right > left && nums[left]==nums[left+1]) left++;
 						//right > left && 随想录中给的，我觉得重复了，因为while循环本身的条件就是这个，但是不加这个确实会报错，还没参透内因
                        while(right > left && nums[right]==nums[right-1]) right--;

                        right--;
                        left++;
                        
                    }
                    else if((long)nums[k]+nums[i]+nums[left]+nums[right]>target){
                        right--;

                    }
                    else if((long)nums[k]+nums[i]+nums[left]+nums[right]<target){
                        left++;

                    }
                }
            }
            

            

        }
        return result;

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

PS：经验总结：刷题要考虑数据在工业级场景下的注意事项
特别提示：
在(long)nums[k]+nums[i]+nums[left]+nums[right]==target这个语句中，将nums[k]、nums[i]、nums[left]、nums[right]强制转换为long类型的作用是防止它们相加时溢出。

如果nums[k]、nums[i]、nums[left]、nums[right]的值过大，它们相加后的结果可能会超过int类型所能表示的最大值，从而溢出。为了避免这种情况，可以将这些值先转换为long类型，再进行相加。因为long类型的取值范围比int类型更大，所以即使它们相加后的结果很大，也不会溢出。

需要注意的是，将nums[k]、nums[i]、nums[left]、nums[right]转换为long类型后，它们相加后的结果也需要是long类型。因此，整个表达式的类型为bool，表示判断相加后的结果是否等于target。

哈希表使用总结

戳这里自己看吧，下面的截图也来源于此
在这里插入图片描述

补充：

我们参加笔试时候使用的牛客系统与LeetCode不同，它需要自己把头文件写在编译窗口当中。因此，平时我们不能光学习思想、算法，一些很细节的注意事项也要关注到。
在C++标准库中，可以使用unordered_map和unordered_set容器来实现哈希表。unordered_map容器是一种关联容器，它具有快速查找键值对的特点。unordered_map底层是通过哈希表实现的，每个键值对被映射到一个桶中，桶的位置由键的哈希值决定。因此，unordered_map容器的查找、插入和删除操作的时间复杂度都是O(1)的。
unordered_set容器是一种集合容器，它存储的是一组唯一的元素。unordered_set底层也是通过哈希表实现的，每个元素被映射到一个桶中，桶的位置由元素的哈希值决定。因此，unordered_set容器的查找、插入和删除操作的时间复杂度也都是O(1)的。
头文件记得添加 #include <unordered_map> #include <unordered_set>

字符串专题

一、反转字符串

在这里插入图片描述

基础知识补充：大多数容器都可以使用size()函数来计算元素的个数，因为size()函数是容器的一个成员函数，用于返回容器中元素的数量。例如，对于vector、list、set、map等容器，都可以使用size()函数来计算容器中元素的数量。另外，对于数组，也可以使用sizeof()运算符来计算元素的数量，例如：

int arr[5] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组的元素数量
1
2

不能使用strlen()函数来计算容器中的元素数量，是因为strlen()函数是用于计算以’\0’结尾的C风格字符串的长度的，它的计算方式是从字符串的起始位置开始，逐个遍历字符，直到遇到’\0’为止。但是，C++容器中存储的元素不一定是以’\0’结尾的字符串，因此不能使用strlen()函数来计算元素数量。

方案一：
class Solution {
public:
    void reverseString(vector<char>& s) {
        int L=s.size();
        char temp;
        for(int i=0;i<(L/2);i++){
            temp= s[L-i-1];
            s[L-i-1]=s[i];
            s[i]=temp;
        }
    }
};
方案二：
class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
            //面试手撕代码最好不要用现成的函数，除非你能接受面试官对底层实现的拷打
        }
    }
};
PS：在python中一行代码搞定：s[:] = reversed(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

二、反转字符串II

在这里插入图片描述
常规思路：模拟反转字符串的动作。其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

class Solution {
public:
    string reverseStr(string s, int k) {//感觉题目默认输入的字符串不是以'\0'结尾
        for(int i=0; i<s.size();i+=(2*k))
        //与其在后面的程序中按照step更改数组下标，不如在这里直接改变i的step大小
        //不管是对于剩余字符还是对前面每一组字符，都是对以i为起点的k以内长度的字符做处理
        //简单题重在理清楚框架顺序，中等题会存在很多内部的逻辑完备性考验
        {
            if(i+k<=s.size()){
            //用于处理长度为K的字符串,包括剩余字符(>k && <2k)的情况
            reverse(s.begin()+i,s.begin()+i+k);
            }
            else{//用于处理剩余字符(<k)的情况
                reverse(s.begin()+i,s.end());
            }
        }
        return s;
//如果有严格要求，我们也可以自己设计反转函数，输入为字符串、起始点位置、终点位置，输出为反转后的结果
举例：
 void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[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

三、替换空格

在这里插入图片描述

class Solution {
public:
    string replaceSpace(string s) {
        //首先需要注意到的问题是，当逐个遍历替换内容的时候，当前位置之后所有的元素都需要移动
        //这种操作是什么不简洁的
        //改进的方法减少移动的频次（不是想着尽量不搬移）
        int count=0;
        int L1=s.size();
        for(int i=0;i<L1;i++)
        {
            if(s[i]==' '){
                count++;
            }
        }
        s.resize(s.size()+count*2);//resize()函数记一下
        int L2=s.size();
        //可以开始直接从后往前加元素
        //从原字符串最后一个字符开始向前检索赋值给后面的元素
        for(int i=L2-1, j=L1-1;i>j ;j--,i--){//判断条件我还没反应过来，但的确需要这个
            if(s[j]!=' '){
                s[i]=s[j];
            }
            else{
                s[i]='0';
                s[--i]='2';
                s[--i]='%';
                //在已有的代码随想录的指导下做了点小修改，简化代码量
            }
        }
        return 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
30
31
32
33

使用python来解决这道题，python自身的功能会给予更多的灵活性
方案二：
class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for i in range(len(s)):
            if s[i] == ' ':
                res.append('%20')
            else:
                res.append(s[i])
        return ''.join(res)
熟练使用python的特殊功能会精简很多代码量
1
2
3
4
5
6
7
8
9
10
11
12

四、翻转字符串里的单词

在这里插入图片描述

题外话补充学习：
A. C++中的erase是一个成员函数，用于从容器中删除元素。
它有几种不同的用法，具体如下：

删除单个元素：

container.erase(iterator);
1

其中，container是容器对象，iterator是指向要删除元素的迭代器。此时，erase函数将删除iterator指向的元素，并返回指向被删除元素下一个元素的迭代器。如果要删除容器中的最后一个元素，可以使用pop_back函数。

删除一段元素：

container.erase(start, end);
1

其中，container是容器对象，start和end是迭代器，指定了要删除的元素范围。此时，erase函数将删除从start到end之间的所有元素，并返回指向被删除元素下一个元素的迭代器。

删除满足条件的元素：

container.erase(remove_if(container.begin(), container.end(), condition), container.end());
1

其中，container是容器对象，condition是一个函数对象或lambda表达式，用于判断元素是否应该被删除。此时，erase函数将删除满足condition条件的所有元素，并返回指向被删除元素下一个元素的迭代器。
注意，需要在删除元素后更新迭代器的位置，否则可能会导致未定义的行为。此外，如果容器中的元素是指针或其它引用类型，需要注意在删除元素后，对应的指针或引用可能会失效。
B. 容器与迭代器之间的关系（侯捷老师的STL专题课程里有详细说明）

在C++中，容器是一种可以存储和管理一组数据的数据结构。容器中的数据可以是各种类型，例如整型、浮点型、字符串、对象等。容器可以分为序列式容器和关联式容器两种类型。常见的序列式容器有vector、list、deque等，而常见的关联式容器有map、set等。

迭代器（Iterator）是一种用于访问容器中元素的对象，类似于指针的概念。通过迭代器可以访问容器中的元素，包括读取元素的值、修改元素的值、插入元素和删除元素等操作。迭代器是一个抽象的概念，不同类型的容器对应不同类型的迭代器。

迭代器通常定义在容器中，可以通过容器的成员函数begin()和end()获取容器的迭代器。其中，begin()返回一个指向容器中第一个元素的迭代器，end()返回一个指向容器中最后一个元素的下一个位置的迭代器。使用迭代器可以遍历容器中的元素，例如：

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << std::endl;
}
1
2
3
4

上述代码中，vec.begin()返回一个指向vec中第一个元素的迭代器，vec.end()返回一个指向vec中最后一个元素的下一个位置的迭代器。在循环中，通过迭代器遍历容器中的元素，并输出它们的值。

需要注意的是，对一个迭代器进行解引用（*it）操作，可以获取到该迭代器指向的元素的值。此外，迭代器也可以进行算术运算，例如it++和it–，以及it+n和it-n等操作，其中n为整数。所以它和指针的作用效果及功能看起来真的挺像的。

其实如果学透了python的诸多功能，解决算法题可能是最节省时间的。
这道题用python做效果真的炸裂。

class Solution:
    def reverseWords(self, s: str) -> str:
       return " ".join(s.split( )[::-1])
1
2
3

熟悉掌握python中的各种函数和功能并灵活使用是真的香！但是面试官还是会倾向于不使用标准库工具的人才

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/cm456/article/detail/62902