Dutch National Flag问题 - One Pass算法解读

荷兰三色旗问题(以下简称DNF问题),是Dijkstra提出的一个经典问题,让我们先来看看它的描述:

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

解题思路

乍眼一看,这个问题就是一个简单的排序,我们写一个快排也很简单。

但问题在于数组中只有三种元素,按照排序算法来写肯定会有较大的性能损失。

于是我们可以很直观的想到一个Two Pass算法,即,第一次遍历统计数组得到0,1,2的数目,第二次遍历按序填充0,1,2。

那么有没有One Pass的算法呢?

答案是有的,不过理解起来有一定的难度。

One Pass算法介绍

让我们先看算法吧。

    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int i = 0;
        
        while (i <= right) {
            if (nums[i] == 0) {
                nums[i] = nums[left];
                nums[left] = 0;
                i++;
                left++;
            }
            else if (nums[i] == 2) {
                nums[i] = nums[right];
                nums[right] = 2;
                right--;
            }
            else {
                i++;
            }
        }
    }

我先大致讲解算法的思路,然后详述算法中tricky的点。

设置一个left和right指针,left的左边是已排好序的0,right右边是已排好序的2,由于遍历开始之前,没有排好序的0和2,所以left指向0,right指向n - 1。

以指针i开始遍历数组

如果遇到0,将nums[i]与nums[left]互换,left++, i++

如果遇到2,将nums[i]与nums[right]互换,right–

如果遇到1,将i++

这样在一次遍历以后,0被划分到了左边,2被划分到了右边,中间自然只有1了。

不细想的话似乎很明了,但要真正的透彻理解,还需要下一番功夫。

One Pass算法详解

首先对于上述的算法,让我们考虑一个问题。

为什么索引i与left的值互换时,i要自增,与right的值互换时却不能自增?

下面的讲解我就要解释这个问题。

首先在这个算法中,让我们把整个数组分成4个部分:

1 排好序的0
2 排好序的1
3 未排序的部分
4 排好序的2

如下图所示:

数组分区

在最开始的时候,只有未排好序的部分,即下图:

初始分区

一旦开始遍历

当遇到0时,将left指向的元素与i指向的元素互换

用不用再次比较互换之后i指向的元素呢?答案是不用。

因为互换之后

i不可能指向一个2,因为如果i指向一个2,它在遍历到i之前已经被换到right之后了,而right是不可能小于i的

如果i指向一个1,说明排好序的0之后的第一位刚好是一个1,我们所做的操作扩大了排好序的0的个数,

如果i指向一个0,一定意味着i之前的元素全部是0并且i和start此时相等,因为在遍历到i之前所有的0已经被加入到left之前已排好序的0中,如果此时left仍指向一个未排好序的0,那么这个0只能是i指向的元素

因此,在nums[i]与nums[left]交换后,i和left一样,都可以自增,因为索引i和left元素互换后可能出现的两种情况都不需要对索引i的元素重新进行操作,它已排好序。

当遇到1时,直接将i自增,从上图可以看出这样做时正确的,它缩小了未排序分区,扩大了排好序的1分区

当遇到2时,将i指向的元素与right指向的元素互换,将right自减。

这扩大了已排好序的2分区,但我们不能对i进行自增。

因为我们需要再次判断互换后的i是否仍指向2,如果仍指向2,继续将它与right互换。

如果不这样做的话,就会出现下面这种情况:

错误分区

由于right或者自减,i或者自增,所以他们最后总会相遇,算法结束。

总结

DNF问题是一个经典问题,它还是主要使用了快排的分区、交换的思想,注意体会它的思想,把握它的细节。

NodeJS执行机制

今天在学习《深入浅出NodeJS》,对Node的执行机制感觉有了一定的了解,又有一些迷糊,于是将它做一个梳理与总结。

NodeJS执行机制

按照顺序来整理Node的执行机制。

我将Node中的观察者分为四类。

一类是处理事件的观察者(如I/O观察者、网络请求观察者),称其为 事件观察者

一类是timer的handles,称其为 handles观察者

一类是process.nextTick()的观察者,称其为 tick观察者

