刷题 ------ 双指针

  • 开发
  • 20

文章目录

1.验证回文串 ||

在这里插入图片描述

  • 这道题说可以删除一个字符，也就是说，如果左右两边发现不同的时候,
  • 分别对其两个区间进行判断 [left + 1,right] || [left, right - 1];
  • 这两个区间分别 删除了当前 left 和 right。
  • 两个但凡有一个满足回文就行。
bool validPalindrome(char* s)
{
   
    int count = 0;
    int left = 0, right = strlen(s) - 1;
    while(left < right)
    {
   
        if(s[left] != s[right])
        {
   
            //不一样，因为只能删除一次，所以停止这次循环即可
            count++;
            break;
        }
        left++;
        right--;
    }
    if(count == 1)
    {
   
        int flagLeft = IsPalindrome(s,left+1,right);
        int flagRight = IsPalindrome(s,left,right - 1);
        return flagLeft || flagRight;
    }

    return true;
}

2.计数二进制字串

在这里插入图片描述

  • 额。。真得感谢老哥，好吧。 在这里插入图片描述
  • 看下图，第一组0出现了2 次 1出现了3次，但是能构成的字串只有01 0011 两种，意思就是说
  • 两者中小的那个才是这俩的极限，
  • 所以:min(2,3) + min(3,1) + min(1,2) = ans

在这里插入图片描述
我们当然可以专门用一个数组，来计算出上图中的第二行，但是也可以利用一个变量lastCount来维护，这样剩下了空间，也剩下了时间

int countBinarySubstrings(char* s)
{
   
    int i, len = strlen(s), ans = 0, lastCount = 0;
    while(i < len)
    {
   
        char c = s[i];
        int count = 0;
        //统计当前相同的0或者1出现的次数
        while(i < len && s[i] == c)
        {
   
            i++;
            count++;
        }
        //和上一个出现的进行比较
        ans += (lastCount < count ? lastCount : count);
        //更新前一个出现的次数
        lastCount = count;
    }
    return ans;
}

3. 字符的最短距离

在这里插入图片描述
我是说哈，咱有时候想不出来，就真别想了，就我在那里想半天，做了老多的 if else，总是有测试用例是错了，题解该看还是得看。

  • 遍历两边，从左到右遍历一遍，再从👉到左遍历。
  • 拿一个 j 下标来指向前一次的 c 字符出现的位置，
  • 第一次遍历，j 最开始在左边的时候，是 i - j的形式去计算距离，所以刚开始的 j 给一个小值（负值），这样 i - j 永远都会是一个很大的值，再第二次从右往左遍历的时候，他就会被新的小值给比下去。
  • 第二次遍历， j一定得是在右边记录c的位置，是 j - i的形式去计算距离，所以j刚开始就可以给一个比较大的值，这样 j - i 和第一次遍历后的值去比较，选择小的即可。
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* shortestToChar(char* s, char c, int* returnSize)
{
   
    int i,j;
    int len = strlen(s);
    int* ans = (int*)malloc(sizeof(int) * len);
    *returnSize = len;
    for (i = 0, j = -len; i < len; i++)
    {
   
        if(s[i] == c)
        {
   
            //j 记录这前一个 c 的下标
            j = i;
        }
        ans[i] = i - j;
    }

    for (i = len - 1, j = 2*len; i >= 0; i--)
    {
   
        if(s[i] == c)
        {
   
            j = i;
        }
        ans[i] = ans[i] < j - i ? ans[i] : j - i;
    }

    return ans;
}

4.按奇偶排序数组

在这里插入图片描述
办法有很多，你可以，对数组进行两次遍历，第一次存偶数，第二次存奇数，
还可以利用双指针 一次遍历的时候，是偶数的存前面，奇数存后面。
下面我同样也是用双指针，进行原地修改了直接，没开辟空间

  • 左边去找奇数，右边去找偶数，
  • 当左边奇数，右边是偶数的时候，交换他俩就好了
