3

私は就職の面接の質問を読んで、次のコードを書きました。

文字列内の最初の繰り返されない文字を見つけるための効率的な関数を記述します。たとえば、「total」の最初の繰り返されない文字は「o」であり、「teeter」の最初の繰り返されない文字は「r」です。アルゴリズムの効率について話し合います。

私はPythonでこのソリューションを思いついた。しかし、それを行うにはもっと美しい方法があると確信しています。

word="googlethis"
dici={}

#build up dici with counts of characters
for a in word:
    try:
        if dici[a]:
            dici[a]+=1
    except:
        dici[a]=1

# build up dict singles for characters that just count 1 

singles={}
for i in dici:
    if dici[i]==1:
        singles[i]=word.index(i)

#get the minimum value

mini=min(singles.values())

#find out the character again iterating...

for zu,ui in singles.items():
    if ui==mini:
        print zu

より簡潔で効率的な答えはありますか？

4

22 に答える 22

9 
In [1033]: def firstNonRep(word):
   ......:     c = collections.Counter(word)
   ......:     for char in word:
   ......:         if c[char] == 1:
   ......:             return char
   ......:         

In [1034]: word="googlethis"

In [1035]: firstNonRep(word)
Out[1035]: 'l'

編集:次のようなヘルパーを使用せずに同じことを実装する場合Counter:

def firstNonRep(word):
    count = {}
    for c in word:
        if c not in count:
            count[c] = 0
        count[c] += 1
    for c in word:
        if count[c] == 1:
            return c
于 2013-01-24T21:46:06.800 に答える
2 
from collections import defaultdict
word="googlethis"
dici=defaultdict(int)

#build up dici with counts of characters
for a in word:
    if dici[a]:
        dici[a]+=1
for a in word:
    if didic[a] < 2:
        return a

それはうまくいきませんか？

于 2013-01-24T21:47:34.767 に答える
2 
sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]

DSMも良心的だと思います

next(c for c in word if word.count(c) == 1)

これはわずかに効率的です

>>> word = "teeter"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'r'
>>> word = "teetertotter"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'o'
>>> word = "teetertotterx"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'o'
于 2013-01-24T21:45:29.497 に答える
1

質問: 文字列内の最初の非反復文字

方法 1: カウント配列を作成する

a = "GGGiniiiiGinaaaPrrrottiijayi"
count = [0]*256
for ch in a: count[ord(ch)] +=1
for ch in a :
    if( count[ord(ch)] == 1 ):
        print(ch)
        break

Method2: リスト内包表記

# 1st  non repeating character
pal = [x for x in a if a.count(x) == 1][0]
print(pal)

方法 3: 辞書

d={}
for ch in a: d[ch] = d.get(ch,0)+1
aa = sorted(d.items(), key = lambda ch  :ch[1])[0][0]
print(aa)
于 2018-05-08T06:51:17.837 に答える
0

私の解決策。私はそれがどれほど効率的であるかについて話すことができません。n^2時間で実行されると思います。

>>> def fst_nr(s):
...     collection = []
...     for i in range(len(s)):
...             if not s[i] in collection and not s[i] in s[i+1:]:
...                     return s[i]
...             else:
...                     collection+=[s[i]]
... 
>>> fst_nr("teeter")
'r'
>>> fst_nr("floccinaucinihilipilification")
'u'
>>> fst_nr("floccinacinihilipilification")
'h'
>>> fst_nr("floccinaciniilipilification")
'p'
>>> fst_nr("floccinaciniiliilification")
't'
>>> fst_nr("floccinaciniiliilificaion")
>>>

謙虚なスタック初心者のためのアドバイスはありますか？

于 2013-01-24T23:11:36.750 に答える
0

ソリューションを取得するための 3 行の Python コード:

word="googlethis"
processedList = [x for x in word if word.count(x)==1]
print("First non-repeated character is: " +processedList[0])

または、

word="googlethis"
print([x for x in word if word.count(x)==1][0])
于 2016-12-29T20:05:39.393 に答える
0

パイソン; O(N+N) だと思います。

def find_first_non_occuring(test_str):
    results = {}
    for letter in test_str:
        if letter in results.keys():
            if results[letter] == 1:
                results[letter] = results[letter]+1
        else:
            results[letter] = 1 

    for letter in test_str:
        if results[letter] is 1:
            return letter
test_str = 'afixuboshafe fafd weagdgdg'
print find_first_non_occuring(test_str)
于 2016-02-09T20:40:29.483 に答える
-1

Java では、1) 文字数ハッシュマップを作成します。各文字について、文字に値が格納されていない場合は 1 に設定します。そうでない場合は、文字の値を 1 増やします。

2)次に、各文字の文字列をスキャンしました。hashmap のカウントが 1 の場合、文字を返します。カウント 1 の文字がない場合は、null を返します。

package com.abc.ridhi;
import java.util.HashMap;
import java.util.Scanner;

public class FirstNonRepeated {

    public static void main(String[] args) {
        System.out.println(" Please enter the input string :");
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char c = firstNonRepeatedCharacter(s);
        System.out.println("The first non repeated character is :  " + c);
    }

    public static Character firstNonRepeatedCharacter(String str) {
    HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
        int i, length;
        Character c;
        length = str.length(); 
        // Scan string and build hashmap
        for (i = 0; i < length; i++) {
            c = str.charAt(i);
            if (map1.containsKey(c)) {
                // increment count corresponding to c
                map1.put(c, map1.get(c) + 1);
            } else {
                map1.put(c, 1);
            }
        }
        // Search map in order of string str

        for (i = 0; i < length; i++) {
            c = str.charAt(i);
            if (map1.get(c) == 1){
                return c;
        }
        }
        return null;
    }
}
于 2016-08-16T05:40:15.743 に答える