一类是setImmediate()的观察者,称其为 immediate观察者

下面是进程启动时执行的机制(1):

1、依序执行所有同步代码

2、如果遇到普通的事件,将其加入到对应类型的事件观察者

3、如果遇到setTimeout()及setInterval(),将其timer加入到handles观察者

4、把遇到的所有process.nextTick()加入tick观察者,将所有process.nextTick()的回调函数加入任务队列

5、把遇到的所有setImmediate()加入immediate观察者,将第一个setImmediate()的回调函数加入任务队列

这就是按序执行所有Node代码时所做的事,然后就开始进行事件循环了,下面是事件循环中一个tick所做的事(2),需要注意的是,以下步骤中执行的每一个回调,都按照(1)的步骤执行:

1、检查tick观察者,由于其中所有事件的回调都在任务队列上,所以执行其中所有事件的回调

2、检查immediate观察者,因为只有其中第一个事件的回调在任务队列上,所以执行其中第一个事件的回调

3、检查是否有普通事件触发,如果触发则将其回调加入任务队列并执行

4、逐个检查handles观察者中的timer,如果计时已到,将其对应的回调添加到任务队列并执行

5、如果在上述过程执行完没有检查到事件(可以没有回调,检查到待处理事件即可),则退出进程,否则重新进行(2)循环

而JavaScript中的事件循环机制与Node应该是类似的,只是没有tick观察者等特殊的观察者而已。

slot思想、用法及原理详解

slot的意思是插槽,它主要是用来做内容分发的工具,那么什么是内容分发呢?slot又有几种用法?slot的每种用法主要是用于解决什么问题?

可能在学习Vue的文档时,不少人都会有这样的疑问。

今天我就来总结一下slot思想、用法及原理。

slot

首先我们需要明确的是Vue的组件化思想。

组件的意义在于复用,所以我们在写出一个组件后总是希望父组件用某种方式来调用它,for instance:

<child-component :para="xxx" @evt="yyy"></child-component>

这样的做法是Vue推荐的,我们可以在使用时像子组件prop参数,也可以监听子组件emit的事件。

但是存在一个问题,子组件的内部对父组件是不透明的。

这就意味着父组件没有办法自由控制子组件的部分行为,无法将它的内容直接分发到子组件,无法在调用组件时实现定制化。

于是slot就可以发挥作用了。

举一个例子,假设我们有一个btn组件,它的意义在于被各个组件复用,不同的父组件button可能有不同的文字,我们可能会想到这样写:

<template id="btn-template">
    <button>{{ text }}</button>
</template>
Vue.component('btn', {
    template: '#btn-template',
    props: ['text']
})

然后父组件在调用时:

<btn text="删除"></btn>

<btn text="添加"></btn>

这样做不是不可以,但存在问题,一是如何处理prop数据是由子组件控制的,父组件无法操控,不直观也不透明;二是父组件需要分发较为复杂的模板内容时,子组件会存在许多复杂的DOM操作逻辑。

我们可以用slot来解决这个问题。

<template id="btn-template">
    <button>
        <slot>
            默认的内容
        </slot>
    </button>
</template>
Vue.component('btn', {
    template: '#btn-template'
})

在调用时:

<btn>删除</btn>

<btn>添加</btn>

子组件中默认的内容只有在父组件没有分发内容时才会渲染,如果父组件有分发的内容,则会被覆盖。

上述的调用会渲染成:

<button>删除</button>

<button>添加</button>

命名slot

可能讲的有点啰嗦了,不过基本的思想阐述清楚了。

下面尽量简洁一点。

命名slot,顾名思义,这个插槽是有名字的。

之所以要有名字,是为了方便父组件分发多个内容,并在子组件中正确渲染。

这个例子官方文档举的很好,假设子组件的模板是这样:

<div class="container">
  <header>
    <slot name="header"></slot>
  </header>
  <main>
    <slot></slot>
  </main>
  <footer>
    <slot name="footer"></slot>
  </footer>
</div>

看到这个模板应该已经清楚了。

我们需要的就是父组件在调用时指明要分发的内容给分别名为header和footer的插槽,指明的过程也很简单,给分发内容加上一个相应值的slot特性即可。

