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

这篇具有很好参考价值的文章主要介绍了C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题,c++,c语言,leetcode,位运算,动态规划

目录

1. 位1的个数  🌟

2. 递归和非递归求和  ※

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

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


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/文章来源地址https://www.toymoban.com/news/detail-564709.html

C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题,c++,c语言,leetcode,位运算,动态规划

Golang每日一练 专栏

C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题,c++,c语言,leetcode,位运算,动态规划

Python每日一练 专栏

C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题,c++,c语言,leetcode,位运算,动态规划

C/C++每日一练 专栏

C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题,c++,c语言,leetcode,位运算,动态规划

Java每日一练 专栏

到了这里,关于C/C++每日一练(20230421) 位1的个数、递归和非递归求和、俄罗斯套娃信封问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Golang每日一练(leetDay0065) 位1的个数、词频统计

    目录 191. 位1的个数 Nnumber of 1-bits  🌟 192. 统计词频 Word Frequency  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为

    2024年02月06日
    浏览(65)
  • C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素

    目录 1. 区间和的个数  🌟🌟🌟 2. 二叉搜索树的最近公共祖先  🌟 3. 找最接近元素  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个整数数组  nums  以及两个整数  lower  和  upper  。求数组中,值

    2024年02月04日
    浏览(42)
  • 十大排序算法(中):冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归)

    这篇文章,我们接着来讲剩下的排序算法:冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归) 中心思想: 交换就是指根据序列中的两个元素的比较结果来对换这两个元素在序列中的位置,特点就是:将值较大的元素向序列尾部移动,将值较小的元素向序列

    2024年02月05日
    浏览(57)
  • 排序算法:归并排序(递归和非递归)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录 1.归并排序

    2024年02月07日
    浏览(40)
  • 快速排序算法的递归和非递归

    基本思路 选择一个基准值,将数组划分三个区域,小于基准值的区域位于左侧,等于基准值的区域位于中间,大于基准值的区域位于右侧。将大于和小于区域继续进行分区,周而复始,不断进行分区和交换,直到排序完成 递归 思路: 步骤1: 在当前分区范围[l,r]中随机选中一

    2024年02月09日
    浏览(49)
  • 快速排序递归方法和非递归方法详解

    1.1、快速排序思想(递归) 快速排序(递归)是对数组进行拆解,也就是基于 分治 的思想。这里讨论将数组升序的情况:每次选出一个 枢轴 ,在这部分数据中将小于该枢轴的元素放到枢轴的左边,大于枢轴的元素放到枢轴的右边,然后基于此次枢轴的位置,分成左右两个

    2024年02月08日
    浏览(38)
  • C语言实现八大排序算法(详解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序(递归和非递归)、归并排序(递归和非递归)和计数排序)

    本篇文章使用C语言实现了数据结构中常见的八大排序算法,它们分别是 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序 。在排序算法的实现过程中,每种算法都有其独特的特点和适用场景。插入排序通过逐步构建有序序列来排序,希尔

    2024年01月24日
    浏览(54)
  • ZZULIOJ 1039: n个数求和 (C/C++)

    题目描述  输入一个整数n和n个整数,输出这n个整数的和。 输入  输入有两行:第一行是一个正整数n,第二行是n个整数。 输出  输出一个整数,即n个数的和。输出单独占一行。 样例输入 Copy  3  7 3 2 样例输出 Copy  12 代码

    2024年02月06日
    浏览(54)
  • 排序算法进阶——归并排序【详细图解,递归和非递归】

    在了解归并排序之前让我们先了解一下归并这一算法吧! 归并算法一般应用于合并两个已经有序的序列,使合并后的序列也有序,是一个时间复杂度为O(N)的算法,不过一般要借助两个要排序的序列的元素个数个额外的空间。 一一一一一一一一一一一一一一一一一一一一一

    2024年01月24日
    浏览(45)
  • 排序算法:快速排序(三种排序方式、递归和非递归)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 目录 前言: 1.快速排

    2024年02月09日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包