2023

2023

12月往前的应该就不会补题解了,大概有时间会往前一直补到12/1的题解

12/25

1276. 不浪费原料的汉堡制作方案

题目分析：

数学题，解二元一次方程即可
具体过程有$$\left { \begin{array}{c}4x+2y=tomatoSlices\x+y=cheeseSlices \end{array}\right.$$
解得$$\left { \begin{array}{c}y=(4*cheeseSlices-tomatoSlices)/2\x=cheeseSlices-y \end{array}\right.$$
另外，我们还需要判断y是否为整数，否则没法刚好配完

Rust代码

impl Solution {
    pub fn num_of_burgers(t: i32, c: i32) -> Vec<i32> {
        if t >= 2 * c && (t - 2 * c) % 2 == 0 && 4 * c >= t && (4 * c - t) % 2 == 0 { vec![(t - 2 * c) / 2, (4 * c - t) / 2] } else { vec![] }
    }
}

C++代码

class Solution {
public:
    vector<int> numOfBurgers(int t, int c) {
        return (4 * c - t) % 2 || (t - 2 * c) / 2 < 0 || (4 * c - t) / 2 < 0 ? vector<int>{} : vector<int>{(t - 2 * c) / 2, (4 * c - t) / 2};
    }
};

12/26

https://leetcode.cn/problems/maximum-students-taking-exam/?envType=daily-question&envId=2023-12-27

困难的一道困难题，暂时没有敲出代码，题解里有两种思路，动态规划的代码相对简短，但是时间复杂度到了 $O(2^n)$ ，这里暂时贴出LightT大佬的将原问题看成二分图最大独立集的思路，大概是到寒假有时间补上代码。
动态规划思路：

每次计算第 i 行取 j 个座位时，前 i 行的最大值
采用位运算减少判断次数：
1. 首先假设第 i 行的状态是010010 ,我们将其记为 j
2. 将其做左移|右移运算后，得到 101101 ，其中1的位置不能坐人,这个座位状态我们将其记为 t
3. 那么 $$dp(i,j)=\max_{s\subseteq j}\lbrace dp(i-1,t)+|s|\rbrace$$
最后得到前 n 行的最大值

最大二分独立集思路：

同一列上的人座位可以随便坐
奇数列向源节点 $s$ 连边，偶数列向汇点 $t$ 连边
冲突的奇偶列再连边
算出最大流(即能抄到答案的座位匹配最大数)
计算：所有可坐人的座位-最大流（得到的就是不能互相抄答案的最大匹配数

12/27

2660. 保龄球游戏的获胜者

题目分析：

模拟计算出总分即可
对于每个计算：
一次遍历，同时判断前两个是否包含 10 ，如果包含，则当前值 *2

Rust代码

impl Solution {
    pub fn is_winner(player1: Vec<i32>, player2: Vec<i32>) -> i32 {
        let sore_sum = |player: &Vec<i32>| -> i32 {
            (0..player.len()).fold(0, |x, i| { //求和
                (x + player[i] * (if i > 0 && player[i - 1] == 10 || i > 1 && player[i - 2] == 10 { 2 } else { 1 })) //当前两个中存在==10时 *2
            })
        };
        match sore_sum(&player1).cmp(&sore_sum(&player2)) {
            std::cmp::Ordering::Equal => 0, //相等返回0
            std::cmp::Ordering::Greater => 1, //player1胜
            std::cmp::Ordering::Less => 2, //player2胜
        }
    }
}

C++代码

class Solution {
public:
    int isWinner(vector<int>& player1, vector<int>& player2) {
        auto f = [](vector<int>& player) { //lambda表达式
            int s = 0;
            for (int i = 0, n = player.size(); i < n; ++i) {
                int k = (i && player[i - 1] == 10) || (i > 1 && player[i - 2] == 10) ? 2 : 1; //判断是否需要 *2
                s += k * player[i];
            }
            return s;
        };
        int a = f(player1), b = f(player2); //计算
        return a > b ? 1 : (b > a ? 2 : 0);
    }
};

持续更新ing……

526互联

Leetcode每日一题

2023

12/25

12/26

12/27