父组件中没有具名的分发内容,会被渲染到不具名的slot中。

比如我们这样调用子组件:

<app-layout>
  <h1 slot="header">这里可能是一个页面标题</h1>
  <p>主要内容的一个段落。</p>
  <p>另一个主要段落。</p>
  <p slot="footer">这里有一些联系信息</p>
</app-layout>

最终渲染的结果是这样的:

<div class="container">
  <header>
    <h1>这里可能是一个页面标题</h1>
  </header>
  <main>
    <p>主要内容的一个段落。</p>
    <p>另一个主要段落。</p>
  </main>
  <footer>
    <p>这里有一些联系信息</p>
  </footer>
</div>

作用域slot

作用域slot可能就没有那么见名知义了。

我的想法是,作用域slot的意思就是,将分发的内容限制在插入插槽的作用域内,这个作用域中的数据既可以是自己定义的变量,也可以是prop得到数据。

这在分发内容需要依靠复杂数据时特别有用(如渲染表格、列表等),举一个例子,假设我们子组件中有一个插槽列表:

<ul>
  <slot 
    name="item"
    v-for="item in items"
    :text="item.text"></slot>
</ul>

从这一段模板我们可以看出,子组件中有多个同名的slot。

那么如何把父组件分发的内容限制在其对应插槽的作用域内呢?

也很简单,在父组件的分发内容中加入一个slot-scope特性就可以了。

这个slot-scope特性的值指向这个插槽的作用域对象(也可以使用解构~)

比如在调用这个子组件时,分发内容可以这样写:

<my-awesome-list :items="items">
  <li
    slot="item"
    slot-scope="props"
    class="my-fancy-item">
    {{ props.text }}
  </li>
</my-awesome-list>

假设items是一个数组:['hello', 'world']

渲染结果会是这样的:

<ul>
  <li>hello</li>
  <li>world</li>
</ul>

需要注意的一点是,在Vue 2.5以前,slot-scope特性必须在template标签上使用,Vue 2.5以后,slot已经可以用于任意的元素和组件中了。

在render函数中渲染slot

讲完了在template中的slot用法,我们来讲一讲在render函数中如何使用slot接收分发的内容。

事实上template是被编译成render函数以生成VNode的,所以本文接下来也可以看做是对slot工作原理的阐述。

在render函数中使用slot接收分发的内容,我们需要首先熟悉一些实例属性API。

我们要知道的是,访问分发给插槽的内容,需要调用vm.$slots这个API。

比如,slot="foo"中的内容可以在vm.$slots.foo中找到,default属性包括了所有没有被包含在具名插槽中的分发内容。

用官方文档举一个例子:

Vue.component('blog-post', {
    render(createElement) {
        const header = this.$slots.header
        const body = this.$slots.default
        const footer = this.$slots.footer
        return createElement('div', [
            createElement('header', header),
            createElement('main', body),
            createElement('footer', footer)
        ])
    }
})

在调用子组件时我们就可以正常的分发内容了:

<blog-post>
  <h1 slot="header">
    About Me
  </h1>
  <p>Here's some page content, which will be included in vm.$slots.default, because it's not inside a named slot.
  </p>
  <p slot="footer">
    Copyright 2016 Evan You
  </p>
  <p>If I have some content down here, it will also be included in vm.$slots.default.</p>.
</blog-post>

分发内容会被渲染到它应在的位置。

在render函数中分发内容

render函数可以用来渲染子组件,当然也可以在父组件中调用子组件,而在调用子组件时,自然可以向其分发内容,举个例子:

render(createElement) {
    return createElement('div', [
        createElement('child', [
            createElement('p', '这是一个不具名slot'),
            createElement('p', {
                slot: 'main'
            },
            '这是一个名为main的slot')
        ])
    ])
}

如此分发内容给插槽,可以使内容分发有别于prop,更加清晰(I guess…)

这个render函数返回的VNodes如下:

<div>
  <child>
    <p>这是一个不具名slot</p>
    <p slot="main">这是一个名为main的slot</p>
  </child>
</div>

在render函数中渲染作用域插槽

