12点刚过，该睡觉了。
1. 字符串的前缀分数和
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
与前缀树相关，这个东西比较有意思，放后面研究一下。
代码
2. 统计共同度过的日子数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
写三个（准确来说是俩）辅助函数。一个用于计算起止日期间有多少天；一个用于返回两个日期中较大的那个；一个用于返回两个日期中较小的那个。
然后取到达时间中最大的那个，离开时间中最小的那个，作为 起止日期，计算期间天数即可。
代码
class Solution {
private:
const vector<int> dayOfMonth={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 定义a到b有多少天
int totalDay(string a,string b) {
int ans=0;
int sum=0;
int startMonth=(a[0]-'0')*10+(a[1]-'0');
int endMonth=(b[0]-'0')*10+(b[1]-'0');
int startDay=(a[3]-'0')*10+(a[4]-'0');
int endDay=(b[3]-'0')*10+(b[4]-'0');
int startMonthSurplus=startDay-1;
int endMonthSurplus=dayOfMonth[endMonth-1]-endDay;
for (int i=startMonth;i<=endMonth;++i) sum+=dayOfMonth[i-1];
ans = sum-endMonthSurplus-startMonthSurplus;
return ans<0?0:ans;
}
string maxDay(string a,string b) {
if (a[0]-'0'>b[0]-'0') return a;
if (a[0]-'0'==b[0]-'0'&&a[1]-'0'>b[1]-'0') return a;
if (a[0]-'0'==b[0]-'0'&&a[1]-'0'==b[1]-'0'&&a[3]-'0'>b[3]-'0') return a;
if (a[0]-'0'==b[0]-'0'&&a[1]-'0'==b[1]-'0'&&a[3]-'0'==b[3]-'0'&&a[4]-'0'>b[4]-'0') return a;
return b;
}
string minDay(string a,string b) {
if (maxDay(a,b)==a) return b;
else return a;
}
public:
int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
string start=max(arriveAlice,arriveBob);
string end=min(leaveAlice,leaveBob);
return totalDay(start,end);
}
};3. 运动员和训练师的最大匹配数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
排序后逐个匹配即可。这题明显比上一个Easy简单……
代码
class Solution {
public:
int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
int i=0,j=0,p=players.size(),t=trainers.size(),ans=0;
sort(players.begin(),players.end());
sort(trainers.begin(),trainers.end());
while(i<p&&j<t) {
if (players[i]<=trainers[j]) {
++i;++j;++ans;
} else {
++j;
}
}
return ans;
}
};4. 按位或最大的最小子数组长度
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
参考这篇
动态规划，时间复杂度O(n)。或运算是只要有一个1，就变为1。从位的角度考虑，右侧每一个数字都对最大值有某几位1的贡献，我们需要找到最近的那个最远1由谁贡献，则距离可以确定。
代码
class Solution {
public:
vector<int> smallestSubarrays(vector<int>& nums) {
int n=nums.size();
vector<int> ans(n);
vector<int> dp(32,-1);
for (int i=n-1;i>=0;--i) {
int maxLen=1;
for (int j=0;j<32;++j) {
if ((nums[i]>>j)&1==1) dp[j]=i;
if (dp[j]!=-1) maxLen=max(maxLen,dp[j]-i+1);
}
ans[i]=maxLen;
}
return ans;
}
};5. 完成所有交易的初始最少钱数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
参考这篇 ，优雅，实在是太优雅了。
考虑最坏情况，所有亏钱交易先进行，得到一个总的亏钱量。然后考虑两种情况，一个是亏完钱后马上进行一个不亏钱交易，但这个不亏钱交易的cost要最大；一个是最后一个亏钱交易，它的cost最大。就看这两种情况下，哪个最大。
对于最坏情况的分析值得学习。
代码
class Solution {
public:
long long minimumMoney(vector<vector<int>>& transactions) {
long long mx=0;
long long totalLost=0;
int n=transactions.size();
for (int i=0;i<n;++i) {
totalLost+=max(transactions[i][0]-transactions[i][1],0);
mx=max(mx,(long long)min(transactions[i][0],transactions[i][1]));
}
return totalLost+mx;
}
};6. 出现最频繁的偶数元素
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
简单模拟。
用按位与判断奇偶，不知道为什么进不了if……
代码
class Solution {
public:
int mostFrequentEven(vector<int>& nums) {
map<int,int> mp;
for (int i=0;i<nums.size();++i) if (nums[i]%2==0) mp[nums[i]]++;
int maxCnt=INT_MIN;
int ans=-1;
for (auto& elem:mp) {
if (elem.second==maxCnt) ans=elem.first<ans?elem.first:ans;
if (elem.second>maxCnt) {
maxCnt=elem.second;
ans=elem.first;
}
}
return ans;
}
};7. 子字符串的最优划分
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
意外简单，一次遍历即可。
维护一个26元素的数组last，记录当前字母上次出现的下标，如果为-1，则赋当前下标，如果不为-1，说明必须要划分一次，++ans后重置last数组，并且--下标。
代码
class Solution {
public:
int partitionString(string s) {
int n=s.size();
vector<int> last(26,-1);
vector<int> temp(26,-1);
int ans=0;
for (int i=0;i<n;++i) {
if (last[s[i]-'a']==-1) last[s[i]-'a']=i;
else {
ans++;
last=temp;
--i;
}
}
return ans+1;
}
};8. 将区间分为最少组数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
模拟的做法虽然优化了，依然超时。
答案用了小根堆来存储每个组的最大结束时间。这块内容还需要复习。
代码
class Solution {
public:
static bool cmp(vector<int>& a,vector<int>& b) {
if (a[0]<b[0]) return true;
else if (a[0]==b[0]) return a[1]<b[1];
else return false;
}
int minGroups(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int n=intervals.size();
priority_queue<int,vector<int>,greater<int>> pq;
for (auto& elem:intervals) {
if (!pq.empty()&&elem[0]>pq.top()) pq.pop();
pq.push(elem[1]);
}
return pq.size();
}
};9. 检查相同字母间的距离
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
用一个last数组记录字母上次出现位置即可。
代码
class Solution {
public:
bool checkDistances(string s, vector<int>& distance) {
vector<int> last(26,-1);
int n=s.size();
for (int i=0;i<n;++i) {
if (last[s[i]-'a']==-1) last[s[i]-'a']=i;
else {
if (i-last[s[i]-'a']-1!=distance[s[i]-'a']) return false;
}
}
return true;
}
};10. 恰好移动 k 步到达某一位置的方法数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我的想法是转换成求大数阶乘问题。
要从start走到end，无论以什么顺序走，必有abs(end-start)步是确定要走的。那么剩下m=k-abs(end-start)步。如果m为奇，返回0。那么剩下的事情，就是(m/2+abs(end-start))步往一个方向走，(m/2)步往另一个方向走，共有多少种走法，是一个排列组合问题。求组合数可以利用公式，n的平方复杂度。
求组合数参考这篇
代码
class Solution {
const int MOD = 1000000007;
public:
int numberOfWays(int startPos, int endPos, int K) {
int d = abs(startPos - endPos);
if ((d + K) % 2 == 1 || d > K) return 0;
// 递推求组合数
vector<vector<long long>> f;
f.resize(K + 1, vector<long long>(K + 1));
for (int i = 0; i <= K; i++) {
f[i][0] = 1;
for (int j = 1; j <= i; j++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
}
return f[K][(d + K) / 2];
}
};
Comments NOTHING