Leetcode刷题笔记

LCP40 心算挑战

题目

「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

输入：cards = [1,2,8,9], cnt = 3

输出：18

解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

思路和算法

将cards从大到小排序后，先贪心的将前cnt个数字加起来，若此时sum为偶数，直接返回即可。

若此时答案为奇数，有两种方案:

• 在数组后面找到一个最大的奇数与前cnt个数中最小的偶数进行替换；

• 在数组后面找到一个最大的偶数与前cnt个数中最小的奇数进行替换。

两种方案选最大值即可。

代码

class Solution {
public:
    int maxmiumScore(vector<int>& cards, int cnt) {
        sort(cards.begin(), cards.end(), greater<int>());
        int score = 0;
        int ans = 0;
        int odd = 0;
        int even = 0;
        for (int i = 0; i < cnt; ++i) {
        score += cards[i];
        if(cards[i] %2 == 0) even = cards[i];
        else odd = cards[i];
        }
        if(score % 2 == 0){
            return score;
        }
        else{
            for(int j = cnt; j < cards.size(); j++)
            {
            if(cards[j] %2 == 0 && odd) 
                ans = max(ans, score - odd + cards[j]);
            else if (even)
                ans = max(ans, score - even + cards[j]);
            }

        }
        return ans;
    }
};

复杂度分析

时间复杂度：$O(nlogn)$，其中$n$为数组的长度，主要开销在排序。

空间复杂度：$O(1)$。

T258 各位相加

题目

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

输入: num = 38
输出: 2
解释: 各位相加的过程为：
38 –> 3 + 8 –> 11
11 –> 1 + 1 –> 2
由于 2 是一位数，所以返回 2。

进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

思路和算法

https://leetcode.cn/problems/add-digits/solutions/1301157/ge-wei-xiang-jia-by-leetcode-solution-u4kj/

假设整数num的十进制表示有n位，从最低位到最高位依次是$a_0$到$a_{n−1}$，则 num可以写成
$$
\sum_{i=0}^{n-1}a_i \times (10^i-1) + \sum_{i=0}^{n-1}a_i
$$

对于任意非负整数 $i$，$10^i−1$ 都是 9 的倍数。由此可得num与其各位相加的结果模 9 同余。重复计算各位相加的结果直到结果为一位数时，该一位数即为 num 的数根，num 与其数根模 9 同余。由于最终结果取值为0～9，我们可以对num先减去1再取余，最后加上1，这样就能同时处理num是9的倍数（结果为9）和num为0的情况。

代码

class Solution {
public:
    int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
};

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

T3128 直角三角形

题目

给你一个二维 boolean 矩阵 grid 。

请你返回使用 grid 中的 3 个元素可以构建的直角三角形数目，且满足3个元素值都为1。

注意：

• 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]

输出：2

解释：有 2 个直角三角形。

思路和算法

https://leetcode.cn/problems/right-triangles/solutions/2861202/zhi-jiao-san-jiao-xing-by-leetcode-solut-zbz2/

直接枚举三个点判断是否为直角三角形的方法未免过于低效，我们可以固定一个点，然后来统计其他两个点的合法方法数。

考虑枚举两条直角边的交点，然后将「该点所在行的其他点」与「该点所在列的其他点」一一匹配，即可得到所有以该点为直角边交点的所有方案。设 row 为交点所在行 1 的个数，col 为交点所在列 1 的个数，那么它的贡献是 (row−1)×(col−1)，将所有交点的贡献加起来就是答案。

class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> col(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                col[j] += grid[i][j];
            }
        }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            int row = accumulate(grid[i].begin(), grid[i].end(), 0);
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    res += (row - 1) * (col[j] - 1);
                }
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(nm)$，其中$n$是$grid$的行数，$m$是$grid$的列数。

空间复杂度：$O(m)$。