数据结构、算法与应用 C++语言描述

第一章 习题25

子集生成法（Subset Generation）

三元素集{a,b,c}的子集是：{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。 这些子集又可以使用01序列来表示，分别是000,100,010,001,110,101,011,111。 0/1分别代表着 含有/不含 原集合中的对应元素。

输出n个元素的所有子集（以01序列的形式）。

在网上看了一下基本上最终输出的都是数组，但并没有按照题目输出01序列。所以我这里严格按照题目来解。

分析

子集生成是一个完全排列组合问题，包括退化情况空集，以及极限情况自身。 其他的情况分别是[1,n)个元素的任意组合。 所以如果递归的话，也就是每一次元素数量+1 或者是-1，如果不是输出01序列，那么输出的元素个数就刚好等于递归中的n。输出序列的时候，只需要在其他位置补0即可。而补0逻辑也可以反过来考虑，即默认是n个0 e.g. 0000，随着循环的i改变，在不同的位置上填1e.g. 0001,0010,0100,1000，这样更加便捷。

至此，已经有了算法的模型了：

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void subsetGeneration( T* const A, int len, string code = "", int focus = 0 ){

    if( focus > len ) return;
    if( focus == len ){ cout << string(len,'1') << endl; return; }
    if( focus == 0 ){ cout << string(len,'0') << endl; }

    if( code == "" ){ code = string(len,'0'); }

    code[focus] = '1';
    for( int i = focus; i<len; i++ ){
        code[i] = '1';
        cout << code << endl;
        code[i] = '0';
    }

    subsetGeneration( A, len, code, focus + 1 );
}
int main(){

    subsetGeneration( "abcd", 4 );
    return 0;
}

思考1 上述算法已经成功解题，但是思维略显复杂，直觉上就感觉不是一个优质解。

- 阅读剩余部分 -

遇到这个问题的时候在网上搜索 绝大部分都是同样的一个解决方案 就是改一下软件的某个设置。 这个方法是十分不严谨的，所以网仔细琢磨了一下这个错误说明。

首先看一下官方给的说明： 微软 - 编译器错误 C2760

有多种方法可导致此错误。 通常，它是由编译器无法识别的令牌序列引起的。
There are several ways to cause this error. Usually, it's caused by a token sequence that the compiler can't make sense of.

这里实际上是表示有某个标识符，无法被编译器识别。而问题不一定出在最后的“;”。

这个时候我也是很头大，因为我的代码简单明了，没有任何有问题的字符。

这里最好的方式是检查一下类的定义和使用 比如说你定义了一个 A类，但是在引入这个类声明之前，就已经在使用了，就会报这个错误。

最终，我找到了问题，由于我使用的 FibonacciHelper类，定义在了使用之后，这个时候类还没有定义，所以会被当成一个标识符，而此时编译器不认识这个标识符所以出现了一些难以理解的错误说明。

把类的定义放到该文件的上方，（ 有的时候这种问题和 .h文件导入位置有关系。 ） 譬如导入的 .h文件中的类 在导入之前就使用，也会有同样的问题。

int main{
    TestClass t;
}

class TestClass{
    // ...
}
// 报错

TestClass c;

#include "TestClass.h";
// 也会报错

ZangoDB是一个indexedDB的类MongoDB轻量级接口库，主要是为了更轻松快速的编写indexedDB相关的操作。

关于indexedDB: IndexedDB - MDN

Github: ZangoDB

在MDN的推荐中介绍了几款不同的轻量级类库 来简化indexdb的使用，其中dexie.js也是不错的，但是在多条件筛选上并没有支持，所以介绍一下ZangoDB。

对于熟悉MongoDB这类NoSQL的开发者来说，应该简单看一下文档就能够快速上手。这里我将会对熟悉关系型数据库的来做一下说明。

ZangoDB主要将indexedDB简化为3个对象

Db - 数据库

Collection - 集合(表)

Cursor - 游标 查询( SQL )

不同于关系型数据库的初始化时数据库,表,所有字段名称和类型,索引结构都要确定。

NoSQL数据库通常只需要建立数据库的名称，表名称以及需要索引的字段。 其他的数据可以任意存储。

ZangoDB的主要特性集中在运算符的部分，类似于SQL中的( GROUP BY, ORDER BY 等 ) 包括以下几类

文末会给出更详细的介绍

Filter Operators 筛选查询运算符

Expression Operators 表达式运算符

Update Operators 更新运算符

Group Operators 组运算符

- 阅读剩余部分 -

最近在基于chrome开发一个用于收集和整理 信息（知识）的插件，名称叫Memoreasy。 一贯以来我都是用自己写的AppSiteJS框架在写web前台的功能，很少去涉及到异步编程，一般来说也就只是在XMLRequest( Ajax )的时候会用。

而在开发chrome插件的时候，几乎所有的api都是异步API，在第一时间的时候还是让我有些不适应。

但是很多时候理解一个技术或者说模式，最重要的并不是强迫自己去理解很多别人的说明、解释或者说代码。最关键的是需要以一个好的思路领会到这个概念的精髓。

我们先说同步编程，大家肯定不陌生，最初学习编程的时候我们都是使用同步编程，同步编程就好比工厂的流水线。

我们在进行同步编程的时候 每一个后续的步骤都依赖于前一步的计算或结果（返回值），如果其中一个过程出现问题，那后续的工作也无法继续了。 换言之，我进行后续工作的时候肯定已经获得了前一步的结果了。 从我们的思维习惯上来讲，这个过程的可控性是很好的。

// 一个简单同步编程的代码说明
var a = "hello", b = 10;
var u = getUseid();
if( u ){
    var obj = { text: a, number: b, user: u };
    console.log(obj);
}else{
    console.log( 'user not found' );
}
function getUserid(){
    return localStorage.getItem('userid');
}

在这段程序中，无论是否找到userid 控制流程实际上还是在当前这段代码中的。 这相当于开发者是公司的老板，让员工去完成一些任务，且无论完成的如何，都需要向老板汇报，然后老板再向员工发布下一步的任务。 这就是我们常识中的“集权"。 我们喜欢同步编程，也就是喜欢他的掌控度。

但是同步也会遇到问题。譬如说，从网络中请求数据(Ajax)时我们无法掌控对方的后续结果。 这就相当于我们在网上下单购物，快递走哪里，什么时间到什么位置，会不会被堵车，会不会在仓库里被堆积，被哪个快递员投递等等。 这种情况我称之为不可控编程，在这个时候，我们不可能一直在手机前面全程跟踪一直到收到商品，我们一般放下手机该吃吃该喝喝，等待快递员的电话。 其实我们也早已习惯了“放权”，只是在编程中，我们需要对那些习惯做一些适应。 来看一段示例代码：

// 购物异步编程 仅供参考 完全不严谨！

function 购物( 订单 ){
    return Promise( 付款之后, 没给钱 ){
        给钱( 订单.价格 ).then( function(){ 
            付款之后( 订单 ) 
        }).catch(function(){
            没给钱()
        })
    }
}

function 发快递( 订单 ){
    var 包裹 = 商家打包( 订单 ); // 打包好了才能发包裹，所以需要同步
    return Promise( 到货, 丢了 ){
        发货().then( function( 包裹 ){
            到货( 包裹 )
        }).catch(function(  ){
            丢了()
        })
    }
}

function 到货( 包裹 ){
    return Promise( 在家, 不在家 ){
        打电话( 包裹.收件人 ).then( function(){
            在家( 包裹 ); // 送货上门
        }).catch(function(){
            放到快递柜( 包裹 )
        })
    }
}

这里我们定义了多个购物相关的异步方法，而我们在调用的时候就很简单了

购物( 订单 ).then( 发快递 ).catch( 弹窗提示 );

是不是感觉打开了新世界，因为发快递之后的事情我都不用管了，放权也是很爽的。

Flex布局 在CSS中是当前最流行的布局方式，并且在移动端以及较新的pc浏览器有着很高的支持度，基本上已经可以完全替代传统的 float, inline-block 各种混合的布局方式了。

flex布局因为是比较新的标准，所以在设计之初就着重解决了纵向排布的问题。而之前的css布局方式，对于纵向布局做的比较少。诸如纵向居中对齐、纵向铺满都是需要花费不少力气来处理。

当前的现代浏览器中 flex layout支持度已经超过98%

Flexible box - Can I use

CSS 弹性盒子布局是 CSS 的模块之一，定义了一种针对用户界面设计而优化的 CSS 盒子模型。在弹性布局模型中，弹性容器的子元素可以在任何方向上排布，也可以“弹性伸缩”其尺寸，既可以增加尺寸以填满未使用的空间，也可以收缩尺寸以避免父元素溢出。子元素的水平对齐和垂直对齐都能很方便的进行操控。通过嵌套这些框（水平框在垂直框内，或垂直框在水平框内）可以在两个维度上构建布局。

Container Style 容器样式:

flex可以提供block和inline两种对外效果。但是并不影响内部元素。因为内部元素会被设定为flex项目。

设置一个flex容器:

设为 Flex 布局以后，子元素的float、clear和vertical-align属性将失效。

.flex{
    display:flex;
    display: -webkit-flex; /* Safari */
}
.inline-flex{
    display:inline-flex;
}

- 阅读剩余部分 -

使用phpDocumentor可以快速根据规范的注释生成一整套接口文档，是进行php开发十分便利的工具。 有时候我们会在自己的框架内引入别的库，这个时候一键生成文档会导致将库文件一起分析，不仅速度很慢同时也会导致生成的文档出现不必要的内容。

可以使用 -i,-ignore 设定屏蔽文件夹的参数 可以参考官方文档:

project:run

-i|–ignore[”...”]
Provide a comma-seeparated list of paths to skip when parsing.

在使用phpar命令进行生成的时候，需要注意使用 --igonre 或 -i

参考如下:

sudo php /Library/WebServer/Documents/phpDoc/phpDocumentor.phar  -d /Library/WebServer/Documents/appsite-new/server -t /Library/WebServer/Documents/docs/appsite-new/doc --ignore library/ custom/ demo.php

如果有多个目录，使用 and 进行分隔，单一文件使用完整文件名结尾，文件目录要以/结尾。

旧版本官方文档 using.command-line.ignore

-i, --ignore
Use the -i option to exclude files and directories from parsing. The -i option recognizes the * and ? wildcards, like -f does. In addition, it is possible to ignore a subdirectory of any directory using "dirname/".

phpdoc -i tests/ will ignore /path/to/here/tests/* and /path/tests/*

phpdoc -i *.inc will ignore all .inc files

phpdoc -i *path/to/* will ignore /path/path/to/my/* as well as /path/to/*

phpdoc -i *test* will ignore /path/tests/* and /path/here/my_test.php

Since v1.3.2, the value or pattern you provide will be case-sensitive (OS permitting, anyway), and will be applied relative to the top-level directory in the -d argument.

phpdoc -i CVS/ will ignore /path/to/CVS/* but will not ignore /path/to/cvs

phpdoc -d /home/myhome/cvs/myproject -i cvs/ will ignore /home/myhome/cvs/myproject/files/cvs/* but will not ignore /home/myhome/cvs/*

基于最近考虑着手iOS 安卓 双平台的开发，整理了一下现存的一些跨平台开发思路。

为了让自己更直观的感受不同跨平台思路的差异，我简单的做了几个图示。

套壳模式

微信公众号H5(相当于) , jQuery Mobile ?

套壳模式是开发APP可以说是最简单快捷的（对于web开发者来说），基本上只要有一个正常能用的手机端可以UI适应的web就可以通过套一个壳完成APP开发。 套壳的问题主要有2个

1. 体验不好，完全通过套壳的webapp 从性能以及UI交互上来说都会比原生app差，通过对js、css的优化，可以解决一部分，比如说click事件在手机端应当用tap事件(封装tap事件)，另一部分解决不了，比如说iOS端的侧滑返回或侧滑删除功能，这个体验如果要靠js来实现，效果当然是可以写出来的，但是流畅度、细节表现大大不如原生，而且会花费比较多的时间，而且没有什么这一块比较好的库可以用。
2. 没有原生功能支持,在微信公众号h5中，还可以通过微信的JSAPI调用部分微信提供的功能，譬如说存储图片。但是套壳在app里的时候，就完全没有办法支持了。

Web 框架模式

Dcloud H5 plus (SDK)

除了Dcloud h5 目前没有发现明确的web框架模式，这里的web框架模式主要是指以web形式开发，通过特定的SDK或者插件api访问app原生功能，不需要使用该框架特定的打包流程，支持以sdk嵌入等方式构建app的。

Web框架模式相对来说简单，快速。不用深入学习原生的内容即可快速使用原生平台的能力，通过插件的扩展也能提高一定程度上的体验效果。

- 阅读剩余部分 -

在进行iOS应用开发的时候，经常会用到带有图标的按钮。

最近在更新账号小助手的时候，我发现xcode更新了一系列的系统图标，而且下拉一看都是十分规范而精美的，涵盖的内容也很丰富，这对于我们这样的独立的开发来说可以说是雪中送炭。

在网上搜一搜，不难发现这些系统图标是源自于2019WWDC大会的发布，并且苹果官方给了一套说明，甚至还有一个方便查找的mac app 传送门: Human Interface Guidelines - SF Symbols

而在具体的开发时，也还是能发现一些问题。

- 阅读剩余部分 -

``最早的时候博客是使用的WordPress搭建，基于一些原因( 使用Typecho搭建一个极简又好用的技术博客 )，去年选择了用typecho重做。

重构博客之后的很长一段时间都没有去看搜索引擎的收录状态，最近发现在百度、搜狗都只有一个首页收录，但是bing是有大量收录的。而这在以前WordPress搭建时不可能出现的，所以开始着手解决一下。

参考: 浅谈typecho百度收录问题

- 阅读剩余部分 -

在使用Xcode进行iOS手机APP开发的时候，最方便的方式就是数据线连接手机，这样无需任何设置就可以直接开启真机调试。

同样，在无需发布到App Store的一些临时用APP的安装也可以用这个方式！

由于最近数据线经常不好用，而且同时需要在不同分辨率的设备上调试，如果同时插多跟线亦或是一会换一个就会造成非常不方便的情况，那么基于网络进行真机调试就显得非常有必要了。

- 阅读剩余部分 -

1. tableView下方出现莫名的空白

1. tableFooterView问题 一般来说，tableview会默认有一个footerview 解决:在视图加载时将这个footerview设为没有高度或者是空view就可以

   tableView.footerView = UIView()
   tableView.footerView.height = 0

2. contentSize自动计算问题 tableView会有一个自动计算contentSize的功能 即我们改变dataSource里的数据刷新视图的时候，tableview的总高度是被改变的，而这时自动计算出来的，不像scrollview是需要手动指定的。这时如果系统计算的预估值出现误差就会出现空白的问题。 解决: 设置tableView的自动预估值为0

   tableView.estimatedRowHeight = 0

- 阅读剩余部分 -

最近刚更新 macOS 10.15 Catalina，写一个新的ios项目的时候发现，pod突然不能用了。提示找不到文件。 与此同时，打开bash的时候还在提示几行英文。 仔细一看，是推荐换一个命令行的工具，叫zsh。通过复制系统提示可以一键切换过去。

zsh: /usr/local/bin/pod: bad interpreter: /System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin: no such file or directory

切换完了之后尝试使用pod 依然提示找不到文件。于是在网上搜索。

- 阅读剩余部分 -

在使用SwiftyJSON做数据传输的时候，经常需要从JSON格式中取值到对象中，在开发ios应用时，对象的字段和类型通常也是固定的，如何在接口获取到数据的时候优雅的进行类型转换是一个很值得考虑的细节。

优雅不仅是在可读性上提高，同时也方便后期对于数据格式的管理维护。

否则每次做细节调整的时候，需要查找所用的工作量就不可小觑了。

在网上也有通过反射机制来实现所有类自动转换的，见参考1。逻辑上是成立的，没有仔细研究。实际测试发现无法转换（与语言版本等可能有关）。

这里我先用比较务实的方式，做一层封装。主要完成的是将JSON赋值操作，写入到对象的结构体中，这样的话我们就不用在业务流程中进行复杂的赋值操作了。

1. 设计一个用于支持JSON互转的接口

这里我设计了两种初始化的方式，实际上一种就够了 主要是调用的时候写法略有不同，且便捷初始化开销更小一点。 我个人会喜欢以函数名来区分不同的运作方式，所以额外增加了静态的fromJSON方法

- 阅读剩余部分 -

想要做好iOS的应用开发，深入的理解Cocoa框架是十分重要的。 今天做一下自上而下梳理，这样在开发的时候会更清晰，遇到问题也可以更容易的找到方向。

OS X架构中的Cocoa

iOS架构中的Cocoa

Cocoa

Mac OS X上五大API之一 Cocoa, Carbon, POSIX, X11, Java

- 阅读剩余部分 -

字符串替换

REPLACE ( fieldname, search, replace )

字符串截取

substring

length()： 单位是字节，utf8编码下,一个汉字三个字节，一个数字或字母一个字节。gbk编码下,一个汉字两个字节，一个数字或字母一个字节。 char_length()：单位为字符，不管汉字还是数字或者是字母都算是一个字符。

SELECT substring(poetry,1,length(poetry)-1) FROM `bless_lot`
SELECT substring(poetry,1,char_length(poetry)-1) FROM `bless_lot`

带有中文的截取应该使用 charlength，因为substring切的时候按照字符位数切

数据去重

DELETE ...

DELETE FROM table_copy 
WHERE key IN ( 
    SELECT t.key FROM (
    SELECT key FROM table_copy GROUP BY key having count(*) >1
    ) t
) 
AND id NOT IN(
    SELECT t.id FROM (
    SELECT id FROM table_copy GROUP BY key having count(*) >1
    ) t
)