2019獨角獸企業重金招聘Python工程師標準>>>

題目：在字符串中找出第一個只出現一次的字符。如輸入"abaccdeff"，則輸出'b'.

看到這樣的題目，我們最直觀的想法就是從頭開始掃描這個字符串中的字 符。當訪問某個字符時拿這個字符和后面的每個字符相比較，如果在后面沒有發現重復的字符，則該字符就是只出現一次的字符。如果字符串有n個字符，每個字符 可能與后面的O(n)個字符想比較，因此這種思路的時間復雜度為O(n2)，面試官不會滿意這種思路，它會提示我們繼續想更快的思路。

由于題目與字符出現的次數有關，我們是不是可疑統計每個字符在該字符 串中出現的次數，要達到這個目的，我們需要一個數據容器來存放每個字符出現的次數。在這個容器中可以根據字符來查找它出現的次數，也就是說這個容器的作用 就是把一個字符映射稱一個數字。在常用的數據容器中，哈希表正是這個用途。

為了解決這個問題，我們可以定義哈希表的鍵值（key)是字符，而值 （Value)是該字符出現的次數。同時我們還需要從頭開始掃描字符串兩次。第一次掃描字符串時，每掃描到一個字符就在哈希表中的對應項中把次數加1.接 下來第二次掃描時，每掃描到一個字符就能從哈希表中得到該字符出現的次數。這樣第一個只出現一次的字符就是符合要求的輸出。

用Java代碼實現我們的思路：

package cglib;

import java.util.LinkedHashMap;

public class jiekou {

?? ?public Character firstNotRepeating(String str){ ?
??????? if(str == null) ?
??????????? return null; ?
??????? char[] strChar = str.toCharArray();? //將字符串轉換成數組
??????? LinkedHashMap<Character,Integer> hash = new LinkedHashMap<Character,Integer>(); ?
??????? for(char item:strChar){ ?
??????????? if(hash.containsKey(item)) ?
??????????????? hash.put(item, hash.get(item)+1); ?
??????????? else ?
??????????????? hash.put(item, 1); ?
??????? } ?
??????? for(char key:hash.keySet()) ?
??????? { ?
??????????? if(hash.get(key)== 1) ?
??????????????? return key; ?
??????? } ?
??????? return null; ?
??? } ?
??? public static void main(String[] args){ ?
??????? String str = "abaccdebff"; ?
??????? jiekou test = new jiekou(); ?
??????? System.out.println(test.firstNotRepeating(str)); ?
??? } ?
???? }

?

輸出d

?

拓展1：

在前面的例子中，我們之所以可以把哈希表的大小設為256，是因為字符（char）是8個bit的類型，總共只有256個字符。但實際上字符不只是256個，比如中文就有幾千個漢字。如果題目要求考慮漢字，前面的算法是不是有問題？如果有，可以怎么解決。

?

public class jiekou {

?? ? /**
???? * @param args
???? */ ?
??? public static void main(String[] args) { ?
??????? // TODO 自動生成的方法存根 ?
??????? String testString="ccaaddddb北京bb11大學？？//"; ?
??????? getFirstMaxOccurrenceChar(testString); ?
???? ?
?
?
??? } ?
??? /*查找第一次出現單獨字符的主函數*/ ?
??? private static void getFirstMaxOccurrenceChar(String temString) { ?
??????? char[] temp=temString.toCharArray(); ?
??????? MyHashTable myHashTable=new MyHashTable(); ?
??????? for (char c : temp) { ?
??????????? MyData myData=new MyData(); ?
??????????? myData.setCharData(c); ?
??????????? myHashTable.insert(myData); ?
??????? } ?
??????? MyData[] result=MyHashTable.getHashMap(); ?
??????? boolean flag=false; ?
??????? for (int i = 0; i < result.length; i++) { ?
??????????? MyData myData = result[i]; ?
??????????? /*只要hash表中該數據不為null且計數為1則輸出并跳出循環*/ ?
??????????? if (myData!=null&&myData.getCount()==1) { ?
??????????????? System.out.println("第一次出現單字符為："+myData.getCharData()); ?
??????????????? flag=true; ?
??????????????? break; ?
??????????? } ?
??????? } ?
??????? if (flag==false) { ?
??????????? System.out.println("不存在單字符！"); ?
??????? } ?
??? } ?
?
} ?
/*設計hash表,包含一個長度為Oxffff的數組和insert函數*/ ?
class MyHashTable{ ?
??? private static MyData[] hashMap=new MyData[0xffff]; ?
??? /*如果第一次插入，則將計數設置為1，否則計數+1*/ ?
??? public void insert(MyData myData){ ?
??????? if (hashMap[myData.getCharData()]==null) { ?
??????????? myData.setCount(1); ?
??????? }else { ?
??????????? myData.setCount(hashMap[myData.getCharData()].getCount()+1); ?
??????? } ?
??????? hashMap[myData.getCharData()]=myData; ?
???????? ?
??? } ?
??? public static MyData[] getHashMap() { ?
??????? return hashMap; ?
??? } ?
???? ?
} ?
/*設計hash表中的類型，即一個字符和它的計數*/ ?
class MyData{ ?
??? private char charData; ?
??? private int count; ?
??? public char getCharData() { ?
??????? return charData; ?
??? } ?
??? public void setCharData(char charData) { ?
??????? this.charData = charData; ?
??? } ?
??? public int getCount() { ?
??????? return count; ?
??? } ?
??? public void setCount(int count) { ?
??????? this.count = count; ?
??? } ?
???? }? ?

