阿Q技术站

深浅色

双指针 ​

1、合并两个有序的数组 ​

1.1、问题描述 ​

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组。

示例1

输入：[4,5,6],[1,2,3]

返回值：[1,2,3,4,5,6]

说明：

A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组

示例2

输入：[1,2,3],[2,5,6]

返回值：[1,2,2,3,5,6]

1.2、思路及代码 ​

思路：

  1. 初始化两个指针，分别指向数组 A 和数组 B 的有效元素的末尾。
  2. 从数组 A 和数组 B 的末尾开始比较元素，将较大的元素放入数组 A 的末尾，并将相应指针向前移动。
  3. 当数组 B 的元素全部合并到数组 A 中，或者数组 A 的元素已经全部处理完，合并过程结束。

参考代码：

C++
#include <iostream>
#include <vector>

using namespace std;

// 函数：合并两个有序数组
void merge(vector<int>& A, int m, vector<int>& B, int n) {
    int i = m - 1; // 指向数组 A 的有效元素的末尾
    int j = n - 1; // 指向数组 B 的末尾
    int k = m + n - 1; // 指向数组 A 的最终末尾，即合并后的末尾

    // 从后往前比较并合并
    while (i >= 0 && j >= 0) {
        if (A[i] > B[j]) {
            A[k--] = A[i--];
        } else {
            A[k--] = B[j--];
        }
    }

    // 如果数组 B 中还有元素未合并，将其复制到数组 A 中
    while (j >= 0) {
        A[k--] = B[j--];
    }
}

int main() {
    // 输入两个有序数组
    vector<int> A1 = {4, 5, 6, 0, 0, 0};
    vector<int> B1 = {1, 2, 3};
    int m1 = 3;
    int n1 = 3;

    vector<int> A2 = {1, 2, 3};
    vector<int> B2 = {2, 5, 6};
    int m2 = 3;
    int n2 = 3;

    // 合并数组
    merge(A1, m1, B1, n1);
    merge(A2, m2, B2, n2);

    // 输出结果
    cout << "示例1结果: [";
    for (int num : A1) {
        cout << num << " ";
    }
    cout << "]" << endl;  // 期望输出: [1 2 3 4 5 6]

    cout << "示例2结果: [";
    for (int num : A2) {
        cout << num << " ";
    }
    cout << "]" << endl;  // 期望输出: [1 2 2 3 5 6]

    return 0;
}

2、判断是否为回文字符串 ​

2.1、问题描述 ​

给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。

字符串回文指该字符串正序与其逆序逐字符一致。

示例1

输入："absba"

返回值：true

示例2

输入："ranko"

返回值：false

示例3

输入："yamatomaya"

返回值：false

示例4

输入："a"

返回值：true

2.2、思路及代码 ​

思路：

  1. 定义两个指针，一个指向字符串的开头，一个指向字符串的末尾。
  2. 比较两个指针指向的字符是否相等，如果相等，则继续向中间移动；如果不相等，则说明不是回文，返回 false。
  3. 重复步骤2，直到两个指针相遇或者交叉。

参考代码：

C++
#include <iostream>
#include <string>

using namespace std;

// 函数：判断字符串是否为回文
bool isPalindrome(string s) {
    // 定义两个指针，一个指向开头，一个指向末尾
    int start = 0;
    int end = s.length() - 1;

    // 比较两个指针指向的字符是否相等，向中间移动
    while (start < end) {
        // 忽略非字母和数字字符
        while (start < end && !isalnum(s[start])) {
            start++;
        }
        while (start < end && !isalnum(s[end])) {
            end--;
        }

        // 比较字符是否相等，不区分大小写
        if (tolower(s[start]) != tolower(s[end])) {
            return false;
        }

        // 向中间移动指针
        start++;
        end--;
    }

    // 如果整个过程中没有发现不相等的字符，则是回文
    return true;
}

int main() {
    // 输入字符串
    string s1 = "absba";
    string s2 = "ranko";
    string s3 = "yamatomaya";
    string s4 = "a";

    // 输出结果
    cout << "示例1结果: " << (isPalindrome(s1) ? "true" : "false") << endl; // 期望输出: true
    cout << "示例2结果: " << (isPalindrome(s2) ? "true" : "false") << endl; // 期望输出: false
    cout << "示例3结果: " << (isPalindrome(s3) ? "true" : "false") << endl; // 期望输出: false
    cout << "示例4结果: " << (isPalindrome(s4) ? "true" : "false") << endl; // 期望输出: true

    return 0;
}

3、合并区间 ​

3.1、问题及描述 ​

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

示例1

输入：[[10,30],[20,60],[80,100],[150,180]]

返回值：[[10,60],[80,100],[150,180]]

