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++代码

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.empty()) return false;
        int n = nums.size();
        vector<int> min1(n);
        min1[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            min1[i] = min(min1[i-1], nums[i]);
        }
        typedef pair<int, int> pii;
        stack<pii> s;
        vector<int> max1;
        for (int i = 0; i < n; ++i) {
            int I = nums[i];
            while (!s.empty() && s.top().first <= I) s.pop();
            if (s.empty()) {
                max1.push_back(-1);
            } else {
                max1.push_back(s.top().second);
            }
            s.push(make_pair(I, i));
        }
        for (int i = n-1; i >= 0; --i) {
            int I = nums[i];
            int j = max1[i];
            if (j == -1 || j == 0) continue;
            if (min1[j-1] < I) return true;
        }
        return false;
    }
};

因为写的很赶,好多边界都没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 应该是这样的:

container: {
  flex: 1,
  flexDirection: 'row', // 子元素横向分布
  justifyContent: '', // 这个无所谓,因为子元素要占满整行
  alignItems: 'center', // 竖向居中线排列
},

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

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

<ScrollView style={{flex: 1}}
    contentContainerStyle={{...}}>
  <View>...很长的内容...</View>
</ScrollView>

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

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

class Header extends Component {
  render() {
    return <View style={header_styles.header}>
      <View style={header_styles.container}>
        {this.props.children}
      </View>
    </View>;
  }
}

const header_styles = StyleSheet.create({
  header: {
    backgroundColor: "#2196F3",
    height: 60,
    paddingLeft: 20,
    paddingRight: 20,
    shadowRadius: 2,
    shadowOffset: {width:0, height:2},
    shadowOpacity: 0.7,
    shadowColor: 'black',
    elevation: 2,
  },
  container: {
    flex: 1,
    flexDirection: 'row',
    flexWrap: 'nowrap',
    justifyContent: 'flex-start',
    alignItems: 'center',
  },
});


class Single extends Component {
  render() {
    return <View style={single_styles.container}>
      <Header>
        <TouchableOpacity>
          <Icon
            name="arrow-left"
            size={20}
            color="#E3F2FD"
          />
        </TouchableOpacity>
        <Text style={single_styles.title} numberOfLines={2}>
          ...
        </Text>
        (注意:我的标题栏中只用了左侧图标,没有右侧图标。)
      </Header>
      <ScrollView style={single_styles.scroll}
        contentContainerStyle={single_styles.scroll_container}>
        <View>
          ...
        </View>
        <View style={single_styles.list}>
          <SingleLeft />
          <SingleRight />
        </View>
      </ScrollView>
    </View>;
  }
}

const single_styles = StyleSheet.create({
  container: {
    flex: 1,
  },
  scroll_container: {
  },
  list: {
    flexDirection: 'row',
    alignItems: 'flex-start',
  },
  scroll: {
    flex: 1,
  },
  title: {
    fontSize: 20,
    color: '#E3F2FD',
    marginLeft: 10,
    flex: 1,
    flexWrap: 'wrap',
  },
});

 

回忆今天的华为上机考试题

今天下午参加了华为在济南的上机考试(据说上午也有一批,题不一样)。回忆一下考的题目,总体还是很水,但是最后一题还是可耻的 WA 了……

  1. 初级题(100分,6个点):送分,输入a和b,输出[a,b]之间的素数,没有时间、空间限制,而且题干用中文把算法都给描述出来了,考验你是否会打开VS或Eclipse、编译、运行……
  2. 中级题(200分,4个点):输入一串逗号分隔(脑残)的数,不超过1000且无重复,输出这串数中可以被其它数整除的数,要求按输入顺序。基本也是送分,除了输入比较恶心(一般都是输入n,然后输入n个数;这个我只能用字符串一位一位处理了)。
    样例:输入”3,4,2,6″,输出”4 6″。
  3. 高级题(300分,4个点):有N个岛,给出岛间距离,全部连通最少需要多少距离的桥?输入n(3<=n<=1000),再输入n*n的邻接矩阵表示距离(没有给出距离的范围……都没说是不是整数……),输出最短桥距离。
    明显是MST,写完贪心(Kruskal,只记得这一种,也不让上网搜)交上去WA 2/4,而且只能提交五次,改了4种版本之后依然稳定的2/4,最后就只拿到一半分。交完最后一次才想到,是不是距离可能有浮点数……
    样例输入(自己编的):
    3
    0 123 456
    123 0 789
    456 789 0
    输出:579

总之是很水的题目,而且要吐槽的是做完之后不能走(15分钟做完前两题、45分钟败完5次提交,剩下一小时就瞪着监考老师),还要做职业测试(精神病测试),做完一遍因为做的太水又被迫做了第二遍……呵呵哒。

PS: 考场上有个孩子,可怜兮兮的给监考老师说,老师我没用过VS,我只会用Code::Blocks,这个VS简单的程序也报错,blah blah……当时我就傻了,还真有只用过Code::Blocks的大神orz……

PSS: 蒋震机房的XP+VS2005真是亮瞎了朕的氪金狗眼,新建工程Debug报缺少DLL,必须先修改一个“FAT32什么什么”的选项才能用……

回忆一下 360 实习编程题

现在两批人都考完了,来透个题。规定上说不能用笔抄,没说不能用脑子记。省略全部废话,只说题干。总体来说就是一个字:

1. 两个人A、B,从一个整数范围(说是N,目测是[1,N],题出的非常模糊)里面各选一个数a和b,然后用一个均匀随机生成器在范围里生成一个数c,看谁离c近赢,相同距离算b赢。

现在输入是N和a,求b选几的时候胜率最大,相同胜率取最小。

样例:3 1 (输出2)、4 3 (输出2),完美的避开了是0还是1开始的问题……

</题干> 卤煮做了40%(还做出过20%,应该是5个点),还想出一个边界条件没写对,不知道剩下的错在哪里。

2. 给定字符串s,由a~z和小数点“.”组成,定义操作a(s),表示将s中最早出现的连续两个点替换成一个点;定义函数f(s),表示进行多少次操作a可以使得字符串中没有连续的点。

输入为n(字符串长度),m(字符串替换操作);第二行为n长字符串;第3行开始的m行,每行有k和c,表示将s中第k个字符(从1开始数,傻叉)替换为c。要求在每次替换后,输出替换后s’当前f(s’)的值。

样例:原来的巨长无比,我就随便编一个:4 1 a..b 4 . (输出2)。

</题干> 水题,只要注意是1开始这个大坑。读入后先计算原始的f(s),然后每次操作后,拿出操作位左右各一位,判断这三位在变化前后的diff,加到原始f(s)即可(当然,过后要真的替换)。

————————————————

2/5的WA啊,哪有这么多边界条件啊,我猜是大数据点输出的时候变成了科学记数法,但是我安装了跟OJ一样的g++版本,并没有被科学……天知道为什么,呵呵哒。

另外理论题考了好多设计模式、算法、数据库的细节题,理论渣表示全靠蒙,不服跑个分。

激活(或重新激活) 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。