輸出

第一次出現單字符為：京

?

拓展2：

定義一個函數，輸入兩個字符串，從第一個字符串中刪除在第二個字符串中出現過的所有字符。例如第一個字符串"we are students"，第二個字符串是"aeiou"，結果應該是"w r stdnts"。

package cglib;

public class jiekou {

?? ?
?? ??? ? public static String fun1 ( String s, String b )
?? ??? ???? {
?? ??? ???????? if (s.isEmpty ())
?? ??? ???????? {
?? ??? ???????????? return "";
?? ??? ???????? }
?? ??? ???????? char first = s.charAt (0);
?? ??? ???????? if (b.indexOf (first) != -1)//返回 String 對象b內第一次出現子字符串的字符位置
?? ??? ???????? {
?? ??? ???????????? return fun1 (s.substring (1), b);//截取s的下標為1的字符串，跟b繼續比較
?? ??? ???????? }
?? ??? ???????? return first + fun1 (s.substring (1), b);//b中沒有這個，則沒有的這個字符返回
?? ??? ???? }
?? ??? ?
?? ??? ???? public static void print ( String s )
?? ??? ???? {
?? ??? ???????? for ( int i = 0; i < s.length (); i++ )
?? ??? ???????? {
?? ??? ???????????? System.out.print (s.charAt (i));
?? ??? ???????? }
?? ??? ???? }
?? ??? ?
?? ??? ???? public static void main ( String args[] )
?? ??? ???? {
?? ??? ??? ??? ?String str = "we are students"; ?
?? ??? ???????? String str1 = "aeiou";
?? ??? ???????? String str2 = fun1 (str, str1);
?? ??? ???????? print (str2);
?? ??? ???? }
???? }? ?

輸出：

w r stdnts

?

拓展3： 定義一個函數，刪除字符串中所有重復出現的字符。例如輸入"google"，則輸出結果應該是"gole"。