示例2

输入：[[0,10],[10,20]]

3.2、思路及代码 ​

思路：

  1. 对区间数组按照起点升序排序。
  2. 使用两个指针，一个指向当前合并的区间的起点，一个指向当前合并的区间的终点。
  3. 遍历排序后的区间数组，对于每个区间：
    1. 如果当前区间的起点在当前合并区间的范围内，则扩展当前合并区间的终点。
    2. 如果当前区间的起点不在当前合并区间的范围内，则将当前合并区间加入结果，并更新当前合并区间为当前区间。
  4. 最后将最后一个合并区间加入结果。

参考代码：

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义区间的数据结构
struct Interval {
    int start;
    int end;

    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

// 函数：合并重叠区间
vector<Interval> mergeIntervals(vector<Interval>& intervals) {
    // 如果区间数组为空，直接返回空数组
    if (intervals.empty()) {
        return {};
    }

    // 对区间数组按照起点升序排序
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });

    // 合并区间的结果数组
    vector<Interval> result;

    // 初始化合并区间的起点和终点
    int start = intervals[0].start;
    int end = intervals[0].end;

    // 遍历区间数组
    for (const Interval& interval : intervals) {
        // 如果当前区间的起点在合并区间的范围内，则扩展合并区间的终点
        if (interval.start <= end) {
            end = max(end, interval.end);
        } else {
            // 如果当前区间的起点不在合并区间的范围内，则将当前合并区间加入结果，并更新合并区间
            result.push_back(Interval(start, end));
            start = interval.start;
            end = interval.end;
        }
    }

    // 将最后一个合并区间加入结果
    result.push_back(Interval(start, end));

    return result;
}

// 输出区间数组
void printIntervals(const vector<Interval>& intervals) {
    cout << "[";
    for (const Interval& interval : intervals) {
        cout << "[" << interval.start << "," << interval.end << "] ";
    }
    cout << "]" << endl;
}

int main() {
    // 输入区间数组
    vector<Interval> intervals1 = {{10, 30}, {20, 60}, {80, 100}, {150, 180}};
    vector<Interval> intervals2 = {{0, 10}, {10, 20}};

    // 合并区间
    vector<Interval> result1 = mergeIntervals(intervals1);
    vector<Interval> result2 = mergeIntervals(intervals2);

    // 输出结果
    cout << "示例1结果: ";
    printIntervals(result1); // 期望输出: [[10,60],[80,100],[150,180]]

    cout << "示例2结果: ";
    printIntervals(result2); // 期望输出: [[0,20]]

    return 0;
}

4、最小覆盖子串 ​

4.1、问题描述 ​

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

示例1

输入："XDOYEZODEYXNZ","XYZ"

返回值："YXNZ"

示例2

输入："abcAbA","AA"

返回值："AbA"

4.2、思路及代码 ​

思路：

  1. 使用两个指针 left 和 right 表示子串的左右边界，初始化为字符串 s 的开头。
  2. 移动右指针 right 直到包含了字符串 t 中的所有字符。
  3. 缩小子串范围，移动左指针 left，直到不能再缩小为止，期间记录最小子串的起始位置和长度。
  4. 重复步骤2和3，直到右指针 right 到达字符串 s 的末尾。
  5. 返回最小子串。

参考代码：

C++
#include <iostream>
#include <unordered_map>

using namespace std;

// 函数：在字符串 s 中找出包含 t 中所有字符的最短子串
string minWindow(string s, string t) {
    unordered_map<char, int> targetFreq, currentFreq;
    // 初始化目标字符频率
    for (char ch : t) {
        targetFreq[ch]++;
    }

    int left = 0; // 左指针
    int right = 0; // 右指针
    int minLen = INT_MAX; // 最小子串长度
    int minStart = 0; // 最小子串的起始位置

    int requiredChars = targetFreq.size(); // 需要匹配的字符种类数量

    while (right < s.size()) {
        char rightChar = s[right];

        // 更新当前字符频率
        currentFreq[rightChar]++;

        // 如果当前字符频率达到目标字符频率，则需要匹配的字符种类数量减少
        if (currentFreq[rightChar] == targetFreq[rightChar]) {
            requiredChars--;
        }

        // 当需要匹配的字符种类数量为0时，说明当前子串包含了字符串 t 中的所有字符
        while (requiredChars == 0) {
            // 更新最小子串信息
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            char leftChar = s[left];

            // 缩小子串范围，左指针向右移动
            currentFreq[leftChar]--;
            if (currentFreq[leftChar] < targetFreq[leftChar]) {
                requiredChars++;
            }

            left++;
        }

        // 右指针向右移动
        right++;
    }

    // 如果找到了符合条件的子串，则返回最小子串，否则返回空字符串
    return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}

