对运营网站有什么见解,培训网站有哪些,工商网上注册,用mockplus做网站原型题目#xff1a;有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
题解 数组其实是有序的#xff0c; 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的…题目有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
题解 数组其实是有序的 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端不是最左边就是最右边不可能是中间。可以使用两个指针分别指向位置 0 和 n−1每次比较两个指针对应的数选择较大的那个逆序放入答案并移动指针。时间复杂度O(n)其中 n 是数组 nums 的长度。空间复杂度O(1)。除了存储答案的数组以外我们只需要维护常量空间。 如果A[i] * A[i] A[j] * A[j] 那么result[k--] A[j] * A[j]; 。如果A[i] * A[i] A[j] * A[j] 那么result[k--] A[i] * A[i]; 。 class Solution {
public:vectorint sortedSquares(vectorint nums) {int left0,rightnums.size()-1;int ptr_index nums.size()-1;vectorint res(ptr_index1);while(leftright){if(nums[left]*nums[left] nums[right]*nums[right]){res[ptr_index] nums[right]*nums[right];--right;}else{res[ptr_index] nums[left]*nums[left];left;}--ptr_index;}return res;}
};此时的时间复杂度为O(n)相对于暴力排序的解法O(n nlog n)还是提升不少的。
题目长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
题解 这道题目暴力解法当然是 两个for循环然后不断的寻找符合条件的子序列时间复杂度很明显是 O ( n 2 ) O(n^2) O(n2)。接下来就开始介绍数组操作中另一个重要的方法滑动窗口。代码随想录 (programmercarl.com) 所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。 那么滑动窗口如何用一个for循环来完成这个操作呢如果只用一个for循环来表示 滑动窗口的起始位置那么如何遍历剩下的终止位置 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。 在本题中实现滑动窗口主要确定如下三点 窗口内是什么窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组 如何移动窗口的起始位置(如果当前窗口的值大于s了窗口就要向前移动了) 如何移动窗口的结束位置(窗口的结束位置就是遍历数组的指针也就是for循环里的索引) 可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将 O ( n 2 ) O(n^2) O(n2) 暴力解法降为O(n)。 不要以为for里放一个while就以为是 O ( n 2 ) O(n^2) O(n2) 啊 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int len_nums nums.size();int sum 0;int start_index 0,sub_lenlen_nums3;for(int i 0;ilen_nums;i){sum nums[i];while(sumtarget){sub_len min(sub_len,i-start_index1);sum - nums[start_index];start_index;}}return sub_lenlen_nums?0:sub_len;}
};题目螺旋矩阵 II
给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
题解 本题并不涉及到什么算法就是模拟过程但却十分考察对代码的掌控能力。模拟矩阵的生成。按照要求初始位置设为矩阵的左上角初始方向设为向右。若下一步的位置超出矩阵边界或者是之前访问过的位置则顺时针旋转进入下一个方向。如此反复直至填入 n 2 n^2 n2 个元素。求解本题要坚持循环不变量原则。模拟顺时针画矩阵的过程: 填充上行从左到右 填充右列从上到下 填充下行从右到左 填充左列从下到上 由外向内一圈一圈这么画下去。这里一圈下来我们要画每四条边这四条边怎么画每画一条边都要坚持一致的左闭右开或者左开右闭的原则这样这一圈才能按照统一的规则画下来。 class Solution {
public:vectorvectorint generateMatrix(int n) {vectorvectorint res(n,vectorint(n,0));int startx0,starty0;int cirle n/2;int offset1;int count1;int i,j;while(cirle--){istartx;jstarty;for(jstarty;jn-offset;j){res[startx][j] count;}for(istartx;in-offset;i){res[i][j]count;}for(;jstarty;j--){res[i][j]count;}for(;istartx;i--){res[i][j]count;}startx;starty;offset;}if(n%2){res[startx][starty]count;}return res;}
};C STL 四种智能指针 C 标准模板库 STLStandard Template Library 一共给我们提供了四种智能指针auto_ptr、unique_ptr、shared_ptr 和 weak_ptr其中 auto_ptr 是 C98 提出的C11 已将其摒弃并提出了 unique_ptr 替代 auto_ptr。虽然 auto_ptr 已被摒弃但在实际项目中仍可使用但建议使用更加安全的 unique_ptr。shared_ptr 和 weak_ptr 则是 C11 从准标准库 Boost 中引入的两种智能指针。此外Boost 库还提出了 boost::scoped_ptr、boost::scoped_array、boost::intrusive_ptr 等智能指针虽然尚未得到 C 标准采纳但是在开发实践中可以使用C STL 四种智能指针_c智能指针_恋喵大鲤鱼的博客-CSDN博客。 C 智能指针底层是采用引用计数的方式实现的。智能指针在申请堆内存空间的同时会为其配备一个整形值初始值为 1每当有新对象使用此堆内存时该整形值 1反之每当使用此堆内存的对象被释放时该整形值减 1。当堆空间对应的整形值为 0 时即表明不再有对象使用它该堆空间就会被释放掉。 每种智能指针都是以类模板的方式实现的shared_ptr 也不例外。shared_ptr其中 T 表示指针指向的具体数据类型的定义位于memory头文件并位于 std 命名空间中因此在使用该类型指针时程序中应包含如下 2 行代码 #include memory
using namespace std;unique_ptr 作为智能指针的一种unique_ptr 指针自然也具备“在适当时机自动释放堆内存空间”的能力。和 shared_ptr 指针最大的不同之处在于unique_ptr 指针指向的堆内存无法同其它 unique_ptr 共享也就是说每个 unique_ptr 指针都独自拥有对其所指堆内存空间的所有权。 这也就意味着每个 unique_ptr 指针指向的堆内存空间的引用计数都只能为 1一旦该 unique_ptr 指针放弃对所指堆内存空间的所有权则该空间会被立即释放回收。 创建空的 unique_ptr 指针 std::unique_ptrint p1();
std::unique_ptrint p2(nullptr);构建 unique_ptr 智能指针并初始化确定数据 std::unique_ptrint p3(new int);基于 unique_ptr 类型指针不共享各自拥有的堆内存因此 C11 标准中的 unique_ptr 模板类没有提供拷贝构造函数只提供了移动构造函数。例如 std::unique_ptrint p4(new int);
std::unique_ptrint p5(p4);//错误堆内存不共享
std::unique_ptrint p5(std::move(p4));//正确调用移动构造 函 数
//值得一提的是对于调用移动构造函数的 p4 和 p5 来说
//p5 将获取 p4 所指堆空间的所有权而 p4 将变成空指针nullptr。默认情况下unique_ptr 指针采用 std::default_delete 方法释放堆内存。也可自定义释放规则。和 shared_ptr 指针不同 unique_ptr 自定义释放规则只能采用函数对象的方式。
shared_ptr 值得一提的是和 unique_ptr、weak_ptr 不同之处在于多个 shared_ptr 智能指针可以共同使用同一块堆内存。并且由于该类型智能指针在实现上采用的是引用计数机制即便有一个 shared_ptr 指针放弃了堆内存的“使用权”引用计数减 1也不会影响其他指向同一堆内存的 shared_ptr 指针只有引用计数为 0 时堆内存才会被自动释放。 构造 shared_ptr 类型的空智能指针 std::shared_ptrint p1; //不传入任何实
std::shared_ptrint p2(nullptr); //传入空指针 nullptr构建 shared_ptr 智能指针并初始化确定数据 std::shared_ptrint p3(new int(10));
std::shared_ptrint p3 std::make_sharedint(10);
//调用拷贝构造函数
std::shared_ptrint p4(p3);//或者 std::shared_ptrint p4 p3;//调用移动构造函数
std::shared_ptrint p5(std::move(p4)); //或者 std::shared_ptrint p5 std::move(p4);如上所示p3 和 p4 都是 shared_ptr 类型的智能指针因此可以用 p3 来初始化 p4由于 p3 是左值因此会调用拷贝构造函数。需要注意的是如果 p3 为空智能指针则 p4 也为空智能指针其引用计数初始值为 0反之则表明 p4 和 p3 指向同一块堆内存同时该堆空间的引用计数会加 1。而对于 std::move(p4) 来说该函数会强制将 p4 转换成对应的右值因此初始化 p5 调用的是移动构造函数。另外和调用拷贝构造函数不同用 std::move(p4) 初始化 p5会使得 p5 拥有了 p4 的堆内存而 p4 则变成了空智能指针。 注意一普通指针不能同时为多个 shared_ptr 对象赋值否则会导致程序发生异常。例如 int* ptr new int;
std::shared_ptrint p1(ptr);
std::shared_ptrint p2(ptr);//错误初始化 shared_ptr 智能指针时可自定义堆内存的释放规则当堆内存的引用计数为 0 时会优先调用自定义的释放规则。 //指定 default_delete 作为释放规则
std::shared_ptrint p6(new int[10], std::default_deleteint[]());
//自定义释放规则
void deleteInt(int*p) {delete []p;
}
//初始化智能指针并自定义释放规则
std::shared_ptrint p7(new int[10], deleteInt);weak_ptr C11标准虽然将 weak_ptr 定位为智能指针的一种但该类型指针通常不单独使用没有实际用处只能和 shared_ptr 类型指针搭配使用。甚至于我们可以将 weak_ptr 类型指针视为 shared_ptr 指针的一种辅助工具借助 weak_ptr 类型指针 我们可以获取 shared_ptr 指针的一些状态信息比如有多少指向相同的 shared_ptr 指针、shared_ptr 指针指向的堆内存是否已经被释放等等。 需要注意的是当 weak_ptr 类型指针的指向和某一 shared_ptr 指针相同时weak_ptr 指针并不会使所指堆内存的引用计数加 1同样当 weak_ptr 指针被释放时之前所指堆内存的引用计数也不会因此而减 1。也就是说weak_ptr 类型指针并不会影响所指堆内存空间的引用计数。 std::unique_ptr内存的所有者或者说管理者必须是唯一的。如果进入不同的模块或者调用者那么执行所有权转移。 std::shared_ptr: 内存由多个指针变量共同使用共同拥有内存的所有权。但是必须杜绝循环拷贝 std::weak_ptr: 对内存的使用仅仅是访问而已不涉及其生命周期的管理。 1。也就是说weak_ptr 类型指针并不会影响所指堆内存空间的引用计数。
