A.速算机器人

解题思路：
模拟。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int calculate(string s) {
        int x =1,y=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='A'){
                x = 2*x+y;
            }else{
                y = 2*y+x;
            }
        }
        return x+y;
    }
};

B.早餐组合

解题思路：
二分。对drinks进行从小到大排序，遍历staple数组中每个元素，二分查找余额 x - staple[i] 的位置，即找出有多少drink可以与之搭配。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef long long ll;
const ll mod = 1e9+7;
class Solution {
public:
    int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) {
        ll ans=0;
        sort(staple.begin(),staple.end());
        sort(drinks.begin(),drinks.end());
        for(int i=0;i<staple.size();i++){
            int t = upper_bound(drinks.begin(),drinks.end(),x-staple[i]) - drinks.begin();
            ans = (ans + t)%mod;
        }
        return ans;
    }
};

C.秋叶收藏集

解题思路：
动态规划。dp[i] [0] 表示第i个元素为第一段r需要调整的次数，dp[i] [1] 表示第i个元素为第一段y需要调整的次数，dp[i] [2] 表示第i个元素为第二段r需要调整的次数。

  • dp[i] [0] = dp[i-1] [0] + leaves[i] == ‘y’
  • dp[i] [1] = min(dp[i-1] [0], dp[i-1] [1]) + leaves[i] == ‘r’
  • dp[i] [2] = min(dp[i-1] [1], dp[i-1] [2]) + leaves[i] == ‘y’

代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define mmin(x,y) (x)<(y)?(x):(y)
class Solution {
public:
    int minimumOperations(string leaves) {
        int n = leaves.size();
        vector<vector<int>> dp(n,vector<int>(3,0x3f3f3f3f));
        if(leaves[0] == 'y')    dp[0][0] = 1;
        else dp[0][0] = 0;
        for(int i=1;i<n;i++){
            if(leaves[i] == 'y'){
                dp[i][0] = dp[i-1][0]+1;
                dp[i][1] = min(dp[i-1][0],dp[i-1][1]);
                dp[i][2] = min(dp[i-1][1],dp[i-1][2])+1;
            }else{
                dp[i][0] = dp[i-1][0] ;
                dp[i][1] = min(dp[i-1][0],dp[i-1][1]) +1;
                dp[i][2] = min(dp[i-1][1],dp[i-1][2]);
            }
        }
        return dp[n-1][2];
    }
};

D.快速公交

解题思路：

递归。对于位置n，遍历每一个jump，n一定是从最近的前后两个jump的倍数得来。如示例1：ans[31] =ans[30] + inc or ans[31] = ans[36] - 5 *dec, 其中 ans[30] = ans[5] + cost , ans[36] = ans[6] + cost;从所有可能得到n的方式中取一个最小值。

需要注意，取模要在最后取，否则会改变ans的结果，并且需要map进行记忆化防止多次重复计算。

代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define mmin(x,y) (x)<(y)?(x):(y)
typedef long long ll;
const ll  mod = 1e9+7;
class Solution {
public:
    unordered_map<ll,ll> ans;
    ll in,de;
    vector<int> ju,co;
    int busRapidTransit(int target, int inc, int dec, vector<int>& jump, vector<int>& cost) {
        in = inc; de = dec; ju = jump; co = cost;
        return minCost(target)%mod;
    }
    ll minCost(ll n){
        if(n==0)  return 0;
        if(ans.count(n))    return ans[n];
        ll res = in * n;
        for(int i=0;i<ju.size();i++){
            ll j = ju[i],c = co[i];
            res = mmin(res,(minCost(n/j) +c+(n%j)*in));
            if(n>1 && n%j) res = mmin(res,(minCost(n/j+1) +c +(j-n%j)*de ));
        }
        ans[n] = res;
        return res;
    }
};

做题情况：
AC 三题
排名：324 / 3244
总结反思：
现场只A了三题，第三题多次Wa暴露出动态规划算法的不熟练，第四题卡在了mod上。