LeetCode 456: “132” Pattern

这个题是昨晚上回寝室前赶出来的,因为看到是Medium而且感觉不难(实际也不难)。

原题:https://leetcode.com/problems/132-pattern

题目意思是,判断一个数组是否包含子序列ai、aj、ak(i<j<k),满足ai<ak<aj

好像跟一般领奖台是反着的,但是可以直观理解题意。
好像跟一般领奖台是反着的,但是可以直观理解题意。

主算法

思路是遍历每一个可能的k值,然后找到它之前第一个(也就是距离最近的)比它大的数作为aj,然后再判断a0~aj-1之间的最小值是否小于ak

之所以要找到“第一个”比它大的数,理由也很明显:要尽量扩大找ai的范围,否则可能会有false negative的情况。

思路很简单,关键是如何做到O(n)。因为遍历每一个k的过程就是O(n)的,所以要求后面两个步骤都是O(1),也就是要预处理。预处理最小值很简单,开一个数组记录一下即可,空间复杂度O(n)。预处理“之前第一个比ak大的数(的位置)”就比较麻烦了,放在子算法里说,空间复杂度也是O(n)。

因此最终算法分三步:预处理a0~aj的最小值,预处理ak之前第一个大的数,遍历每一个可能的k。

子算法

要预处理每个数之前第一个比它大的数,用到了之前一个stack的奇技淫巧。方法是维护一个pair<数, 位置>的stack,其中数是递减的;对于数组从头到尾遍历,每个数先将栈顶比它小的数pop出去,如果pop完了栈空了,说明前面没有比它大的数,此时预处理结果为-1;否则预处理结果为栈顶数的位置。处理完之后将当前pair<数, 位置>也push进栈。

原理:因为要找到之前第一个比它大的数,如果栈顶的数比当前数还小,那对于它们之后的数来说,当前数更可能是比后面数大的结果,所以将栈顶pop出去。因为每个数最多进出栈一次,时间复杂度O(n)。

C++代码

因为写的很赶,好多边界都没care,其实应该还有能优化的地方(因为运行时间才到beat 55%的位置……)

理解 React Native 的 FlexBox 排版模型

这两天尝试用 React Native 写了一个 APP,总体感觉是个好东西。目前没有 macOS 环境,没法测试 iOS 上的表现,但是安卓上是不错的。

在设计界面的过程中,如何正确排版、正确使用 FlexBox 模型就成了一个关键问题。其实这里的 FlexBox 跟 CSS3 中新加的那个 FlexBox (Flexible Box) 基本上是一样的,所以通过 MDN 上的这篇文章可以了解 FlexBox 的基础知识,例如主轴和侧轴、每个轴的元素排列等。另外,SegmentFault 上有一篇关于 React Native 布局的文章也不错,介绍了 FlexBox 排列元素时,遇到多个 flex 元素或有固定大小的(不 flex 的)元素,会怎样安排他们的大小。

假定读者阅读了上面两篇文章,明白了基础知识。接下来我结合 APP 中的实例来讲一下使用 FlexBox 过程中遇到的问题、解决方法和对 FlexBox 模型的理解。

考虑如图所示的 UI,上面是一个固定高度的标题栏,其中包含左右各一个固定大小的按钮,中间的文字填满剩余空间;下面是很长的内容,可以上下滚动,滚动时标题栏一直在最上面不动。

首先整个界面的顶层 <View> 标签,其 style 应该包括: {flex: 1, flexDirection: 'column',} ,这样内部元素就会上下排布。标题栏我额外定义了一个 Header 类( class Header extends Component {} ),因此 <View> 的第一个子元素就是 <Header style={...}>(标题栏子元素)</Header> 。这里要注意的是,给 Header 定义 style 本身没有任何效果,应该在 Header 类的 render() 方法中,将其实际顶级元素的 style 附加上 this.props.style,即  <View style={[header_styles.basic, this.props.style]}>...</View>

然后看 <Header> 对应的 <View> 的 style。由于 <Header> 本身是固定高度的,因此可以肯定它不是 {flex: 1} 的。但是我们又想使用 FlexBox 中的排版功能,对标题栏中的元素横向排版,所以在顶层 <View> 中再嵌套一层 <View>,它的 style 应该是这样的:

接下来看内层 <View> 的子元素。首先是左上角、右上角的图标,这里我用的是 react-native-vector-icons,就是两个 <Icon> 元素,它们都是固定大小的(其实就是一个特殊字符),因此我们需要中间的标题 <Text style={{flex: 1}}> 以填满剩余空间。这里就看出来,{flex: 1} 的意思就是这个元素的长宽可以任意放大(或缩小),以适应排版的需要。

这样 <Header> 部分就搞定了,接下来看正文的滚动部分,这里用的是 React Native 的 <ScrollView> 元素。通过文档中看出,ScrollView 是由一个外层短元素包含一个内层长容器,外层短元素可以是固定高度(height)的或 flex 填满剩余高度的,但内层容器应该是内容的实际高度,而不应该是 flex 的。这里文档写的很迷茫(“把 flex 从视图栈向下传递”,并没有看明白哪里是栈、哪里是下……),我是踩了很多坑才搞明白这是什么意思。主要代码如下:

