Day06 | 242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和

Leetcode 242.有效的字母异位词

题目：242.有效的字母异位词 关于哈希表：https://www.jianshu.com/p/6e88d63061f2

初始思路

暴力解法是双层for循环，同时记录字符是否重复出现。
根据题目可知，题目中字符串只有小写字符，众所周知英文字符只有26个，那么我们可以申请两个长度为26的数组来存储字母出现的情况，如果两个数组相同，那么就是字母异位词。

代码

var isAnagram = function (s, t) {
    if (s.length !== t.length) return false
    let n = s.length
    // 26个空间的数组，因为有26个字母
    let arr1 = new Array(26).fill(0)
    let arr2 = new Array(26).fill(0)
    for (let i = 0; i < n; i++) {
        // charAt()方法返回指定索引位置的char值。
        // charCodeAt() 方法可返回指定位置的字符的 Unicode 编码。
        // 找到第i个位置上的字符是什么，并转换为unicode编码
        let index1 = s.charAt(i).charCodeAt() - 97
        let index2 = t.charAt(i).charCodeAt() - 97
        arr1[index1]++
        arr2[index2]++
    }
    for (let j = 0; j < 26; j++) {
        if (arr1[j] !== arr2[j]) {
            return false
        }
    }
    return true
};

// 优化写法
var isAnagram = function (s, t) {
    if (s.length !== t.length) return false
    const resSet = new Array(26).fill(0)
    const base = 'a'.charCodeAt()
    for (const i of s) {
        // 辅助数组中对应的地方加一
        resSet[i.charCodeAt() - base]++
    }
    for (const i of t) {
        // 出现一次就减一
        resSet[i.charCodeAt() - base]--
    }
    for (const count of resSet) {
        // 如果最后所有数组元素都为0，说明是字母异位词
        if (count !== 0) return false
    }
    return true
}

感想

1. 第一种写法申请了两个数组，存储两个字符串的字母出现情况。可以只申请一个辅助数组，第一个数组加，第二个数组减，如果值都为0，说明是字母异位词，
2. 要掌握JS的charCodeAt和charAt方法

Leetcode 349.两个数组的交集

题目：349.两个数组的交集 关于set：https://www.jianshu.com/p/2b9b5871313d

初始思路

同上题，暴力解法就是使用双层for循环。

代码

var intersection = function (nums1, nums2) {
    let a = new Set(nums1)
    let res = new Set()
    for (let n of nums2) {
        if (a.has(n)) {
            res.add(n)
        }
    }
    // 通过解构赋值把set转化为数组
    return [...res]
};

感想

1. 在JS中，set可以实现自动去重。将其中一个数组转换为set后，遍历另一个数组，如果a中也存在这个元素，就把他加入结果中，因为结果也是set，所以就算出现了重复元素也没关系，会自动去重。
2. 最后要记得使用ES6的解构赋值把res从set转化为数组。

Leetcode 202.快乐数

题目：202.快乐数 关于map：https://www.jianshu.com/p/c53460c9c8e4

初始思路

第一次看题目觉得这是个无限循环，除了判断和为1，怎么样能跳出循环呢。

代码

var getSum = function (n) {
    let sum = 0
    while (n) {
        // 取个位平方
        sum += (n % 10) ** 2
        // 去掉最后一位
        n = Math.floor(n / 10)
    }
    return sum
}
var isHappy = function (n) {
    let m = new Map()
    while (true) {
        // 如果n出现过，说明是无限循环
        if (m.has(n)) return false
        if (n === 1) return true
        m.set(n, 1)
        n = getSum(n)
    }
};

var getSum = function (n) {
    let sum = 0
    while (n) {
        // 取个位平方
        sum += (n % 10) ** 2
        // 去掉最后一位
        n = Math.floor(n / 10)
    }
    return sum
}
var isHappy = function (n) {
    // set里的值不可以重复
    let set = new Set()
    while (n !== 1 && !set.has(n)) {
        // 如果在循环中某个值重复出现，说明出现了死循环
        set.add(n)
        n = getSum(n)
    }
    return n === 1
}

感想

1. 将每次求的和放在map里，一旦后面又出现这个和，说明这是个无限循环。
2. 使用set，因为set本身就非重复，可以更简洁的判断。
3. 也可以使用环形链表，如果有闭环，就有重复元素。

Leetcode 1.两数之和

题目：1.两数之和

初始思路

梦开始的地方！暴力解法依旧是双层for循环遍历记录。
使用map(key, value)来记录。key是数组元素，value是数组元素下标。

代码

var twoSum = function (nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            // 如果在map中能找到匹配的元素
            // 就返回这两个数的下标
            return [map.get(target - nums[i]), i]
        } else {
            // 如果map中找不到匹配的元素
            // 把这个元素存入map以便后面的元素使用
            // 记住key是数组元素，value是数组下标
            map.set(nums[i], i)
        }
    }
    return []
};

感想

1. 我们遍历到数字a时，用 target减去a，就会得到b，若b存在于哈希表中，我们就可以直接返回结果了。若b 不存在，那么我们需要将a存入哈希表，好让后续遍历的数字使用。
2. 要记住map(key, value)中key和value记录的到底是什么。key是数组元素，value是数组元素下标。
3. 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。