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を使用できます.
cc 150を拾い直す...
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を拾い直す...