javascript版アルゴリズム学習記録(1)

26229 ワード

jsアルゴリズムの能力を鍛えて記録します.
文章の中のテーマは力ボタンから来て、思想は慕授業ネットを通じて勉強して獲得します.
1.文字列の単語を反転
文字列を指定すると、文字列の各単語の文字順を反転させながら空白と単語の初期順序を保持します.
例1:
入力:「Let’s take LeetCode contest」出力:「s’teL ekat edcotel tsetnoc」注意:文字列では、各単語は単一のスペースで区切られ、文字列には追加のスペースがありません.
ソース:スナップリンク:https://leetcode-cn.com/problems/reverse-words-in-a-string-iii 著作権はネットの所有権を受領する.商業転載は公式の授権に連絡してください.商業転載ではないので、出典を明記してください.解法:1.
(str) => {
  return str.split(' ').map(item => {
     return item.split('').reverse().join('')
  }).join(' ')

  •  (str) => {
      return str.match(/[\w']+/g).map(item => {
        return item.split('').reverse().join('')
      }).join(' ')
    
    2.バイナリ文字列をカウントします.
    文字列sを指定すると、同じ数の0と1を持つ非空(連続)サブ文字列の数が計算され、これらのサブ文字列のすべての0とすべての1が結合されます.
    繰り返すサブストリングは、それらの出現回数を計算します.
    例1:
    入力:「0010011」出力:6は、同じ数の連続1と0があると解釈します.「0011」、「01」、「1100」、「10」、「0011」、「01」があります.
    いくつかの重複したサブストリングはそれらの出現回数を計算することに注意してください.
    また、「0010011」は、すべての0(および1)が結合されていないので、有効なサブストリングではない.例2:
    入力:「10101」出力:4説明:「10」、「01」、「10」、「01」があり、それらは同じ数の連続1と0を持っています.注意:
    s.lengthは1から50,000の間にあります.sには「0」または「1」の文字しか含まれていません.
    ソース:スナップリンク:https://leetcode-cn.com/problems/count-binary-substrings 著作権はネットの所有権を受領する.商業転載は公式の授権に連絡してください.商業転載ではないので、出典を明記してください.解法:
    (str) => {
    //                
      let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
      //              
      let searchArr = str.split('')
      //                       
      let mapStr = []
      searchArr.forEach(item => {
        mapStr.push(map[item])
      })
      //     , mapStr                   ,                
      let put = (arr) => {
        let app = []
        for (let i = 0; i < arr[0].length; i++) {
          for (let j = 0; i < arr[1].length; j++) {
            app.push(`${arr[0][i]}${arr[1][j]}`)
          }
          //   
          arr.splice(0, 2, app)
          if (arr.length > 1) {
            put(arr)
          } else {
            return app
          }
        }
        return arr[0]
      }
      return put(mapStr)
    }
    
    3.カードグループ:
    指定された牌には、各牌に整数が書いてあります.この時、数字Xを選択してください.サブプレートを下記の規則で1セット以上に分けることができます.各グループにはXカードがあります.グループ内のすべてのカードには同じ整数が書かれています.あなたが選択したX>=2の時だけtrueに戻ります.
    例1:
    入力:[1,2,3,4,3,2,1]出力:true解釈:実行可能なパケットは[1,1],[2,2],[3,3],[4,4]例2:
    入力:[1,1,2,2,3,3]出力:false解釈:要求を満たすパケットがない.例3:
    入力:[1]出力:false解釈:要求を満たすパケットがない.例4:
    入力:[1,1]出力:true解釈:実行可能なパケットは[1,1]例5:
    入力:[1,1,2,2,2,2]出力:true解釈:実行可能なパケットは[1,1],[2,2],[2,2]である.
    ヒント:
    1<=deck.length<=10000==deck[i]<10000
    ソース:スナップリンク:https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards 著作権はネットの所有権を受領する.商業転載は公式の授権に連絡してください.商業転載ではないので、出典を明記してください.解法:
    (arr) => {
      //        sort  ,         return   ,  {} return,      
      arr.sort((a, b) => a - b)
      //  Number.MAX_SAFE_INTEGER  js      
      let min = Number.MAX_SAFE_INTEGER
      //               
      let dist = []
      //         
      for (let i = 0, temp = []; i < arr.length; i++) {
        temp.push(arr[i])
        for (let j = i + 1; j < arr.length; j++) {
          if (arr[i] === arr[j]) {
            temp.push(arr[j])
          } else {
            //         
            if (min > temp.length) {
              min = temp.length
            }
            //     push  temp  ,         ,    push    
            dist.push([].concat(temp))
            //     
            temp.length = 0
            //         arr[i]
            i = j
          }
        }
      }
      return dist.every(item => {
        if (item.length % min !== 0) {
          return false
        }
        return true
      })
    }
    
    4.花台種花:
    もしあなたが長い花壇を持っていたら、一部の土地に花が植えられましたが、もう一つの部分はありません.しかし、花は隣の土地に植えられず、水源を奪い合い、どちらも死ぬ.一つの花壇(1つの配列として0と1が含まれています.0は花を植えていないことを表し、1は花を植えたことを表します.)と1つの数nが与えられます.栽培規則を破らないようにn花を植えてもいいですか?できればTrueに戻り、できなければFalseに戻ります.
    例1:
    入力:flower bed=[1,0,0,0,1],n=1出力:True例2:
    入力:flower bed=[1,0,0,0,1],n=2出力:False注意:
    配列内に植えられた花は栽培規則に違反しない.入力された配列長範囲は[1,20000]です.nは非負の整数であり、入力配列のサイズを超えない.
    ソース:スナップリンク:https://leetcode-cn.com/problems/can-place-flowers 著作権はネットの所有権を受領する.商業転載は公式の授権に連絡してください.商業転載ではないので、出典を明記してください.解法:
    (arr, n) => {
      let max = 0
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 0) {
          if (i === 0 && arr[1] === 0) {
            max++
            arr[i] = 1
            //        
            i++
          } else if (arr[i - 1] === 0 && arr[i + 1] === 0) {
            max++
            //        
            arr[i] = 1
            i++
          } else if (i === arr.length - 1 && arr[i - 1] === 0) {
            max++
          }
        }
      }
    
      return max >= n
    }
    
    5.グレイコード:
    グレイ符号化は、2つの連続した数値が1桁の差しかないバイナリデジタルシステムである.符号化全体のビット数を表す負の整数nが与えられ、そのゴーレイ符号化シーケンスが印刷される.グレイ符号化シーケンスは0で始まる必要があります.
    例1:
    入力:2出力:[0,1,3,2]説明:00-0 01-1 11-3 10-2
    与えられたnに対して、ゴーレイ符号化シーケンスは一意ではない.例えば、[0,2,3,1]も、効果的なゴーレイ符号化シーケンスである.
    00-0 10-2 11-3 01-1例2:
    入力:0出力:[0]説明:グレイ符号シーケンスを定義するには0で始まる必要があります.与えられた符号化の合計ビット数はnであり、その長さは2 nである.n=0の場合、長さは20=1です.したがって、n=0の場合、そのゴーレイ符号化シーケンスは[0]である.
    ソース:スナップリンク:https://leetcode-cn.com/problems/gray-code 著作権はネットの所有権を受領する.商業転載は公式の授権に連絡してください.商業転載ではないので、出典を明記してください.解法:
    (n) => {
      let mark = (n) => {
        let arr = []
        if (n === 1) {
          return ['0', '1']
        } else {
          let prev = mark(n - 1)
          let max = Math.pow(2, n) - 1
          for (let i = 0; i < prev.length; i++) {
            arr[i] = `0${prev[i]}`
            arr[max - i] = `1${prev[i]}`
          }
        }
        return arr
      }
      return mark(n)
    }