Finger Offer- the first character position that appears only once

Topic describes

Find the first character that occurs only once in a string (1<= string length <=10000, all letters) and return its position

Train of thought

Idea 1:

Count occurrences using an integer array.

Idea 2:

Use BitSet to count the number of occurrences. 0, 1, and more

Code implementation

package String; import java.util.BitSet; /** * The first character position that occurs only once * in a string (1<= string length <=10000, Public class void main(String[] args) {public static void main(String[] args) {Solution51 solution51 = new Solution51(); String str = "eabbaecdffd"; System.out.println(solution51.FirstNotRepeatingChar_2(str)); } /** * use BitSet to count occurrences 0,1, more * corresponding to 256 ASCII characters ** @param STR * @return */ public int FirstNotRepeatingChar_2(String str) { BitSet bs1 = new BitSet(256); BitSet bs2 = new BitSet(256); for (char c : str.toCharArray()) { if (! bs1.get(c) && ! bs2.get(c)) { bs1.set(c); // 0 0 } else if (bs1.get(c) && ! bs2.get(c)) { bs2.set(c); // 0 1 } } for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (bs1.get(c) && ! bs2.get(c)) return i; } return -1; } /** * count the number of occurrences of an integer array * the 256 characters of the ASCII table * the index of the array is the character, * * @param STR * @return */ public int FirstNotRepeatingChar(String STR) {int[] CNTS = new int[256]; for (int i = 0; i < str.length(); i++) cnts[str.charAt(i)]++; for (int i = 0; i < str.length(); i++) if (cnts[str.charAt(i)] == 1) return i; return -1; }}Copy the code

Wu Peixuan



www.cnblogs.com/wupeixuan/