package cglib;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class jiekou {

?? ?static StringBuffer sb = new StringBuffer();

?? ?// 普通的方法，不使用集合
?? ?static void removeDuplicateByOriginalMethod(String str) {

?? ??? ?System.out.println("方法一：普通方法");
?? ??? ?char[] cy = str.toCharArray();
?? ??? ?String temp = "";
?? ??? ?for (int i = 0; i < cy.length; i++) {
?? ??? ??? ?if (temp.indexOf(cy[i]) == -1) {
?? ??? ??? ??? ?temp += cy[i];
?? ??? ??? ?}
?? ??? ?}
?? ??? ?System.out.println("去除重復字符后：" + temp);
?? ??? ?sb.setLength(0);
?? ?}

?? ?// 方法二,使用LinkedHashSet可以在去掉重復字符后按照原字符順序排列字符
?? ?static void removeDuplicateByLinkedHashSet(String str, String[] ss, int len) {
?? ??? ?System.out.println("方法二：LinkedHashSet");
?? ??? ?Set<String> set = new LinkedHashSet<String>();
?? ??? ?iterate(set, ss, len);
?? ??? ?System.out.println("去除重復字符后：" + sb.toString());
?? ??? ?// 清空StringBuffer對象sb
?? ??? ?sb.setLength(0);
?? ?}

?? ?// 方法三，使用ArrayList可以在去掉重復字符后按照原字符順序排列字符
?? ?static void removeDuplicateByArrayList(String str, String[] ss, int len) {
?? ??? ?System.out.println("方法三：ArrayList");
?? ??? ?List<String> list = new ArrayList<>();
?? ??? ?iterate(list, ss, len);
?? ??? ?System.out.println("去除重復字符后：" + sb.toString());
?? ??? ?// 記住要輸出后才清空sb
?? ??? ?sb.setLength(0);
?? ?}

?? ?// 集合迭代器，用于去除重復字符并重新拼接字符
?? ?static void iterate(Object obj, String[] ss, int len) {
?? ??? ?if (obj instanceof Set) {
?? ??? ??? ?System.out.println("迭代器正在迭代Set");
?? ??? ??? ?@SuppressWarnings("unchecked")
?? ??? ??? ?Set<String> set = (Set<String>) obj;
?? ??? ??? ?for (int i = 0; i < len; i++) {
?? ??? ??? ??? ?if (!set.contains(ss[i])) {
?? ??? ??? ??? ??? ?set.add(ss[i]);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?for (String s : set) {
?? ??? ??? ??? ?sb.append(s);
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if (obj instanceof List) {
?? ??? ??? ?System.out.println("迭代器正在迭代List");
?? ??? ?
?? ??? ??? ?@SuppressWarnings("unchecked")
?? ??? ??? ?List<String> list = (List<String>) obj;
?? ??? ??? ?for (int i = 0; i < len; i++) {
?? ??? ??? ??? ?if (!list.contains(ss[i])) {
?? ??? ??? ??? ??? ?list.add(ss[i]);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?for (String s : list) {
?? ??? ??? ??? ?sb.append(s);
?? ??? ??? ?}
?? ??? ?}
?? ?}

?? ?public static void main(String[] args) {
?? ??? ?String str = "google";
?? ??? ?String[] ss = str.split(""); // 在此處先拆分字符串，處理后再傳給各個需要用到的方法，提高程序性能。
?? ??? ?int len = ss.length;
?? ??? ?System.out.println("等待去除重復字符的字符串：" + str);
?? ??? ?//方法一
?? ??? ?removeDuplicateByOriginalMethod(str);
?? ??? ?// 方法二
?? ??? ?removeDuplicateByLinkedHashSet(str, ss, len);
?? ??? ?// 方法三
?? ??? ?removeDuplicateByArrayList(str, ss, len);
?? ?}

?? ?
???? }? ?

輸出：

方法一：普通方法
去除重復字符后：gole
方法二：LinkedHashSet
迭代器正在迭代Set
去除重復字符后：gole
方法三：ArrayList
迭代器正在迭代List
去除重復字符后：gole

?

拓展4：

請完成一個函數，判斷輸入的兩個字符串是否是Anagram，即互為變位詞

變位詞(anagrams)指的是組成兩個單詞的字符相同，但位置不同的單詞。比如說， abbcd和abcdb就是一對變位詞。該題目有兩種做法：

O(nlogn)的解法

由于組成變位詞的字符是一模一樣的，所以按照字典序排序后，兩個字符串也就相等了。 因此我們可以用O(nlogn)的時間去排序，然后用O(n)的時間比較它們是否相等即可。

package cglib;

import java.util.Arrays;

public class jiekou {

?? ?public static void main(String[] args) {
?? ??? ?// TODO Auto-generated method stub
?? ??? ?System.out.println(func("silent", "listen"));
?? ??? ?System.out.println(func("", ""));
?? ??? ?System.out.println(func("silent", "liste"));
?? ??? ?
?? ?}

?? ?public static boolean func(String str1, String str2) {
?? ??? ?
?? ??? ?if(str1.length() != str2.length()){ ?
??????????? return false; ?
??????? }
?? ??? ?char[] arr1 = str1.toCharArray();
?? ??? ?char[] arr2 = str2.toCharArray();
?? ??? ?Arrays.sort(arr1);
?? ??? ?Arrays.sort(arr2);
?? ??? ?for(int i = 0; i < arr1.length; i++) {
?? ??? ??? ?if(arr1[i] != arr2[i]) {
?? ??? ??? ??? ?return false;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?return true;
?? ?}
?? ?
???? }??

輸出
true
true
false

?

O(n)的解法

由于組成變位詞的字符是一模一樣的， 因此我們可以先統計每個字符串中各個字符出現的次數， 然后看這兩個字符串中各字符出現次數是否一樣。如果是，則它們是一對變位詞。 這需要開一個輔助數組來保存各字符的出現次數。我們可以開一個大小是256的整數數組， 遍歷第一個字符串時，將相應字符出現的次數加1；遍歷第二個字符串時， 將相應字符出現的次數減1。最后如果數組中256個數都為0，說明兩個字符串是一對變位詞。 (第1個字符串中出現的字符都被第2個字符串出現的字符抵消了)， 如果數組中有一個不為0，說明它們不是一對變位詞。

package cglib;

public class jiekou {

?? ?public static void main(String[] args) {
?? ??? ?// TODO Auto-generated method stub
?? ??? ?System.out.println(anagram("silent", "listen"));
?? ??? ?//System.out.println(anagram("", ""));
?? ??? ?//System.out.println(anagram("silent", "liste"));
?? ??? ?
?? ?}

??? private static boolean anagram(String s1,String s2){ ?
?????? ?
??????? int[] nums = new int[26]; ?
???????? ?
??????? char[] s1_char = s1.toCharArray(); ?
??????? char[] s2_char = s2.toCharArray(); ?
???????? ?
??????? int s1_length = s1_char.length; ?
??????? int s2_length = s2_char.length; ?
???????? ?
??????? if(s1_length != s2_length){ ?
??????????? return false; ?
??????? } ?
???????? ?
??????? for(int i=0; i<s1_length; i++){
?????? ??? ?System.out.println("s1的s1_char[i]="+s1_char[i]);
??????????? int index = s1_char[i] - 'a';
??????????? System.out.println("s1的index="+index);
??????????? nums[index]++;
??????????? System.out.println("s1的nums[index]="+nums[index]);
??????? } ?
?
??????? for(int i=0; i<s1_length; i++){
?????? ??? ?System.out.println("s2的s2_char[i]="+s2_char[i]);
??????????? int index = s2_char[i] - 'a';
??????????? System.out.println("s2的index="+index);
??????????? nums[index]--;
??????????? System.out.println("s2的nums[index]="+nums[index]);
??????? } ?
???????? ?
??????? for(int i=0; i<nums.length; i++){
?????? ??? ?System.out.println("nums的i="+i);
?????? ??? ?System.out.println("nums[i]="+nums[i]);
??????????? if(nums[i]>0) return false; ?
??????? } ?
???????? ?
??????? return true; ?
???????? ?
??? }? ?

?? ?
???? }? ?

輸出：

s1的s1_char[i]=s
s1的index=18
s1的nums[index]=1
s1的s1_char[i]=i
s1的index=8
s1的nums[index]=1
s1的s1_char[i]=l
s1的index=11
s1的nums[index]=1
s1的s1_char[i]=e
s1的index=4
s1的nums[index]=1
s1的s1_char[i]=n
s1的index=13
s1的nums[index]=1
s1的s1_char[i]=t
s1的index=19
s1的nums[index]=1
s2的s2_char[i]=l
s2的index=11
s2的nums[index]=0
s2的s2_char[i]=i
s2的index=8
s2的nums[index]=0
s2的s2_char[i]=s
s2的index=18
s2的nums[index]=0
s2的s2_char[i]=t
s2的index=19
s2的nums[index]=0
s2的s2_char[i]=e
s2的index=4
s2的nums[index]=0
s2的s2_char[i]=n
s2的index=13
s2的nums[index]=0
nums的i=0
nums[i]=0
nums的i=1
nums[i]=0
nums的i=2
nums[i]=0
nums的i=3
nums[i]=0
nums的i=4
nums[i]=0
nums的i=5
nums[i]=0
nums的i=6
nums[i]=0
nums的i=7
nums[i]=0
nums的i=8
nums[i]=0
nums的i=9
nums[i]=0
nums的i=10
nums[i]=0
nums的i=11
nums[i]=0
nums的i=12
nums[i]=0
nums的i=13
nums[i]=0
nums的i=14
nums[i]=0
nums的i=15
nums[i]=0
nums的i=16
nums[i]=0
nums的i=17
nums[i]=0
nums的i=18
nums[i]=0
nums的i=19
nums[i]=0
nums的i=20
nums[i]=0
nums的i=21
nums[i]=0
nums的i=22
nums[i]=0
nums的i=23
nums[i]=0
nums的i=24
nums[i]=0
nums的i=25
nums[i]=0
true

?

轉載于:https://my.oschina.net/u/2822116/blog/725453

總結

以上是生活随笔為你收集整理的剑指Offer（java版）：第一个只出现一次的字符的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。