刷题09 双指针

2540. 最小公共值

给你两个整数数组 nums1 和 nums2 ，它们已经按非降序排序，请你返回两个数组的 最小公共整数 。如果两个数组 nums1 和 nums2 没有公共整数，请你返回 -1 。

如果一个整数在两个数组中都 至少出现一次 ，那么这个整数是数组 nums1 和 nums2 公共 的。

输入：nums1 = [1,2,3], nums2 = [2,4]
输出：2
解释：两个数组的最小公共元素是 2 ，所以我们返回 2 。

        暴力循环会超时，用两个指针进行寻找下标。 

int getCommon(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int idx1=0,idx2=0;
    while(idx1<nums1Size&&idx2<nums2Size){
        if(nums1[idx1]==nums2[idx2]){
            return nums1[idx1];
        }else{
            if(nums1[idx1]<nums2[idx2]){
                idx1++;
            }else{
                idx2++;
            }
        }
    }
    return -1;
}

2562. 找出数组的串联值

给你一个下标从 0 开始的整数数组 nums 。现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。

如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

输入：nums = [7,52,2,4]
输出：596
解释：在执行任一步操作前，nums 为 [7,52,2,4] ，串联值为 0 

long long findTheArrayConcVal(int* nums, int numsSize){
    int l=0,r=numsSize-1;
    long long ans=0;
    int pre,back;
    while(l<r){
        pre=nums[l++],back=nums[r--];
        while(back){
            pre*=10;
            back/=10;
        }
        ans+=pre+nums[r+1];
    }
    if(r==l) ans+=nums[l];
    return ans;
}

2824. 统计和小于目标的下标对数目

 给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

输入：nums = [-1,1,2,3,1], target = 2
输出：3

        暴力法：

int countPairs(int* nums, int numsSize, int target){
    int ans=0;
    for(int i=0;i<numsSize;++i){
        for(int j=i+1;j<numsSize;++j){
            if(nums[i]+nums[j]<target){
                ans++;
            }
        }
    }
    return ans;
}

        双指针法:

int cmp(int *a, int *b) {
    return *a - *b;
}
int countPairs(int* nums, int numsSize, int target){
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans=0;
    int i=0,j=numsSize-1;
    while(i<j){
        if(nums[i]+nums[j]<target){
            ans+=j-i;
            i++;
        }else{
            j--;
        }
    }
    return ans;
}

443. 压缩字符串 

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

• 如果这一组长度为 1 ，则将字符追加到 s 中。
• 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

输入：chars = ["a","a","b","b","c","c","c"]
输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。

int compress(char* chars, int charsSize){
    char* res=malloc(sizeof(char)*2000);
    int len=0;
    int l=0,r=0;
    while(r<charsSize){
        int count=0;
        while(r<charsSize&&chars[l]==chars[r]){
            r++;
        }
        chars[len++]=chars[l];
        count=r-l;
        if(count>1){
            char tmp[10];
            sprintf(tmp,"%d",count);
            for(int i=0;i<strlen(tmp);++i) {
                chars[len++]=tmp[i];
            }
        }
        l=r;
    }
    return len;
}

 
1679. K 和数对的最大数目

 给你一个整数数组 nums 和一个整数 k 每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。返回你可以对数组执行的最大操作数。

输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。

int cmp(int *a,int *b){
    return *a-*b;
}
int maxOperations(int* nums, int numsSize, int k){
    qsort(nums,numsSize,sizeof(int),cmp);
    int ans=0;
    int l=0,r=numsSize-1;
    while(l<r){
        int sum=nums[l]+nums[r];
        if(sum<k){
            l++;
        }else if(sum>k){
            r--;
        }else{
            ans++;
            l++;r--;
        }
    }
    return ans;
}

31. 下一个排列 

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。

类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。

而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

输入：nums = [1,2,3]
输出：[1,3,2]

