LeetCode 热题 100
哈希hash
1 两数之和
/*
* 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
* 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
* 你可以按任意顺序返回答案。
*/
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++)
{
auto iter = map.find(target - nums[i]);
if (iter != map.end()) {
return {iter->second, i};
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
int main()
{
vector<int> nums = {2, 7, 11, 15};
int target = 0;
cin >> target;
vector<int> result = twoSum(nums, target);
for (auto a : result) {
cout << a << ' ';
}
return 0;
}
2 字母异位词分组
思路：由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
/*
* 给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
* 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
*/
#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<vector<string>> groupWord(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (auto a : strs) {
string key = a;
sort(key.begin(), key.end());
map[key].emplace_back(a);
}
vector<vector<string>> ans;
for (auto iter = map.begin(); iter != map.end(); iter++) {
ans.emplace_back(iter->second);
}
return ans;
}
int main()
{
vector<string> s = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> result = groupWord(s);
for (auto a : result) {
for (auto b : a) {
cout << b << ' ';
}
cout << endl;
}
return 0;
}
复杂度分析
（1）时间复杂度： O ( n k l o g ( k ) ) O(nklog(k)) O(nklog(k))
（2）空间复杂度： O ( n k ) O(nk) O(nk)
3 最长连续序列
/*
* 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
* 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
*/
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int longestS(vector<int>& nums) {
int res = 0;
int subLength = 0;
unordered_set<int> nums_set(nums.begin(), nums.end());
for (auto num : nums_set) {
if (!nums_set.count(num - 1)) {
subLength = 1;
while (nums_set.count(++num)) subLength++;
res = max(res, subLength);
}
}
return res;
}
int main()
{
vector<int> nums = {100,4,200,1,3,2};
cout << longestS(nums) << endl;
return 0;
}
双指针
1 移动零
/*
* 给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
* 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
*/
#include <iostream>
#include <vector>
using namespace std;
void moveZeros(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow++], nums[fast]);
}
}
}
int main()
{
vector<int> nums = {0,1,0,3,12};
moveZeros(nums);
for (auto i : nums) {
cout << i << ' ';
}
return 0;
}
/*
* 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
* 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
* 返回容器可以储存的最大水量。
* 说明：你不能倾斜容器。
*/
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
int maxArea(vector<int> heights) {
int left = 0;
int right = heights.size() - 1;
int res = INT_MIN;
while (left < right) {
if (heights[left] < heights[right]) {
res = max(res, (right - left) * heights[left]);
left++;
} else {
res = max(res, (right - left) * heights[right]);
right--;
}
}
return res;
}
int main()
{
vector<int> heights = {1,8,6,2,5,4,8,3,7};
cout << maxArea(heights) << endl;
return 0;
}
/*
* 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
* 你返回所有和为 0 且不重复的三元组。
* 注意：答案中不可以包含重复的三元组。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) return result;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 2]) right--;
left++;
right--;
}
}
}
return result;
}
int main()
{
vector<int> nums = {-1,0,1,2,-1,-4};
vector<vector<int>> res = threeSum(nums);
for (auto a : res) {
for (auto b : a) {
cout << b << ' ';
}
cout << endl;
}
}
/*
* 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
*/
#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
int sum = 0;
for (int i = 0; i < height.size(); i++) {
if (i == 0 || i == height.size() - 1) continue;
int left = height[i];
int right = height[i];
for (int j = i - 1; j >= 0; j--) {
if (left < height[j]) left = height[j];
}
for (int j = i + 1; j < height.size(); j++) {
if (right < height[j]) right = height[j];
}
int h = min(left, right) - height[i];
if (h > 0) sum += h;
}
return sum;
}
int main()
{
vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
cout << trap(height) << endl;
return 0;
}
二叉树
1 二叉树的中序遍历
class Solution {
public:
void traversal(TreeNode* node, vector<int>& vec) {
if (node == NULL) return;
if (node->left) traversal(node->left, vec);
vec.push_back(node->val);
if (node->right) traversal(node->right, vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
2 二叉树的最大深度
递归法：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};
迭代法：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
queue<TreeNode*> que;
que.push(root);
int depth = 0;
while (!que.empty()) {
int size = que.size();
depth++;
while (size--) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return depth;
}
};
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right);
if (root->left) invertTree(root->left);
if (root->right) invertTree(root->right);
return root;
}
};
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if (left != NULL && right == NULL) return false;
else if (left == NULL && right != NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
return outside && inside;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
class Solution {
public:
int ans;
int depth(TreeNode* node) {
if (node == NULL) return 0;
int left = depth(node->left);
int right = depth(node->right);
ans = max(ans, left + right + 1);
return max(left, right) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == NULL) return result;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int> vec;
while (size--) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
Day1做了13道题，暂且打住，明天再干👊