算法练习

[coderliush]

Q: 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词 输入: s = "anagram", t = "nagaram" 1 输出: true

输入: s = "rat", t = "car" 1 输出: false

1. 字符串转为数组，判断一个数组中的所有元素是否存在于另一个数组。

   function isAnagram(str1, str2) {
        let obj = {}
        let arr1 = str1.split('')
        let arr2 = str2.split('')
        arr1.forEach(item => obj[item] = item)
        return arr2.every(item => obj[item])
   }

   时间复杂度 O(n)，空间复杂度O(1)

2. 字符串转为数组，sort 对元素进行排序后比较

   function isAnagram(str1, str2) {
       let arr1 = str1.split('')
       let arr2 = str2.split('')
       return JSON.stringify(arr1.sort()) === JSON.stringify(arr2.sort())
   }

   申请两个数组，数组空间长度跟字符串长度线性相关，所以为 空间复杂度O(n)

[coderliush]

Q: 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 输入：s = "leetcode" 输出：返回 0

输入：s = "loveleetcode", 输出：返回 2

 function findUnique(str) {
    let obj = {}
    str.split('').forEach(item => {
        if (!obj[item]) {
            obj[item] = 1
        } else {
            obj[item] += 1
        }
    })

    for (let k in obj) {
        if (obj[k] === 1) {
            return k
        } 
    }
    return - 1
}

时间复杂度 O(n)，空间复杂度 O(1)

[coderliush]

Q：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。 以下称 haystack 字符串为匹配字符串，needle 字符串为查找字符串 输入：haystack = 'hello world', needle = 'll' 输出：2

function findUnique (haystack, needle) {
    let obj = {}
    for (let i=0; i < haystack.length; i++) {
        let str = haystack.substring(i, i + needle.length)
        obj[str] = i
    }

    for (let k in obj) {
        if (k === needle) {
            return obj[k]
        }
    }
    return -1
}

时间复杂度 O(n)，空间复杂度 O(1)

[coderliush]

Q：最长公共前缀，编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
输入: ["flower", "flow", "flight"]
输出: "fl"

思路：计算前两个很容易，之后递归循环。以第一个字符串为最长的公共前缀，循环数组，对公共前缀逐个修正。 写法1：获取两个字符相同的前缀：将公共前缀字符串的每个字符存储于一个对象，之后逐个比较。

function getCommonPrefix(arr) {   
    let commonPre = ''
    function findCommPrefix(_commonPre, compareStr) {
        let obj = {}
        for (let i=0; i<_commonPre.length; i++) {
            let string = _commonPre.substring(0, i)
                obj[string] = string
            }

        for (let k in obj) {
            if (compareStr.includes(k)) {
                commonPre = k
            }
        }
    }

    for (let i=0; i<arr.length; i++) {
        if (i === 0) {
            findCommPrefix(arr[0], arr[1])
        } else {
            findCommPrefix(commonPre, arr[i])
        }
    }

    return commonPre
}

写法二：获取两个字符相同的前缀：逐个字符判断，找到相同字符的索引然后截取。

const longestCommonPrefix = function (strs) {
    function findCommonPrefix(a, b) {
        let i = 0
        while (i < a.length && i < b.length && a.charAt(i) === b.charAt(i)) {
            i++
        } 
        return i > 0 ? a.substring(0, i) : ''
    } 
    if (strs.length > 0) {
        let commonPrefix = strs[0]
        for (let i = 1; i < strs.length; i++) {
            commonPrefix = findCommonPrefix(commonPrefix, strs[i])
        } 
        return commonPrefix
    } 
    return ''
}