/**
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParity(int* nums, int numsSize, int* returnSize)
{
   
    int i = 0, j = numsSize - 1;
    *returnSize = numsSize;
    while(i < j)
    {
   
        if(nums[i] % 2 == 0 || nums[i] == 0)
        {
   
            //左边找奇数
            i++;
        }   
        if(nums[j] % 2 != 0)
        {
   
            //右边找偶数
            j--;
        }
        if(i < j && nums[i] % 2 != 0 && nums[j] % 2 ==0)
        {
   
            //交换
            int tmp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = tmp; 
        }
    }

    return nums;
}

5.仅仅反转字母

在这里插入图片描述

  • 双指针，左右两个，
  • 左边和右边，分别去找是字母的字符。
  • 找到之后进行交换即可
char* reverseOnlyLetters(char* s)
{
   
    int len = strlen(s);
    int left = 0, right = len - 1;

    while (left < right)
    {
   
        //两边同时去找字母
        while (left < len && !((s[left] >= 'a' && s[left] <= 'z') || (s[left] >= 'A' && s[left] <= 'Z')))
        {
   
            left++;
        }
        while ( right >= 0 && !((s[right] >= 'a' && s[right] <= 'z') || (s[right] >= 'A' && s[right] <= 'Z')))
        {
   
            right--;
        }

        if (left < right)
        {
   
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

    return s;
}

6. 奇偶排序数组 ||

在这里插入图片描述

  • i 代表 偶数下标， j 代表奇数下标
  • 去依次遍历数组，如果发现偶数下标对应的数据不是偶数。
  • 那么就去动用 j 去找那个奇数下标不是奇数的。
  • 找到之后将这俩交换即可。
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParityII(int* nums, int numsSize, int* returnSize)
{
   
    int i = 0,j = 1;    //i 表示偶数下标, j 表示奇数下标
    *returnSize = numsSize;
    for (i = 0; i < numsSize; i += 2)
    {
   
        //如果偶数下标，所对应的是数据是奇数
        if(nums[i] % 2 != 0)
        {
   
            //去找奇数下标对应的偶数
            while(nums[j] % 2 != 0)
            {
      
                j += 2;
            }
            //这俩交换
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    return nums;
}

7.长按键入

在这里插入图片描述

  • 首先我的思路是这样的。
  • i 和 j 有一个大于自身的长度了就结束循环
  • 如果 i 都没走完，就说明肯定不行
  • 如果 j 没走完，那么就去判断它后面的字母是否与name结尾一致。如果有不一致的，则返回false
  • 然后中间过程中拿一个ch变量记录着当前相同的字母，就是下面这幅图的工作

在这里插入图片描述
代码如下:

bool isLongPressedName(char* name, char* typed)
{
   
    int i = 0, j = 0;
    int lenName = strlen(name);
    int lenTyped = strlen(typed);
    char ch = name[0];
    while(i < lenName && j < lenTyped)
    {
   
        if(name[i] == typed[j])
        {
   
            ch = name[i];
            i++;
            j++;
        }
        else
        {
   
            if(typed[j] != ch)
            {
   
                return false;
            }
            j++;
        }
    }
    //如果 j 没走完，去判断剩余的部分是否与最后一个相同
    while(j < lenTyped)
    {
   
        if(typed[j] != name[i - 1])
        {
   
            return false;
        }
        j++;
    }

    return i == lenName;
}
  • 而官方题解的话，优化了不少，
  • 首先在循环上，它的结束条件是 走完 j
  • 还有就是中间省去了我上面的ch变量，它使用typed[ j ] 和 typed[ j - 1 ]直接进行比较。
  • 还是官方的妙，(;´༎ຶД༎ຶ`)
  • (;´༎ຶД༎ຶ`)
  • (;´༎ຶД༎ຶ`)
  • (;´༎ຶД༎ຶ`)
bool isLongPressedName(char* name, char* typed)
{
   
    int i = 0,j = 0;
    int lenName = strlen(name), lenType = strlen(typed);
    
    while(j < lenType)
    {
   
        // i < lenName  ---   i 可能先走完
        if( i < lenName && name[i] == typed[j])
        {
   
            i++;
            j++;
        }
        else if(j > 0 && typed[j] == typed[j - 1])
        {
   
            // j > 0 ----- j 如果是 0 （0 - 1 = -1）ERROR
            j++;
        }
        else
        {
   
            return false;
        }
    }

    return i == lenName;
}

8. 递减字符匹配

在这里插入图片描述

  • 从题目和测试用例也能看出来，就是输出数组中最大的数是 len 最小的数十是 0.
  • 我们只需要遍历一遍字符串，如果是 I的话就把大的值赋值上去，反之赋值小的，完成后对应的指针进行移动即可。
    在这里插入图片描述
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* diStringMatch(char* s, int* returnSize)
{
   
    int len = strlen(s);
    int size = len + 1;
    int* ans = (int*)malloc(sizeof(int) * size);
    int i;
    int low = 0, high = len;
    for (i = 0; i < len; i++)
    {
   
        if(s[i] == 'I')
        {
   
            //当前位置小
            ans[i] = low++;
        }
        else if(s[i] == 'D')
        {
   
            //当前位置大
            ans[i] = high--;
        }
    }
    ans[i] = low;
    *returnSize = size;
    return ans;
}

9.有序数组的平方

在这里插入图片描述

  • 一组有序的数字，如果其还带负数，一定是两边数的平方最大嘛。
  • 所以，利用 i 和 j 分别表示表示数组左右两边的数。
  • 然后拿一个index当ans数组的下标，其index一定是从后往前赋值的（因为不管 i 和 j）算出来取的是那个大值。
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize)
{
   
    int* ans = (int*)malloc(sizeof(int)  * numsSize);
    *returnSize = numsSize;
    int i = 0, j = numsSize - 1,index; // i 和 j 分别为nums数组的前后指针，index为ans数组的索引
    for (index = numsSize - 1; index >= 0; index--)
    {
   
        if(pow(nums[j],2) > pow(nums[i],2))
        {
   
            ans[index] = pow(nums[j--],2);
        }
        else
        {
   
            ans[index] = pow(nums[i++],2);
        }
    }

    return ans;
}

10.复写零

在这里插入图片描述

  • 利用 i 和 j ，主要是i指针进行遍历，如果发现是0，那么j就进行自增的。当j大于或者等于了arrsize的时候停下来。
  • 然后在从 i 开始，往前倒着遍历的同时给相应的 j 去赋值
void duplicateZeros(int* arr, int arrSize)
{
   
    int i,j;    //j 随着 i 的对数组的遍历，最后将会代表调整后数组的末尾，
    for (i = 0,j = 0; i < arrSize; i++,j++)
    {
   
        if(arr[i] == 0)
        {
   
            j++;
        }
        if(j >= arrSize - 1)
        {
   
            //在数组原地调整，j不能超出去。
            break;
        }
    }

    if(j == arrSize)
    {
   
        // j 等于了 arrsize 就说明其最后一个元素是0,但是放不下了。
        arr[--j] = arr[i--];
        j--;
    }

    while(i >= 0)
    {
   
        if(arr[i] != 0)
        {
   
            //赋值即可
            arr[j--] = arr[i--];
        }
        else
        {
   
            //两个0写入
            arr[j--] = 0;
            arr[j--] = 0;
            i--; //然后i指向下一个
        }
    }
}

11.删除回文子序列

在这里插入图片描述

？？？？？，就是说，如果这个字符串是回文的，只需要删除一次，不是回文的，可以全删a 和 全删 b 也就两次，题目中说的是子序列，不是字串
在这里插入图片描述

bool IsPalindrome(char* s)
{
   
    int left = 0, right = strlen(s) - 1;
    while(left < right)
    {
   
        if(s[left] != s[right])
        {
   
            return false;
        }
        left++;
        right--;
    }

    return true;
}


int removePalindromeSub(char* s)
{
   
    return IsPalindrom(s) ? 1 : 2;
}

12.检查单词是否为剧中其他单词的前缀

在这里插入图片描述

  • 首先得会分隔单词的区间[begin,end];
  • 用index 记录第几个单词。
  • 然后去判断当前这个单词的前缀是否满足searchWord的就好了
int isPrefixOfWord(char* sentence, char* searchWord)
{
   
    int len1 = strlen(sentence), len2 = strlen(searchWord);
    int i = 0,index = 1;//index 表示第几个单词
    while(i < len1)
    {
   
        int begin = i,end = begin;
        //分隔单词区间[begin,end];
        while(end < len1 && sentence[end] != ' ')
        {
   
            end++;
        }
        //判断
        int k = 0; // k 代表searchword的索引
        while(k < len2 && begin < end && sentence[begin] == searchWord[k])
        {
   
            begin++;
            k++;
        }
        if(k == len2)
        {
   
            return index;
        }

        i = end + 1;
        index++;
    }

    return -1;
}

13.交替合并的字符串

在这里插入图片描述

  • i 和 j 分别代表word1 和word2的起点，然后当发现有一个走完的时候。
  • 将另一个没走完的拷过去就好了。


char * mergeAlternately(char * word1, char * word2)
{
   
    int len1 = strlen(word1), len2 = strlen(word2);
    char* ans = (char*)malloc(sizeof(char) * (len1 + len2 + 1));
    int size = 0,i = 0, j = 0;
    while(i < len1 && j < len2)
    {
   
        ans[size++] = word1[i++];
        ans[size++] = word2[j++];
    }

    while(j < len2)
    {
   
        ans[size++] = word2[j++];
    }
    while(i < len1)
    {
   
        ans[size++] = word1[i++];
    }

    ans[size] = '\0';
    return ans;
}

14.反转单词前缀

在这里插入图片描述

  • 利用begin 和 end 两个下标去遍历word，如果end都走完了还没有发现目标ch，返回原来的。
  • 如果找到了，从begin 和 end 进行反转字串，并返回
char* reversePrefix(char* word, char ch)
{
   
    int len = strlen(word);
    int begin = 0, end = 0;
    while(end < len)
    {
   
        //word的中有字串
        if(word[end] == ch)
        {
   
            //进行反转即可
            while(begin < end)
            {
   
                char tmp = word[begin];
                word[begin++] = word[end];
                word[end--] = tmp;
            }
            return word;
        }
        end++;
    }


    return word;
}

15.找出数组中的第一个回文字符串

在这里插入图片描述

  • 嗯。。。。。
bool IsPalindrome(char* s)
{
   
    int left = 0, right = strlen(s) - 1;
    while(left < right)
    {
   
        if(s[left] != s[right])
        {
   
            return false;
        }
        left++;
        right--;
    }

    return true;
}



char* firstPalindrome(char** words, int wordsSize)
{
   
    int i;
    for (i = 0; i < wordsSize; i++)
    {
   
        if(IsPalindrome(words[i]))
        {
   
            return words[i];
        }
    }
    return "";
}

16.与对应负数同时存在的最大正整数

在这里插入图片描述

  • 先给数组尽心排序，然后利用 i 和 j 两和指针对数组进行遍历。
  • 其中 i 开始是指向负数的，如果它的绝对值小于j那么 j–。
  • 反之i++;
int cmp_int(const void* x,const void* y)
{
   
    return *(int*)x - *(int*)y;
}


int findMaxK(int* nums, int numsSize)
{
   
    qsort(nums,numsSize,sizeof(int),cmp_int);
    int i = 0, j = numsSize - 1;
    while(i < j)
    {
   
        if(-nums[i] > nums[j])
        {
   
            i++;
        }
        else if (-nums[i] < nums[j])
        {
   
            j--;
        }
        else 
        {
   
            return nums[j];
        }
    }
    
    return -1;
}

16. 不同的平均值的数目

在这里插入图片描述

  • 先排序，然后对利用两个指针，一前一后的去相加求和。
  • 记录有多少个是第一次出现就行。
int cmp_int(const void* x, const void* y)
{
   
    return *(int*)x - *(int*)y;
}


int distinctAverages(int* nums, int numsSize)
{
   
    qsort(nums,numsSize,sizeof(int),cmp_int);
    int* map = (int*)calloc(201,sizeof(int));
    int low = 0, high = numsSize - 1, count = 0;    
    while(low < high)
    {
   
        int sum = nums[low] + nums[high];
        //和如果一样，平均值肯定也一样。
        if(map[sum] == 0)
        {
   
            //记录第一次出现的次数
            map[sum++]++;
            count++;
        }
        low++;
        high--;
    }
    return count;
}

17. 最多可以摧毁敌人城堡数目

在这里插入图片描述

  • 这道题就是计算出1和-1之间的最大差距，
  • 在找到第一个 1 或者 -1 的时候，记录begin ，begin即是开始，也是结束
  • 比如1：相对于我方军队时开始，相对于敌方军队的话，不就是结束了嘛？
  • 然后再去找下一个出现的位置，如果他俩不相同的话，就记录其长度，否则就更换begin
int captureForts(int* forts, int fortsSize)
{
   
    int begin = -1,end,ans = 0;
    for(end = 0; end < fortsSize; end++)
    {
   
        if(forts[end] == 1 || forts[end] == - 1)
        {
   
            if(begin >= 0 && forts[begin] != forts[end])
            {
   
                ans = ans > end - begin - 1 ? ans : end - begin - 1;
            }
            //如果两者一致的话不进去求距离，而是更新位置，
            begin = end;
        }
    }

    return ans;
}

18.合并两个二维数组 - 求和法

在这里插入图片描述

  • 上面做过类似的题
  • 只不过这里变成了二维的了。
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** mergeArrays(int** nums1, int nums1Size, int* nums1ColSize, int** nums2, int nums2Size, int* nums2ColSize, int* returnSize, int** returnColumnSizes)
{
   
    int** ans = (int**)malloc(sizeof(int*) * (nums1Size + nums2Size));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (nums1Size + nums2Size));
    int size = 0,i = 0, j = 0;
    while(i < nums1Size && j < nums2Size)
    {
   
        ans[size] = (int*)malloc(sizeof(int) * 2);
        (*returnColumnSizes)[size] = 2;
        if(nums1[i][0] < nums2[j][0])
        {
   
            //赋nums1的值
            ans[size][0] = nums1[i][0];
            ans[size++][1] = nums1[i++][1];
        }
        else if(nums1[i][0] > nums2[j][0])
        {
   
            //
            ans[size][0] = nums2[j][0];
            ans[size++][1] = nums2[j++][1];
        }
        else
        {
   
            ans[size][0] = nums1[i][0];
            ans[size++][1] = nums1[i++][1] + nums2[j++][1];
        }
    }

    //将未遍历完的全部导入到后面去
    while(i < nums1Size)
    {
   
        ans[size] = (int*)malloc(sizeof(int) * 2);
        (*returnColumnSizes)[size] = 2;
        ans[size][0] = nums1[i][0];
        ans[size++][1] = nums1[i++][1];
    }

    while(j < nums2Size)
    {
   
        ans[size] = (int*)malloc(sizeof(int) * 2);
        (*returnColumnSizes)[size] = 2;
        ans[size][0] = nums2[j][0];
        ans[size++][1] = nums2[j++][1];
    }


    *returnSize = size;
    return ans;
}

19.字典序最小回文串

在这里插入图片描述

  • 回文的话就是左右两边取进行遍历，
  • 如果发现二者不一样，那么就赋值成他俩中那个较小的（最小回文串）。
char * makeSmallestPalindrome(char * s)
{
   
    int left = 0, right = strlen(s) - 1;
    while(left < right)
    {
   
        if(s[left] < s[right])
        {
   
            s[right] = s[left];
        }
        else if(s[left] > s[right])
        {
   
            s[left] = s[right];
        }

        left++;
        right--;
    }

    return s;
}

20.找出满足差值条件的洗标| **

在这里插入图片描述

  • 需要用两个指针分别记录着当前最大数和最小数的下标。
  • 然后j从所给的index开始，i 就从0索引出开始，这样子，他们同时加加，这样子index条件肯定是永远满足的。
  • 而val则是去循环内部去判断。
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findIndices(int* nums, int numsSize, int indexDifference, int valueDifference, int* returnSize)
{
   
    int maxIndex = 0, miniIndex = 0; //这俩分别记录着数组中当前最大数的下标，和最小数的下标
    int* ans = (int*)malloc(sizeof(int) * 2);
    ans[0] = -1;
    ans[1] = -1;
    *returnSize = 2;
    int i,j;
    //i 和 j同时++，这样他俩的距离永远适合的，再循环内判断val即可
    for (i = 0, j = indexDifference; j < numsSize; j++,i++)
    {
   
        //更新其最小值和最大值的下标索引
        if(nums[maxIndex] < nums[i])
        {
   
            maxIndex = i;
        }
        else if(nums[miniIndex] > nums[i])
        {
   
            miniIndex = i;
        }

        if(nums[maxIndex] - nums[j] >= valueDifference)
        {
   
            ans[0] = maxIndex;
            ans[1] = j;
            return ans;
        }
        if(nums[j] - nums[miniIndex] >= valueDifference)
        {
   
            ans[0] = miniIndex;
            ans[1] = j;
            return ans;
        }

    }

    return ans;
}

21.训练计划 |

在这里插入图片描述

  • 双指针分别在左边找和右边找
  • 左边去找偶数，右边去找奇数。
  • 最后交换就好了
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* trainingPlan(int* actions, int actionsSize, int* returnSize)
{
   
    int left = 0, right = actionsSize - 1;
    *returnSize = actionsSize;
    while(left < right)
    {
   
       while(left < actionsSize && actions[left] % 2 != 0)
       {
   
           left++;
       }

       while(right >= 0 && actions[right] % 2 == 0)
       {
   
           right--;
       }

        if(left < right)
        {
   
            int tmp = actions[left];
            actions[left++] = actions[right];
            actions[right--] = tmp;
        }
    }

    return actions;
}

22.字符串中的单词反转

在这里插入图片描述

  • 从后往前开始遍历，用begin和end记录单词的开始和结尾，发现一个单词后，应该从该单词的结尾处开始拷贝。
  • 然后往后面赋值上一个空格。
  • 循环结束时候，将最后一个空格改成 **‘\0’**就好了
char* reverseMessage(char* message)
{
      
    int len = strlen(message);

    char* ans = (char*)malloc(sizeof(char) * (len + 1));
    int begin,end;
    int size = 0;
    for (begin = len - 1, end = begin; end >= 0; end--)
    {
   
        while(end >= 0 && message[end] == ' ')
        {
   
            end--;
        }
        //调整新的单词开始位置
        begin = end;

        //去找单词的结束位置
        while(end >= 0 && message[end] != ' ')
        {
   
            end--;
        }

        //begin - end就是拷贝的大小
        if(begin - end != 0)
        {
   
            //有单词
            memcpy(ans + size,message + end + 1,sizeof(char) * (begin - end));
            size += (begin - end);
            ans[size++] = ' ';
        }
    }
    if(size == 0)
    {
   
        //如果一个单词都没有返回空串即可
        return "";
    }

    ans[--size] = '\0';
    return ans;
}

23.动态口令

在这里插入图片描述

  • 这道题，可以先拷贝target之后的，然后再拷贝tarrget之前的，就能解决了。
  • 下面我只拷贝一次，但是需要申请一下空间。
  • 将前面追加到原字符串末尾，最后返回password + target 就好了。
char* dynamicPassword(char* password, int target)
{
   
    int len = strlen(password);
    password = (char*)realloc(password,sizeof(char) * (len + target + 1));
    int i = 0, j = len;
    while(i < target)
    {
   
        password[j++] = password[i++];
    }
    password[j] = '\0';
    return password + target;
}

24.字符串压缩

在这里插入图片描述

  • 利用两个指针begin指向重复开始的起点，而end去找它的末尾。
  • 找到之后将其进行相应的赋值。
  • 最后计算两个字符串的长度，再决定返回哪一个。


char* compressString(char* S)
{
   
    int len = strlen(S);
    int begin = 0, end = 0;
    char* ans = (char*)malloc(sizeof(char) * ( 2 * len + 1));
    int size = 0;
    while(end < len)
    {
   
        int count = 0;
        //找结尾
        while(end < len && S[end] == S[begin])
        {
   
            count++;
            end++;
        }
        //当前重复的结束。
        ans[size++] = S[begin];
        size += sprintf(ans + size,"%d" ,count);
        //更新begin 指向新的位置
        begin = end;
    }
    ans[size] = '\0';   
    int len2 = strlen(ans);
    return len <= len2 ? S : ans;
}

25.合并排序数组

在这里插入图片描述

  • 利用 i 和 j 分别指向A 和B两个数组的数字末端，同时拿k去A数组的末端。
  • 然后比较两者大小，哪一个大，哪一个赋值给k。
  • 最后循环结束，B数组中还有值的话，把它们全部移到A上面去。

void merge(int* A, int ASize, int m, int* B, int BSize, int n)
{
   
    int i = m - 1,j = n - 1,k = ASize - 1;
    while(i >= 0 && j >= 0)
    {
   
        if(A[i] > B[j])
        {
   
            A[k--] = A[i--]; 
        }
        else   
        {
   
            A[k--] = B[j--];
        }
    }

    while(j >= 0)
    {
   
        A[k--] = B[j--];
    }

}
阅读全部

相关推荐

  3. 刷题09 双指针

    2024-01-19 03:36:05       38 阅读

  5. Leetcode双指针刷题（一）

    2024-01-19 03:36:05       10 阅读

  9. LeetCode刷题笔记之双指针算法

    2024-01-19 03:36:05       32 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-01-19 03:36:05       19 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-01-19 03:36:05       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-01-19 03:36:05       19 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-01-19 03:36:05       20 阅读

热门阅读

  2. 文件上传报错总结

    2024-01-19 03:36:05       31 阅读

  3. LC674. 最长连续递增序列

    2024-01-19 03:36:05       37 阅读

  4. Fastapi打包exe后无限启动导致死机的解决办法

    2024-01-19 03:36:05       42 阅读

  8. nlk学习笔记 新闻摘要自动提取

    2024-01-19 03:36:05       30 阅读

  12. Pandas实战100例 | 案例 49: 数值运算

    2024-01-19 03:36:05       32 阅读

  14. D - Disastrous Doubling

    2024-01-19 03:36:05       39 阅读

  17. 配置git环境

    2024-01-19 03:36:05       30 阅读

  21. 【Git】GitHub上手动解决冲突

    2024-01-19 03:36:05       33 阅读

  24. iptables使用

    2024-01-19 03:36:05       24 阅读

  25. PHP 数组面试题

    2024-01-19 03:36:05       32 阅读

  26. uniapp使用camera完成指定区域大小扫描拍照功能--自定义拍照区域，相册选择剪裁 打开闪光灯

    2024-01-19 03:36:05       30 阅读

  27. 解密Spring Boot的定时任务

    2024-01-19 03:36:05       30 阅读
  30. dpwwn:01

    dpwwn:01

    2024-01-19 03:36:05      34 阅读