[数据结构与算法]【AcWing07】【LeetCode】双指针-11/13

这里的指针，并非专指c中指针的概念，而是指索引，游标或指针，可迭代对象等.

模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

数组求和

#include<iostream>
using namespace std;
const int N=1000010;
int a[N],b[N];
int n,m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];

    for(int i=1,j=m;i<=n;i++){
       while(j>0&&a[i]+b[j]>k)
        {
             j--;
        }
        if(j>0&&a[i]+b[j]==k)
          cout<<i-1<<" "<<j-1<<endl;
    }
    return 0;
}

最大子序列

#include<iostream>
using namespace std;

const int N=100010;
int a[N],s[N];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int res=0;
   for(int i=0,j=0;i<n;i++){
        s[a[i]]++;
       while(s[a[i]]>1){
            s[a[j]]--;
            j++;

        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}

双指针与排序

快速排序

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;// 判断排序的数字长度

    int i = l - 1, j = r + 1, x = q[l];
    //选取双指针i,j与 中间随机值
    while (i < j)
    {
        //进行判断比较大小并交换值
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        //注意！！！使用语言有没有swap方法（如果没有建议用位运算）
        else break;
    }
    //再将俩个部分（小于等于随机值||大于小于随机值）再次划分
    quick_sort(q, l, j),;
    quick_sort(q, j + 1, r);
}

归并排序

void merge_sort(int q[], int l, int r)
{
if (l >= r) return;//元素为0 or 1
int mid = l + r >> 1;//选取中间值
//划分区间
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
//确定双指针
int k = 0, i = l, j = mid + 1;
//条件一
while (i <= mid && j <= r)
//边界判断
if (q[i] < q[j]) tmp[k ] = q[i ];
else tmp[k ] = q[j ];
//条件二 
//左边没有循环完
while (i <= mid) tmp[k ] = q[i ];
//条件三
//右边没有循环完
while (j <= r) tmp[k ] = q[j ];
//合并
for (i = l,j = 0; i <= r; i , j ) q[i]= tmp[j];
}

奇偶排序

void function(int arr[],int n){
    int i = 0;
    int j = n-1;
        while(i<j){
        //if(i==j) break；刚开始打错了，谢谢提醒提醒
            while(i<j && arr[i]%2 == 1) i++;
            while(i<j && arr[j]%2 == 0) j--;
            if(i<j)swap(arr[i],arr[j]);
        }
}

Leetcode 11. 盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                max(res, (j - i) * height[i++]): 
                max(res, (j - i) * height[j--]); 
        }
        return res;
    }
};

Leetcode 13. 罗马数字转整数

例如MCMXCIV，从右往左依次遍历：
V +5 第一个数字，永远做加法
I -1 比右边小，做减法
C +100 比右边大，做加法
X -10 比右边小，做减法
M +1000 比右边大，做加法
C -100 比右边小，做减法
M +1000 比右边大，做加法
结果全部累加，即可得到答案1994。

class Solution {
public:
    int romanToInt(string s) {
        int sum = 0;
        int n = 0;
        int lastn = 0;
        // 从右往左反向遍历
        for (int i=s.size()-1; i>=0; i--) {
            if (s[i] == 'I') n = 1;
            else if (s[i] == 'V') n = 5;
            else if (s[i] == 'X') n = 10;
            else if (s[i] == 'L') n = 50;
            else if (s[i] == 'C') n = 100;
            else if (s[i] == 'D') n = 500;
            else if (s[i] == 'M') n = 1000;
            // 不是首个, 且数字比右边的小, 则属于特殊规则, 做减法, 其余情况做加法
            if (sum != 0 && n < lastn) {
                n = -n;
            }
            lastn = n;
            sum += n;
        }
        return sum;
    }
};