首页 > 编程语言 >天天学编程Day10

天天学编程Day10

时间:2024-11-08 19:50:42浏览次数:3  
标签:std int 编程 mid 天天 Day10 内存 ptr 模板

今日两道编程题

LCR 140. 训练计划 II

class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        //我选择使用双指针方法 定义两个位置在头结点的指针
        //先让快指针先走cnt个位置 然后让两个指针同时走
        //当快指针走到空节点后 慢指针所在的位置就在题目想要的地方
        ListNode* p1,*p2;
        p1 = p2 =head;
        while(cnt--)
        {
            p1=p1->next;
        }
        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2;
    }
};

69. x 的平方根

二分查找概述:

        二分查找通过不断折半查找区间,来快速缩小目标值的位置。在计算平方根时,目的是找到最大的整数 y,使得 y * y <= x

问题背景:

        我们要在区间 [0, x] 上进行二分查找,以找到整数平方根。在每一步中,我们计算中点 mid,然后检查 mid * midx 的关系,从而决定如何调整搜索区间。

class Solution {
public:
    int mySqrt(int x) {
        // 初始化搜索区间,i 为下界,j 为上界
        int i = 0;
        
        // 设置上界为 46341 或 x 中较小的值 + 1。46341 是 2^31 的平方根,32 位整数范围内的最大平方根
        int j = min(46341, x) + 1;

        // 开始二分查找
        while (i <= j) {
            // 计算中点 mid
            int mid = (i + j) / 2;

            // 为了避免溢出,将 mid 转换为 long long 类型计算 mid * mid
            // 如果 mid 的平方大于 x,则 mid 太大,缩小搜索区间
            if ((long long)mid * mid > x) {
                j = mid - 1; // 更新上界,尝试更小的值
            } else {
                // 如果 mid 的平方小于等于 x,则说明 mid 是候选值
                i = mid + 1; // 更新下界,尝试更大的值
            }
        }
        
        // 当循环结束时,i 就是最小的使得 i * i > x 的值,返回 i-1 即为最大整数平方根
        return i - 1;
    }
};

1. 如果 mid * mid == x

  • 如果 mid * mid 恰好等于 x,我们已经找到了 x 的平方根,应该直接返回 mid

2. 如果 mid * mid < x

  • 这种情况下,mid 还太小,我们需要更大的数来找到平方根。也就是说,当前的 mid 可能是平方根的一个候选值,但我们还可以尝试更大的值。为了继续逼近平方根,我们需要调整 i,让其变得更大。
  • 由于 mid 是小于 sqrt(x) 的,所以我们可以将下界 i 更新为 mid + 1,以便在下次迭代中尝试更大的数。

3. 如果 mid * mid > x

  • 如果 mid * mid 大于 x,说明 mid 的平方大于 x,而我们只关心 mid * mid <= x 的情况。也就是说,当前的 mid 已经太大了,不能作为平方根。为了缩小搜索区间,应该将上界 j 更新为 mid - 1,使搜索区间变小,继续尝试更小的数。

为什么 i = mid + 1j = mid - 1 必须这样更新:

  • i = mid + 1:因为我们已经知道 mid 太小,mid 是潜在的平方根,但它还不够大,所以我们必须让搜索区间的下界更大,继续寻找可能的平方根值。

  • j = mid - 1:因为 mid 的平方大于 x,我们排除了 mid 作为有效的平方根,所以我们缩小上界,尝试一个更小的 mid

示例说明:

        假设我们要计算 x = 10 的平方根,区间是 [0, 10],并且我们使用二分查找。

  1. 初始值i = 0, j = 10

  2. 第一次循环

    • 计算 mid = (0 + 10) / 2 = 5
    • mid * mid = 25 > 10,所以 mid 太大了。
    • 更新 j = mid - 1 = 4
  3. 第二次循环

    • 计算 mid = (0 + 4) / 2 = 2
    • mid * mid = 4 < 10,所以 mid 还太小了。
    • 更新 i = mid + 1 = 3
  4. 第三次循环

    • 计算 mid = (3 + 4) / 2 = 3
    • mid * mid = 9 < 10,还是太小了。
    • 更新 i = mid + 1 = 4
  5. 第四次循环

    • 计算 mid = (4 + 4) / 2 = 4
    • mid * mid = 16 > 10,太大了。
    • 更新 j = mid - 1 = 3

现在,ij 都指向 4,且 i > j,循环结束。此时,j = 3 就是我们想要的平方根的整数部分。

总结:

  • i = mid + 1 是因为当 mid * mid < x 时,我们要寻找更大的数,因此下界要向右移动。
  • j = mid - 1 是因为当 mid * mid > x 时,我们要寻找更小的数,因此上界要向左移动。

