[数据结构与算法]一星期冲刺蓝桥杯备赛题单及详解

七天冲刺蓝桥杯备赛题单及详解

说明：

• 选用平台：leetcode
• 选用语言：c++
• 难度：煎蛋
• 覆盖知识点：递归、链表

题单

day1：康复训练，基础题，无数据结构

leetcode-简单题：70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：88. 合并两个有序数组 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：283. 移动零 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：448. 找到所有数组中消失的数字 - 力扣（LeetCode） (leetcode-cn.com)

day2：链表专题

leetcode-简答题：21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：83. 删除排序链表中的重复元素 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-中等题：142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：234. 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)

leetcode-简单题：剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode） (leetcode-cn.com)

c++代码与详解

day1

爬楼梯

leetcode：70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)

这个题的坑在于不能用递归，leetcode会报超时，改用dp，用数组记录结果

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a[46];
        a[1] = 1;
        a[2] = 2;
        for(int i = 3; i <= n; i++){
            a[i] = a[i-1] + a[i-2];
        }
        return a[n];
    }
};

斐波那契数列

leetcode：剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode） (leetcode-cn.com)

这个题的坑是：第一次提交结果忘了取模，重新加上取模就OK了

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int a[101];
        a[0] = 0;
        a[1] = 1;
        for(int i = 2; i <= n; i++){
            a[i] = a[i-1]%(1000000007) + a[i-2]%(1000000007);
        }
        return a[n]%(1000000007);
    }
};

两数之和

暴力yyds

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <int> ans;
        map <int,int> mp;
        int size = nums.size();
        for(int i = 0; i < size; i++){
            int iter = mp.find(target - nums[i]);
            if(iter != mp.end()){
                ans.push_back(i]);
                ans.push_back(mp.find(target - nums[i]))
                return ans;
            }else{
                mp[nums[i]] = i;
            }
        }
        
    }
};

合并两个有序数组

sort yyds stl yyds， vector排序是要传入迭代器，不能直接排~

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0; i < n; i++){
            nums1[i+m] = nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

移动零

属于是非常直，连弯都没有的那种了

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector <int> temp;
        int size = nums.size();
        for(int i = 0; i < size; i++){
            if(nums[i] != 0) temp.push_back(nums[i]);
        }
        int size2 = temp.size();
        for(int i = 0; i < size2; i++){
            nums[i] = temp[i];
        }
        for(int i = size2; i < size; i++){
            nums[i] = 0;
        }
    }
};

找到所有数组中消失的数字

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector <int> ans;
        int size = nums.size(),a[size+1];
        for(int i = 1; i <= size; i++){
            a[i] = i; 
        }
        for(int i = 0; i < size; i++){
            a[nums[i]] = 0;
        }
        for(int i = 1; i <= size; i++){
            if(a[i] != 0){
                ans.push_back(i);
            }
        }
        return ans;
    }
};

day2

合并两个有序链表

做链表的题需要先在脑子里想清楚，每个节点需要怎么连接，有条件的话可以画一下图，理清逻辑后在写代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list2 == NULL && list1 == NULL) return NULL;
        ListNode *ans = new ListNode(0,NULL);
        ListNode *temp = ans;
        while(list1 != NULL || list2 || NULL){
            if(list1 == NULL){
                temp -> next = list2;
                return ans -> next;
            }else if(list2 == NULL){
                temp -> next = list1;
                return ans -> next;
            }else{
                if(list1->val > list2->val){
                    ListNode *temp2 = new ListNode(list2->val,NULL);
                    temp -> next = temp2;
                    temp = temp -> next;
                    list2 = list2 -> next;
                }else{
                    ListNode *temp2 = new ListNode(list1->val,NULL);
                    temp -> next = temp2;
                    temp = temp -> next;
                    list1 = list1 -> next;
                }
            }
        }
        return ans;
    }
};

删除排序链表中的重复元素

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *ans = new ListNode(0,NULL);
        ListNode *temp = ans;
        int last=-101,flag;
        while(head != NULL){
           flag = 1;
           if(head->val == last) flag = 0;
           if(flag == 1){
               ListNode *temp2 = new ListNode(head->val,NULL);
               temp -> next = temp2;
               temp = temp -> next;
               last = head -> val;
           }
           head = head->next;
        }
        return ans -> next;
    }
};

环形链表

题目中说链表的节点数目是 [0,10⁴]，所以循环10⁴次后，head仍不为NULL，就是循环链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        int cnt = 0;
        while(head != NULL){
            cnt++;
            head = head -> next;
            if(cnt > 10000) return true;
        }
        return false;
    }
};

环形链表2

快慢双指针，第一次相遇时相等，第二次相遇是循环开始

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode *slowIndex = head,*fastIndex = head;
        int ifHasCircle = 0;
        while(fastIndex -> next != NULL && fastIndex -> next -> next != NULL){
            slowIndex = slowIndex -> next;
            fastIndex = fastIndex -> next -> next;
            if(slowIndex == fastIndex){
                ifHasCircle = 1;
                break;
            }
        }
        if(ifHasCircle == 0) return NULL;
        slowIndex = head;
        while(slowIndex != fastIndex){
            slowIndex = slowIndex->next;
            fastIndex = fastIndex->next;
        }
        return slowIndex;
    }
};

相交链表

双指针，走完自己的链表后去走别人的，最后总距离一定相等！

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headB == NULL || headA == NULL) return NULL;
        ListNode *indexa = headA,*indexb = headB;
        while(indexa != indexb){
            indexa = indexa == NULL ? headB : indexa -> next;
            indexb = indexb == NULL ? headA : indexb -> next;
        }
        return indexb;
    }
};

反转链表

新建一个链表，将val倒序存进去

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return NULL;
        ListNode *ans = new ListNode(head->val);
        head = head->next;
        while(head != NULL){
            ListNode *temp = new ListNode(head->val,ans);
            head = head -> next;
            ans = temp;
        }
        return ans;
    }
};

回文链表

三步走：

1. 找到中间结点
2. reverse后半部分
3. 对比

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *fast = head,*slow = head,*prev = NULL;
        // 找到中间节点
        while(fast){
            slow = slow->next;
            fast = fast->next ? fast->next->next : fast->next;
        }
        // 翻转
        while(slow){
            ListNode *temp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = temp;
        }
        // 对比
        while(head && prev){
            if(head -> val != prev->val){
                return false;
            }
            head = head -> next;
            prev = prev -> next;
        }

        return true;
    }
};

链表的中间节点

双指针，一个走2，一个走1，2走到头，1走到中间

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL) return NULL;
        ListNode *pa = head,*pb = head;
        while(pa -> next != NULL && pa -> next -> next != NULL){
            pa = pa -> next -> next;
            pb = pb -> next;
        }
        if(pa -> next != NULL){
            return pb -> next;
        }else{
            return pb;
        }
    }
};

链表中倒数第k个结点

两次循环，第一次统计节点个数，第二次找到第k个结点

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL) return NULL;
        int cnt = 0,cnt2=0;
        ListNode *temp = head;
        while(temp != NULL){
            cnt++;
            temp = temp->next;
        }
        temp = head;
        while(cnt2 < cnt-k){
            cnt2++;
            temp = temp->next;
        }
        return temp;
    }
};