美文网首页
leetCode之Hash相关

leetCode之Hash相关

作者: Benzic | 来源:发表于2020-09-25 17:03 被阅读0次

首页目录 点击查看

第一题:

  • 难度:简单
  • 题目: 1.两数之和
    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

解题思路

我首先想到遍历数组两次的方法,找到num[j] = traget - num[i],保存后输出两个index.

我的答案

  • 两个for循环
        var twoSum = function (nums, target) {
            for (let i = 0; i <= nums.length - 1; i++) {
                for (let j = i + 1; j <= nums.length - 1; j++) {
                    if (nums[i] === target - nums[j]) {
                        return [ i, j]
                        break
                    }
                }
            }
        };
  • 时间复杂度:O(N2)
  • 空间复杂度: O(N)
    这明显不是最好的解决方案,就凭这两个for循环就很拉胯


    image.png

当然我也想出了另外一种方案,只需要一个for循环,用一个对象角标来保存目标数值: 这种方法从时间复杂度上只需要O(N)

        var twoSum = function (nums, target) {
            let useNum = {}
            for (let i = 0; i <= nums.length - 1; i++) {
                const currentNum = nums[i];
                const targetNum = target - currentNum;
                const targetIndex = useNum[targetNum]
                if (targetIndex !== undefined) {
                    return [targetIndex, i]
                    break
                }
                useNum[currentNum] = i
            }
        };
  • 时间复杂度:O(N)
  • 空间复杂度: O(N)


    结果

第二题

  • 难度:中等
  • 题目:763. 划分字母区间
    字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例

输入:S = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。

解题思路

  • 这道题虽然标签是贪心算法和双指针,想了一下还是只能想出用hash处理。所以这里把他放到hash相关来

我的答案

var partitionLabels = function (S) {
    let map = {}
    let arr = []
    let start = 0
    for (let i = 0; i <= S.length - 1; i++) {
        map[S[i]] = i;
    }
    let splitIndex = 0;
    for (let i = 0; i <= S.length; i++) {
        let lastIndex = map[S[i]];
        splitIndex = Math.max(splitIndex, lastIndex);
        if (i === splitIndex) {
            arr.push(i - start + 1);
            start = i + 1
        }
    }
    return arr
};
image.png

第三题

  • 难度:中等
  • 题目:49. 字母异位词分组
    给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

解题思路

  • 这道题需要把每个单独的字符串进行排序然后用map对象hash存储,如果相同的则都放在数组里面,最后输出数组

我的答案

var groupAnagrams = function (strs) {
    let map = {};
    let array = []
    for (let i = 0; i <= strs.length - 1; i++) {
        let sortStr = strs[i].split("").sort((a, b) => {
            return a > b ? 1 : -1
        }).join("")
        !map[sortStr] && (map[sortStr] = []);
        map[sortStr].push(strs[i])
    }
    for (let i in map) {
        array.push(map[i])
    }
    return array
};
image.png

第四题

  • 难度:简单
  • 题目:242. 有效的字母异位词
    给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例

输入: s = "anagram", t = "nagaram"
输出: true

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

解题思路

  • 这道题最简单的解法是把两个字符排序然后作比较,但是性能不太好,看了题解,而且这道题本来是用hash来做,前面那样就不算hash解法,所以有了第二个解法。

我的答案

  • 排序
        var isAnagram = function (s, t) {
            let sStr = s.split("").sort((a, b) => {
                return a > b ? 1 : -1
            }).join("");
            let tStr = t.split("").sort((a, b) => {
                return a > b ? 1 : -1
            }).join("");
            return sStr === tStr
        };
image.png
  • hash
        var isAnagram = function (s, t) {
            if (s.length !== t.length) {
                return false
            }
            let hash = new Array(26).fill(0);
            let codeA = "a".charCodeAt()
            for (let i = 0; i <= s.length - 1; i++) {
                hash[s.charCodeAt(i) - codeA]++;
                hash[t.charCodeAt(i) - codeA]--;
            }
            for (let i in hash) {
                if (hash[i]) {
                    return false
                }
            }
            return true
        };
image.png

第五题

  • 难度:简单
  • 题目:204. 计数质数
    统计所有小于非负整数 n 的质数的数量。

示例

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

输入:n = 0
输出:0

