各种语言中的 Enum
C, C++, Java 和 Python 中的 Enum
枚举类是很多编程语言中都有的设计.
它最明显的用途在于给一系列编程中概念相关的但逻辑上在同一层次的事物编号.
大多数编程语言从,枚举类的定义语法类似类,
也就是说它们都将枚举类看成是一个特殊的类。同时,
它们一般允许定义的枚举名称在作用范围内按照整型常量随意使用.
还提供了自定义编号的特性.
C
基本语法
enum 枚举类名{ 枚举名1, 枚举名2, ... 枚举名n};
如果需要自定义编号,
采用枚举名 = 整型常量表达式的形式定义枚举名,
此时下一个枚举名的编号是整型常量表达式 + 1.
Java
在 Java 中,枚举类就是一种继承了 java.lang.Enum,
实现了 java.lang.Comparable 的 final 类,
可以定义类能定义的属性和方法.
枚举类可以有构造方法,默认私有.
基本语法
enum 枚举类名{ // 所有实例都必须在开头定义. 默认以public static final修饰. 枚举名1, 枚举名2, ... 枚举名n}
注意 ...
词语翻译问题
记录我遇到的各种词语翻译问题. 领域以信息技术为主但是不局限于信息技术, 语言也不局限于英语.
单调队列
使用单调队列
单调队列是一种主要用于解决滑动窗口类问题的数据结构.
时间复杂度为 O (n).
其原理就是一句话,当队列中前面的数比后面的小 (大) 时,前面的数出队.
实现上,维护一个双向队列,
遍历时仅当一个元素可能成为某区间的最值时才保留它.
代码
import collectionsmonotonous_queue = collections.deque()class Item(object): def __init__(self, i, v): self.index = i self.value = vitems: tuple[Item] = tuple()def front(): return monotonous_queue[0]def back(): return monotonous_queue[-1]for i in range(0, n): if not monotonous_queue.empty() and top().index <= i - length: monotonous_qu ...
为什么 C 和 C++ 中要引入头文件?
起源:为什么要有头文件
头文件在 1970 年原始的 C 中并不存在。代码的复用靠的是编译后的链接过程.
这也是当时语言的主流选择.
如此的一个最重要的原因是当时的程序设计哲学讲求二进制复用以兼容不同高级语言的编译产物.
因此,C 程序里可能存在对其它语言函数的调用。比起其它 C 程序,
这些函数对于 C 编译器来说更是一头糨糊.
编译的时候碰到这些函数只会识别为外部符号等待链接。既然如此,
没有任何必要为 C 程序单独处理,这也符合 C 语言尽可能简单易实现的哲学.
如此,函数声明也是不必要的.
事实上,现代的 C 程序依然保持这这种兼容性.
例如以下代码完全可以通过编译.
int main(){ puts("Hello");}
这里的 puts 就需要连接 stdio.h 才能正常调用.
那么一个很重要的问题就是,各个编程语言的数据类型风马牛不相及,
链接的时候怎么保证参数和返回值类型检查呢?
在当时根本不需要考虑这个问题。因为
当时的语言基本上都只有字长一种数据类型.
没错,C 语言的类型系统是后加的。因此为了兼容性,C 语言是弱类型的.
这类编程语言的函数调用 f(a, b ...
求解最长上升子序列
使用动态规划和贪心两种算法
最长上升子序列问题,就是对于一个有顺序的数列,
从中按顺序选择的尽可能元素 (可以不连续) 构成的新数列是单调递增的.
最长上升子序列问题在许多与图论,算法,随机矩阵理论,
表示论相关的研究都会涉及,
比如排列图中的最大团是由 ' 定义该图的排列中最长的递减子序列 ' 定义的,
求最长的递减子序列在计算复杂度上 (通过对所有数取它的负数) 等同于求最长的递增子序列.
因此,最长递增子序列算法可用于有效地解决排列图中的分团问题
动态规划
动态规划其实非常好想到。设 f [i] 为以第 i 个数字结尾的最长上升子序列,
则 for j in range(1, i): if nums[i] > nums[j]: f[i] = max(f[j] + 1, f[i]).
贪心
动态规划的复杂度还是有点高,有没有什么更好的办法。毕竟理论上,
我只要扫描一遍数组,这个序列长度就是一定的.
首先考虑的肯定是贪心。要想得到最长上升子序列,
这个序列的上升速度必须有,但是要尽可能的慢,
这样子后面才有更大的上升空间。要想让上升速度慢,
每次加到序列末尾的数字必须尽可能的 ...
Django 初探
Django 是一个用 python 写的 web 服务器。它的优势在于开发的简便性和低门槛,
高度强调可复用性和可插拔性。它内置了大量组建,
还自带与数据库联动的后台管理系统.
Django 初探
Django 采用 MTV 框架模式。即 Model, Template, View.
和现在流行的 MVC 在名称上不太相同.
MVC
MTV
数据模型
Model
Model
用户界面
View
Template
业务逻辑
controller
View
Django 提供了用于管理 Django 项目的命令 django_admin,
由他生成的项目骨架为
```项目名├── 项目名 // 项目全局文件目录│ ├── __init__.py│ ├── settings.py // 全局配置│ ├── urls.py // 全局路由│ └── wsgi.py // WSGI服务接口(暂时不用纠结这个是神马)└── manage.py ...
C++ 静态变量的使用
C/C++ 提供 static 关键字修饰变量,
而这个关键字在不同场合下的用法是在是千奇百怪,因此我决定做一个总结.
C 语言中的 static
首先,当 C 语言引入这个关键字的时候,它的意思可以概括为:
将被修饰的变量放到程序文件的数据段中. 因此,
它有如下特性:
修饰的变量的作用域最大为本文件.
修饰的变量的生命周期为程序运行期间,
因此可以在一个函数内定义一个静态变量而在外部引用它.
修饰的变量只初始化一次.
也因此,它有如下限制:
修饰的变量必须用常量表达式初始化.
修饰的变量不能出现在结构体内,
除非结构体也是静态的.(因为一个结构体只能使用一块连续的内存)
C++ 中的 static
C++ 继承了 C 语言的 static 用法,但是为了一时图方便,
就像承认 const 的常量性那样,允许静态变量用变量表达式初始化.
除此之外,C++ 引入了类,顺便用 static 来表示类域和类方法.
修饰的域和方法属于类而不是某个具体的对象。因此,它有如下特性:
修饰的类域初始化时不受所在类的访问修饰符限制.
因为它是属于类内部的域.
但是它有如下限制:
...
在 C++ 中指定内存位置创建对象
在指定内存位置创建对象
作为一门允许程序员自己操作内存的语言,
C++ 提供了三种方式在指定的内存位置创建对象.
而为什么要在指定位置创建对象呢?作用有三:
预先足够的分配内存,以便减少使用中分配内存的操作.
重复利用内存,减少内存碎片.
方便进行细粒度管理.
实现这个需求的方式有三种.
在接下来的文章中,我们使用如下类作为示例.
class Person { private: int age; std::string name; public: int get_age() { return age; } bool set_age(int a) { age = a; return true; } std::string get_name() { return name; } bool set_name(std::string &s) { name = s; return t ...
数组里的二叉树
用数组实现的二叉树的性质
二叉树 (其实二叉堆也是) 经常可以用数组实现,
但是有些操作可能不够直观需要特别留意
以下假设数组为 0 索引
数组长度
设 l 为数组长度,h 为二叉树高度,则
父子关系
设父节点为 f, 左右子节点为 cl 和 cr.
则 cl 一定为奇数而 cr 一定为偶数.
线段树详解
线段树的二三事
线段树有什么用?
作为一个比较复杂的数据结构能有如此的知名度,线段树一定有它的拿手绝活,
那么线段树能做什么呢?
简而言之,线段树可以高效地维护区间上对于某个操作结果的信息,
但这个操作必须符合结合律.
最有名的应用就是区间和。当然区间积,最值 (也可以用 ST 表) 也是可以的.
注意:线段树不支持动态添加节点,
因此如果需要修改区间长度的场合不能用线段树
线段树长什么样
从图上可以看出,线段树就是一颗二叉树.
其中的节点管理着一定区间内对应操作的结果.
父节点管理的区间是两个子结点管理的区间的并集.
子节点不断向自己的父亲节点传递信息,
而父节点存储的信息则是他的每一个子节点信息的整合.
线段树就是分块思想的树化,
或者说是对于信息处理的二进制化 -- 用于达到 O (logn) 级别的处理速度.
分块的思想,则可以用一句话总结为:
通过将整个序列分为有穷个小块,对于要查询的一段区间,
总是可以整合成 k 个所分块与 m 个单个元素的信息的并 ()().
但普通的分块不能高效率地解决很多问题,所以作为 log 级别的数据结构,
线段树应运而生.
分块的应用范围还 ...