Arrays_Stringsは文字列内の文字が一意かどうかを判断します@CareerCup

1321 ワード

原文:
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
訳文:
1つのアルゴリズムを実装して、1つの文字列の中の文字が唯一であるか(すなわち重複していない)かどうかを判断します.追加のデータ構造は使用できません.(基本的なデータ構造のみを使用)
考え方:
1暴力比較、2つのforサイクル、O(n^2)
2元の文字列の文字を変更できる場合は、O(nlogn)でソートし、隣接文字が同じかどうかを比較できます.
3他のデータ構造(Hashtable)は使用できませんが、arrayを使用してハッシュ・テーブルをシミュレートできます.Time: O(n), Space: O(1)
4文字列に小文字のみが含まれる場合、arrayの代わりに32ビットのintegerを使用できます.
package Arrays_Strings;

public class S1_1 {

	
	//      ,         
	// Time O(n), Space O(1)
	public static boolean isUniqueChars(String s) {
		if(s.length() > 256) {		//          ,    256,      ,    
			return false;
		}
		
		boolean[] used = new boolean[256];
		for (int i=0; i 256) {
			return false;
		}
		
		int checker = 0;
		for(int i=0; i 0) {		//   checker    i 
				return false;
			}
			checker |= (1<

cc 150を拾い直す...