LeetCode-文字列関連アルゴリズムコード実装

12784 ワード
アルゴリズムとデータ構造
初級アルゴリズム-文字列関連アルゴリズム
1.文字列の反転
タイトル:
入力した文字列を反転させる機能を持つ関数を作成します.
例1:
入力:hello出力:olleh例2:
入力:「A man,a plan,a canal:Panama」出力:「amanap:lanac a,nalp a,nam A」
に答える
/**
 * @param {string} s
 * @return {string}
 */
var reverseString = function(s) {
    return [...s].reverse().join('')
};

2.整数を逆さまにする
タイトル:
32ビットの符号付き整数を指定し、整数の数値を反転します.
例1:
入力:123出力:321例2:
入力:-123出力:-321例3:
入力:120出力:21注意:
我々の環境では32ビットの符号付き整数しか記憶できないと仮定し,その数値範囲は[−231,231−1]である.この仮定によれば,反転後の整数がオーバーフローすると0を返す.
に答える
/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    const maxNumStr = (2 ** 31 - 1).toString()
    const minNumStr = (2 ** 31 * -1).toString()
    const [allStr, flagStr, numStr] = x.toString().match(/^(\D?)(\d+)$/)
    const reverseNumStr = flagStr + [...numStr].reverse().join('')
    if (flagStr) {
        if (reverseNumStr > minNumStr && reverseNumStr.length >= minNumStr.length) return 0
    } else {
        if (reverseNumStr > maxNumStr && reverseNumStr.length >= maxNumStr.length) return 0
    }
    return Number(reverseNumStr)
};

3.文字列の最初の一意の文字
タイトル:
文字列を指定し、最初の重複しない文字を見つけ、インデックスを返します.存在しない場合は、-1を返します.
ケース:
s="leetcode"は0を返す.
s=「loveleetcode」で、2を返します.
注意:文字列には小文字のみが含まれていると仮定できます.
に答える
/**
 * @param {string} s
 * @return {number}
   : https://blog.csdn.net/dangpianjikuang/article/details/79748432
 */
var firstUniqChar = function(s) {
    const strList = [...s]
    const sumObj = {}
    strList.forEach(strItem => {
        sumObj[strItem] = sumObj[strItem] ? sumObj[strItem] + 1 : 1
    })
    for(let [index, strItem] of strList.entries()) {
        if (sumObj[strItem] === 1) return index
    }
    return -1
};

4.有効なアルファベット異位語
タイトル:
2つの文字列sとtを与え、tがsのアルファベット異位語であるか否かを判断する関数を記述する.
例1:
入力:s=「anagram」、t=「nagaram」出力:true例2:
入力:s=「rat」、t=「car」出力:false説明:文字列に小文字のみが含まれていると仮定できます.
ステップ:入力文字列にunicode文字が含まれている場合はどうしますか?あなたの解法を調整してこのような状況に対応することができますか?
に答える
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    const key1Obj = {}
    for (let key1 of s) {
        key1Obj[key1] = key1Obj[key1] ? key1Obj[key1] + 1 : 1
    }
    const key2Obj = {}
    for (let key2 of t) {
        key2Obj[key2] = key2Obj[key2] ? key2Obj[key2] + 1 : 1
    }
    if (Reflect.ownKeys(key1Obj).length !== Reflect.ownKeys(key2Obj).length) return false
    for (let key1 in key1Obj) {
        if (key1Obj[key1] !== key2Obj[key1]) return false
    }
    return true
};

5.入力文字列の検証
タイトル:
文字列を指定し、文字列が文字列であるかどうかを検証し、文字と数字のみを考慮し、文字の大文字と小文字を無視できます.
説明:この問題では、空の文字列を有効な文字列として定義します.
例1:
入力:「A man,a plan,a canal:Panama」出力:true例2:
入力:「race a car」出力:false
に答える
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    const mystr = s.toLowerCase().replace(/[^\w\d]/g, '')
    if (mystr === '') return true
    for (let i = 0; i + 1 <= mystr.length / 2; i++ ) {
        if (mystr[i] !== mystr[mystr.length -1 - i]) return false
    }
    return true
};

