一只攻城狮的学习之旅

状态转移方程定义动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。若给定了第K阶段的状态Sk以及决策uk(Sk),则第K+1阶段的状态Sk+1也就完全确定。也就是说Sk+1与Sk,uk之间存在一种明确的数量对应关系，记为Tk(Sk,uk),即有Sk+1= Tk(Sk,uk)。 这种用函数表示前后阶段关系的方程，称为状态转移方程。在上例中状态转移方程为 Sk+1= uk(Sk) 。 设计适用条件 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。 1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过 ...

Union-Find 算法（并查集算法）⼀、问题介绍简单说，动态连通性其实可以抽象成给⼀幅图连线。⽐如下⾯这幅图，总共 有 10 个节点，他们互不相连，分别⽤ 0~9 标记： 现在我们的 Union-Find 算法主要需要实现这两个 API： 12345678class UF {     /* 将 p 和 q 连接 */     public void union(int p, int q);     /* 判断 p 和 q 是否连通 */     public boolean connected(int p, int q);     /* 返回图中有多少个连通分量 */     public int count(); } 这⾥所说的「连通」是⼀种等价关系，也就是说具有如下三个性质： 1、⾃反性：节点 p 和 p 是连通的。 2、对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。 3、传递性：如果节点 p 和 q 连通， q 和 r 连通，那么 p 和 r 也连通。 ⽐如说之前那幅图，0〜9 任意两个不同的点都不连通，调⽤ connected 都 会 ...

数据结构简介前言数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。 如下图所示，常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。 从零开始学习算法的同学对数据结构的使用方法可能尚不熟悉，本节将初步介绍各数据结构的基本特点，与 Python3 , Java , C++ 语言中各数据结构的初始化与构建方法。 代码运行可使用本地 IDE 或 力扣 PlayGround 。 数组数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。 如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下： 12345678// 初始化一个长度为 5 的数组 arrayint[] array = new int[5];// 元素赋值array[0] = 2;array[1] = 3;array[2] = 1;array[3] = 0;array[4] ...

