C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题

简介: C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题

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\n",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


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
6月前
|
IDE 测试技术 开发工具
Poco新增对cocos c++游戏的支持
Poco新增对cocos c++游戏的支持
汉诺塔问题(递归)/梵塔问题c++
汉诺塔问题(递归)/梵塔问题c++
|
6月前
|
设计模式 中间件 程序员
【C/C++ 奇异递归模板模式 】C++中CRTP模式(Curiously Recurring Template Pattern)的艺术和科学
【C/C++ 奇异递归模板模式 】C++中CRTP模式(Curiously Recurring Template Pattern)的艺术和科学
318 3
|
1月前
|
人工智能 算法 BI
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
|
5月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
1月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
2月前
|
图形学 C++ C#
Unity插件开发全攻略:从零起步教你用C++扩展游戏功能,解锁Unity新玩法的详细步骤与实战技巧大公开
【8月更文挑战第31天】Unity 是一款功能强大的游戏开发引擎,支持多平台发布并拥有丰富的插件生态系统。本文介绍 Unity 插件开发基础,帮助读者从零开始编写自定义插件以扩展其功能。插件通常用 C++ 编写,通过 Mono C# 运行时调用,需在不同平台上编译。文中详细讲解了开发环境搭建、简单插件编写及在 Unity 中调用的方法,包括创建 C# 封装脚本和处理跨平台问题,助力开发者提升游戏开发效率。
165 0
|
5月前
|
C++
C++小练习:猜数游戏
C++小练习:猜数游戏
|
5月前
|
定位技术 C++ Windows
第一人称射击游戏 C++控制台版(未完成)
第一人称射击游戏 C++控制台版(未完成)
第一人称射击游戏 C++控制台版(未完成)
|
5月前
|
存储 人工智能 C++
【PTA】L1-093 猜帽子游戏(C++)
【PTA】L1-093 猜帽子游戏(C++)
94 1