newmalloc 申请空间时,超出可申请的大小会引发异常

在 C++ 中,newmalloc 都用于动态内存分配,但它们的行为和异常处理略有不同。

可申请的最大内存大小

  • newmalloc 的内存限制:

    • 允许申请的内存大小受限于系统的总可用内存、操作系统限制以及进程内存空间的大小(通常由操作系统的架构决定,如 32 位或 64 位系统)。
    • 在 32 位系统上:
      • 一个进程的最大地址空间通常为 2GB 或 3GB(在 Windows 中,具体的可用空间取决于操作系统版本和内存分配)。即使 newmalloc 申请的内存小于这个值,也可能因系统资源问题而无法分配成功。
    • 在 64 位系统上:
      • 进程的地址空间理论上非常大,通常可以达到数 TB。但实际上,受限于系统的物理内存、虚拟内存和操作系统的配置,实际能申请的内存可能远小于理论值。
  • mallocnew 失败的情况:

    • mallocnew 无法分配请求的内存时,它们的行为有所不同:
      • malloc: 如果无法分配内存,malloc 返回 NULL
      • new: 如果无法分配内存,new 会抛出一个 std::bad_alloc 异常,除非使用了 nothrow 版本(new(std::nothrow)),此时它会返回 nullptr
如何处理内存分配失败:
  • 使用 new 的时候:
    • 可以捕获 std::bad_alloc 异常:
      try {
          int* ptr = new int[1000000000]; // 尝试分配大内存
      } catch (const std::bad_alloc& e) {
          std::cerr << "Memory allocation failed: " << e.what() << std::endl;
      }
      
  • 使用 malloc 的时候:
    • 如果 malloc 失败,通常需要检查返回值:
      int* ptr = (int*)malloc(sizeof(int) * 1000000000);
      if (ptr == NULL) {
          std::cerr << "Memory allocation failed" << std::endl;
      }
      

C++ 中的循环引用

循环引用是什么:

        循环引用指的是两个或多个对象之间形成了相互引用的情况,形成一个闭环,这种引用关系会导致内存无法正常释放,从而造成内存泄漏。通常,循环引用发生在智能指针、集合等地方。

循环引用的示例:

        假设我们有两个类,AB,并且它们分别持有对方的指针或智能指针:

#include <memory>

class B; // 前向声明

class A {
public:
    std::shared_ptr<B> b;
    A() { std::cout << "A created\n"; }
    ~A() { std::cout << "A destroyed\n"; }
};

class B {
public:
    std::shared_ptr<A> a;
    B() { std::cout << "B created\n"; }
    ~B() { std::cout << "B destroyed\n"; }
};

int main() {
    std::shared_ptr<A> a = std::make_shared<A>();
    std::shared_ptr<B> b = std::make_shared<B>();
    
    a->b = b; // A持有B
    b->a = a; // B持有A
    
    // a和b之间的相互引用会导致无法释放内存
}

在上面的代码中,AB 通过 std::shared_ptr 相互引用,导致它们无法被销毁,因为两者的引用计数永远不为零,造成了循环引用

循环引用的问题:
  • 内存泄漏:即使程序退出时,AB 对象依然存在,内存无法被释放,造成内存泄漏。
  • 性能损耗:因为对象永远无法被释放,它们占用了内存。
