各种用到哈希表的题目，集中记录一下。
问题描述
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例
1
2
3
| 输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int findMaxLength(vector<int>& nums) {
int res = 0;
unordered_map<int, int> mp;
int cnt = 0;
mp[cnt] = -1;
for (int i = 0; i < nums.size(); ++ i) {
if (nums[i] == 0) cnt --;
else cnt ++;
if (mp.count(cnt)) {
res = max(res, i - mp[cnt]);
}
else mp[cnt] = i;
}
return res;
}
};
|
题目描述
给定一个整数数组nums和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例
1
2
3
| 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mymap;
for (int i = 0; i < nums.size(); ++ i) {
if (mymap[target - nums[i]] > 0) {
return {i, mymap[target - nums[i]] - 1};
}
mymap[nums[i]] = i + 1;
}
return {};
}
};
|
问题描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例
1
2
| 输入：nums = [1,1,1], k = 2
输出：2
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int cnt = 0;
unordered_map<int, int> mymap;
mymap[0] = 1;
vector<int> s(nums.size() + 1);
for (int i = 0; i < nums.size(); ++ i) {
s[i + 1] = s[i] + nums[i];
}
for (int i = 0; i < nums.size(); ++ i) {
if (mymap.count(s[i + 1] - k)) {
cnt += mymap[s[i + 1] - k];
}
mymap[s[i + 1]] ++;
}
return cnt;
}
};
|
问题描述
给你一个整数数组 nums 和一个整数 k。
如果某个连续子数组中恰好有 k个奇数数字，我们就认为这个子数组是**「优美子数组」**。
请返回这个数组中「优美子数组」的数目
示例
1
2
3
| 输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
|
代码
本题用双指针做法更好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int numOfOdd = 0, res = 0;
unordered_map<int, int> mymap;
mymap[0] = 1;
for (int i = 0; i < nums.size(); ++ i) {
if (nums[i] & 1) numOfOdd ++;
if (mymap.count(numOfOdd - k)) res += mymap[numOfOdd - k];
mymap[numOfOdd] ++;
}
return res;
}
};
|
问题描述
给你四个整数数组 nums1、nums2、nums3 和nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例
1
2
3
4
5
6
| 输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> cnt1_2;
int res = 0;
for (auto i : nums1) {
for (auto j : nums2) {
cnt1_2[i + j] ++;
}
}
for (auto i : nums3) {
for (auto j : nums4) {
if (cnt1_2.count(-i-j)) {
res += cnt1_2[-i-j];
}
}
}
return res;
}
};
|
设计一个支持下述操作的食物评分系统：
- 修改 系统中列出的某种食物的评分。
- 返回系统中某一类烹饪方式下评分最高的食物。
实现 FoodRatings 类：
FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，长度均为 n 。foods[i] 是第 i 种食物的名字。cuisines[i] 是第 i 种食物的烹饪方式。ratings[i] 是第 i 种食物的最初评分。
void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列，返回 字典序较小 的名字。
注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，或者在满足 x[i] != y[i] 的第一个位置 i 处，x[i] 在字母表中出现的位置在 y[i] 之前。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class FoodRatings {
Map<String, Food> store;
Map<String, TreeSet<Food>> cuisineToFood;
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
this.store = new HashMap<>();
this.cuisineToFood = new HashMap<>();
for (int i = 0; i < foods.length; ++i) {
Food f = new Food(foods[i], ratings[i], cuisines[i]);
store.put(foods[i], f);
cuisineToFood.computeIfAbsent(cuisines[i], key -> new TreeSet<>()).add(f);
}
}
public void changeRating(String food, int newRating) {
Food f = store.get(food);
TreeSet<Food> set = cuisineToFood.get(f.cuisine);
set.remove(f);
f.rate = newRating;
store.put(food, f);
set.add(f);
}
public String highestRated(String cuisine) {
TreeSet<Food> set = cuisineToFood.get(cuisine);
return set.first().name;
}
}
class Food implements Comparable<Food>{
String name, cuisine;
int rate;
public Food(String name, int rate, String c) {
this.name = name;
this.rate = rate;
cuisine = c;
}
@Override
public int compareTo(Food y) {
if (this.rate != y.rate) return y.rate - this.rate;
else return this.name.compareTo(y.name);
}
}
|