Ալգորիթմներ. Գտեք առաջին չկրկնվող նիշը

Որոնեք տող առաջին եզակի նիշի համար

Այս հոդվածում մենք կներկայացնենք ալգորիթմի մարտահրավեր, այնուհետև երկու լուծում կտանք՝ երկրորդ տեղը զբաղեցնող և օպտիմալ ալգորիթմ: Ալգորիթմները գրված են Python-ով։

Մարտահրավեր

Գտեք առաջին չկրկնվող նիշը փոքրատառերի շարքում: Չկրկնվողը սահմանվում է որպես նիշ, որը միայն մեկ անգամ է հայտնվում տողում: Եթե ​​բոլոր նիշերը կրկնվում են, վերադարձրեք ընդգծում:

Ահա մի քանի նմուշ տողեր և պատասխաններ յուրաքանչյուրի համար.

"aabcdb" # c
"abcddc" # a
"aabbcc" # _
"abbcda" # c

Այժմ, երբ մենք հասկանում ենք մարտահրավերը, ես կխրախուսեմ ձեզ փորձել ինքնուրույն:

Եթե ​​արդեն փորձել եք կամ ցանկանում եք առաջ անցնել, ապա եկեք գնանք լուծմանը:

Փոխչեմպիոն

Օգտագործելով զույգ for loops, մենք կարող ենք կրկնել տողի վրա ներդիր ձևով՝ որոշելու, թե արդյոք նիշը կրկնվել է.

Այս լուծման վերաբերյալ մի քանի նշում.

• Nested for loop ալգորիթմը ունի O(n^2) բազմանդամ ժամանակային բարդություն:
• Օպտիմալացրեք ներկառուցված հանգույցների լուծումները՝ նվազեցնելով ալգորիթմը մինչև մեկ օղակ:

Օպտիմալ լուծում

Ներդրված օղակ չունենալու համար մենք կարող ենք հետևել, թե քանի անգամ է յուրաքանչյուր արժեք գոյություն ունի տողի մեջ՝ օգտագործելով բառարանը  , որտեղ նիշը տերմինն է, իսկ հաշվիչը՝ սահմանումը:

Երբ մենք ունենք մեր հաշվարկները, բառարանը դառնում է հղում, քանի որ մենք ստուգում ենք առաջին նիշը միայն մեկ երևույթով.

Որոշ նշումներ այս լուծման վերաբերյալ.

• Քանի որ բառարանն ըստ սահմանման դասավորված չէ, մենք պետք է երկրորդ անգամ շրջենք՝ համոզվելու համար, որ պահպանում ենք տողի հաջորդականությունը:
• Սկսած 3.7 տարբերակից, Python բառարանները կպահպանեն մուտքի կարգը: Սա կվերացնի տողի միջով անցնելու անհրաժեշտությունը և թույլ կտա մեզ ուղղակիորեն կրկնել բառարանի փոխարեն:

Բոնուսային լուծում

Բարեբախտաբար մեզ՝ Pythonistas-ի համար, կան բնիկ լարային ֆունկցիաներ, որոնք այս ալգորիթմը դարձնում են հով:

Օգտագործելով .find()-ը և .rfind()-ը, մենք կարող ենք որոշել նիշի ձախ և աջ ցուցիչը: Եթե ​​ձախ և աջ որոնումները վերադարձնում են նույն ինդեքսը, ապա կարող ենք եզրակացնել, որ կերպարի միայն մեկ երևույթ կա:

def firstNotRepeatingCharacter(my_string):
  for c in my_string:
    if my_string.index(c) == my_string.rindex(c):
      return c
  return "_"

Որոշ նշումներ այս լուծման վերաբերյալ.

• Քանի որ ալգորիթմը հիմնված է լեզվին հատուկ մեթոդների վրա, այն լեզվաագնոստիկ չէ:
• Թեև այս ալգորիթմը շարահյուսորեն ավելի քիչ կրկնություն ունի, քան մեր օպտիմալ լուծումը, երկուսն էլ կիսում են նույն ժամանակի բարդությունը:

Եզրակացություն

Ինչպե՞ս ստացվեց ձեզ մոտ: Ո՞րն էր ձեր նախնական լուծումը: Կիսվեք ձեր փորձով ստորև:

Հատուկ շնորհակալություն Nick White-ին այս ալգորիթմի բացատրության համար: