今天第一次参加周赛，结果有点让我羞愧……继续加油吧。
赛前随便写了几个Easy放松，再就是竞赛题四道，今天七题结束。
1. 将有序数组转换为二叉搜索树
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
代码
2. 平衡二叉树
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
代码
3. 路径总和
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
回溯法，时间超过82.9%，空间超过45%。
第一遍写完之后为了一些特例改了三四次。比如targetSum为负的情况，不能随便剪枝。
代码
// struct TreeNode {
// int val;
// TreeNode *left;
// TreeNode *right;
// TreeNode() : val(0), left(nullptr), right(nullptr) {}
// TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
class Solution {
private:
int path;
bool flag=false;
void backtracking(int targetSum,TreeNode* root) {
if (root->left==nullptr&&root->right==nullptr) {
if (path==targetSum) flag=true;
return;
}
if (root->left!=nullptr) {
path+=root->left->val;
backtracking(targetSum,root->left);
path-=root->left->val;
}
if (root->right!=nullptr) {
path+=root->right->val;
backtracking(targetSum,root->right);
path-=root->right->val;
}
}
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root==nullptr) return false;
path=root->val;
flag=false;
backtracking(targetSum,root);
return flag;
}
};4. 温度转换
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
周赛简单题，毋须多言，第一眼看到的时候还想有没有这么简单……
代码
class Solution {
public:
vector<double> convertTemperature(double celsius) {
vector<double> ans(2,0);
ans[0]=celsius+273.15;
ans[1]=celsius*1.80+32.00;
return ans;
}
};5. 最小公倍数为 K 的子数组数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
周赛中等题。第一眼看到就想用DP，然后死磕，然后我的第一次周赛就这么结束了……
事后看评论区，原来暴力解法不会超时。
需要一些数学知识。竞赛中虽然去百度得到了求最小公倍数的公式，但不以为意，以为强行求一定超时。
写两个辅助函数，一个求最小公因子，一个求最小公倍数，后者要调用前者。
然后两层遍历，即每次起点+1，遍历至终点。还要假设在首元素前存在一个元素1。
一旦发现当前元素不满足条件，这一轮遍历跳出。
代码
class Solution {
private:
long long gcd(long long a,long long b) {
if (a<b) {
long long temp=a;
a=b;
b=temp;
}
if (b!=0) {
return gcd(b,a%b);
}
else return a;
}
long long lcm(long long a,long long b) {
return a*b/gcd(a,b);
}
public:
int subarrayLCM(vector<int>& nums, int k) {
int res=0;
for (int i=0;i<nums.size();++i) {
int init=1;
for (int j=i;j<nums.size();++j) {
init=lcm(init,nums[j]);
if (k%init!=0) break;
if (init==k) ++res;
}
}
return res;
}
};6. 逐层排序二叉树所需的最少操作数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
这题我是直接想到了暴力法，取出每一层的所有数组成一个序列，计算交换操作数，加和即可。但我的做法性能不佳，直接超时了。
评论区有一样思路的解法，正常通过。
我的想法是用广度遍历得到每一层所有元素，但答案依然使用深度遍历，记录当前深度，并将每一个元素push到层数对应的二维数组中去，这样比较好理解和实现。dfs函数执行完后，就得到一个二维数组，里面是每一层元素的一维数组。
计算每个数组中需要执行交换的次序，是个经典问题。理解了这题相当于多学了一个经典题目的解法，赚到了。
主程序调用dfs获得含有分层元素的二维数组，再遍历每一个一维数组，调用minOps计算其最小操作数，累加到res上，最后返回。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
vector<vector<int>> vec;
void dfs(TreeNode* root,int d) {
if (root==nullptr) return;
while(vec.size()<=d) vec.push_back(vector<int>());
vec[d].push_back(root->val);
dfs(root->left,d+1);
dfs(root->right,d+1);
}
int minOps(vector<int>& nums) {
vector<int> B=nums;
sort(B.begin(),B.end());
unordered_map<int,int> mp;
for (int i=0;i<nums.size();++i) mp[B[i]]=i;
int res=0;
for (int i=0;i<nums.size();++i) {
while(nums[i]!=B[i]) {
swap(nums[i],nums[mp[nums[i]]]);
++res;
}
}
return res;
}
public:
int minimumOperations(TreeNode* root) {
vec.clear();
dfs(root,0);
int res=0;
for (auto &nums:vec) res+=minOps(nums);
return res;
}
};7. 不重叠回文子字符串的最大数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
竞赛中完全没看这题。
答案使用了DP，但应该说不是单纯DP，而是先使用了中心扩散法去找到以l为起始,r为终止的子串是否为回文串。再使用DP数组f表示到i为止，最大的选取数。状态转移方程有点复杂。
i每前进一位，面对选择，加上这一位还是不加上这一位。在这两个之间选最大的。不加都的话就等于i-1的值。加的话要看条件是否满足。
代码
class Solution {
public:
int maxPalindromes(string s, int k) {
int n=s.size();
vector<vector<bool>> flag(n,vector<bool>(n,false));
for (int i=0;i<n;++i) {
for (int l=i,r=i;l>=0&&r<n&&s[l]==s[r];--l,++r) {
flag[l][r]=true;
}
}
for (int i=0;i<n-1;++i) {
for (int l=i,r=i+1;l>=0&&r<n&&s[l]==s[r];--l,++r) {
flag[l][r]=true;
}
}
vector<int> f(n+1,0);
for (int i=1;i<=n;++i) {
f[i]=f[i-1];
for (int j=i-k;j>=0;--j) {
if (flag[j][i-1]) {
f[i]=max(f[i],f[j]+1);
}
}
}
return f[n];
}
};
Comments NOTHING