LeetCode 热题 100 (尽量ACM模式刷) 持续更新!!!

2024-03-06 02:20

本文主要是介绍LeetCode 热题 100 (尽量ACM模式刷) 持续更新!!!,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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;
}

2 盛最多水的容器

/** 给定一个长度为 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;
}

3 三数之和

/** 给你一个整数数组 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;}
}

4 接雨水

/** 给定 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;}
};

3 翻转二叉树

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;}
};

4 对称二叉树

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);}
};

5 二叉树的直径

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;}
};

6 二叉树的层序遍历

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道题,暂且打住,明天再干👊

这篇关于LeetCode 热题 100 (尽量ACM模式刷) 持续更新!!!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/778567

相关文章

大数据spark3.5安装部署之local模式详解

《大数据spark3.5安装部署之local模式详解》本文介绍了如何在本地模式下安装和配置Spark,并展示了如何使用SparkShell进行基本的数据处理操作,同时,还介绍了如何通过Spark-su... 目录下载上传解压配置jdk解压配置环境变量启动查看交互操作命令行提交应用spark,一个数据处理框架

Docker部署Jenkins持续集成(CI)工具的实现

《Docker部署Jenkins持续集成(CI)工具的实现》Jenkins是一个流行的开源自动化工具,广泛应用于持续集成(CI)和持续交付(CD)的环境中,本文介绍了使用Docker部署Jenkins... 目录前言一、准备工作二、设置变量和目录结构三、配置 docker 权限和网络四、启动 Jenkins

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1

Linux Mint Xia 22.1重磅发布: 重要更新一览

《LinuxMintXia22.1重磅发布:重要更新一览》Beta版LinuxMint“Xia”22.1发布,新版本基于Ubuntu24.04,内核版本为Linux6.8,这... linux Mint 22.1「Xia」正式发布啦!这次更新带来了诸多优化和改进,进一步巩固了 Mint 在 Linux 桌面

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

Ubuntu 24.04 LTS怎么关闭 Ubuntu Pro 更新提示弹窗?

《Ubuntu24.04LTS怎么关闭UbuntuPro更新提示弹窗?》Ubuntu每次开机都会弹窗提示安全更新,设置里最多只能取消自动下载,自动更新,但无法做到直接让自动更新的弹窗不出现,... 如果你正在使用 Ubuntu 24.04 LTS,可能会注意到——在使用「软件更新器」或运行 APT 命令时,

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,