void nextPermutation(int* nums, int numsSize) {
    int i=numsSize-2;
    //找到第一个非降序的i
    while(i>=0&&nums[i]>=nums[i+1]){
        i--;
    }
    if(i>=0){
        int j=numsSize-1;
        //找到大于nums[i]最大的数
        while(j>=0&&nums[i]>=nums[j]){
            j--;
        }
        //交换
        char tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    //将i后面的数反转
    int l=i+1,r=numsSize-1;
    while(l<r){
        char tmp=nums[l];
        nums[l]=nums[r];
        nums[r]=tmp;
        l++;r--;
    }
}

556. 下一个更大元素 III 

 给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ,返回-1

输入：n = 12                 输入：n = 21
输出：21           ​​​​​​​          输出：-1

int nextGreaterElement(int n) {
    char nums[32];
    sprintf(nums,"%d",n);
    int i=strlen(nums)-2;
    //找第一个非递减的i
    while(i>=0&&nums[i]>=nums[i+1]){
        i--;
    }
    if(i<0) return -1;
    int j=strlen(nums)-1;
    //找到第一个大于nums[i]的j
    while(j>=0&&nums[i]>=nums[j]){
        j--;
    }
    //交换
    char tmp=nums[i];
    nums[i]=nums[j];
    nums[j]=tmp;
    //将i后面的数字反转
    int l=i+1,r=strlen(nums)-1;
    while(l<r){
        char tmp=nums[l];
        nums[l]=nums[r];
        nums[r]=tmp;
        l++;r--;
    }
    long long ans=atol(nums);
    if(ans>INT_MAX||ans<INT_MIN) return -1;
    return ans;
}

面试题 16.06. 最小差

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)

int cmp(int* a, int* b) {
    return *a-*b;
}
int smallestDifference(int* a, int aSize, int* b, int bSize){
    if(a==NULL||aSize==0||b==NULL||bSize==0) {
        return 0;
    }
    qsort(a, aSize, sizeof(int), cmp);
    qsort(b, bSize, sizeof(int), cmp);
    int i=0,j=0;
    long ans=abs((long)(a[0]-b[0]));
    while(i<aSize&&j<bSize){
        if(a[i]!=b[j]){
            long cur=abs((long)a[i]-(long)b[j]);
            ans=fmin(ans,cur);
            if(a[i]>b[j]){
                j++;
            }else{
                i++;
            }
        }else{
            return 0;
        }
    }
    return ans;
}

80. 删除有序数组中的重复项 II 

 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

int removeDuplicates(int* nums, int numsSize) {
    if(numsSize<=2) return numsSize;
    int slow=2,fast=2;
    while(fast<numsSize){
        if(nums[slow-2]!=nums[fast]){
            nums[slow]=nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

2161. 根据给定数字划分数组 

 给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，它们在结果数组中的相对顺序需要保留。

int* pivotArray(int* nums, int numsSize, int pivot, int* returnSize) {
    int *res=malloc(sizeof(int)*numsSize);
    int l=0,r=numsSize-1;
    memset(res,0,numsSize*sizeof(int));
    for(int i=0;i<numsSize;++i){
        if(nums[i]<pivot){
            res[l++]=nums[i];
        }else if(nums[i]>pivot){
            res[r--]=nums[i];
        }
    }
    for(int i=l;i<=r;++i){
        res[i]=pivot;
    }
    int i=r+1,j=numsSize-1;
    while(i<j){
        char tmp=res[i];
        res[i]=res[j];
        res[j]=tmp;
        i++;j--;
    }
    *returnSize=numsSize;
    return res;
}

1750. 删除字符串两端相同字符后的最短长度 

选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。前缀和后缀在字符串中任意位置都不能有交集。前缀和后缀包含的所有字符都要相同。同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

输入：s = "ca"
输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。

输入：s = "cabaabac"
输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "" 。

int minimumLength(char* s) {
    int n=strlen(s);
    int l=0,r=n-1;
    while(l<r&&s[l]==s[r]){
        char c=s[l];
        while(l<=r&&s[l]==c){
            l++;
        }
        while(l<=r&&s[r]==c){
            r--;
        }
    }
    return r-l+1;
}