Нашр шудааст дар

Таҷрибаҳои маъмулие, ки ҳангоми навиштани таърихи TypeScript ба даст оварда шудаанд

Муаллифон

Маҷмӯаи GitHub: https://github.com/ImBIOS/common-char-extractor-ts

Дар ҷаҳони мусоҳибаҳои коди навӣ, мушкилоти алгоритмӣ танҳо ҳамчун санҷиши дониши техникии номзадҳо хизмат намекунанд, балки ҳамчун равзанае ба ҳунармандии ҳалли мушкилоти онҳо мебошанд. Яке аз ин мушкилоти ҷолиб, ки аксар вақт дучор мешавад, дар атрофи манипулятсияи ришта - як ҳунармандии асосӣ дар арсенали як барномасоз мегардад. Имрӯз, мо ба мушкилоти ҷолибе менигарем: муайян кардани аломатҳои муштарак дар байни риштаҳои гуногун ва он ки чӣ гуна мо ҳалли онро бо истифода аз TypeScript пайдо кардем.

Мушкилоти ошкоршуда

Вазифаи дар даст, ба назар осон, вале ғайричашмдошт мураккаб буд: бо назардошти як маҷмӯи риштаҳо, мо бояд як функсия навиштаем, ки маҷмӯи аломатҳоеро, ки дар ҳамон мавқеъ дар тамоми риштаҳо пайдо мешаванд, истихроҷ ва баргардонад. Масалан, бо назардошти маълумоти воридшуда ["abcd", "bcd", "cde", "cdef"], натиҷаи интизоршуда ["c", "d"] хоҳад буд, ки нишон медиҳад, ки 'c' ва 'd' аломатҳои муштарак мебошанд, ки дар байни ҳамаи риштаҳо дар мавқеъҳои мувофиқ мубодила карда мешаванд.

Ҳалли эҷод

Сафари мо аз интихоби TypeScript барои ҳалли ин мушкилот оғоз ёфт - як қарори бар пояи системаи мустаҳками намуди TypeScript, ки эътимоднокии код ва самаранокии корбариро беҳтар мекунад. Қадами аввал дар бар гирифтани такрори ҳар як аломат дар риштаи аввал, истифода аз он ҳамчун истинод барои муқоиса бо аломатҳои мувофиқ дар риштаҳои баъдӣ буд.

/**
 * Маҷмӯи аломатҳоеро, ки дар ҳамон мавқеъ дар тамоми риштаҳо дар маҷмӯи маълумоти воридшуда пайдо мешаванд, истихроҷ ва баргардонад.
 *
 * @param {string[]} words - Маҷмӯи риштаҳое, ки бояд таҳлил шаванд.
 * @returns {string[]} Маҷмӯи аломатҳое, ки дар байни ҳамаи риштаҳои додашуда умумӣ мебошанд,
 * нигоҳдории тартиби зоҳирии онҳо дар риштаи аввал.
 */
export function extractCommonLetters(words: string[]): string[] {
  if (words.length === 0) {
    return []
  }

  const copiedWords = [...words]
  const result: string[] = []
  const referenceWord = copiedWords[0]

  // Такрори ҳар як аломат дар калимаи аввал
  for (let i = 0; i < referenceWord.length; i++) {
    const currentChar = referenceWord[i]
    let isCharCommonAcrossWords = true

    // Санҷиши он ки оё аломати ҷорӣ дар ҳар кадоме аз калимаҳои дигар вуҷуд дорад
    for (let j = 1; j < copiedWords.length; j++) {
      const word = copiedWords[j]
      const charIndex = word.indexOf(currentChar)

      // Агар аломат пайдо нашавад, аз давр баромада ва парчамиро ба нодуруст таъин кунед
      if (charIndex === -1) {
        isCharCommonAcrossWords = false
        break
      } else {
        // Ҳазфи аломати пайдошуда аз калима барои коркарди такрорҳо
        copiedWords[j] = word.slice(0, charIndex) + word.slice(charIndex + 1)
      }
    }

    // Агар аломат дар байни ҳамаи калимаҳо умумӣ бошад, онро ба натиҷа илова кунед
    if (isCharCommonAcrossWords) {
      result.push(currentChar)
    }
  }

  return result
}

Ин парчаи код ҷавҳари тарзи кори мо, таъкиди хондан ва мантиқи рост барои ҳалли мушкилот.

