今天试了下上次的周赛，感觉只能写出两题。
1. 组合
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
说好的用回溯慢呢，为什么只有我这么慢orz。
研究了下，主要问题在暂存的数组上。我每次都建一个新数组暂存结果，浪费了很多性能。而答案只使用一个数组暂存结果，在每次处理后用pop撤销刚才的处理，所以更节省性能。
另外主函数里没必要手动调用第一轮。
最后，我写的时候意识到了有些调用是不必要的，因为剩下的元素个数不足以凑一个elem了，但我的处理不太合适，随想录给出了正确的“剪枝”方法。即 i<=n-(k-size)+1 。优化这一步后，用时超过了98%。
代码
#include <vector>
using std::vector;
vector<vector<int>> res;
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
res.clear();
for (int i=1;i<=n-k+1;++i) {
vector<int> v;
backtracking(v,i,k,0,n);
}
return res;
}
void backtracking(vector<int> v,int next,int k,int deep,int n) {
v.push_back(next);
++deep;
if (deep==k) {
res.push_back(v);
return;
}
for (int i=next+1;i<=n;++i) {
backtracking(v,i,k,deep,n);
}
}
};优化后
#include <vector>
using std::vector;
class Solution {
private:
vector<vector<int>> res;
vector<int> v;
void backtracking(int k,int start,int n) {
if (v.size()==k) {
res.push_back(v);
return;
}
for (int i=start;i<=n;++i) {
v.push_back(i);
backtracking(k,i+1,n);
v.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
res.clear();
v.clear();
backtracking(k,1,n);
return res;
}
};2. 组合总和 III
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
时间超过100%，空间超过60%，真是意外惊喜。
总体思路跟组合是一样的，只不过固定了可用的数字范围，并且在将elem加入res集之前加个判断，看看sum是否等于目标n。
剪枝操作还可以优化下，当sum大于目标值的时候就可以return了，再地跪下去没有意义。
代码
#include <vector>
using std::vector;
class Solution {
private:
vector<vector<int>> res;
vector<int> v;
int sum=0;
void backtracking(int start,int k,int n) {
if (v.size()==k) {
if (sum==n) res.push_back(v);
return;
}
for (int i=start;i<=9-(k-v.size())+1;++i) {
v.push_back(i);
sum+=i;
backtracking(i+1,k,n);
v.pop_back();
sum-=i;
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
res.clear();
v.clear();
backtracking(1,k,n);
return res;
}
};3. 电话号码的字母组合
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
时间超过100%，空间超过53.77%。
终止条件是字符串path长度已经等于数字串长度，那就直接返回。
否则继续到下一层去遍历。
每一层都是从0开始的，才能求出所有组合。
我用一个二维数组存储数字和字符的对应关系。这里要注意转换，字符比数字要大48。比如字符的2，转成int是50，所以要减个48才能用。
回溯函数参数里的start代表的是每个数字所对应字符的顺序，递归深度本身是给定数字串的长度。这点要分清楚，所以每次进循环是从i=0开始，而不是start+1。
随想录用一个index去记录遍历的深度，但其实可以省掉这个量。因为如果当前path长度小于数字串长度，那么当前path长度就是当前要遍历的数字串中数字的下标！比如“23”这个串，我们刚遍历到某个'2'对应的字母，当前path长度1，所以下一步要遍历“23”中下标1的数组所对应的字母！当然，这样写的话代码稍微难懂一点。
代码
#include <vector>
#include <string>
using std::vector;
using std::string;
class Solution {
private:
const vector<vector<int>> m={{},{},{97,98,99},{100,101,102},{103,104,105},{106,107,108},{109,110,111},{112,113,114,115},{116,117,118},{119,120,121,122}};
vector<string> res;
string path;
void backtracking(const string& digits) {
if (path.size()==digits.size()) {
res.push_back(path);
return;
}
for (int i=0;i<m[int(digits[path.size()])-48].size();++i) {
path.push_back(char(m[int(digits[path.size()])-48][i]));
backtracking(digits);
path.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
res.clear();
path="";
if (digits=="") return res;
backtracking(digits);
return res;
}
};4. 最大子数组和
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
之前贪心法做过一次，这次要求用dp做。
核心还是状态转移方程的确定。每次增加一个元素，总是做一个选择：累加还是重置。在累加和重置之间选最大的即可。
代码
#include <vector>
#include <algorithm>
using std::vector;
using std::max;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 贪心算法
// int res=INT_MIN,count=0;
// for (int i=0;i<nums.size();++i) {
// count+=nums[i];
// if (count >res) res=count;
// if (count <=0) count =0;
// }
// return res;
// dp
int res=nums[0];
vector<int> dp(nums.size(),INT_MIN);
dp[0]=nums[0];
for (int i=1;i<nums.size();++i) {
dp[i]=max(dp[i-1]+nums[i],nums[i]);
res=max(res,dp[i]);
}
return res;
}
};5. 判断子序列
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
直接简单模拟，可以在O(n)时间内完成。但本题放在dp类里，可以用dp解。
代码
#include <vector>
#include <string>
using std::vector;
using std::string;
class Solution {
public:
bool isSubsequence(string s, string t) {
// 简单模拟
if (s=="") return true;
if (s!=""&&t=="") return false;
int i=0;
for (int j=0;j<t.size();++j) {
if (t[j]==s[i]&&i==s.size()-1) return true;
else if (t[j]==s[i]) ++i;
}
return false;
}
};6. 对数组执行操作
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
就硬写。虽然vector的动态扩展能力非常差。
代码
#include <vector>
#include <list>
using std::list;
using std::vector;
class Solution {
public:
vector<int> applyOperations(vector<int>& nums) {
for (int i=0;i<nums.size()-1;++i) {
if (nums[i]==nums[i+1]) {
nums[i]*=2;
nums[i+1]=0;
}
}
int count=0;
for (vector<int>::iterator iter=nums.begin();iter!=nums.end();) {
if (*iter==0) {
nums.erase(iter);
++count;
}
else ++iter;
}
for (int i=0;i<count;++i) nums.push_back(0);
return nums;
}
};7. 长度为 K 子数组中的最大和
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
被折磨了……
老想着赶紧开始写代码，结果细节部分总出错。一开始以为是不连续子序列。
还是要先想清楚。
最后的代码性能也不太行。但周赛感觉能做出来就算赢，性能不考虑了。
代码
#include <vector>
#include <map>
#include <algorithm>
using std::vector;
using std::map;
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
long long res=0;
long long temp=0;
int count=0;
vector<int> last(100005,-k);
for (int i=0;i<nums.size();++i) {
if (last[nums[i]]!=i&&last[nums[i]]>i-k) {
int newPos=last[nums[i]]+1;
last[nums[i]]=i;
i=newPos;
temp=0;
count=0;
} else last[nums[i]]=i;
temp+=nums[i];
++count;
if (count==k) {
res=temp>res?temp:res;
temp-=nums[i-k+1];
--count;
}
}
return res;
}
};8. 不同的子序列
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我自己的思路是用回溯法列出所有等长子序列，再计算相等的串数。显然时间复杂度比较感人，逻辑是没问题，但有用例超时。
答案用dp做，逻辑确实有点难懂。
代码
#include <vector>
#include <string>
using std::vector;
using std::string;
class Solution {
// private:
// vector<string> permutation;
// string path;
// void backtracking(const string&s,int len,int start) {
// if (path.size()==len) {
// permutation.push_back(path);
// return;
// }
// for (int i=start;i<=s.size()-(len-path.size())+1;++i) {
// path.push_back(s[i]);
// backtracking(s,len,i+1);
// path.pop_back();
// }
// }
public:
int numDistinct(string s, string t) {
// permutation.clear();
// path="";
// backtracking(s,t.size(),0);
// int res=0;
// for (int i=0;i<permutation.size();++i) {
// if (permutation[i]==t) ++res;
// }
// return res;
vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1,0));
dp[0][0]=1;
for (int i=0;i<=s.size();++i) dp[i][0]=1;
for (int i=1;i<=s.size();++i) {
for (int j=1;j<=t.size();++j) {
if (s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
else dp[i][j]=dp[i-1][j];
}
}
return dp[s.size()][t.size()];
}
};9. 两个字符串的删除操作
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
说实话，做这题没思考太多，大多是直觉和经验写出来的代码……
代码
#include <vector>
#include <string>
using std::vector;
using std::string;
using std::min;
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
for (int i=1;i<=word1.size();++i) dp[i][0]=i;
for (int j=1;j<=word2.size();++j) dp[0][j]=j;
for (int i=1;i<=word1.size();++i) {
for (int j=1;j<=word2.size();++j) {
if (word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
else {
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
dp[i][j]=min(dp[i-1][j-1]+2,dp[i][j]);
}
}
}
return dp[word1.size()][word2.size()];
}
};10. 编辑距离
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
感觉两个字符串操作的dp基本有公式了。
代码
#include <vector>
#include <string>
using std::vector;
using std::string;
using std::min;
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
for (int i=1;i<=word1.size();++i) dp[i][0]=i;
for (int j=1;j<=word2.size();++j) dp[0][j]=j;
for (int i=1;i<=word1.size();++i) {
for (int j=1;j<=word2.size();++j) {
if (word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
else {
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
}
}
return dp[word1.size()][word2.size()];
}
};
Comments NOTHING