在render函数中使用作用域插槽同样需要我们对实例属性vm.$scopedSlots有一定的理解。

vm.$scopedSlots用来访问作用域插槽接收到的分发内容,包括默认插槽在内的每一个插槽接收到的分发内容,都可用该对象访问,该对象会包含一个返回相应VNode的函数(类似于一个createElement函数)。

比如我们这样写一个render函数:

return createElement('div', [
    this.$scopedSlots.default({
        text: this.defaultMsg
    }),
    this.$scopedSlots.foo({
        property: this.fooMsg
    })
])

上面这一段render函数相当于这样一个模板:

// child
<div>
  <slot :text="defaultMsg"></slot>
  <slot :property="fooMsg" name="foo"></slot>
</div>

于是我们可以这样给它分发内容:

<child>
  <p slot-scope="props">{{ props.text }}</p>
  <!-- 下面使用了解构语法 -->
  <p slot-scope="{ property }" slot="foo">{{ property }}</p>
</child>

在render函数中分发内容给作用域插槽

在render函数中分发内容给作用域插槽,可以使用createElement函数的data参数对象的scopedSlots属性。

还是以一个例子来说明:

render(createElement) {
    return createElement('div', [
        createElment('child', {
            scopedSlots: {
                default: props => createElement('span', props.text)
            }
        })
    ])
}

如此分发内容给作用域插槽,可以使内容分发有别于props,更加清晰,同时也是由于Vue 2.5之前slot-scope必须写在template标签上(I guess…)

事实上,上面这一段渲染函数渲染出的VNodes如下:

<div>
  <child>
    <span slot-scope="props">{{ props.text }}</span>
  </child>
</div>

结语

这篇文章从内容分发/slot的思想讲到用法,最后讲到在render函数中的实现原理,我感觉写的还是比较清晰的。

也希望读者可以有一定收获。

理解Kadane算法

最近刷leetcode时遇到一道题:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

做题时想了想,除了暴搜之外没有想到其他的办法,然后看Discuss区,发现一个很有意思的算法:

    public int maxSubArray(int[] nums) {
        int maxForNow = nums[0];
        int maxPostfix = nums[0];
        for(int i = 1; i < nums.length; i++) {
            maxPostfix = Math.max(maxPostfix + nums[i], nums[i]);
            maxForNow = Math.max(maxForNow, maxPostfix);
        }
        return maxForNow;
    }

看了很久都没有看明白,去了解了一下历史,发现这是一个著名的求解最大子数组的线性O(n)算法–Kadane算法。

算法的篇幅虽然比较短,但是理解起来比较困难,所以我记录一下我理解的思路,以期帮助有困惑的学习者,也便于复习。

为了更方便的说明这个算法,我先用测试用例进行一次遍历:

测试用例遍历

可以看到的是maxForNow总是存储目前最大的子数组,maxPostfix总是存储最大后缀的子数组。

于是就可以很清晰的理解Kadane算法了:

该算法的本质就是利用动态规划的思想,通过寻找局部最优解 + 状态转移来寻找全局最优解。

用直白的语言说就是:如果我已经知道nums[0]-nums[i - 1]的最大子数组,那么我如何寻找nums[0]-nums[i]的最大子数组。

显然的,nums[0]-nums[i]的最大子数组可能取以下两个值:

1、之前nums[0]-nums[i - 1]时的最大子数组,即之前的maxForNow
2、nums[k]-nums[i](0 <= k <= i),加上nums[i]之后的,由nums[i]及其之前的多个元素构成的最大子数组,也就是最大后缀,我们称之为maxPostfix

于是就很容易理解:

maxForNow = Math.max(maxForNow, maxPostfix);

那么maxPostfix怎么求呢?

同样很显然的,maxPostfix只有可能取以下两个值:

1、previous maxPostfix + nums[i]
2、nums[i]

于是这一语句也容易理解了:

maxPostfix = Math.max(maxPostfix + nums[i], nums[i]);

从nums[0]开始,遍历数组,不断更新maxForNow和maxPostfix,遍历整个数组后,得到maxForNow,就是我们需要的最大子数组。