2024年2月12日力扣题目训练
2024年2月12日力扣题目训练
2024年2月12日第十九天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的,我会慢慢补回来，争取一天发两篇，把之前的都补上。
575. 分糖果
链接: 分糖果
难度： 简单
题目：
运行示例：
思路：
这道题就是单纯的计数，能吃的糖类型要么是所有的糖类型要么是n/2。
代码：
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
int n = candyType.size();
unordered_map<int,int> res;
int type = 0;
for(int i = 0; i < candyType.size(); i++){
if(res[candyType[i]] == 0){
res[candyType[i]]++;
type++;
}
}
return min(type, n / 2);
}
};
589. N 叉树的前序遍历
链接: N 叉树的前序遍历
难度： 简单
题目：
运行示例：
思路：
这道题就是考察前序遍历，递归即可。也可以迭代，迭代的话需要利用栈，大家可以自己尝试一下。
代码：
class Solution {
public:
void Preorder(Node* root,vector<int>&ans){
if(root == NULL) return;
ans.push_back(root->val);
for(auto c: root->children){
Preorder(c,ans);
}
}
vector<int> preorder(Node* root) {
vector<int> ans;
Preorder(root,ans);
return ans;
}
};
590. N 叉树的后序遍历
链接: N 叉树的后序遍历
难度： 简单
题目：
运行示例：
思路：
这道题就是考察后序遍历，递归即可。也可以迭代，迭代的话会比较麻烦一点，需要注意该节点的所有子树都遍历之后才可以让其出栈。
代码：
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> res;
if (root == nullptr) {
return res;
}
unordered_map<Node *, int> cnt;
stack<Node *> st;
Node * node = root;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
st.emplace(node);
if (node->children.size() > 0) {
cnt[node] = 0;
node = node->children[0];
} else {
node = nullptr;
}
}
node = st.top();
int index = cnt.count(node) ? (cnt[node] + 1) : 0;
if (index < node->children.size()) {
cnt[node] = index;
node = node->children[index];
} else {
res.emplace_back(node->val);
st.pop();
cnt.erase(node);
node = nullptr;
}
}
return res;
}
};
275. H 指数 II
链接: H 指数 II
难度： 中等
题目：
运行示例：
思路：
这道题与上一次274. H 指数类似，这道题已经排序所以我们可以采用二分法。
代码：
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int left = 0,right = n-1;
while(left <= right){
int mid = left + (right - left) / 2;
if(citations[mid] >= n - mid) right = mid - 1;
else left = mid + 1;
}
return n - left;
}
};
279. 完全平方数
链接: 完全平方数
难度： 中等
题目：
运行示例：
思路：
这道题采用动态规划完成，f[i] 表示最少需要多少个数的平方来表示整数 i。状态转移方程：
f[i]=1+minf[i-j*j]
代码：
class Solution {
public:
int numSquares(int n) {
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) {
int minn = INT_MAX;
for (int j = 1; j * j <= i; j++) {
minn = min(minn, f[i - j * j]);
}
f[i] = minn + 1;
}
return f[n];
}
};
132. 分割回文串 II
链接: 分割回文串 II
难度： 困难
题目：
运行示例：
思路：
这道题与之前131. 分割回文串的类似，然后我们需要知道在什么时候进行分割，设 f[i]表示字符串的前缀 s[0…i]的最少分割次数。要想得出 f[i]的值，我们可以考虑枚举 s[0…i]分割出的最后一个回文串，这样我们就可以写出状态转移方程：
f[i]=min0≤j<i{f[j]}+1,其中 s[j+1…i] 是一个回文串
即我们枚举最后一个回文串的起始位置 j+1，保证 s[j+1…i]是一个回文串，那么 f[i]就可以从 f[j] 转移而来，附加 1次额外的分割次数。
代码：
class Solution {
private:
int n;
public:
int minCut(string s) {
n = s.size();
vector<vector<bool>> f(n,vector<bool>(n,true));
for(int i = n -1; i >= 0; i--){
for(int j = i + 1; j < n; j++){
f[i][j] = (s[i] == s[j]) && f[i+1][j-1];
}
}
vector<int>g(n,INT_MAX);
for(int i = 0; i < n; i++){
if(f[0][i]) g[i] = 0;
else{
for(int j = 0; j < i; j++){
if(f[j+1][i])
g[i] = min(g[i],g[j]+1);
}
}
}
return g[n-1];
}
};
