C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]

简介: C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]

说明

此题相对简单,所以代码在课程视频中。当时忘记收集亲密度的代码了,以后一定注意。

最大亲密度

有若干包饼干,每包饼干的数量记录在数组nums中,比如:{4,1,7,5} ,分配给若干(如:3)小朋友。

每种分配方案的亲密度:任意两个小朋友饼干数的差的绝对值的最小值

求所有分配方案中的最大亲密度。

分配方案{1,7,5}的亲密度=min(7-1,5-1,7-5}=2

分配方案{4,7,5}的亲密度=min(7-4,5-4,7-5}=1

分配方案{4,1,5}的亲密度=min(4-1,5-4,5-1}=1

分配方案{4,1,7}的亲密度=min(4-1,7-4,7-1)=3

解决思路

先按升序排序

完成函数is,判断是否存在方案能够满足亲密只大于等于iQinMi。

因为要找最大值,所以中值符合的时候,抛弃左边。中值跟随右边,用左开右闭。

完全 平方数(PerfectSquare)

判断正整数y是否是完全 平方数。如果能找到正整数x,使得x*x==y,则y是平方数。

思路

条件

处理

x*x>y

丢弃右半部分

x*x==y

y是完全 平方数

x*x<y

丢弃左半部分

x的取值范围是[1,y],我们用左闭右开空间,就是[1,y+1)。

注意:计算过程要注意溢出。

扩展:如果y是自然数呢?y可以为0。

排列箱子

有n个箱子,求可以排列多少行(包括不完整行)。第一行1个箱子,第二行2个箱子...第i行i个箱子。注意:最后一行可能没满,除最后一行外其他行全满。

解题思路

m行排满,共有maxN= m*(1+m)/2个箱子。

m行只排一个,共有minN = maxN-m+1个箱子。

如果n小于minN,则抛弃右边;

如果n大于maxN,则抛弃左边。

边界[1,n],左闭右开空间是[1,n+1)

扩展

如果求完整的行,最后一行如果没满,则忽略。

解法一:

则判断m对应的maxN是不是等于n。如果是,返回m;不是,返回m-1。

解法二:

如果maxN 小于等于n,则返回ture,如果有多个,则返回索引最大的一个。

条件

处理

maxN < n

抛弃左边

maxN ==n

抛弃左边

maxN > n

抛弃右边

用左闭右开区间。[1,n+1)

第一步代码

// PerfectSquare.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
bool IsPerfectSquare(int y )
{
}
int main()
{
    std::vector<int> v;
    for (int i = 1; i < 1000; i++)
    {
        if (IsPerfectSquare(i))
        {
            v.emplace_back(i);
        }
    }
    for (const auto& n : v)
    {
        std::cout << n << " ";
    }
}

第二步代码

#include <iostream>
#include <vector>
bool IsPerfectSquare(int y )
{
    int left = 1, right = y + 1;
    while (right - left > 1)
    {
        int x = left + (right - left) / 2;
        if (x * x == y)
        {
            return true;
        }
        else if (x * x > y)
        {
            right = x;
        }
        else
        {
            left = x;
        }
    }
    return left * left == y;
}
int main()
{
    std::vector<int> v;
    for (int i = 1; i < 1000; i++)
    {
        if (IsPerfectSquare(i))
        {
            v.emplace_back(i);
        }
    }
    for (const auto& n : v)
    {
        std::cout << n << " ";
    }
}

 

其它

视频课程

如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。

https://edu.csdn.net/course/detail/38771

我的其它课程

https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17 或Win10 VS2022 Ck++17

相关下载

算法精讲《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

目录
打赏
0
0
1
0
36
分享
相关文章
|
1月前
|
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
二分查找的基本思想是:每次比较中间元素与目标元素的大小,如果中间元素等于目标元素,则查找成功;顺序表是线性表的一种存储方式,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理存储位置上也相邻。第1次比较:查找范围R[0...10],比较元素R[5]:25。第1次比较:查找范围R[0...10],比较元素R[5]:25。第2次比较:查找范围R[0..4],比较元素R[2]:10。第3次比较:查找范围R[3...4],比较元素R[3]:15。,其中是顺序表中元素的个数。
136 68
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
43 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
53 11
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
51 19
|
1月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
68 19
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
57 15
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
50 13
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等