Пешравии ғайричашмдошт: Санҷиши ҳалли масъала

Барои тасдиқи ҳалли масъалаи мо, мо як маҷмӯи озмоишҳоро истифода кардем, ки ҳолатҳои гуногунро дар бар мегирад - аз ҳолатҳои оддӣ то ҳолатҳои мураккабтар, ки аломатҳои махсус ва ҳассосияти ҳолатҳоро дар бар мегиранд. Ин озмоиши пурра кафолат медиҳад, ки алгоритми мо дар байни маҷмӯи васеи маълумоти воридшуда устувор ва дуруст аст.

Таҳлили мураккабии ҷой ва вақт

Пас аз инъикос, мураккабии вақти ҳалли масъалаи мо асосан аз шумораи аломатҳо дар риштаи аввал (биёед инро N таъин кунем) ва шумораи умумии риштаҳо (инро M таъин кунем) муайян карда мешавад. Барои ҳар як аломат дар риштаи аввал, мо ҳодисаи онро дар ҳамон мавқеъ дар байни ҳамаи риштаҳои дигар тафтиш мекунем, ки ба мураккабии вақти O(N*M) меорад.

Мураккабии ҷои ҳалли масъалаи мо O(N) аст, зеро мо аломатҳои муштаракро дар як маҷмӯа нигоҳ медорем. Дар ҳолати бадтарин, ки ҳамаи аломатҳо дар байни ҳамаи риштаҳо умумӣ мебошанд, андозаи ин маҷмӯа ба дарозии риштаи аввал мутаносиб хоҳад буд.

Роҳҳои беҳбуд

Дар ҳоле ки ҳалли масъалаи мо барои шумораи миёнаи риштаҳо ва аломатҳо самаранок аст, ҳамеша ҷой барои беҳтар кардани он вуҷуд дорад. Инҳо чанд стратегияи барои беҳтар кардани самаранокии он мебошанд:

  1. Хатми барвақтӣ: Агар дар ҳар лаҳзае аломат дар ҳамон мавқеъ дар байни ҳамаи риштаҳо мувофиқат накунад, мо метавонем аз давр барвақт баромада, муқоисаҳои беҳударо сарфа кунем.

  2. Беҳтар кардани риштаҳои кӯтоҳ: Оғози кор аз риштаи кӯтоҳтарин ҳамчун истинод метавонад ба таври эҳтимолӣ шумораи такрорҳоро кам кунад, зеро шумораи максималии аломатҳои тафтишшавандаро кам мекунад.

  3. Коркарди параллелӣ: Барои маҷмӯаҳои калони маълумот, истифода аз усулҳои коркарди параллелӣ барои муқоисаи аломатҳо дар байни риштаҳо ба таври ҳамзамон метавонад вақти иҷроро ба таври назаррас кам кунад.

  4. Усулҳои ҳашинг: Истифода аз харитаи ҳашинг барои нигоҳдории мавқеъҳо ва ҳодисаҳои аломат метавонад роҳи мураккабтарро барои муайян кардани аломатҳои муштарак, махсусан ҳангоми коркарди маҷмӯаҳои васеи риштаҳо пешниҳод кунад.

Андешаҳои ниҳоӣ

Мушкилоти аломатҳои муштарак ҳамчун як шоҳиди беназири зебоии мушкилоти манипулятсияи ришта хизмат мекунад, ки барномасозонро ба таҳқиқи нуқтаҳои нозуки алгоритмҳо ва сохторҳои маълумот даъват мекунад. Бо истифода аз TypeScript, мо на танҳо ҳалли масъаларо ёфтем, балки ба як сафари равшанӣ, бехатарии намуд ва ҳалли самараноки мушкилот шурӯъ кардем.

Ҳангоми ба итмом расидани кор, муҳим аст, ки дар хотир дорем, ки сафари мушкилоти коди навӣ ҳамон қадар дар бораи роҳест, ки дар он қадам мегузорем, ки дар бораи мақсади расида ба он аст. Ҳар як мушкилот, аз ҷумла ин, як имконияти беназирро барои такмил додани маҳорати мо, фикр кардани дубора дар бораи тарзи кори мо ва аз ҳама муҳимтар, идомаи омӯзиш пешниҳод мекунад.

Муҳокима дар Twitter

БАҲР