int main() {
    // 输入字符串
    string s1 = "XDOYEZODEYXNZ";
    string t1 = "XYZ";
    string s2 = "abcAbA";
    string t2 = "AA";

    // 输出结果
    cout << "示例1结果: " << minWindow(s1, t1) << endl; // 期望输出: "YXNZ"
    cout << "示例2结果: " << minWindow(s2, t2) << endl; // 期望输出: "AbA"

    return 0;
}

5、反转字符串 ​

5.1、问题描述 ​

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）。

示例1

输入："abcd"

返回值："dcba"

示例2

输入：""

返回值：""

5.2、思路及代码 ​

思路：

  1. 使用两个指针，一个指向字符串的开头，一个指向字符串的末尾。
  2. 交换两个指针指向的字符，然后将两个指针向中间移动，继续交换，直到两个指针相遇或者交叉。

参考代码：

C++
#include <iostream>
#include <string>

using namespace std;

// 函数：反转字符串
string reverseString(string s) {
    int left = 0; // 左指针
    int right = s.length() - 1; // 右指针

    while (left < right) {
        // 交换两个指针指向的字符
        swap(s[left], s[right]);

        // 向中间移动指针
        left++;
        right--;
    }

    return s;
}

int main() {
    // 输入字符串
    string input1 = "abcd";
    string input2 = "";

    // 输出结果
    cout << "示例1结果: " << reverseString(input1) << endl; // 期望输出: "dcba"
    cout << "示例2结果: " << reverseString(input2) << endl; // 期望输出: ""

    return 0;
}

6、最长无重复子数组 ​

6.1、问题描述 ​

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

示例1

输入：[2,3,4,5]

返回值：4

说明：[2,3,4,5]是最长子数组

示例2

输入：[2,2,3,4,3]

返回值：3

说明：[2,3,4]是最长子数组

示例3

输入：[9]

返回值：1

6.2、思路及代码 ​

思路：

  1. 使用两个指针 left 和 right 表示当前无重复元素子数组的起始和结束位置，初始化为数组的开头。
  2. 使用一个哈希表记录元素的索引，即每个元素最后出现的位置。
  3. 遍历数组，对于每个元素：
    1. 如果元素在哈希表中不存在，或者其索引小于等于 left，说明当前元素没有重复，可以扩展无重复元素子数组的范围。
    2. 如果元素在哈希表中存在且索引大于 left，说明当前元素重复了，需要缩小无重复元素子数组的范围，将 left 移动到重复元素的下一个位置。
  4. 计算每次扩展无重复元素子数组范围时的长度，并更新最大长度。

参考代码：

C++
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 函数：返回最长无重复元素子数组的长度
int maxLengthOfUniqueSubarray(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) {
        return n; // 数组长度为1或者0时，最长无重复子数组长度为数组长度
    }

    unordered_map<int, int> lastIndex; // 哈希表记录元素的索引
    int left = 0; // 左指针
    int maxLength = 0; // 最长无重复子数组长度

    for (int right = 0; right < n; right++) {
        int current = arr[right];

        // 如果元素在哈希表中不存在，或者其索引小于等于 left，说明当前元素没有重复
        if (lastIndex.find(current) == lastIndex.end() || lastIndex[current] <= left) {
            // 扩展无重复元素子数组的范围
            maxLength = max(maxLength, right - left + 1);
        } else {
            // 如果元素在哈希表中存在且索引大于 left，说明当前元素重复了
            // 需要缩小无重复元素子数组的范围，将 left 移动到重复元素的下一个位置
            left = lastIndex[current] + 1;
        }

        // 更新元素的索引
        lastIndex[current] = right;
    }

    return maxLength;
}

int main() {
    // 输入数组
    vector<int> arr1 = {2, 3, 4, 5};
    vector<int> arr2 = {2, 2, 3, 4, 3};
    vector<int> arr3 = {9};

    // 输出结果
    cout << "示例1结果: " << maxLengthOfUniqueSubarray(arr1) << endl; // 期望输出: 4
    cout << "示例2结果: " << maxLengthOfUniqueSubarray(arr2) << endl; // 期望输出: 3
    cout << "示例3结果: " << maxLengthOfUniqueSubarray(arr3) << endl; // 期望输出: 1

    return 0;
}

7、盛水最多的容器 ​

7.1、问题描述 ​

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水。

1.你不能倾斜容器

2.当n小于2时，视为不能形成容器，请返回0

3.数据保证能容纳最多的水不会超过整形范围，即不会超过2(31)-1

如输入的height为[1,7,3,2,4,5,8,2,7]，那么如下图:

image-20240121200657553

示例1

输入：[1,7,3,2,4,5,8,2,7]

返回值：49

示例2

输入：[2,2]

返回值：2

示例3

输入：[5,4,3,2,1,5]

返回值：25

7.2、思路及代码 ​

思路：

  1. 使用两个指针 left 和 right 分别指向数组的开头和结尾。
  2. 计算当前容器的盛水量，即 min(height[left], height[right]) * (right - left)。
  3. 将指向较小高度的指针向内移动，以寻找更高的高度，因为移动较大高度的指针不会得到更大的盛水量，而移动较小高度的指针可能找到更高的高度。
  4. 重复步骤2和3，直到两个指针相遇。

参考代码：

C++
#include <iostream>
#include <vector>

using namespace std;

// 函数：计算容器最多能容纳的水量
int maxWaterContainer(vector<int>& height) {
    int n = height.size();
    if (n < 2) {
        return 0; // 当n小于2时，无法形成容器，返回0
    }

    int left = 0; // 左指针
    int right = n - 1; // 右指针
    int maxWater = 0; // 最大水量

    while (left < right) {
        // 计算当前容器的盛水量
        int currentWater = min(height[left], height[right]) * (right - left);
        // 更新最大水量
        maxWater = max(maxWater, currentWater);

        // 移动较小高度的指针，以寻找更高的高度
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

int main() {
    // 输入数组
    vector<int> height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    vector<int> height2 = {4, 3, 2, 1, 4};
    vector<int> height3 = {1, 2, 1};

    // 输出结果
    cout << "示例1结果: " << maxWaterContainer(height1) << endl; // 期望输出: 49
    cout << "示例2结果: " << maxWaterContainer(height2) << endl; // 期望输出: 16
    cout << "示例3结果: " << maxWaterContainer(height3) << endl; // 期望输出: 2

    return 0;
}

8、接雨水问题 ​

8.1、问题描述 ​

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)。

image-20240121200810608

示例1

输入：[3,1,2,5,2,4]

返回值：5

说明：

数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。

示例2

输入：[4,5,1,3,2]

返回值：2

8.2、思路及代码 ​

思路：

  1. 使用两个指针 left 和 right 分别指向数组的开头和结尾。
  2. 使用两个变量 leftMax 和 rightMax 分别表示左侧和右侧的最大高度，初始化为数组的两端高度。
  3. 使用一个变量 result 来累计雨水量，初始化为0。
  4. 当 left 小于等于 right 时，进行以下操作：
    1. 如果 height[left] <= height[right] 且 height[left] <= leftMax，说明 left 处可以存水，累加雨水量并更新 leftMax。
    2. 如果 height[left] > leftMax，更新 leftMax。
    3. 否则，移动 left 指针。
    4. 对于右侧同理。
  5. 重复步骤4，直到 left 大于 right。

参考代码：

C++
#include <iostream>
#include <vector>

using namespace std;

// 函数：计算能接的雨水量
int trapRainWater(vector<int>& height) {
    int n = height.size();
    if (n <= 2) {
        return 0; // 当数组长度小于等于2时，无法形成雨水池，返回0
    }

    int left = 0; // 左指针
    int right = n - 1; // 右指针
    int leftMax = height[left]; // 左侧最大高度
    int rightMax = height[right]; // 右侧最大高度
    int result = 0; // 雨水量

    while (left <= right) {
        // 如果左侧高度小于等于右侧高度且小于等于左侧最大高度
        if (height[left] <= height[right] && height[left] <= leftMax) {
            // 左侧可以存水，累加雨水量
            result += leftMax - height[left];
            // 更新左侧最大高度
            leftMax = max(leftMax, height[left]);
            // 移动左指针
            left++;
        } else if (height[left] > leftMax) {
            // 如果左侧高度大于左侧最大高度，更新左侧最大高度
            leftMax = height[left];
            // 移动左指针
            left++;
        } else if (height[right] <= rightMax) {
            // 如果右侧高度小于等于左侧高度且小于等于右侧最大高度
            // 右侧可以存水，累加雨水量
            result += rightMax - height[right];
            // 更新右侧最大高度
            rightMax = max(rightMax, height[right]);
            // 移动右指针
            right--;
        } else {
            // 如果右侧高度大于右侧最大高度，更新右侧最大高度
            rightMax = height[right];
            // 移动右指针
            right--;
        }
    }

    return result;
}

int main() {
    // 输入数组
    vector<int> arr1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    vector<int> arr2 = {4,2,0,3,2,5};

    // 输出结果
    cout << "示例1结果: " << trapRainWater(arr1) << endl; // 期望输出: 6
    cout << "示例2结果: " << trapRainWater(arr2) << endl; // 期望输出: 9

    return 0;
}