輪轉數組

思路一

創建一個新內存空間，將需輪轉的數依次放入，之后在把其它數放入

代碼：

void rotate(int* nums, int numsSize, int k) {k = k % numsSize;// 確定有效的旋轉次數if(k == 0)return;int* newnums = (int*)malloc(sizeof(int) * numsSize);//臨時數組//復制需要旋轉的元素int i;for(i = 0;i < k;i++){newnums[i] = nums[numsSize - k + i];}//復制不需要旋轉的元素for(i = 0;i<numsSize - k;i++){newnums[k + i] = nums[i]; }//拷貝至原數組memmove(nums,newnums,sizeof(int) * numsSize);
}

思路二

三段逆置，這個方法比較不容易想到具體為：

第一段 先把需要旋轉的元素逆置

第二段 再把不需要旋轉的元素逆置

第三段 最后再把整體逆置

這樣子就可以很好的完成題目的需求了

?代碼：

void nizhi(int *arr,int numssize){int left = 0;int right = numssize - 1;while(left < right){int temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}
}void rotate(int* nums, int numsSize, int k) {k = k % numsSize;// 確定有效的旋轉次數if(k == 0)return;//第一端 逆置nizhi(nums + (numsSize - k),k);//第二段 逆置nizhi(nums,numsSize - k);//第三段逆置nizhi(nums,numsSize);}

消失的數字?

?思路一

將 0 - n 的數全部加起來，再把數數組中的元素全部減去，剩下的那個數字就是消失的數字

例如：

?

?代碼：

int missingNumber(int* nums, int numsSize){//等差數列算出總和int ret = numsSize*(1+numsSize)/2;int count = 0;//把數組中的數全部加起來for(int i = 0;i<numsSize;i++){count += nums[i];}//拿總數減去數組中的數，得到的就是消失的數字return ret - count;
}

?思路二：

使用位的運算，將 0 ~ n 的數，全部與數組內的數進行 (按位異或) ^ 運算 留下來的數就是缺失的

原理：

任何數都等于 ^ 0? = 自己? ?例如 ：001010 ^ 000000 =?001010

任何數 ^ 任何數 = 0? ?例如 ：001010 ^?001010 =?000000

知道了這個結論我們再將它帶入實際例子中

我們發現兩兩成對的都被消除了，剩下的那個就是缺少的數字了

注意：0 ^ 0 ^1 ^ 1 ^ 2 ^ 2 ^ 3 ^?3 ^ 5 ^ 5 ^ 4 它們打亂順序對最終結果也不影響

像 1 + 1+ 2 = 4? ?||? ?2 + 1 + 1 = 4一樣沒有區別

代碼：

int missingNumber(int* nums, int numsSize){int find = 0;for(int i = 0;i < numsSize;i++) //先把數組的數字 ^ 完{find ^= nums[i];}for(int i = 0;i <= numsSize;i++)//再把 0~ numsSize 的數字 ^ 完{find ^= i;}return find;
}

或?

int missingNumber(int* nums, int numsSize){int find = 0;for(int i = 0;i < numsSize;i++)//通過i訪問素組所有元素{find ^= nums[i] ^ (i + 1); //i + 1 作為 1 ~ numsSize 去^ ，因為下標是從0開始的}return find;
}