二分查找模版模版第⼀个，最基本的⼆分查找算法： 因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1 因为我们只需找到⼀个 target 的索引即可 所以当 nums[mid] == target 时可以⽴即返回 1234567891011121314int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { ...

C++编译期多态与运行期多态前言今日的C++不再是个单纯的“带类的C”语言，它已经发展成为一个多种次语言所组成的语言集合，其中泛型编程与基于它的STL是C++发展中最为出彩的那部分。在面向对象C++编程中，多态是OO三大特性之一，这种多态称为运行期多态，也称为动态多态；在泛型编程中，多态基于template(模板)的具现化与函数的重载解析，这种多态在编译期进行，因此称为编译期多态或静态多态。在本文中，我们将了解： 什么是运行期多态 什么是编译期多态 它们的优缺点在哪 运行期多态运行期多态的设计思想要归结到类继承体系的设计上去。对于有相关功能的对象集合，我们总希望能够抽象出它们共有的功能集合，在基类中将这些功能声明为虚接口（虚函数），然后由子类继承基类去重写这些虚接口，以实现子类特有的具体功能。典型地我们会举下面这个例子： 123456789101112131415161718192021222324252627282930313233343536class Animal{public : virtual void shout() = 0;};class ...

虚基类1、使用virtual修饰 基类是虚的时候静止信息通过中间类传递给基类 需要显示的调用所需的基类构造函数 1.为什么要引入虚基类？在类的继承中，如果我们遇到这种情况：“B和C同时继承A，而B和C都被D继承”在此时，假如A中有一个函数fun（）当然同时被B和C继承，而D按理说继承了B和C，同时也应该能调用fun()函数。这一调用就有问题了，到底是要调用B中的fun（）函数还是调用C中的fun（）函数呢？在C++中，有两种方法实现调用：(注意：这两种方法效果是不同的) 使用作用域标识符来唯一表示它们比如：B::fun（）另一种方法是定义虚基类，使派生类中只保留一份拷贝。作用域标识符表示例子： 1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;class base{ public: base(){a=5;cout<<"base="<<a<<endl;} ...

C/C++ 关于 cJson 库的使用关于 Json 这种数据格式，在前面已经做了详细的介绍 Json 的格式和用途，在项目开发过程中我们需要针对不同的语言使用不同的库对 Json 格式的数据进行解析，下面给大家介绍一个基于 C 语言的 Json 库 – cJson。cJSON 是一个超轻巧，携带方便，单文件，简单的可以作为 ANSI-C 标准的 JSON 解析器。 cJSON 是一个开源项目，github 下载地址： https://github.com/DaveGamble/cJSON cJSON，目前来说，主要的文件有两个，一个 cJSON.c 一个 cJSON.h。使用的时候，将头文件 include 进去即可。 如果是在 Linux 操作系统中使用，编译 到时候需要添加数学库 libm.so，如下所示： 1gcc *.c cJSON.c -lm 1. cJSON 结构体在 cJSON.h 中定义了一个非常重要的结构体 cJSON，想要熟悉使用 cJSON 库函数可从 cJSON 结构体入手，cJSON 结构体如下所示： 123456789typedef ...

C++ 使用 chrono 库处理日期和时间C++11 中提供了日期和时间相关的库 chrono，通过 chrono 库可以很方便地处理日期和时间，为程序的开发提供了便利。chrono 库主要包含三种类型的类：时间间隔duration、时钟clocks、时间点time point。 1. 时间间隔 duration1.1 常用类成员duration表示一段时间间隔，用来记录时间长度，可以表示几秒、几分钟、几个小时的时间间隔。duration 的原型如下： 12345// 定义于头文件 <chrono>template< class Rep, class Period = std::ratio<1>> class duration; ratio 类表示每个时钟周期的秒数，其中第一个模板参数 Num 代表分子，Denom 代表分母，该分母值默认为 1，因此，ratio 代表的是一个分子除以分母的数值，比如：ratio<2> 代表一个时钟周期是 2 秒，ratio<60 > 代表一分钟，ratio<60*60 & ...

C++后台学习篇：一、一个项目入门C++足以：CPlusPlusThings.CPlusPlusThings 是国人开源一个 C++ 学习项目。它系统地将 C++ 学习分为了【基础进阶】、【实战系列】、【C++2.0 新特性】、【设计模式】和【STL 源码剖析】、【并发编程】、【C++ 惯用法】、【学习课程】、【工具】、【拓展】。 作为一个全面系统的 C++ 学习项目，CPlusPlusThings 是优秀的，它合理地安排了 10 Days 的实战部分，在实战中了解语法和函数用法，唯一不足的是，在注释部分有些不尽人意，对部分新手程序员并不是很友好。 CPlusPlusThings C++那些事 (light-city.club) 二、C++实现的算法合集：C-Plus-PlusC-Plus-Plus 是收录用 C++ 实现的各种算法的集合，并按照 MIT 许可协议进行授权。这些算法涵盖了计算机科学、数学和统计学、数据科学、机器学习、工程等各种主题。除外，你可能会发现针对同一目标的多个实现使用不同的算法策略和优化。 C-Plus-Plus 三、进阶指南：CppTemplateTu ...

C++ 八股文（一）多态什么是多态，有什么用C++ 多态有两种：静态多态（早绑定）、动态多态（晚绑定）。静态多态是通过函数重载实现的；动态多态是通过虚函数实现的。 定义：“一个接口，多种方法”，程序在运行时才决定要调用的函数。 实现：C++ 多态性主要是通过虚函数实现的，虚函数允许子类重写 override(注意和 overload 的区别，overload 是重载，是允许同名函数的表现，这些函数参数列表/类型不同）。 注：多态与非多态的实质区别就是函数地址是静态绑定还是动态绑定。如果函数的调用在编译器编译期间就可以确定函数的调用地址，并产生代码，说明地址是静态绑定的；如果函数调用的地址是需要在运行期间才确定，属于动态绑定。 目的：接口重用。封装可以使得代码模块化，继承可以扩展已存在的代码，他们的目的都是为了代码重用。而多态的目的则是为了接口重用。 用法：声明基类的指针，利用该指针指向任意一个子类对象，调用相应的虚函数，可以根据指向的子类的不同而实现不同的方法。 用一句话概括：在基类的函数前加上 virtual 关键字，在派生类中重写该函数，运行时将会根据对象的实际类 ...