这个 <ScrollView> 在顶层 flex <View> 中,将其设为 {flex: 1} 即可填满除 <Header> 以外的剩余屏幕高度。但是 contentContainerStyle 控制的内层样式绝不应该有 {flex: 1},否则会被缩小到与外层元素一样高,裁剪掉多余的内容,因此无法实现滚动。这里与 <Header> 中类似,内部长内容可能还有更复杂的排版(比如进一步上下/左右分割),所以可以在 <View> 子元素的 style 上下功夫,比如设为  {flex: 1, flexDirection: 'row',} 即可将内部元素再左右排列。

下面提供一些我的 APP 中实现上述布局的代码(省略了逻辑和内容,只保留排版相关的代码,最终效果类似于 Material Design),供读者参考:

 

激活(或重新激活) Bitbucket 教育套餐

我在 2011 年的文章“大学生免费申请 Bitbucket 帐号”中曾经介绍过,Atlassian 免费为在校大学生提供无限用户的私有 Git 和 Mercurial 代码仓库。现在国内很多服务(例如 [email protected])也提供了类似的服务。

Bitbucket 现在做了更新,只要在账户中添加一个现有的 .edu(包括 .edu.cn)邮箱,即可自动开通教育套餐,享受私有仓库无限个用户(collaborators)。但是像我今天手滑把套餐点成了“Free”,就降到了 5 个用户,而且不能直接改回来。

为了防止其他人也犯类似错误,这里提供一个补救方法:

  1. 先将账户中其它邮箱设为主邮箱。在右上角点击“头像–管理账号”,然后在左边点击“邮件地址”,将除了 .edu 邮箱之外的另一个邮箱“设为主要的”。
    • 如果只有一个 .edu 邮箱,则需要先添加一个其它邮箱,验证并设为主要邮箱。
  2. 删除用于教育认证的 .edu 邮箱。
  3. 重新添加并认证 .edu(包括 .edu.cn)邮箱,认证后在左侧“套餐明细”中,即可显示为Academic,用户数量为 Unlimited。

现有32位 C++ 工程修改为64位编译,以 OpenCV 为例

好久没有更新了,今天介绍一下我的一个32位OpenCV C++工程如何修改为64位下编译。

  1. 确保 Visual Studio (Visual C++) 已经带有x64编译器。

如果使用的是完整版VS,在安装时会有选项。如果使用 Express(速成版),则根据微软官方介绍,还需要安装“Windows 软件开发工具包 (SDK)”。

  1. 将工程配置修改为x64。

 

如图,首先在工具栏中,点击(默认为)“Win32”–“配置管理器”。

然后如果在“活动解决方案平台”下没有“x64”,先点击“新建”,在“键入或选择新平台”下选择“x64”并确定。

在添加x64平台之后,在下面将需要64位编译的工程后面设置为“x64”。

  1. 将外部库也设置为对应的x64版本。

这里以 OpenCV 的二进制预编译库为例,在 build 文件夹中可以找到 x64 (32位为 x86),再找到对应的编译器下对应文件,并在属性页中配置好即可。

  1. 编译程序,如果有问题则修改代码。

这里建议阅读官方的“Visual C++ 64 位迁移的常见问题”(见参考资料),尤其要检查指针、size_t和int/long类型之间的兼容性问题。

 

参考资料:

[1] 如何:针对 64 位平台配置 Visual C++ 项目 – MSDN

[2] Visual C++ 64 位迁移的常见问题 – MSDN

非营利组织或大学生免费申请Bitbucket无限账号

最近需要做一个学校的项目,用Mercurial做代码管理,在Bitbucket上申请了一个免费5用户账号,然后看到他们提供给非营利组织(NPO)和大学生免费申请无限账号(原价$80每月)的机会。

Atlassian Bitbucket网站:https://bitbucket.org

首先说一下何为无限账号:Bitbucket提供每个用户无限公开和私有库,唯一限制的是对私有库有读写权限的帐户总数。默认的免费账号,可以总共有5个帐户对你的私有库进行读写;无限账号则有无限的名额,但是每月需要付80美元的费用。

1. 首先,你需要是大学生(University student)或非营利组织(Non-profit organization member)成员的身份,而且你需要进行非开源的工程(开源工程可以使用公开库)。

2. 大学生帐户的话,需要使用学校邮箱(大陆是.edu.cn结尾,米国是.edu结尾)注册一个帐户(作为主地址,而不能作为备用地址添加到其他帐户里);非营利组织则需要准备组织的各种资料。

3. 填写对应的表格:大学生申请表 / 非营利申请表

4. 对于大学生表格的填写要求:正文部分要全部用英文填写(包括地址,翻译一下,大学生这点技能没问题吧)。学校网站要写你们学校首页,最好能把英文首页地址和其他重要信息填在附注(Additional notes)部分。至少我就这样填写,申请过了。

    对于非营利表格的填写要求,请仔细阅读申请表页面的注释。

5. 提交表格,等待人工审核。他们没说具体审核时间多少,应该一天之内都能审核完吧。审核通过后,你的账号里就会显示为无限账号(Unlimited users)的套餐了。(点击网页上的Account链接,右下方即可看见。)

注意:很幸运能有一家公司提供这么好的方案,为我等穷学生提供一个免费的Hg代码服务器。希望不是大学生和NPO身份的人、有工作有项目收入的人就不要申请了,任何服务只要国人多了都会下场悲惨,请手下留情,留给真正需要的人吧。