回溯法:Xenia and Weights
问题描述
给定 n 种砝码,重量位于区间 [1,10] ，不同种类砖码重量互不相同,且每种砝码的数量不限。轮流在天平两侧放砖码，要求：每次所使用的砝码与前一次不同(第一次可以为任意重量)，且当前放置砝码的一侧放置砝码后比另一侧重 。问能否进行 m 次操作，如果能，输出任意一种方案，如果不能，输出NO。
分析
思路大致和之前回溯法章节相同，只是需要左右两边分开处理。process() 的参数较多，这是因为笔者个人偏好 利用函数栈自动完成回溯法所需要的撤销操作，所以必须用参数（而且必须为值传递）；也可以用全局变量，然后再递归后手动撤销。 详细过程不再阐述，代码注释已经解释清楚：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include<iostream>#include<cstdlib>//rand()#includ ...
回溯法:超级幸运数
问题阐述
幸运数为 4 和 7，超级幸运数则是指因数只有 4 和 7 的数，比如 28，16，49 等。给出一个个数为 N 的数列，求其中幸运数的个数；数据范围：num>1, N>1；
分析
暴力破解不难，直接给出代码：
12345678910111213141516171819void comparator(int num){ if (num == 1) return; while (num!=0) { if (num == 1) { count_2++; break; } if (num % 4 != 0 && num % 7 != 0) break; if (num % 4 == 0) num /= 4; if (num % 7 == 0) num /= 7; }}
其中，第 3、5、12 行代码是容易忽略的地方。
那么，如何用回溯法解决此问题？不同于暴力破解对 num 的 拆分 (除、模)，回溯法是对 num 进行 拼凑 ，比如，对于数字 18，会尝 ...
冒泡、选择、插入排序
冒泡排序
冒泡排序网上有很多资料，只想强调几点：
固定往哪个方向冒泡，个人喜欢从左向右冒泡，不要一会向左一会向右，思绪易乱。
泡泡到达右边后，相应位置就固定住了，所以下一次无需再经过此处，于是内层循环还要减去外层循环已进行的次数。
冒泡时是第 K 个与第 K+1 个元素相比较，所以外层循环次数为 size-1 次即可，最后一个位置无需单独比较。
1234567891011template<class T, class comparator>void mySort(T* arr, int size,comparator cmp){ for(int i=0;i<size-1;i++)//注意-1！！！ for (int k = 0; k < size - i - 1; k++)//注意-i-1！！！ { if (cmp(arr[k], arr[k + 1]))//使用比较器 swap(arr[k], arr[k + 1]); }}
选择排序
选择排序也只须注意以下几个小坑：
外层目标位置 K 确定后，内层 ...
归并排序及其三道加强习题
归并排序(Merge Sort) 是利用归并的思想实现的排序方法，该算法采用经典的 分治(divide-and-conquer) 策略将问题分成一些小的问题然后递归求解，即分而治之。
递归实现
图解：
先递归将数组一分为二，直到不可再分；然后=依次将两边 合并(merge) ，合并的图解如下（以最后一次合并为例）：
注意，之所以能这样合并，是因为两边的子数组都是已经排好序了的！而子数组最终也是通过该方法从单个元素排序而来 。从图可知，我们需要 new 一个辅助数组来存放左右两边比较后的结果；注意，当 i 移到 7 位置时，7>6，将 6 放入辅助数组，然后 j++，于是 j 超出数组范围，此时就直接将左半边余下的 7、8 放入辅助数组 ，结束。
12345678910111213141516171819202122232425262728293031323334353637template<class T, class cmptor>void merge(T* vec, int l, int m, int r, cmptor cmp){ T* help ...
MySQL基础-表连接
交叉连接
交叉连接（CROSS JOIN）一般用来直接返回连接表的笛卡尔积。
交叉连接的语法格式如下：
123SELECT <字段名> FROM <表1> CROSS JOIN <表2> [WHERE子句]#或SELECT <字段名> FROM <表1>, <表2> [WHERE子句]
注意，
笛卡尔积示例：第一种方式为官方指定写法，语义更加清晰；第二种写法默认为交叉连接，如果想指定为内连接和外连接，就需要显式指定。
123456789101112131415161718192021222324252627282930313233343536373839404142mysql> SELECT * FROM stuinfo;+-------+------+-----------+------+| name | age | course_id | sex |+-------+------+-----------+------+| Jack | 18 | 23 | M || Mik ...
回溯法:填数字
问题描述：
有 7 对数字:两个 1 ,两个 2 ,两个 3 ,…两个 7 ,把它们排成一行。要求,两个 1 间有 1 个其它数字,两个 2 间有 2 个其它数字,以此类推,两个 7 之间有 7 个其它数字。如下就是一个符合要求的排列:
1 7 1 2 6 4 2 5 3 7 4 6 3 5
请列出所有满足条件的排列。
问题分析：
稍作分析我们就可以得到以下结论：
放数字时，不仅要在当前位置放，还需要在关联位置上放：
在 [4] 位置放置 3 时，也必须同时在 [8] 位置放置 3；
每放一个数字时，都需要将此数字标记为已放置。
放置数字时，必须在没有放置(未标记)的数字中 从小到大 试每个数字，直到能够放置或试完所有数字：
在 [9] 位置放置时，遍历 1,2,3,4,5 发现都已标记，于是尝试 6，不可；在尝试 7，不可；于是撤销上一步操作；
当发现某个空白位不能放任何数字时，说明之前的放置方式是错误的， 需要撤回上一次的放置 ，并放置其他数字，再重复以上过程：
在上图中，执行到第 6 步(箭头6)时陷入死路，于是撤回到第 5 步(箭头5)，并在此处尝试放置 ...
MySQL基础-数据操作(二)
基本格式：
1234567891011SELECT [DISTINCT]{* | <字段列名>}[ FROM <表 1>, <表 2>…[WHERE <表达式>[GROUP BY <group by definition>[HAVING <expression> [{<operator> <expression>}…]][ORDER BY <order by definition>][LIMIT[<offset>,] <row count>]]
注意，以上指令的输入顺序不能乱！
基础示例：
12345678910111213141516171819mysql> SELECT * FROM demo_0;+-------+------+------+--------+| id | name | age | addr |+-------+------+------+--------+| 33703 ...
数组的起始下标为什么为0?
x数组的起始下标为什么为0?
相信每一位初学者都曾吐槽过 C 语言的数组下标为什么从 0 开始，而不是从 1 开始，这样太不人性化了:smile: 。实际上，不仅是 C 语言，其他绝大多数语言的数组下标也是从 0 开始的，既然都如此设计，就必然有它的好处。下面我们就这个问题来进行粗略的讨论。
首要目标：为了方便计算出每个元素的具体内存地址：
a[0] 的内存地址 = a的地址 + 0 * 4 (第一个元素的地址计算结果跟数组的首地址一样)
a[1] 的内存地址 = a的地址 + 1 * 4 (下标是1,内存地址就就是首地址偏移 4 字节)
a[2] 的内存地址 = a的地址 + 2 * 4 (下标是2,内存地址就首地址偏移 8 字节)
…
a[5]的内存地址 = a的地址 + 5 * 4 (下标是5 内存地址就是首地址 偏移 20字节)
如果从 1 开始，每一步都要减去1,多一步运算,效率就相对较低；而从 0 开始，就无需减 1。
利于边界处理： 下面这张图胜过千言万语
将一个左闭右开区间“切割”时，其子区间也能很好的符合左闭右开的形式。例如：区 ...
初识复杂度与对数器
时间复杂度
务必细分过程，区别出常数操作和与 N 有关的操作。这也要求你对调用的 API 有一定熟悉程度！
对于插入排序这样会由于数据状态而影响到算法过程的，一律按最差情况统计复杂度！
冒泡和选择排序的算法性能是固定的，不受数据状态影响；而插入会受数据状态影响。后者性能大于前两者。
当两算法的复杂度都相等时(比如，冒泡和插入都为O(N2)O(N^2)O(N2)) ，就需要比拼各自的常数项时间。如何比拼常数项时间：
放弃理论分析,生成随机数据直接测 。为什么不去理论分析?不是不能纯分析,而是没必要。因为不同常数时间的操作,虽然都是固定时间,但还是有快慢之分的。比如,位运算的常数时间小于算术运算的常数时间,这两个运算的常数时间又小于数组寻址的时间 。所以如果纯理论分析,往往会需要非常多的分析过程（就比如，算术运算在某些时候可转为位运算，详见csapp）。常数时间不考虑在最优解范畴。
算法优劣：O(1)>O(logN)>O(N)>O(N×logN)>O(NX)>O(XN)>O(N!)O(1)>O(logN)>O(N)>O(N×logN) ...
MySQL基础-数据操作语言(一)
数据操作语句只适用于表，而无法作用于数据库，所以无需在操作关键词后添加 TABLE 关键字。
INSERT
INSERT 语句有三种语法形式：
INSERT...VALUES语句
12INSERT [INTO] <表名> [ <列名1> [ , … <列名n>] ]VALUES ({expr|DEFAULT},...),(...),...
示例：
123456789mysql> CREATE TABLE demo_0( -> id CHAR(12), -> `name` VARCHAR(32), -> age TINYINT, -> addr VARCHAR(32));mysql> INSERT INTO demo_0 -> (id, `name`, age, addr) -> VALUE('12336', 'QuanHa', 20, '四川');Q ...
