C++每日一练(20230421)网站首页 技术交流

C/C++每日一练(20230421)

Hann Yang 2023-06-04 20:00:02

简介C/C++每日一练(20230421)

1. 位1的个数 🌟

3. 俄罗斯套娃信封问题 🌟🌟🌟

1. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

输入必须是长度为 32 的 二进制串 。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

出处：

https://edu.csdn.net/practice/26143233

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int count = 0;
        uint32_t res = 1;
        for (int i = 0; i < 32; i++)
        {
            if (res & n)
            {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
};
int main()
{
	Solution s;
    uint32_t n = 0b00000000000000000000000000001011;
	cout << s.hammingWeight(n) << endl;
    n = 0b00000000000000000000000010000000;
	cout << s.hammingWeight(n) << endl;
    n = 0b11111111111111111111111111111101;
	cout << s.hammingWeight(n) << endl;

	return 0;
}

输出：

3
1
31

代码2： bitset

C++11 用bitset.count()方法直接计数

int hammingWeight(uint32_t n)
{
bitset<32> bitN(n);
return bitN.count();
}

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
    	bitset<32> bitN(n);
        return bitN.count();
    }
};
int main()
{
	Solution s;
    uint32_t n = 0b00000000000000000000000000001011;
	cout << s.hammingWeight(n) << endl;
    n = 0b00000000000000000000000010000000;
	cout << s.hammingWeight(n) << endl;
    n = 0b11111111111111111111111111111101;
	cout << s.hammingWeight(n) << endl;

	return 0;
}

2. 递归和非递归求和

编写一个递归函数和一个非递归函数，分别实现求1+2+3+...+n

出处：

https://edu.csdn.net/practice/26143234

代码：

#include <stdio.h>
int sum(int n)
{
    if(n == 1)
        return 1;
    else
        return n + sum(n-1);
}
int sum_2(int n)
{
    int ss = 0;
    for (int i = 1; i <=n;i++)
    {
        ss += i; 
    }
    return ss;
}
int main()
{
    int n;
    printf("请输入n：");
    scanf("%d",&n);
    if(n == 0)
        {
            printf("请输入正整数n");
            return -1;
        }
    int s1 = sum(n);
    int s2 = sum_2(n);
    printf("递归计算=%d;循环计算=%d
",s1,s2);
    return 0;
}

输出：

略

3. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104

出处：

https://edu.csdn.net/practice/26143235

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), comp);
        vector<int> dp(envelopes.size(), 1);
        for (int i = 0; i < (int)envelopes.size(); ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (envelopes[i][1] > envelopes[j][1])
                    dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
            }
        }
        int res = 0;
        for (int i = 0; i < (int)dp.size(); ++i)
            res = res > dp[i] ? res : dp[i];
        return res;
    }
    static bool comp(const vector<int> &a, const vector<int> &b)
    {
        if (a[0] < b[0])
            return true;
        else if (a[0] > b[0])
            return false;
        else
        {
            if (a[1] > b[1])
                return true;
            else
                return false;
        }
    }
};

int main()
{
	Solution s;
    vector<vector<int>> envelopes = {{5,4},{6,4},{6,7},{2,3}};
	cout << s.maxEnvelopes(envelopes) << endl;
    envelopes = {{1,1},{1,1},{1,1}};
	cout << s.maxEnvelopes(envelopes) << endl;

	return 0;
}

输出：

3
1