559-双指针思想解决数组问题

「爱情、让人受尽委屈。」 2022-08-28 14:53 142阅读 0赞

## 将字符串逆序 ##

**采用双指针的思想**  
分别指向数组的首元素和末尾元素  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]

//逆序字符串
    void Reverse(char arr[], int size)
    {
        
        char* p = arr;
        char* q = arr + size - 1;
        while (p < q)
        {
        
            char ch = *p;
            *p = *q;
            *q = ch;
            p++;
            q--;
        }
    }
    int main()
    {
        
        char arr[] = "hello world";
        Reverse(arr, strlen(arr));
        cout << arr << endl;
    }

## 整形数组，把偶数调整到数组的左边，把奇数调整到数组的右边 ##

![在这里插入图片描述][c8b915a3a39f4343b67852f4e000a01e.png]  
我们采用双指针的思想  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**我们要把右边的偶数放左边，左边的奇数放右边**  
p指针就是从最左边向右找奇数，然后q指针从右向左找偶数，当p从左向右找到1个奇数，q从右向左找到1个偶数，就把p指针指向的奇数和q指针指向的偶数一交换，这样一来，就把右边的偶数放左边，左边的奇数放右边了  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]

处理交换完之后，p后移，q前移

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
然后重复刚才的过程。  
**直到p和q相遇，退出while循环。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_10_color_FFFFFF_t_70_g_se_x_16]

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    #include <string.h>
    using namespace std;
    
    //整形数组，把偶数调整到数组的左边，把奇数调整到数组的右边
    void AdjustArray(int arr[], int size)//接收数组的首地址，数组的个数 
    {
        
        int* p = arr;
        int* q = arr + size - 1;
    
        while (p < q)
        {
        
            //p->从左向右找奇数
            while (p < q)
            {
        
                if ((*p & 0x1) == 1)//是奇数了，因为只有奇数的第一位是1 
                {
        
                    break;
                }
                p++;//是偶数，继续向后走 
            }
    
            //q <- 偶数
            while (p < q)
            {
        
                if ((*q & 0x1) == 0)//是偶数 
                {
        
                    break;
                }
                q--;//是奇数，继续向前走 
            }
    
            //p->奇数   q->偶数
            if (p < q)
            {
        
                int tmp = *p;
                *p = *q;
                *q = tmp;
                p++;
                q--;
            }
        }
    }
    int main()
    {
        
        int arr[10] = {
         0 };
        srand(time(0));//每次运行随机数是不一样的，随系统时间不断变化 
        for (int i = 0; i < 10; i++)
        {
        
            arr[i] = rand() % 100;
        }
    
        for (int v : arr)
        {
        
            cout << v << " ";
        }
        cout << endl;
    
        AdjustArray(arr, 10);
        for (int v : arr)
        {
        
            cout << v << " ";
        }
        cout << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 移除元素问题 ##

![在这里插入图片描述][9afa0f7dc53c4dbea4785be918e935d9.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**把val值的元素都调整到末尾**  
**我们采用双指针的思想**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
**我们就是把右边残留的不等于val的元素的值放到左边等于val的元素上**  
**返回的数组的长度**就是p移动到的位置减去数组的首地址  
q从右向左找不等于val的元素， p从左向右找等于val的值，如果找到，就q解引用赋值给p的解引用  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 3]  
p==q，这个元素也是要判断的。如果这个元素等于val值3，这个值就不记录，p-首元素地址=1，长度就是1，没有问题。如果这个值不等于val，p还要往后加一下  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
不满足while的条件，跳出，**所以我们的while条件要修改一下(p<=q)**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]  
**p-首元素地址=2，刚好是2,2，长度是2**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**优化代码一下**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16 1]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/098689c775734aa18a26d845ee31b169.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e26b3a7bdbf949e5aae61ee6ec79a0e9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8099165f77874b60bf87745b48391148.png
[c8b915a3a39f4343b67852f4e000a01e.png]: /images/20220828/86340d1e526f481c9b69a04cc0a6f1b3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/450c31439de74e27bb0ae14b75134bef.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/fed70efc4b1b43119d86aa20da70f1b5.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/fc7382a15f094a8ea19fa61136597f5e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ef48729d1f3a4ee8afd1f457afccacdb.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_10_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1c8359923960496c8c796751bfba2004.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_10,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/2061713779e0405c84002f23b94eb53c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16
[9afa0f7dc53c4dbea4785be918e935d9.png]: https://img-blog.csdnimg.cn/9afa0f7dc53c4dbea4785be918e935d9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/f7acb85842c14216a7a0c1eabc8f9196.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/5018fed9a4034889aa8773c4d5fea873.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/eb85f2de8e194ad0baae233fe944f0c5.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/96d6164c14a64c2d90d2567f13c95758.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7c3f621e3dfb4a54ab8f1feb195971ad.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_16,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/8e681bb2f8424dc4baa6db334f798c24.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/6cea6e539e1a48f9a7a17ac11321df77.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/94e7d9785f934346aa79884048253e3a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/0e34a68f767b4c4192dc9615eb6b13eb.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b2aefdfa61e440f499877621f0481f55.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/3627a6771fa54115a2d498728d6a835d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBALeael-azveWuhw==,size_20,color_FFFFFF,t_70,g_se,x_16