20天力扣算法刷题计划-第二天双指针

「爱情、让人受尽委屈。」 2022-09-11 14:13 23阅读 0赞

[977. 有序数组的平方![icon-default.png_t_L892][]https://leetcode-cn.com/problems/squares-of-a-sorted-array/][977. _icon-default.png_t_L892_https_leetcode-cn.com_problems_squares-of-a-sorted-array]我的代码

/**
     * Note: The returned array must be malloced, assume caller calls free().
     */
     void bubble_sort(int arr[], int sz)
    {
        int i = 0;
        //趟数
        for (i = 0; i < sz - 1; i++)
        {
            //一趟冒泡排序
            int j = 0;
            for (j = 0; j < sz - 1 - i; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }
    
    int* sortedSquares(int* nums, int numsSize, int* returnSize){
        (*returnSize) = numsSize;
        int* ans =(int*)malloc(numsSize*sizeof(int));
        //遍历平方
        for(int i=0;i<numsSize;i++){
            ans[i]=nums[i]*nums[i];
        }
        //冒泡排序
        bubble_sort(ans,numsSize);
        return ans;
    }

[189. 旋转数组![icon-default.png?t=L9C2][icon-default.png_t_L9C2]https://leetcode-cn.com/problems/rotate-array/][189. _icon-default.png_t_L9C2_icon-default.png_t_L9C2_https_leetcode-cn.com_problems_rotate-array]数学常识：公倍数(common multiple)是指在两个或两个以上的[自然数][Link 1]中，如果它们有相同的[倍数][Link 2]，这些倍数就是它们的公倍数。公倍数中最小的，就称为这些[整数][Link 3]的**[最小公倍数][Link 4]**（lowest common multiple）。

公约数，亦称“公因数”。它是指能同时整除几个整数的数 \[1\] 。如果一个整数同时是几个整数的[约数][Link 5]，称这个整数为它们的“公约数”；公约数中最大的称为最大公约数。对任意的若干个[正整数][Link 6]，1总是它们的公因数。

C语言常识：条件运算符(?:)是C语言中唯一的一个三目运算符，它是对第一个表达式作真/假检测，然后根据结果返回另外两个表达式中的一个。  
<表达式1>?<表达式2>:<表达式3>  
在运算中，首先对第一个表达式进行检验，如果为真，则返回表达式2的值；如果为假，则返回表达式3的值。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_20_color_FFFFFF_t_70_g_se_x_16][]![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_20_color_FFFFFF_t_70_g_se_x_16 1][]![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

方法一代码

void rotate(int* nums, int numsSize, int k){
        int newArr[numsSize];
        for(int i=0;i<numsSize;++i){
            newArr[(i+k)%numsSize]=nums[i];
        }
        for(int i=0;i<numsSize;++i){
            nums[i]=newArr[i];
        }
    }

方法二代码

int gcd(int a,int b){
        return b?gcd(b,a%b):a;
    }
    void swap(int* a,int* b){
        int temp=*a;
        *a=*b;
        *b=temp;
    }
    
    void rotate(int* nums, int numsSize, int k){
        k=k%numsSize;
        int count=gcd(k,numsSize);
        for(int start=0;start<count;++start){
            int current=start;
            int prev=nums[start];
            do{
                int next=(current+k)%numsSize;
                swap(&nums[next],&prev);
                current=next;
            }while(start!=current);
        }
    }

[icon-default.png_t_L892]: /images/20220828/13172a9f863e45a0a12d031ad343d505.png
[977. _icon-default.png_t_L892_https_leetcode-cn.com_problems_squares-of-a-sorted-array]: https://leetcode-cn.com/problems/squares-of-a-sorted-array/
[icon-default.png_t_L9C2]: https://csdnimg.cn/release/blog_editor_html/release1.9.2/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=L9C2
[189. _icon-default.png_t_L9C2_icon-default.png_t_L9C2_https_leetcode-cn.com_problems_rotate-array]: https://leetcode-cn.com/problems/rotate-array/
[Link 1]: https://baike.baidu.com/item/%E8%87%AA%E7%84%B6%E6%95%B0/385394
[Link 2]: https://baike.baidu.com/item/%E5%80%8D%E6%95%B0/7827981
[Link 3]: https://baike.baidu.com/item/%E6%95%B4%E6%95%B0/1293937
[Link 4]: /images/20220828/ba2d89b096854f1490f66c4834e6e37d.png
[Link 5]: https://baike.baidu.com/item/%E7%BA%A6%E6%95%B0/8417882
[Link 6]: https://baike.baidu.com/item/%E6%AD%A3%E6%95%B4%E6%95%B0/8461335
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/9b139b1d381547ee83fdeb1d17577761.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA56We6L-55bCP5Y2S,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/14b61b8524334bad9510d3b500023da4.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA56We6L-55bCP5Y2S,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We6L-55bCP5Y2S_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/eaadcdca49c045aea0947e5a4ca2d358.png