欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言雙指針多方法旋轉(zhuǎn)數(shù)組解題LeetCode

 更新時(shí)間:2022年02月15日 08:36:21   作者:?jiǎn)虇碳业凝堼? 
這篇文章主要為大家介紹了C語(yǔ)言雙指針使用多方法旋轉(zhuǎn)數(shù)組題解LeetCode,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步

LeetCode題目如下:

在這里插入圖片描述

首先這個(gè)中等難度我是沒(méi)搞懂,后面才發(fā)現(xiàn)原來(lái)中等中在要求多方法上,那就來(lái)看看怎么搞定他吧。

暴力思路

首先我說(shuō)一下我本人的思路,就是函數(shù)進(jìn)行倒序操作,分三步:

1.整體倒序 :1234567-------7654321

2.前半部分倒序:7654321------- 5674321

3.后半部分倒序:5674321-------5671234

由于題目已經(jīng)給出了我們 k 的值,我們直接暴力思路(注意是暴力思路非暴力求解),雙指針交換對(duì)應(yīng)的值就行:

void exchange(int* a, int* b)
{
int n=*a;
*a = *b;
*b = n;
}   //交換a,b位置
void reverse(int* nums,int left,int right)
{
while(left<right)
{
exchange(&nums[left],&nums[right]);
left++;
right--;
}   //對(duì)指定范圍內(nèi)元素進(jìn)行翻轉(zhuǎn)操作
}
void rotate(int* nums, int numsSize, int k){
k%=numsSize;
if(k==0)
{
return ;  //防止k過(guò)大或0導(dǎo)致無(wú)意義操作
}
reverse(nums,0,numsSize-1);//全倒序
reverse(nums,0,k-1);//前半部分倒序
reverse(nums,k,numsSize-1);//后半部分倒序
}

這種方法直觀(guān),最容易想到,特點(diǎn)是思路清晰,完美符合了流程,時(shí)間復(fù)雜度是O(n),空間復(fù)雜度是O(1),將將就就

外加數(shù)組

自力更生不想要咱就尋求外援嘛,直接創(chuàng)建一個(gè)額外數(shù)組,前半部分放前面,后半部分放后面不就行了,用 numsSize 表示數(shù)組的長(zhǎng)度,我們遍歷原數(shù)組,將原數(shù)組下標(biāo)為 n 的元素放至新數(shù)組下標(biāo)為 n+k 的位置,最后將新數(shù)組拷貝至原數(shù)組即可:

void rotate(int* nums, int numsSize, int k){
int arr[numsSize] = {0};
for(int n = 0;n<numsSize;n++)
{
arr[(k+n)%numsSize] = nums[n]; //nums所有元素向前移動(dòng) k 個(gè)單位,依次存到數(shù)組arr
}
for(int n = 0;n<numsSize;n++)
{
nums[n] = arr[n];  //將arr數(shù)組內(nèi)容拷貝回原數(shù)組nums
}

同理,我們可以選擇直接 malloc 一塊空間出來(lái),這種方法同上不贅述

格局抬高

既然我們能想到 malloc 開(kāi)辟空間操作,那再想想庫(kù)函數(shù)里面好像還有個(gè)好東西叫 memcpy ,頭文件:#include <string.h>,memcpy() 用來(lái)復(fù)制內(nèi)存,且忽略 \0,其原型為:

  void * memcpy ( void * dest, const void * src, size_t num );

memcpy() 會(huì)復(fù)制 src 所指的內(nèi)存內(nèi)容的前 num 個(gè)字節(jié)到 dest 所指的內(nèi)存地址上。memcpy() 并不關(guān)心被復(fù)制的數(shù)據(jù)類(lèi)型,只是逐字節(jié)地進(jìn)行復(fù)制,這給函數(shù)的使用帶來(lái)了很大的靈活性,可以面向任何數(shù)據(jù)類(lèi)型進(jìn)行復(fù)制。

代碼如下:

void rotate(int* nums, int numsSize, int k){
int arr[numsSize];
k %= numsSize;
memcpy(arr,nums+(numsSize-k),k*(int)sizeof(int));
memcpy(arr+k,nums,(numsSize-k)*(int)sizeof(int));
memcpy(nums,arr,numsSize*(int)sizeof(int));
}

但是在重疊內(nèi)存塊這方面,memmove() 是比 memcpy() 更安全的方法,所以可能會(huì)有一個(gè)疑問(wèn)就是為什么不用 memmove?

memmove 相比 memcpy 更容易造成數(shù)據(jù)丟失。如果目標(biāo)區(qū)域和源區(qū)域有重疊的話(huà),memmove() 能保證源串在被覆蓋之前將重疊區(qū)域的字節(jié)拷貝到目標(biāo)區(qū)域中,復(fù)制后源區(qū)域的內(nèi)容會(huì)被更改。如果目標(biāo)區(qū)域與源區(qū)域沒(méi)有重疊,則和 memcpy() 函數(shù)功能相同。

強(qiáng)調(diào)一下,與 strcpy() 不同的是,memcpy() 會(huì)完整的復(fù)制 num 個(gè)字節(jié),不會(huì)因?yàn)橛龅?ldquo;\0”而結(jié)束。