如何解决循环引用:
  1. 弱引用(std::weak_ptr

    修改上面的代码:

    class B; // 前向声明
    
    class A {
    public:
        std::shared_ptr<B> b;
        A() { std::cout << "A created\n"; }
        ~A() { std::cout << "A destroyed\n"; }
    };
    
    class B {
    public:
        std::weak_ptr<A> a; // 使用 weak_ptr 代替 shared_ptr
        B() { std::cout << "B created\n"; }
        ~B() { std::cout << "B destroyed\n"; }
    };
    
    int main() {
        std::shared_ptr<A> a = std::make_shared<A>();
        std::shared_ptr<B> b = std::make_shared<B>();
     
        a->b = b; // A持有B
        b->a = a; // B持有A,但没有增加引用计数
     
        // 现在,A 和 B 可以正确销毁,避免了循环引用的内存泄漏
    }
    
    • 在智能指针中,std::weak_ptr 用于打破循环引用的闭环。std::weak_ptr 不会增加引用计数,因此它不会阻止对象的销毁。
    • 解决方案:将其中一个类的成员变量使用 std::weak_ptr 代替 std::shared_ptr,从而打破循环引用。
  2. 设计改进

  • 除了使用 std::weak_ptr 外,还可以考虑优化设计,减少不必要的相互引用,或者将业务逻辑从依赖关系中解耦。
  1. 智能指针的使用

  • 除了 std::shared_ptrstd::weak_ptr,在设计时也要避免滥用智能指针。过多的智能指针可能导致不必要的循环引用。
  1. newmalloc 可申请的最大内存大小:通常由系统的内存和架构限制,malloc 在失败时返回 NULLnew 抛出 std::bad_alloc 异常。

  2. 循环引用:指的是两个对象之间相互引用,形成闭环,导致内存无法释放。解决方法包括使用 std::weak_ptr 来打破循环引用。

如何使用函数模板和类模板?

        在 C++ 中,模板(Template)是一个非常强大的特性,它允许编写泛化的代码,使得代码可以适应不同类型的数据。模板分为 函数模板类模板,我们可以根据需要灵活地定义。

函数模板

        函数模板允许你为不同类型编写函数,而不需要为每种类型都写一个单独的函数。C++ 编译器会根据传入的实际类型来实例化函数模板。

定义和使用函数模板的基本语法

// 函数模板的定义
template <typename T> // 或者 'class T',两者是等价的
T add(T a, T b) {
    return a + b;
}

int main() {
    // 使用函数模板
    int intResult = add(2, 3);          // T 被推断为 int
    double doubleResult = add(2.5, 3.5); // T 被推断为 double
    std::cout << "intResult: " << intResult << "\n";    // 输出 5
    std::cout << "doubleResult: " << doubleResult << "\n"; // 输出 6.0
    return 0;
}

解释

  • template <typename T> 声明了一个模板,T 是一个占位符,可以是任何类型。在 add 函数中,T 会被替换成具体的数据类型(如 intdouble),由编译器根据传递给函数的实际类型来推断。
类模板

类模板允许你定义泛化的类,能够处理不同类型的数据。我们可以通过类模板为多种类型提供统一的接口和实现。

定义和使用类模板的基本语法

// 类模板的定义
template <typename T>
class Box {
private:
    T value;
public:
    Box(T v) : value(v) {}
    T getValue() { return value; }
    void setValue(T v) { value = v; }
};

int main() {
    Box<int> intBox(10);   // 类模板实例化为 Box<int>
    Box<double> doubleBox(3.14); // 类模板实例化为 Box<double>

    std::cout << "intBox value: " << intBox.getValue() << "\n";  // 输出 10
    std::cout << "doubleBox value: " << doubleBox.getValue() << "\n"; // 输出 3.14
    return 0;
}

解释

  • template <typename T> 定义了一个类模板,T 是类型参数,类的成员函数和数据成员都使用了 T 作为类型。
  • main 函数中,分别使用 Box<int>Box<double> 来实例化 Box 类模板,传入不同的类型 intdouble
模板的特化

你还可以特化模板,为特定类型提供专门的实现。

示例:int 类型提供特化版本的 add 函数模板:

// 默认模板版本
template <typename T>
T add(T a, T b) {
    return a + b;
}

// 对 int 类型进行特化
template <>
int add<int>(int a, int b) {
    std::cout << "Specialized for int\n";
    return a + b;
}

int main() {
    std::cout << add(3, 4) << "\n"; // 调用 int 特化版本
    std::cout << add(2.5, 3.5) << "\n"; // 调用通用版本
    return 0;
}

模板的优点

模板在 C++ 中提供了强大的灵活性和可重用性,具有以下优点:

1. 代码复用

模板允许你编写一次函数或类代码,可以适用于多种类型,减少了重复代码的编写。例如,add 函数模板可以同时支持整数、浮动类型等,而不需要为每种类型写一个 add 函数。

2. 类型安全

模板可以确保类型的安全性。由于模板参数是类型,在编译时会进行类型检查,因此可以避免类型不匹配的错误。例如,Box<int>Box<double> 是不同的类型,编译器会强制保证它们之间的类型不混淆。

3. 提高代码的灵活性和可扩展性

模板使得我们可以为不同的类型提供统一的接口,而不用关心类型本身的实现细节。比如,标准库中的容器(如 std::vector)和算法(如 std::sort)就广泛使用了模板,可以支持不同类型的数据。

4. 性能优化

模板通常在编译时生成代码(编译时多态),而不是在运行时(运行时多态)。这意味着模板代码在实际运行时不会引入额外的开销,能够通过编译器进行优化,从而提高性能。例如,std::vector<int>std::vector<double> 的实现是完全独立的,在运行时没有额外的动态分配和类型转换开销。

5. 支持泛型编程

模板是泛型编程的核心,允许你编写与类型无关的代码。这使得代码能够更加通用和灵活,可以处理各种不同的数据类型。标准模板库(STL)就是利用模板实现了一个高度通用且可复用的容器和算法库。

6. 增强代码的可维护性

通过模板,可以将算法和数据结构的实现分离开来,从而增加代码的可维护性。因为模板支持通用的设计模式,可以很容易地适配新的数据类型,而无需修改原来的代码。

标签:std,int,编程,mid,天天,Day10,内存,ptr,模板
From: https://blog.csdn.net/qq_73301411/article/details/143630958

相关文章

  • Cursor:编程软件中的璀璨明珠,解锁高效开发新姿势
    在编程领域,有一款备受瞩目的软件——Cursor。它为开发者们带来了全新的编程体验,无论是新手还是经验丰富的程序员都值得关注。本文将探讨Cursor的功能、特点以及它如何助力开发者提升编程效率。(无广)一、强大的功能特性(一)智能代码补全Cursor的代码补全功能堪称一绝。它不像......
  • 实验三 类和对象_基础编程2
    实验任务1button.hpp 1#pragmaonce23#include<iostream>4#include<string>56usingstd::string;7usingstd::cout;89//按钮类10classButton{11public:12Button(conststring&text);13stringget_label()con......
  • 掌握 IntelliJ IDEA,开启高效编程之旅
    在当今的编程世界中,IntelliJIDEA已成为众多开发者的首选工具。它以其强大的功能和高效的特性,为开发者提供了一个卓越的编程环境。掌握IntelliJIDEA,无疑是开启高效编程之旅的关键一步。IntelliJIDEA拥有智能的代码提示和自动完成功能,这使得编程变得更加快捷和流畅。它能......
  • 嵌入式课程day10-C语言数组
    目录七、数组7.1数组是什么?7.2数组的使用7.3定义数组7.4数组初始化7.5冒泡排序7.6二分法查找七、数组7.1数组是什么?存储多个同种类型的数据 ,方便数据处理7.2数组的使用先定义再使用7.3定义数组存储多少数据 数据的数据类型 数组名元素:数组中数据可以统......
  • 网络编程IO多路复用之poll模式
    网络编程IO多路复用之poll模式文章目录网络编程IO多路复用之poll模式1.poll函数原型2.系统调用过程3.poll编程模型图4.poll事件5.总结6.延伸问题1.poll函数原型#include<poll.h>intpoll(structpollfd*fds,nfds_tnfds,inttimeout);参数说明1......
  • 解锁Java编程新高度!用validate注解做校验,让你的代码更高效、更安全!
    在Java中,@Valid注解通常用于验证对象的属性。它通常与Spring框架一起使用,以自动触发对JavaBean的验证。以下是如何使用@Valid注解进行校验的详细步骤和示例代码:1.添加依赖首先,确保你的项目中包含了SpringBoot的starter-web依赖,因为我们需要用到Spring的验证功能。<depend......
  • 【MFC编程(四)】图形图像:CDC类与GDI绘图
    文章目录绘图引擎简介GDI绘图DC设备上下文CDC类HDC和CDC的区别与转换屏幕绘图成员函数绘制点绘制直线绘制矩形绘制椭圆绘制多边形绘制文本绘制位图绘图引擎简介Windows环境下二维绘图引擎有多种选择:GDI、GDI+、DirectDraw、Qt/QPainter、Agg、Cairo、skia、Direct2......
  • 少儿编程教育的多维度对比:软件类、硬件类与软硬件结合课程的选择
    随着少儿编程教育的不断发展,市场上涌现出多种类型的编程课程,主要分为软件类课程、硬件类课程和软硬件结合类课程。三种课程各有特色,针对不同的编程对象和教学目标。本文将从多个维度深入对比这三类课程的特点、教学目的和学习难点,帮助家长和学生更好地选择适合的编程学习路径......
  • 【java编程】深入浅出JVM(四):类文件结构
    原创菜菜的后端私房菜Java文件编译成字节码文件后,通过类加载机制到Java虚拟机中,Java虚拟机能够执行所有符合要求的字节码,因此无论什么语言,只要能够编译成符合要求的字节码文件就能够被Java虚拟机执行.Java虚拟机和字节码是语言、平台无关性的基石.本篇文章将深入浅出的解析......
  • Rust编程与项目实战-结构体
    《Rust编程与项目实战》(朱文伟,李建英)【摘要书评试读】-京东图书(jd.com)在Rust中,结构体(Struct)是一种自定义数据类型,它允许我们将多个相关的值组合在一起,形成一个更复杂的数据结构。结构体在Rust中被广泛应用于组织和管理数据,具有灵活性和强大的表达能力。本节将详细介绍Rus......