LeetCode Hot100 1~10
目录
- 哈希
- 1. 两数之和
- 2. 字母异位词分组
- 3. 最长连续子序列
- 双指针
- 4. 移动零
- 5. 盛最多水的容器
- 6. 三数之和
- 7. 接雨水
- 子串
- 8. 无重复字符的最长子串
- 9. 找到字符中所有字母的异位词
- 10. 和为K的子数组
哈希
1. 两数之和
利用哈希表找出当前数字还差多少 看看差值时候在哈希表中即可
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int , int> unmapNums;
for (int i = 0; i < nums.size(); i++) {
unmapNums[nums[i]] = i;
}
vector<int> ans = {};
for (int i = 0; i < nums.size(); i++) {
if (unmapNums.count(target - nums[i]) == 1) {
if (i !=unmapNums[target - nums[i]] ) {
ans.push_back(i);
ans.push_back(unmapNums[target - nums[i]]);
break;
}
}
}
return ans;
}
};
2. 字母异位词分组
我们只需要将每个string进行排序 排序后的结果作为key 本身的str作为value即可
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string , vector<string>> unmapString;
for (auto str : strs) {
string key = str;
sort(key.begin() , key.end());
unmapString[key].push_back(str);
}
vector<vector<string>> ans;
for (auto vStr : unmapString) {
ans.push_back(vStr.second);
}
return ans;
}
};
3. 最长连续子序列
我们只需要将所有的数字放到一个set中
之后遍历整个set 找到最长子序列开始最小的一个数 然后不停往后推即可
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> setNums;
for (auto x : nums) {
setNums.insert(x);
}
int ans = 0;
for (auto it : setNums) {
if (setNums.count(it - 1)) {
continue;
}
int cur = 1;
int curNum = it;
while(setNums.count(curNum + 1)) {
cur += 1;
curNum += 1;
}
ans = max(ans , cur);
}
return ans;
}
};
双指针
4. 移动零
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int left = 0;
int right = 0;
for(right = 0; right < nums.size(); right++) {
if (nums[right] != 0) {
nums[left] = nums[right];
left++;
}
}
for (int i = left ; i < nums.size(); i++) {
nums[i] = 0;
}
}
};
5. 盛最多水的容器
本题依然使用双指针就可以解决
我们首先确定当宽度最大的时候能装最多的水为多少 接下来宽度减少
因为宽度确定了 所以高度要尽可能的大 于是我们移动高度较小的那一侧
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int ans = 0;
while(left < right) {
int h = min(height[left] , height[right]);
int w = right - left;
int cur = h * w;
ans = max(ans , cur);
if (height[left] < height[right]) {
left++;
}else {
right--;
}
}
return ans;
}
};
6. 三数之和
本题主要使用双指针法来解决 整体思路比较简单 难点是如何去重
首先我们将整个数目进行排序 i 作为数目的第一号位 left作为二号位 right作为三号位 看看这三个数能够组成一个三元组
如果说大了 right –
如果说小了 left++
如果说正好 则我们将答案放到容器中
去重
- 对i进行去重 如果和上一个数相同 则直接continue
- 对left去重 在得到一个答案之后 不断往右去重
- right同理
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin() , nums.end());
for (int i = 0 ; i < nums.size() - 2; i++) {
if (i > 0 && nums[i-1] == nums[i]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < 0) {
left++;
} else if (nums[i] + nums[left] + nums[right] > 0) {
right--;
}else {
ans.push_back({nums[i] , nums[left] , nums[right]});
while(left < right && nums[left + 1] == nums[left]) {
left++;
}
while(left < right && nums[right - 1] == nums[right]) {
right--;
}
left++;
right--;
}
}
}
return ans;
}
};
7. 接雨水
我们从一列来考虑 只需要确定两旁的高度和当前高度的占用 我们就能确定这一列能接多少雨水
于是乎我们可以使用左右指针分别确认当前位置的最小高度以及占用高度 相减即可
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
int n = height.size();
vector<int> vpre(n , 0);
vector<int> vsuf(n , 0);
vpre[0] = height[0];
for (int i = 1; i < height.size(); i++) {
vpre[i] = max(vpre[i-1] , height[i]);
}
vsuf[n-1] = height[n-1];
for (int i = n -2; i >=0 ; i--) {
vsuf[i] = max(vsuf[i+1] , height[i]);
}
for (int i = 0; i < n; i++) {
ans += (min(vsuf[i] , vpre[i]) - height[i]);
}
return ans;
}
};
子串
8. 无重复字符的最长子串
简单的动态规划
需要注意的是 我们每次遍历都需要更新字符所在的位置 而不是遇到重复值再更新
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
vector<int> dp(n , 0);
unordered_map<char , int> unmapStr;
dp[0] = 1;
unmapStr[s[0]] = 0;
for (int i = 1; i < s.size(); i++) {
dp[i] = dp[i-1] + 1;
if (unmapStr.count(s[i])) {
dp[i] = min(dp[i] , i - unmapStr[s[i]]);
}
unmapStr[s[i]] = i;
}
int ans = 0;
for (auto x : dp) {
ans = max(ans , x);
}
return ans;
}
};
9. 找到字符中所有字母的异位词
我们使用一个“欠账哈希表” 来表示字符的欠账 all表示欠账的总额 （大于等于0）
然后每次L++ R++的时候我们开始还账和入账 如此反复即可
需要注意的是L++ 和R++的位置 以及入账和还账的时机和顺序
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if (p.size() > s.size()) {
return {};
}
vector<int> ans;
int n = p.size();
unordered_map<char , int> unmapStrp1;
for (auto x : p) {
unmapStrp1[x]++;
}
int L = 0;
int R = n - 1;
for (int j = L ; j <= R; j++) {
if (unmapStrp1.count(s[j])) {
unmapStrp1[s[j]]--;
}
}
int all = 0;
for (auto x : unmapStrp1) {
if (x.second > 0) {
all += x.second;
}
}
while (R < s.size()) {
if (all == 0) {
ans.push_back(L);
}
if (unmapStrp1.count(s[L])) {
unmapStrp1[s[L]]++;
if (unmapStrp1[s[L]] > 0) {
all++;
}
}
R++;
if (unmapStrp1.count(s[R])) {
unmapStrp1[s[R]]--;
if (unmapStrp1[s[R]] >= 0) {
all--;
}
}
L++;
}
return ans;
}
};
10. 和为K的子数组
这道题目需要注意的是 我们每次更新一个前缀和就要计算一次结果 以免后面的前缀和进入哈希表后影响前面的结果
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
vector<int> vPre(nums.size() + 1, 0);
vPre[0] = 0;
int ans = 0;
unordered_map<int, int> unmapVpre;
unmapVpre[0]++; // 初始时考虑前缀和为0的情况
for (int i = 0; i < nums.size(); i++) {
vPre[i + 1] = vPre[i] + nums[i];
// 在计算前缀和之后，检查当前前缀和是否满足条件
if (unmapVpre.count(vPre[i + 1] - k)) {
ans += unmapVpre[vPre[i + 1] - k];
}
// 更新当前前缀和的出现次数
unmapVpre[vPre[i + 1]]++;
}
return ans;
}
};