解題所需要的C語言基礎(chǔ)知識(shí)

hello！從現(xiàn)在開始就進(jìn)入本題解的正式內(nèi)容了。首先給大家用圖解的方式介紹3個(gè)C語言位運(yùn)算的基本操作符 & | ^

這些知識(shí)對(duì)下面的解題都非常重要，一定要熟練掌握，不然等會(huì)會(huì)有一種“我在哪，我是誰我在干什么”的感覺。

只出現(xiàn)一次的數(shù)字I

題目描述

只出現(xiàn)一次的數(shù)字
給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,1] 輸出: 1
示例 2:

輸入: [4,1,2,1,2] 輸出: 4

力扣本題鏈接

解題思路

首先，根據(jù)題意，“有不可以額外使用空間這個(gè)限定”，看到這里以后要本能的往位運(yùn)算上面去靠，因?yàn)槲贿\(yùn)算可以不開辟額外空間解決很多問題，然后回看一下剛剛回顧的位運(yùn)算知識(shí)，就知道我們要用到 ^這個(gè)操作符了，因?yàn)樗梢苑浅：?jiǎn)單的消除重復(fù)項(xiàng)，剩下只出現(xiàn)一次的數(shù)字。

說了這么多，接下來讓我們來看看代碼的實(shí)現(xiàn)

int singleNumber(int* nums, int numsSize){
int ret=0;//0異或任何數(shù)都不會(huì)印象他的實(shí)際值
for(int i=0;i<numsSize;i++)
{
 ret^=nums[i];//所有數(shù)異或，重復(fù)的消掉，剩下只出現(xiàn)一次的數(shù)字
}
return ret;//返回這個(gè)數(shù)字
}

這只是一個(gè)開胃菜，下面正式進(jìn)入主菜

只出現(xiàn)一次的數(shù)字II

題目描述

只出現(xiàn)一次的數(shù)字 II 給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)了三次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,3,2] 輸出: 3
``示例 2:

輸入: [0,1,0,1,0,1,99] 輸出: 99

力扣本題鏈接

解題思路

如圖所示，考慮數(shù)字的二進(jìn)制位形式，出現(xiàn)三次的數(shù)字，二進(jìn)制位各位上的1都是三的倍數(shù)，所以求出各位上的1數(shù)目，再對(duì)3求余，則可求出只出現(xiàn)一次的數(shù)字

那么要怎樣求取二進(jìn)制位各位上1的數(shù)目吶，那就要用到&這個(gè)操作符了，來看代碼實(shí)現(xiàn)吧

int singleNumber(int* nums, int numsSize){
 
 int ret=0;
for(int i=0;i<32;++i)//循環(huán)遍歷二進(jìn)制位每一位
{
long cnt=0;//不用long，力扣的編譯器不通過，不讓int類型左移31位，我也不知道
 for(int j=0;j<numsSize;++j) {//將nums數(shù)組中每一個(gè)數(shù)拿出來，二進(jìn)制位向右移動(dòng)i位，與1按位與，
 cnt+=(nums[j]>>i)&1;//則可求出二進(jìn)制位第i位是否為1；
 }
 ret+=(cnt%3)<<i;//將cnt的值模3，求出只出現(xiàn)一次的那個(gè)數(shù)第i位為1還是為0，再向左移動(dòng)i位還原，最后相加求出這個(gè)數(shù)
}
return ret;
}

好了，這個(gè)題目就圓滿解決了。

只出現(xiàn)一次的數(shù)字III

這個(gè)題目就很有技巧了 題目描述
260. 只出現(xiàn)一次的數(shù)字 III 給定一個(gè)整數(shù)數(shù)組 nums，其中恰好有兩個(gè)元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個(gè)元素。你可以按 任意順序 返回答案。

進(jìn)階：你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。你能否僅使用常數(shù)空間復(fù)雜度來實(shí)現(xiàn)？

示例 1：

輸入：nums = [1,2,1,3,2,5] 輸出：[3,5] 解釋：[5, 3] 也是有效的答案。
示例 2：

輸入：nums = [-1,0] 輸出：[-1,0]
示例 3：

輸入：nums = [0,1] 輸出：[1,0]

力扣本題鏈接

解題思路

根據(jù)第一題的思路，就知道要全部按位異或，消除重復(fù)項(xiàng)。但是兩個(gè)只出現(xiàn)一次的數(shù)也異或在了一起，我們的難點(diǎn)就是怎么將這兩個(gè)數(shù)分離。接下來就用圖示法來告訴大家怎樣分離兩個(gè)數(shù)

接下來是代碼的實(shí)現(xiàn)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int m = 0;
int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];//將全部數(shù)異或
}
while (m < 32)
{
	if ((ret>>m)&1)//找出為1的第m位
		break;
	else
  ++m;
}
int x1 = 0, x2 = 0;//分組
int j=0;
while(j<numsSize)
{
	if ((nums[j]>>m)&1)
		x1 ^= nums[j];//異或出只出現(xiàn)一次的數(shù)字
	else
		x2 ^= nums[j];
  j++;
}
int* reRer = (int*)malloc(sizeof(int) * 2);
reRer[0] = x1;
reRer[1] = x2;
*returnSize=2;//根據(jù)題意返回長(zhǎng)度
return reRer;//返回這兩個(gè)數(shù)
}

小編總結(jié)

這是我第一次寫題解，選了三個(gè)相對(duì)簡(jiǎn)單常見的題目，不難，但是也能反應(yīng)出一種做題的思想。我希望大家不是簡(jiǎn)單的學(xué)會(huì)這3個(gè)題目，而是學(xué)會(huì)這種思想去解決更多的題目。同時(shí)大家有好的解題方案，也可以在評(píng)論區(qū)中留言哦，大家互相學(xué)習(xí)，一起進(jìn)步。

到此這篇關(guān)于如何利用C語言位運(yùn)算解決只出現(xiàn)一次數(shù)字的文章就介紹到這了,更多相關(guān)C語言位運(yùn)算解決出現(xiàn)數(shù)字內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論