空与一-CSDN博客

原创 LeetCode链表：多指针和虚拟头结点

链表操作的时间复杂度操作时间复杂度查找元素O(n)插入元素O(1)删除元素O(1)链表的解题技巧多指针2个，快慢指针3个，链表反转4个，结点交换虚拟头结点常用于删除结点的情况其他情况也可具体分析LeetCode 206 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。示例 1：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]C++class Solution {pub

2021-12-23 11:15:39 1690

原创 LeetCode数组：滑动窗口

上文介绍了数组的双下标对撞。本文介绍双下标的滑动窗口:左右2个下标组成一个窗口，初始化窗口大小可以为0根据条件，不断地扩大或者缩小窗口右下标增加，扩大窗口左下标增加，缩小窗口不断地计算窗口是否符要求，比较目前最优解和本次最优解，找出最终的最优解LeetCode 209 来源：力扣（LeetCode）209 Medium 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum 给定一个含有 n 个正整数的数组

2021-12-10 11:58:29 1543

原创 LeetCode数组：双下标对撞

上文中，讲解了多下标的基本使用，每个下标都是从左到右移动。双下标的另一个操作是对撞：两个下标初始化在头部(最左边)和尾部(最右边)，然后不断地向对方移动靠近。LeetCode 167 来源：力扣（LeetCode）Easy 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted 给定一个已按照非递减顺序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数

2021-12-06 11:38:23 2145

原创 LeetCode数组的解题技巧

上文介绍了数组的基本操作以及其时间复杂度。本文结合LeetCode题目，介绍数组的解题技巧。多下标使用一个下标遍历数组。也可以使用2个或者多个下标，每个下标代表不同的含义。区间2个下标可以组成区间，区间可以代表明确的含义：比如相同的元素区间。元素交换在数组中交换两个不同下标的值，其时间复杂度是O(1)。可以代替数组的删除或者插入操作，它们的时间复杂度是O(n)。LeetCode 283 来源：力扣（LeetCode）283 Easy 链接：https://leetcode-cn.co

2021-11-29 11:44:46 234

原创数组的基本操作

数组是线性数据结构。由一块连续的内存空间组成用于储存相同类型的数据元素数组分成2种类型：固定数组：初始化的时候，分配一块内存空间，之后不会重新分配内存空间长度的含义是指数组容纳最多元素的数量，并且必须包含这么多的元素动态数组：初始化的时候，分配一块内存空间，之后可能重新分配空间长度的含义是指当前包含元素的数量，元素数量可以小于数组最大容量，并且允许不断地新增元素如果元素数量超过现有的数组容量，会重新给数组分配内存空间，并拷贝已有元素。这称之为扩容。结合数组的结构，其

2021-11-18 19:54:50 636

原创算法的复杂度

使用数据结构或者算法解决问题，如何判断这种解法的优劣？从2个维度去考察：时间复杂度：用来评估代码运行的时间趋势空间复杂度：用来评估代码运行的内存占用规模时间复杂度下面的代码是求数字1到n的和，那如何评估计算机执行这段代码的时间？int sum(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += i; } return sum;}假定计算机执行每行

2021-11-13 22:36:45 365

原创 C++ STL基本组件：容器，算法，迭代器

STL，是Standard Template Library的缩写，标准模版库。STL使用类模版或者函数模版实现，包含3个最基本最重要的组件：容器：使用类模版实现的各种数据结构算法：使用函数模版实现的各种算法迭代器：类模版，每个容器类都有自定义的迭代器类使用容器对象的相关方法，可以获取迭代器对象算法函数的参数和返回值，很多是迭代器对象STL容器包含2种：序列式容器：容器中的元素是无序的，可以指定元素的位置，比如vector、list、deque关联式容器：容器中的元素是键值对(

2021-11-03 11:43:20 519

原创 C++模版：类模版的友元函数

类模版可以有友元函数。友元函数可以是普通函数。template <typename T>class Stack {private: T items[10]; int top; public: Stack(); void setTop(int top); bool isEmpty(); friend int size2(Stack<T> & stack);};size2()并不是函数模版，但它的参

2021-10-29 11:57:51 142

原创 C++模版：类模版的继承

如果父类是类模版，子类有2种方式继承父类：指定具体类型，继承父类实例化类子类可以定义成普通类子类也可以定义成模版类子类继承父类模版，子类必须定义成模版类，将模版参数传给父类第1种情况：Apple1是普通类，继承模版实例化类Fruit<int>Apple2是模版类，继承模版实例化类Fruit<int>template <typename T>class Fruit {public: Fruit();};template &l

2021-10-27 22:02:17 424

原创 C++模版：类模版初探

在定义类的时候，继承和组合可以满足大部分需求。但是对于某些场景，比如用来储存对象的容器类，针对不同的储存对象类型，容器类都需要提供相同的代码实现。如果使用类模版，可以将储存对象类型作为参数传给容器类，这样就可以使用一套容器类代码。类模版语法类模版的语法如下，<>包起来的是模版参数列表，可以有多个参数，用逗号分隔。template <typename T>类声明template ：关键字，表示定义模板typename ：关键字，表示一个类型参数T ：变量名，其值代表一个

2021-10-18 11:42:31 115

原创 C++模版：深入使用函数模版

上文函数模版初探介绍了函数模版的基本使用，本文深入探讨函数模版。函数模版参数的类型转换函数模版有多个同类型的形参，使用过程中会碰到类型转换问题。下面是一个加法函数模版:template <typename T>T add2(T a, T b) { std::cout << "T add2(T a, T b)" << std::endl; return a + b;}使用隐式实例化，2个实参的类型必须相同，否则编译出错No m

2021-09-26 11:31:33 101

原创 C++模版：函数模版初探

文章目录函数的冗余问题函数模版语法定义函数模版实例化函数模版函数模版基础总结模版是泛型编程的基础。函数模版是通用的函数描述，可以用它来生成具体类型的函数。下面介绍函数模版的基础知识。函数的冗余问题以交换函数为例，针对int，double类型，需要定义2个函数。这2个函数的实现方式是一样的，唯一的区别是不同的参数类型。如果要满足所有的类型，那就要写很多相同的代码。// int类型交换void swapInt(int& a, int& b) { int temp = a; a

2021-09-12 19:46:07 119