環(huán)形替代

在這里插入圖片描述

這是力扣上官方給出的一種方法,需要數(shù)學(xué)推導(dǎo),比較難理解,解析給的是花里胡哨,添油加醋的,我大概概括一下就是把數(shù)組一串元素類(lèi)比成莫比烏斯環(huán),我們構(gòu)圖理解就簡(jiǎn)單多了(ppt手繪勿噴):

在這里插入圖片描述

什么意思呢,就是我們就拿k作為遍歷間隔,不斷拿 1+nk(n從0開(kāi)始) 位置的元素替代 1+ (n+1)k位置元素,直到回到原點(diǎn),回到原點(diǎn)時(shí)因?yàn)楸闅v間隔>0,必定會(huì)有未遍歷的元素我們只需+1 跳到下一位置繼續(xù)上述操作,再使用另一單獨(dú)變量,跟蹤當(dāng)前已經(jīng)訪(fǎng)問(wèn)的元素?cái)?shù)量,當(dāng)該變量 = 元素?cái)?shù)量時(shí)遍歷完成,結(jié)束遍歷過(guò)程。(個(gè)人理解,如有不當(dāng)請(qǐng)聯(lián)系我更正喲~)

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}
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);
    }
}

今天就到這里吧,摸了家人們,更多關(guān)于多方法超度旋轉(zhuǎn)數(shù)組的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(二)

    C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(二)

    這篇文章主要是介紹了利用廣度優(yōu)先算法實(shí)現(xiàn)圖的遍歷,文中利用圖文詳細(xì)的介紹了實(shí)現(xiàn)步驟,對(duì)我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法有一定的幫助,需要的朋友可以參考一下
    2021-12-12
  • Qt實(shí)現(xiàn)矩形大小任意縮放的示例代碼

    Qt實(shí)現(xiàn)矩形大小任意縮放的示例代碼

    這篇文章主要介紹了Qt如何實(shí)現(xiàn)在窗口上繪制任意大小的矩形,并且通過(guò)邊角的拖曳按鈕可改變矩形大小,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2022-06-06
  • C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn))

    C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn))

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(19.移除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • 詳解MFC/C++調(diào)用易語(yǔ)言的整數(shù)型和文本型與VS2010互動(dòng)

    詳解MFC/C++調(diào)用易語(yǔ)言的整數(shù)型和文本型與VS2010互動(dòng)

    在本篇文章里我們給大家分享了MFC/C++調(diào)用易語(yǔ)言的整數(shù)型和文本型與VS2010互動(dòng)相關(guān)知識(shí)點(diǎn)內(nèi)容,有興趣的朋友們可以參考下。
    2018-11-11
  • C++實(shí)現(xiàn)雙向鏈表(List)

    C++實(shí)現(xiàn)雙向鏈表(List)

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)雙向鏈表,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • C++ deque/queue/stack的底層原理解析

    C++ deque/queue/stack的底層原理解析

    這篇文章主要介紹了C++ deque/queue/stack的底層原理解析,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-07-07
  • C++調(diào)用python(執(zhí)行py文件)的全過(guò)程

    C++調(diào)用python(執(zhí)行py文件)的全過(guò)程

    這篇文章主要給大家介紹了關(guān)于C++調(diào)用python(執(zhí)行py文件)的相關(guān)資料,文中通過(guò)圖文以及實(shí)例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2021-12-12
  • C語(yǔ)言中的編碼小技巧

    C語(yǔ)言中的編碼小技巧

    這篇文章主要介紹了C語(yǔ)言中的編碼小技巧,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • C語(yǔ)言深入分析函數(shù)與宏的使用

    C語(yǔ)言深入分析函數(shù)與宏的使用

    C語(yǔ)言函數(shù)是一種函數(shù),用來(lái)編譯C語(yǔ)言,一般包括字符庫(kù)函數(shù),數(shù)學(xué)函數(shù),目錄函數(shù),進(jìn)程函數(shù),診斷函數(shù),操作函數(shù)等,宏在C語(yǔ)言中是一段有名稱(chēng)的代碼片段。無(wú)論何時(shí)使用到這個(gè)宏的時(shí)候,宏的內(nèi)容都會(huì)被這段代碼替換掉
    2022-04-04
  • C++ 數(shù)據(jù)結(jié)構(gòu) 堆排序的實(shí)現(xiàn)

    C++ 數(shù)據(jù)結(jié)構(gòu) 堆排序的實(shí)現(xiàn)

    這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu) 堆排序的實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
    2017-06-06

最新評(píng)論