Leetcode 周赛题解 218

2020-12-31 10:10:52 浏览数 (1)

https://leetcode-cn.com/contest/weekly-contest-219/

难度顺序：

Ale Ble Cle D

。

5625. 比赛中的配对次数

「提示：」

1 <= n <= 200

「思路：」

按题意模拟即可。

时间复杂度：

O(log(n))

.

代码语言：javascript复制
class Solution {
public:
    int numberOfMatches(int n) {
        int ans = 0;
        while(n != 1) {
            if(n & 1) {
                ans  = (n - 1) / 2;
                n = n / 2   1;
            } else {
                ans  = n / 2;
                n /= 2;
            }
        }
        return ans;
    }
};

5626. 十-二进制数的最少数目

「提示：」

  • 1 <= n.length <= 10^5
  • n 仅由数字组成
  • n 不含任何前导零并总是表示正整数

「思路：」很明显只要找到数位最大值就可以配出和为

n

。

时间复杂度：

O(n.length)

.

代码语言：javascript复制
class Solution {
public:
    int minPartitions(string n) {
        int num = 0;
        for(int i = 0;i < n.size();i  ) {
            num = max(num,n[i] - '0');
        }
        return num;
    }
};

5627. 石子游戏 VII

「提示：」

  • n == stones.length
  • 2 <= n <= 1000
  • 1 <= stones[i] <= 1000

「思路」

  • 很明显这是一个博弈
DP

，爱丽丝要选择使得差值更大的子状态，鲍勃要选择使得差值更小的子状态。

  • 定义pair<int,int> dp[l][r][0/1]代表选择
[l,r]

之间石头，且当前先手的人为(爱丽丝/鲍勃)，得到最优决策下两人的权值。

  • 子状态就是选择左边的石头或者选择右边的石头：对于状态
dp[l][r][cur]

，设

sum

数组为前缀和，

nex=1-cur

，则 有

dp[l][r][cur]=(dp[l 1][r].second sum[r]-sum[l],dp[l 1][r].first)

或者

dp[l][r][cur]=(dp[l][r-1].second sum[r-1]-sum[l-1],dp[l][r-1].first)
  • 根据先手的人来选择差值最小（最大）的子状态即可。
  • kickstart Round F 2020 Painters‘ Duel 与这题类似。

时间复杂度：

O(n^2)

.

代码语言：javascript复制
class Solution {
public:
    int sum[1005];
    pair<int,int>dp[1005][1005];
    int vis[1005][1005];
    pair<int,int> dfs(int l,int r,int flag) {
        if(l >= r) return {0,0};
        if(vis[l][r]) {
            return dp[l][r];
        }
        pair<int,int>t1 = dfs(l,r - 1,flag ^ 1);
        pair<int,int>t2 = dfs(l   1,r,flag ^ 1);
        t1 = {t1.second   sum[r - 1] - sum[l - 1],t1.first};
        t2 = {t2.second   sum[r] - sum[l],t2.first};
        if(flag) { //增加差值
            if(t1.first - t1.second > t2.first - t2.second) {
                dp[l][r] = t1;
                vis[l][r] = 1;
                return t1;        
            } else {
                dp[l][r] = t2;
                vis[l][r] = 1;
                return t2;
            }
        } else {
            if(t1.second - t1.first > t2.second - t2.first) {
                dp[l][r] = t2;
                vis[l][r] = 1;
                return t2;
            } else {
                dp[l][r] = t1;
                vis[l][r] = 1;
                return t1;
            }
        }
    }
    int stoneGameVII(vector<int>& stones) {
        for(int i = 0;i < stones.size();i  ) {
            int x = stones[i];
            sum[i   1] = sum[i]   x;
        }
        pair<int,int>ans = dfs(1,stones.size(),1);
        return ans.first - ans.second;
    }
};

5245. 堆叠长方体的最大高度

「提示：」

  • n == cuboids.length
  • 1 <= n <= 100
  • 1 <= widthi, lengthi, heighti <= 100

「思路」

  • 由于长方体可以旋转，所以我们将每个长方体扩展为6份，代表其旋转后的长宽高。因为下面的长方体长宽高都大于等于上面的，所以我们将长方体按照体积排序。
  • 定义
dp[i]

为将第

i

个长方体作为最顶上长方体时能得到的最大高度，则有

dp[i]=dp[j] a[i].z，j>i

，

a[i].z

代表第

i

个长方体的高度

  • 但是这样转移可能有问题，就是同一个长方体分为了多份，可能用多次，所以我们要特判掉这种情况，转移的时候如果两个长方体是同一个，就跳过。

时间复杂度：

O(n^2*6)

.

代码语言：javascript复制
const int maxn = 1005;
struct Node {
    int x,y,z;
    int id;
    
}a[maxn];
int cmp(Node x,Node y) {
    return x.x * x.y * x.z < y.x * y.y * y.z;
}
class Solution {
public:
    int dp[1005],cnt = 0;
    int dfs(int now) {
        if(dp[now] != -1) return dp[now];
        int ans = a[now].z;
        for(int i = now   1;i <= cnt;i  ) {
            if(a[now].id == a[i].id) continue;
            if(a[now].x <= a[i].x && a[now].y <= a[i].y && a[now].z <= a[i].z) {
                ans = max(ans,dfs(i)   a[now].z);
            }
        }
        return dp[now] = ans;
    }
    int maxHeight(vector<vector<int>>& cuboids) {
        memset(dp,-1,sizeof(dp));
        for(int i = 0;i < cuboids.size();i  ) {
            a[  cnt] = {cuboids[i][0],cuboids[i][1],cuboids[i][2],i};
            a[  cnt] = {cuboids[i][0],cuboids[i][2],cuboids[i][1],i};
            a[  cnt] = {cuboids[i][1],cuboids[i][0],cuboids[i][2],i};
            a[  cnt] = {cuboids[i][1],cuboids[i][2],cuboids[i][0],i};
            a[  cnt] = {cuboids[i][2],cuboids[i][0],cuboids[i][1],i};
            a[  cnt] = {cuboids[i][2],cuboids[i][1],cuboids[i][0],i};
        }
        sort(a   1,a   1   cnt,cmp);
        int ans = 0;
        for(int i = 1;i <= cnt;i  ) {
            ans = max(ans,dfs(i));
        }
        return ans;
    }
};
dp int

0 人点赞