leetCode之Hash相关
2020-09-25 本文已影响0人
Benzic
首页目录 点击查看
第一题：
- 难度：简单
- 题目： 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
解释:
解题思路
- 这道题很简单，只需要依次把每一行的数加起来，然后统计每一行某个和出现的次数，最多的那个数字就是没穿过的，穿过的就是数组长度减去出现最多的数字。
我的答案
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
