JavaScript演算法：解壓縮壓縮字串

我想撰寫一個函式，它接受一個壓縮字串并輸出解壓縮字串。

一個像壓縮字串a2b2c3和解壓縮字串是aabbccc 更多的例子

`a` -> `a`
`ab12` -> `abbbbbbbbbbbb`
`a3b2a2` -> `aaabbaa

我試圖實作它，但對于像 ab12

function isNumeric(num) {
    if (num === '') return false
    if (num === null) return false
    return !isNaN(num)
  }
  

function decompress(compressedStr) {
    const array = compressedStr.split('')
    let prevChar, str = ''
    for(let i = 0; i < array.length; i  ) {
        if(i === 0) {prevChar = array[i]}
        if(isNumeric(array[i])) {
            str  = prevChar.repeat(Number(array[i]))
            prevChar = null
        } else {
            if(!prevChar) prevChar = array[i] 
            else {
                str  = prevChar
                prevChar = array[i] 
            }
        }
    }

    return str
}

現在它適用于，a3b2a2但對于像ab12. 需要幫助重寫此函式以使其作業。

uj5u.com熱心網友回復：

您可以String#replace在捕獲字符和重復次數時使用。

function decompress(str) {
  return str.replace(/(\D)(\d )/g, (_, g1, g2) => g1.repeat(g2));
}
console.log(decompress('a'));
console.log(decompress('ab12'));
console.log(decompress('a3b2a2'));

uj5u.com熱心網友回復：

在沒有正則運算式的情況下，您可以直接遍歷字符，直到遇到一個非數字字符，然后消耗掉它之后的所有數字字符。

function decompress(str) {
  let prevCh = '', num = '', res = '';
  function append() {
    if (prevCh)
      if (num) res  = prevCh.repeat(num), num = '';
      else res  = prevCh;
  }
  for (const ch of str) {
    if (isNaN(ch)) {
      append();
      prevCh = ch;
    } else num  = ch;
  }
  append();
  return res;
}
console.log(decompress('a'));
console.log(decompress('ab12'));
console.log(decompress('a3b2a2'));

uj5u.com熱心網友回復：

const is_digit = (ch) => '0' <= ch && ch <= '9'

function decompress(str) {
  if( str.length === 0 ) return ''

  if( is_digit(str[0]) ) return 'invalid input'

  const output = []
  let i = 0
  while(i !== str.length) {

    // collect non-digits into the `output`, stop at the end or at a digit
    while( is_digit(str[i]) === false ) {
      if( i === str.length ) return output.join('')
      output.push(str[i])
        i
    }

    if( i === str.length ) break

    // remember the `ch` with a span
    let ch = str[i-1]

    // parse the span
    let span = 0
    while( is_digit(str[i]) ) {
      if( i === str.length ) break
      span = span * 10   Number(str[i])
        i
    }

    if( span === 0 ) {
      // don't forget about edge cases
      output.pop()
    } else {
      // span-1 because the first `ch` is already in the `output`
      for( let j = 0 ; j !== span-1 ;   j ) {
        output.push(ch)
      }
    }
  }

  return output.join('')
}

// tests
[
  '',
  '12',   // edge case
  'a',
  'ab',
  'a0',   // another edge case
  'ab0',
  'a0b0',
  'a0b',
  'a1',   // yet another
  'a01',  // and another
  'ab1',
  'a1b1',
  'ab01',
  'ab12', // your favorite
  'a12b',
  'a3b2a2',
].forEach((test_case) => console.log('res:', decompress(test_case)))

這不是 JS 中的最佳解決方案（V8 中有很多魔法），因此需要對其進行測驗。但看起來 OP 并不是在撰寫生產代碼，而是在練習。所以這里的要點是

• 代碼總是向前運行并且只創建output，因此它在速度和記憶體上的復雜度為 O(N)
• 它不使用字串連接（因為在幕后……你不能確定，但??你可以假設 V8 每次連接都會創建新的字串，它會破壞復雜性）
• 它不使用Number.parseInt或類似的東西 - 因為，同樣，這將需要創建新的字串

標籤：javascript 算法 行程编码

上一篇：這是對遞回跟蹤的解釋，我無法理解其中的一些邏輯。請幫我分析一下邏輯

下一篇：在javascript中使用for回圈進行二進制搜索