一、第一個只出現(xiàn)一次的字符：

1、題目：

在一個字符串(0<=字符串長度<=10000，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區(qū)分大小寫）.

2、代碼實現(xiàn)：

public class Test8 {public int FirstNotRepeatingChar(String str) {if(str.length()==0){return -1;}HashMap<Character, Integer> map = new HashMap<Character,Integer>();for(int i=0;i<str.length();i++){if(map.containsKey(str.charAt(i))){int time = map.get(str.charAt(i));map.put(str.charAt(i),++time);}else{map.put(str.charAt(i), 1);}}int pos=-1;for(int i=0;i<str.length();i++){char c = str.charAt(i);if(map.get(c)==1){return i;}}return pos;} }

?

?

二、數(shù)組中只出現(xiàn)一次的數(shù)字：

1、題目：

一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了偶數(shù)次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。

2、解題思路：

參考?？途W(wǎng)的“披薩大叔”：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811

首先：位運算中異或的性質(zhì)：兩個相同數(shù)字異或=0，一個數(shù)和0異或還是它本身。

當只有一個數(shù)出現(xiàn)一次時，我們把數(shù)組中所有的數(shù)，依次異或運算，最后剩下的就是落單的數(shù)，因為成對兒出現(xiàn)的都抵消了。

依照這個思路，我們來看兩個數(shù)（我們假設(shè)是AB）出現(xiàn)一次的數(shù)組。我們首先還是先異或，剩下的數(shù)字肯定是A、B異或的結(jié)果，這個結(jié)果的二進制中的1，表現(xiàn)的是A和B的不同的位。我們就取第一個1所在的位數(shù)，假設(shè)是第3位，接著把原數(shù)組分成兩組，分組標準是第3位是否為1。如此，相同的數(shù)肯定在一個組，因為相同數(shù)字所有位都相同，而不同的數(shù)，肯定不在一組。然后把這兩個組按照最開始的思路，依次異或，剩余的兩個結(jié)果就是這兩個只出現(xiàn)一次的數(shù)字。

3、代碼實現(xiàn)：

public class Test1 {//num1,num2分別為長度為1的數(shù)組。傳出參數(shù)//將num1[0],num2[0]設(shè)置為返回結(jié)果public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {if(array==null ||array.length<2)return ;//對數(shù)組所有數(shù)組進行異或int temp=0;for(int i=0;i<array.length;i++){temp^=array[i];}//從左向右移動，獲取第一個為1的位數(shù)int index=findFirstBits(temp);for(int i=0;i<array.length;i++){if(isBit(array[i],index)){num1[0]^=array[i];}else{num2[0]^=array[i];}}}private boolean isBit(int num, int indexOf1) {num = num >>indexOf1;return (num & 1) == 1;}//從左向右移動，獲取第一個為1的位數(shù)private int findFirstBits(int num) {int indexBit = 0;while((num & 1)==0 && indexBit<(8<<2)){num = num>>1;//將num右移1位（也即除以2），然后再將結(jié)果賦值給num++indexBit;}return indexBit;} }

?

?

三、字符流中第一個不重復(fù)的字符：

1、題目：

請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符。例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現(xiàn)一次的字符是"g"。當從該字符流中讀出前六個字符“google"時，第一個只出現(xiàn)一次的字符是"l"。

2、解題思路：

一個字符占8位，因此不會超過256個，可以申請一個256大小的數(shù)組來實現(xiàn)一個簡易的哈希表。時間復(fù)雜度為O(n)，空間復(fù)雜度O(n).

3、代碼實現(xiàn)：

public class Test12 {//一個字符占8位，因此不會超過256個，可以申請一個256大小的數(shù)組來實現(xiàn)一個簡易的哈希表。時間復(fù)雜度為O(n)，空間復(fù)雜度O(n).int[] hashtable = new int[256];//每一個位置初始值都是0StringBuilder builder = new StringBuilder();//Insert one char from stringstreampublic void Insert(char ch){builder.append(ch);hashtable[ch] +=1;}//return the first appearence once char in current stringstreampublic char FirstAppearingOnce(){char[] str = builder.toString().toCharArray();for(char ch:str){if(hashtable[ch]==1){return ch;}}return '#';} }

?

?

四、數(shù)組中重復(fù)的數(shù)字：

1、題目：

在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字2。

2、代碼實現(xiàn)：

public class Test22 {//第一種方法：//不需要額外的數(shù)組或者hashtable來保存，題目里寫了數(shù)組里數(shù)字的范圍保證在0 ~ n-1 之間，//所以可以利用現(xiàn)有數(shù)組設(shè)置標志，當一個數(shù)字被訪問過后，可以設(shè)置對應(yīng)位上的數(shù) + n，之后再遇到相同的數(shù)時，//會發(fā)現(xiàn)對應(yīng)位上的數(shù)已經(jīng)大于等于n了，那么直接返回這個數(shù)即可。//將第一個重復(fù)的數(shù)字放在duplication的0號下標中。public boolean duplicate(int numbers[],int length,int [] duplication) {for(int i=0;i<length;i++){int index = numbers[i];if(index>=length){index = index-length;}if(numbers[index] >= length){duplication[0]=index;return true;}numbers[index]=numbers[index]+length;}return false;}//第二種方法：需要重新開拓一個數(shù)組public boolean duplicate1(int numbers[],int length,int [] duplication) {boolean[] k = new boolean[length];for(int i=0;i<length;i++){if(k[numbers[i]]==true){duplication[0]=numbers[i];return true; }k[numbers[i]]=true;}return false;} }

?

總結(jié)

以上是生活随笔為你收集整理的《剑指offer》-- 第一个只出现一次的字符、数组中只出现一次的数字、字符流中第一个不重复的字符、数组中重复的数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。