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

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

题目意思是，判断一个数组是否包含子序列a_i、a_j、a_k（i<j<k），满足a_i<a_k<a_j。

主算法

思路是遍历每一个可能的k值，然后找到它之前第一个（也就是距离最近的）比它大的数作为a_j，然后再判断a₀~a_j-1之间的最小值是否小于a_k。

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

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

因此最终算法分三步：预处理a₀~a_j的最小值，预处理a_k之前第一个大的数，遍历每一个可能的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 写了一个 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什么什么”的选项才能用……

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

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++版本，并没有被科学……天知道为什么，呵呵哒。

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