6.文字列回転整数(atoi)
タイトル:
atoiを実装し、文字列を整数に変換します.
最初の空でない文字を見つける前に、文字列のスペース文字を削除する必要があります.最初の空白以外の文字が正または負の場合は、記号を選択し、後に続く可能な限り多くの連続する数字と組み合わせると、この部分の文字は整数の値になります.最初の空白以外の文字が数値である場合、その後の連続する数値文字と直接組み合わせて整数を形成します.
文字列は、整数を形成する文字の後ろに余分な文字を含めることができ、これらの文字は無視でき、関数には影響しません.
文字列の最初の空白以外の文字列が有効な整数ではない場合.または文字列が空です.または文字列に空白文字のみが含まれている場合は変換されません.
関数が有効な変換を実行できない場合は、0を返します.
説明:
我々の環境では32ビットの符号付き整数しか記憶できないと仮定し,その数値範囲は[−231,231−1]である.数値が表示可能範囲を超えている場合はINT_を返します.MAX(231−1)またはINT_MIN (−231) .
例1:
入力:42出力:42例2:
入力:"-42"出力:-42解釈:最初の空白以外の文字は「-」で、マイナス記号です.負の記号をできるだけ後ろに連続して現れるすべての数字と組み合わせて、最後に-42を得ます.例3:
入力:“4193 with words”出力:4193解釈:変換は数字“3”に締め切られ、次の文字は数字ではないためである.例4:
入力:「words and 987」出力:0解釈:最初の非空文字は「w」ですが、数字や正、負の記号ではありません.したがって、有効な変換は実行できません.例5:
入力:「-9183472332」出力:-2174848648解釈:数字「-9183472332」が32ビットの符号付き整数範囲を超えた.よってINT_を返すMIN (−231) .
に答える
/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
    const validStr = str.match(/\S+/) ? str.match(/\S+/)[0] : ''
    if (!validStr) return 0
    const numStr = validStr.match(/^[-+]?\d*/)[0]
    if (!numStr || numStr === '-' || numStr === '+') return 0
    const number = Number(numStr)
    if (number > 2 ** 31 - 1) return 2 ** 31 - 1
    if (number < 2 ** 31 * -1) return 2 ** 31 * -1
    return number
};

7.strStrを実現する()
タイトル:
strStr()関数を実装します.
haystack文字列とneedle文字列を指定し、haystack文字列にneedle文字列が現れる最初の位置(0から)を見つけます.存在しない場合は、-1を返します.
例1:
入力:haystack=「hello」、needle=「ll」出力:2例2:
入力:haystack=「aaaa」、needle=「bba」出力:-1説明:
needleが空の文字列である場合、私たちはどの値を返すべきですか?これは面接でいい質問です.
この問題では、needleが空の文字列である場合、0を返します.これはC言語のstrstr()およびJavaのindexOf()定義と一致する.
に答える
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle)
};

8.数えて言う
タイトル:
報数シーケンスとは、1つの整数シーケンスを指し、その中の整数の順序で報数を行い、次の数を得る.最初の5つは次のとおりです.
  • 1
  • 11
  • 21
  • 1211
  • 1112211は「one 1」(「1つ1」)、すなわち11と読まれる.11は「two 1 s」(「2つ1つ」)、すなわち21と読まれる.21は、「one 2」、「one 1」(「1つ2」、「1つ1」)、すなわち1211と読まれる.

    • 正の整数nが与えられ、報数シーケンスのn番目の項が出力される.
    注:整数の順序は文字列として表示されます.
    例1:
    入力:1出力:1の例2:
    入力:4出力:「1211」
    に答える
    /**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if (n === 1) {
        return '1'
    }
    let resultStr = ''
    let currentStr = ''
    let preStr = '1'
    let i = 2
    while (i <= n) {
        let tempStr = preStr
        currentStr = ''
        while (matchRes = tempStr.match(/^(\d)\1*/)) {
            const char = matchRes[1]
            const count = matchRes[0].length
            currentStr += `${count}${char}`
            tempStr = tempStr.substr(count)
        }
        resultStr = currentStr
        preStr = currentStr
        i += 1
    }
    return `${resultStr}`
};

    9.最長共通接頭辞
    タイトル:
    文字列配列の最長の共通接頭辞を検索する関数を作成します.
    共通の接頭辞が存在しない場合は、空の文字列「」を返します.
    例1:
    入力:[「flower」、「flow」、「flight」]出力:「fl」例2:
    入力:[“dog”,“racecar”,“car”]出力:“”解釈:入力に共通接頭辞は存在しません.説明:
    すべての入力には小文字a-zのみが含まれます.
    に答える
    /**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let minLen = Number.MAX_VALUE
    for (let strItem of strs) {
        if (minLen > strItem.length) minLen = strItem.length
    }
    if (minLen === Number.MAX_VALUE) return ''
    for (let i = 0; i < minLen; i++) {
        const char =  strs[0][i]
        for (let strItem of strs) {
            if (char !== strItem[i]) return strItem.substr(0, i)
        }
    }
    return strs[0].substr(0, minLen)
};
    ダイナミックプランニング——リュック問題P 02——完全リュック
    二分検索アルゴリズムの時間的複雑さ