今日两道编程题
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;
}
};
二分查找概述:
二分查找通过不断折半查找区间,来快速缩小目标值的位置。在计算平方根时,目的是找到最大的整数 y
,使得 y * y <= x
。
问题背景:
我们要在区间 [0, x]
上进行二分查找,以找到整数平方根。在每一步中,我们计算中点 mid
,然后检查 mid * mid
和 x
的关系,从而决定如何调整搜索区间。
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 + 1
和 j = mid - 1
必须这样更新:
-
i = mid + 1
:因为我们已经知道mid
太小,mid
是潜在的平方根,但它还不够大,所以我们必须让搜索区间的下界更大,继续寻找可能的平方根值。 -
j = mid - 1
:因为mid
的平方大于x
,我们排除了mid
作为有效的平方根,所以我们缩小上界,尝试一个更小的mid
。
示例说明:
假设我们要计算 x = 10
的平方根,区间是 [0, 10]
,并且我们使用二分查找。
-
初始值:
i = 0
,j = 10
-
第一次循环:
- 计算
mid = (0 + 10) / 2 = 5
mid * mid = 25 > 10
,所以mid
太大了。- 更新
j = mid - 1 = 4
。
- 计算
-
第二次循环:
- 计算
mid = (0 + 4) / 2 = 2
mid * mid = 4 < 10
,所以mid
还太小了。- 更新
i = mid + 1 = 3
。
- 计算
-
第三次循环:
- 计算
mid = (3 + 4) / 2 = 3
mid * mid = 9 < 10
,还是太小了。- 更新
i = mid + 1 = 4
。
- 计算
-
第四次循环:
- 计算
mid = (4 + 4) / 2 = 4
mid * mid = 16 > 10
,太大了。- 更新
j = mid - 1 = 3
。
- 计算
现在,i
和 j
都指向 4,且 i > j
,循环结束。此时,j = 3
就是我们想要的平方根的整数部分。
总结:
i = mid + 1
是因为当mid * mid < x
时,我们要寻找更大的数,因此下界要向右移动。j = mid - 1
是因为当mid * mid > x
时,我们要寻找更小的数,因此上界要向左移动。
new
或 malloc
申请空间时,超出可申请的大小会引发异常
在 C++ 中,new
和 malloc
都用于动态内存分配,但它们的行为和异常处理略有不同。
可申请的最大内存大小
-
new
和malloc
的内存限制:- 允许申请的内存大小受限于系统的总可用内存、操作系统限制以及进程内存空间的大小(通常由操作系统的架构决定,如 32 位或 64 位系统)。
- 在 32 位系统上:
- 一个进程的最大地址空间通常为 2GB 或 3GB(在 Windows 中,具体的可用空间取决于操作系统版本和内存分配)。即使
new
或malloc
申请的内存小于这个值,也可能因系统资源问题而无法分配成功。
- 一个进程的最大地址空间通常为 2GB 或 3GB(在 Windows 中,具体的可用空间取决于操作系统版本和内存分配)。即使
- 在 64 位系统上:
- 进程的地址空间理论上非常大,通常可以达到数 TB。但实际上,受限于系统的物理内存、虚拟内存和操作系统的配置,实际能申请的内存可能远小于理论值。
-
malloc
或new
失败的情况:- 当
malloc
或new
无法分配请求的内存时,它们的行为有所不同: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++ 中的循环引用
循环引用是什么:
循环引用指的是两个或多个对象之间形成了相互引用的情况,形成一个闭环,这种引用关系会导致内存无法正常释放,从而造成内存泄漏。通常,循环引用发生在智能指针、集合等地方。
循环引用的示例:
假设我们有两个类,A
和 B
,并且它们分别持有对方的指针或智能指针:
#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之间的相互引用会导致无法释放内存
}
在上面的代码中,A
和 B
通过 std::shared_ptr
相互引用,导致它们无法被销毁,因为两者的引用计数永远不为零,造成了循环引用。
循环引用的问题:
- 内存泄漏:即使程序退出时,
A
和B
对象依然存在,内存无法被释放,造成内存泄漏。 - 性能损耗:因为对象永远无法被释放,它们占用了内存。
如何解决循环引用:
-
弱引用(
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
,从而打破循环引用。
- 在智能指针中,
-
设计改进:
- 除了使用
std::weak_ptr
外,还可以考虑优化设计,减少不必要的相互引用,或者将业务逻辑从依赖关系中解耦。
-
智能指针的使用:
- 除了
std::shared_ptr
和std::weak_ptr
,在设计时也要避免滥用智能指针。过多的智能指针可能导致不必要的循环引用。
-
new
和malloc
可申请的最大内存大小:通常由系统的内存和架构限制,malloc
在失败时返回NULL
,new
抛出std::bad_alloc
异常。 -
循环引用:指的是两个对象之间相互引用,形成闭环,导致内存无法释放。解决方法包括使用
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
会被替换成具体的数据类型(如int
或double
),由编译器根据传递给函数的实际类型来推断。
类模板:
类模板允许你定义泛化的类,能够处理不同类型的数据。我们可以通过类模板为多种类型提供统一的接口和实现。
定义和使用类模板的基本语法:
// 类模板的定义
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
类模板,传入不同的类型int
和double
。
模板的特化:
你还可以特化模板,为特定类型提供专门的实现。
示例: 为 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