解题思路

  • 这道题我能想到的是暴力算法,但是暴力算法直接超时了,所以得对暴力遍历进行优化,比如对于偶数直接跳过即可。但这明显不是最优解,时间都达到500多MS了,只是内存占用较少,看了题解发现了厄拉多塞筛法,这个方法非常高效。


    image.png

    对此,我们可以声明一个长度为最大限制数的布尔数组。用布尔值来区别筛选出的数和质数。

我的答案

        var countPrimes = function (n) {
            if (n < 3) {
                return 0
            }
            let num = 1;
            for (let i = 3; i <= n - 1; i++) {
                if (i % 2 == 0)      //过滤掉偶数,2 因为默认num就是1了所以也算在其中了。
                    continue;;
                let flag = true
                for (let j = 3; j * j <= i; j += 2) {
                    if (i % j === 0) {
                        flag = false
                        break;
                    }
                }
                if (flag) {
                    num += 1
                }
            }
            return num
        };
image.png
  • 厄拉多塞筛法
        var countPrimes = function (n) {
            let num = 0;
            let map = new Array(n).fill(false);
            for (let i = 2; i <= n - 1; i++) {
                if (!map[i]) {
                    num += 1;
                    for (let j = i + i; j <= n - 1; j += i) {
                        map[j] = true
                    }
                }
            }
            return num
        }
image.png

第六题

  • 难度:中等
  • 题目:299. 猜数字游戏
    你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下:
    你写出一个秘密数字,并请朋友猜这个数字是多少。
    朋友每猜测一次,你就会给他一个提示,告诉他的猜测数字中有多少位属于数字和确切位置都猜对了(称为“Bulls”, 公牛),有多少位属于数字猜对了但是位置不对(称为“Cows”, 奶牛)。
    朋友根据提示继续猜,直到猜出秘密数字。
    请写出一个根据秘密数字和朋友的猜测数返回提示的函数,返回字符串的格式为 xAyB ,x 和 y 都是数字,A 表示公牛,用 B 表示奶牛。
    xA 表示有 x 位数字出现在秘密数字中,且位置都与秘密数字一致。
    yB 表示有 y 位数字出现在秘密数字中,但位置与秘密数字不一致。
    请注意秘密数字和朋友的猜测数都可能含有重复数字,每位数字只能统计一次。

示例

输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 1 公牛和 3 奶牛。公牛是 8,奶牛是 0, 1 和 7。

输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 朋友猜测数中的第一个 1 是公牛,第二个或第三个 1 可被视为奶牛。

解题思路

  • 这道题公牛很好判断,一个for循环相同位置相等的即为公牛,奶牛比较麻烦,就需要两个map对象来存储当前出现的数字次数,最后比较两者之间相同的数字最少出现的次数就为奶牛。

我的答案

var getHint = function (secret, guess) {
    let ANum = 0;
    let BNum = 0;
    let mapS = {};
    let mapG = {}
    for (let i = 0; i <= secret.length - 1; i++) {
        if (secret[i] === guess[i]) {
            ANum += 1
        } else {
            !mapS[secret[i]] && (mapS[secret[i]] = 0);
            !mapG[guess[i]] && (mapG[guess[i]] = 0);
            mapS[secret[i]] += 1;
            mapG[guess[i]] += 1;
        }
    }
    for (let i in mapG) {
        if (mapS[i]) {
            BNum += Math.min(mapS[i], mapG[i])
        }
    }
    return ANum + "A" + BNum + "B"
};
image.png

第七题

  • 难度:中等
  • 题目: 554. 砖墙
    你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。
    砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
    如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量。
    你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。

示例

输入: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]

输出: 2

解释: 
![image.png](https://img.haomeiwen.com/i2669301/0094d2db4bc94c64.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

解题思路

  • 这道题很简单,只需要依次把每一行的数加起来,然后统计每一行某个和出现的次数,最多的那个数字就是没穿过的,穿过的就是数组长度减去出现最多的数字。

我的答案

var leastBricks = function (wall) {
    let map = {}
    let max = 0
    for (let i = 0; i <= wall.length - 1; i++) {
        let sum = 0
        for (let j = 0; j < wall[i].length - 1; j++) {
            sum += wall[i][j]
            !map[sum] && (map[sum] = 0);
            map[sum] += 1
            max = Math.max(map[sum], max)
        }
    }
    return wall.length - max
};
image.png

相关文章

网友评论

      本文标题:leetCode之Hash相关

      本文链接:https://www.haomeiwen.com/subject/zreuyktx.html