C++笔记—基础语法(1)
main 执行之前和之后执行之前:
设置栈指针
初始化static 和global变量
将未初始化的global变量赋初始值short/int/long=0,bool=false,pointer=null
全局对象初始化,调用构造函数
将main的argc/argv传给main
attribute((constructor))
main执行之后:
全局对象的析构函数
atexit函数
attribute((destructor))
指针 Pointer和引用 Reference
指针可以在声明时不初始化,可以稍后赋值,并且可以重新赋值,指向不同的对象。引用必须在声明时初始化,一旦初始化后就不能改变引用的对象。
指针可以为空(nullptr),表示不指向任何对象。引用不能为空,必须始终引用一个有效对象。
指针可以有多级,如指向指针的指针。引用只能有一级。
指针可以进行算术运算,如++或—,引用不能进行算术运算。
指针本身占用一定的内存空间(通常是4bytes(32 bit)或8bytes(64 bit));引用不占用额外的内存空间。
指针是一个变量,存储的地址,而引用等 ...
如何选择和优化排序算法
如何选择排序算法数据规模:
小规模数据(<1000):插入排序、选择排序
中等规模:快速排序、归并排序、堆排序
大规模数据:快速排序、归并排序、基数排序
数据类型:
整数:计数排序、基数排序
浮点数:快速排序、归并排序
字符串:基数排序、快速排序
内存限制:
内存充足:归并排序
内存受限:堆排序、原地快速排序
稳定性要求:
需要稳定:归并排序、插入排序
不需要稳定:快速排序、堆排序
数据分布:
近乎有序:插入排序
完全随机:快速排序
大量重复元素:三路快排
是否并行:
需要并行:归并排序
不需要并行:快速排序
不同排序算法的比较和应用场景快速排序:场景:通用场景,特别是随机分布的大规模数据
优点:平均情况下最快
缺点:最坏情况性能差,不稳定
归并排序:场景:需要稳定排序,外部排序
优点:稳定,性能稳定
缺点:需要额外空间
堆排序:场景:大数据集,需要找出最大/最小的k个元素
优点:空间效率高,最坏情况也是O(n log n)
缺点:不稳定,实际运行时间often比快排慢
插入排序:场景:小数据集,几乎已排序的数据
优点:简单,对小数据集很高效
缺点:大数据集效率低
计 ...
排序算法c++实现
常见排序算法稳定排序算法:
冒泡排序(Bubble Sort) — O(n²)
插入排序(Insertion Sort)— O(n²)
桶排序(Bucket Sort)— O(n); 需要 O(k) 额外空间
计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
合并排序(Merge Sort)— O(nlogn); 需要 O(n) 额外空间
二叉排序树排序 (Binary tree sort) — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
基数排序(Radix sort)— O(n·k); 需要 O(n) 额外空间
不稳定排序算法:
选择排序(Selection Sort)— O(n²)
堆排序(Heapsort)— O(nlogn)
快速排序(Quicksort)— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
排序算法的稳定性稳定性定义: 如果排序前后,相等元素的相对顺序保持不变,则该排序算法是稳定的。
(不稳定)快速排序(Quicksort)— ...
滚动哈希&Rabin-Karp算法
滚动哈希是一种快速计算字符串哈希值的方法。它利用字符串前后子串的关系,只需要 O(1) 的时间就可以计算新的哈希值。
字符串的Hash codeb 是选择的基数,来作为各个位数上的区分,一般b取131或1331等质数
p是用来规避哈希冲突的,是大的素数
初始子字符串的哈希值对于长度为 m 的子字符串 S[0..m-1],其哈希值计算如下:
H(S[0..m-1]) = S[0] \times b^{m-1} + S[1] \times b^{m-2} + \ldots + S[m-1] \times b^0 \% p滚动更新哈希值假设已经计算了子字符串 s[r] 的哈希值 H(s[r]),现在需要计算子字符串 s[r+1] 的哈希值。可以使用以下公式滚动更新哈希值:
H(s[r+1]) = H(s[r]) \times b + s[r+1] \% p前缀和当我们需要计算子串 s[l, r] 的哈希值,只需要利用前缀和思想(注:hashCode之间相减,得到的hashCode有可能是负数):
H(s[l, r]) = (H(s[r]) - H(s[l-1])\times pow(b,r ...
日麻符的介绍
日麻中符的计算符:把所有的项目加起来,然后向上取10的倍数。例如,合计34符的话,就进到40符。
非特殊牌型
符底/副底/底符:20符
门前清荣和:+10
自摸:+2
嵌张、边张、单钓听牌:+2
自风,场风,三元牌的雀头 +2 符
中张牌
幺九牌 风牌 三元牌
明刻
+2
+4
暗刻
+4
+8
明杠
+8
+16
暗杠
+16
+32
特殊牌型
七对子 : 固定25符
门前平和自摸 : 20符
副露平和型的荣和 : 30符
小技巧跳符的法則
手牌只有一個刻子,除非是么九暗刻,否則都不會有跳符。
食斷的牌,沒有開槓的話99%都不會有跳符。
沒有役牌雀頭,而且是良形聽牌(不包含2345亞兩面的假單騎)時,要最少有兩組暗刻才會跳符。
三暗刻必定會有跳符
速找符数
1.手牌是不是平和或七對子?→平和:自摸是20符,榮和是30符→七對子是25符→兩者皆不是,跳到22.是不是食斷?→是:絕大部份都是30符→不是:跳到33.有沒有上面提過的跳符形態?→有:門前榮和是50符,其他情況下是40符→沒有:門前榮和是40符,其他情況下是30符
親の点数早見表
...