《算法集训传送门》

  👉引言

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

---

今日主题：双指针

---

 👉⭐️第一题💎

   ✨题目

      1.合并两个有序数组

   ✨思路：

双指针解法，边比较两边大小，取较小的数放到nums1中（这里直接暴力排序做的）

   ✨代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            vector<int>temp(m+n);
            int j=0;
            for(int i=0;i<m;i++){
                temp[j++]=nums1[i];
            }
            for(int i=0;i<n;i++){
                temp[j++]=nums2[i];
            }
            sort(temp.begin(),temp.end());
            nums1=temp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 👉⭐️第二题💎

   ✨题目

      2.环形链表

快慢指针法，假设慢指针每次只移动一步，而快指针每次移动两步。如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

   ✨代码：

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 👉⭐️第三题💎

   ✨题目

      3.三数之和

   ✨思路：

首先不考虑暴力枚举，因为题目中要求找到所有不重复的三元组，暴力的话时间复杂度就太高了，所以这里选择 双指针与排序解法

   ✨代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int first = 0; first < n; ++first) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; ++second) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

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

 👉⭐️第四题💎

   ✨题目

      4.Z mod X = C

   ✨代码：

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c << " " << b + c << " " << c << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！