2024年2月17日力扣题目训练
2024年2月17日力扣题目训练
2024年2月17日第二十四天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的,我会慢慢补回来，争取一天发两篇，把之前的都补上。
需要反复思考（没有做出来的）：
310. 最小高度树 ：考察了建图，树的性质，图的遍历。
212. 单词搜索 II：考察了前缀树。
661. 图片平滑器
链接: 图片平滑器
难度： 简单
题目：
运行示例：
思路：
这道题就是单纯的遍历，找该点的周围几个点进行求和平均即可。
代码：
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
int m = img.size();
int n = img[0].size();
vector<vector<int>> ans(m,vector<int>(n,0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int num = 0, sum = 0;
for (int x = i - 1; x <= i + 1; x++) {
for (int y = j - 1; y <= j + 1; y++) {
if (x >= 0 && x < m && y >= 0 && y < n) {
num++;
sum += img[x][y];
}
}
}
ans[i][j] = sum / num;
}
}
return ans;
}
};
671. 二叉树中第二小的节点
链接: 第二小的节点
难度： 简单
题目：
运行示例：
思路：
这道题，我们要找第二小，那么我们就是利用深度优先遍历，找到第一个比根节点值大的值即可。
代码：
class Solution {
public:
void dfs(TreeNode* root, int& ans,int rootval){
if(root == NULL) return;
if(ans != -1 && root->val >= ans) return;
if(root->val > rootval) ans = root->val;
dfs(root->left,ans,rootval);
dfs(root->right,ans,rootval);
}
int findSecondMinimumValue(TreeNode* root) {
int ans = -1;
int rootval = root->val;
dfs(root,ans,rootval);
return ans;
}
};
674. 最长连续递增序列
链接: 最长连续递增序列
难度： 简单
题目：
运行示例：
思路：
这道题看出就是查看连续递增的最大长度，可以采用遍历，以及动态规划。dp[i]表示以第i个数字为结束的连续递增的长度。
代码：
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int ans = 1;
vector<int>dp(nums.size(),1);
for(int i = 1; i < nums.size(); i++){
if(nums[i] > nums[i-1]){
dp[i] = dp[i-1]+1;
ans = max(ans,dp[i]);
}
}
return ans;
}
};
310. 最小高度树
链接: 最小高度树
难度： 中等
题目：
运行示例：
思路：
这道题我是想用每一个节点作为根节点生成不同的树从而找到最小的高度树，但是复杂度比较高，官方题解则是抓住了生成树过程中的性质利用找距离最远的两个节点从而找到最小高度树，我觉得·值得我们大家多看看。
代码：
class Solution {
public:
int findLongsNode(int u,vector<int> & parent,vector<vector<int>> & adj){
int n = adj.size();
queue<int> q;
vector<bool> visit(n);
q.push(u);
visit[u] = true;
int node = -1;
while(!q.empty()){
int curr = q.front();
q.pop();
node = curr;
for(auto & v:adj[curr]){
if (!visit[v]){
visit[v] = true;
parent[v] = curr;
q.push(v);
}
}
}
return node;
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if(n == 1) return {0};
vector<vector<int>> adj(n);
for (auto & edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<int> parent(n, -1);
int x = findLongsNode(0,parent,adj);
int y = findLongsNode(x,parent,adj);
vector<int> path;
parent[x] = -1;
while(y != -1){
path.push_back(y);
y = parent[y];
}
int m = path.size();
if (m % 2 == 0) {
return {path[m / 2 - 1], path[m / 2]};
} else {
return {path[m / 2]};
}
}
};
313. 超级丑数
链接: 超级丑数
难度： 中等
题目：
运行示例：
思路：
这道题与之前的丑数 II类似，只不过是将之前的枚举变为循环遍历而已。
代码：
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<long> ans(n,INT_MAX);
ans[0] = 1;
vector<int> tmp(primes.size());
int count = 1;
while(count < n){
vector<long> res(primes.size());
for(int i = 0; i < primes.size(); i++){
res[i] = ans[tmp[i]] * primes[i];
ans[count] = min(ans[count],res[i]);
}
for(int i = 0; i < primes.size(); i++){
if(res[i] == ans[count]){
tmp[i]++;
}
}
count++;
}
return ans[n-1];
}
};
212. 单词搜索 II
链接: 单词搜索 II
难度： 困难
题目：
运行示例：
思路：
这道题我原本以为就是对每个单词进行深度优先遍历即可，但是时间超过了，看了官方题解才知道，我们需要防止多次遍历重复的内容，所以我们需要建立前缀树，保存哪些已经出现过的部分，只对没有出现的部分进行深度优先遍历即可。
代码：
class Solution {
public:
struct TrieNode {
string word;
unordered_map<char,TrieNode *> children;
TrieNode() {
this->word = "";
}
};
void insertTrie(TrieNode*root, string &word){
TrieNode*node = root;
for(auto c : word){
if(!node->children.count(c)){
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->word = word;
}
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool dfs(int start1, int start2,vector<vector<char>>& board,TrieNode *root,set<string> &res)
{
char ch = board[start1][start2];
if(!root->children.count(ch)) return false;
root = root->children[ch];
if (root->word.size() > 0) {
res.insert(root->word);
}
board[start1][start2] = '#';
for(int i = 0; i < 4; i++)
{
int nstart1 = start1+ directions[i][0];
int nstart2 = start2 +directions[i][1];
if(nstart1>=0 && nstart1<board.size() && nstart2>=0 && nstart2<board[0].size())
{
if(board[nstart1][nstart2] != '#')
{
dfs(nstart1,nstart2,board,root,res);
}
}
}
board[start1][start2] = ch;
return false;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode * root = new TrieNode();
set<string>res;
vector<string> ans;
for (auto & word: words){
insertTrie(root,word);
}
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
dfs(i, j,board,root,res);
}
}
for (auto & word: res) {
ans.push_back(word);
}
return ans;
}
};
