面试老被问到闭包相关的问题, 之前也一直答的不是很好. 最近研究了一下闭包相关的一些内容, 以下是我个人的一些理解.

闭包指什么

Closures are functions that refer to independent (free) variables (variables that are used locally, but defined in an enclosing scope). In other words, these functions ‘remember’ the environment in which they were created.

这段话来自MDN - Closures(Last updated by: SphinxKnight, Sep 8, 2016, 1:06:52 AM), 简单的说就是: 当一个函数中使用了其他作用域中的变量, 它就是一个闭包. 闭包能够"记住"其创建时所在的环境.

下面还有一段解释:

A closure is a special kind of object that combines two things: a function, and the environment in which that function was created. The environment consists of any local variables that were in-scope at the time that the closure was created.

这里说闭包是含有一个函数以及创建时所处环境的对象.

可以看出, MDN上对闭包的指代并不明确, 并不知道是指代函数还是函数加创建环境所组成的对象.

《JavaScript高级程序设计》中对闭包的解释是:

闭包是指有权访问另一个函数作用域中的变量的函数

其后对闭包的详细描述也都是将函数视为闭包的.
结合网络上其他的一些解释, 我认为:闭包指的是一个函数.
当然, 这个函数需要能”记住”创建时所在环境, 具体细节后面会讨论.

单行文本的水平垂直居中常通过设置line-height实现, 而当我们需要使多行文字水平垂直居中时, 直接设置line-height不能够实现我们所需的效果.
下面通过四种不同思路实现多行文字的水平垂直居中. 这里主要介绍思路, 兼容性没有详细测过, 对于不同浏览器可能需要微调(我是在chrome 51下面跑的).

HTML如下:

1
2
3
4
5
6

<div id = "test">
    <p>
        MY TEST
        MY TEST
    </p>
</div>

排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void bubble_sort(vector<int> &v) {
    int l = v.size();
    int tmp;
    bool flag;
    // 从右往左枚举i, v[i+1]到v[l-1]已经有序且是最终顺序, 每次循环将把v[0]到v[i]的最大值换给v[i]
    for(int i=l-1;i>0;--i) {
        // 从v[0]开始两两比较, 将大的数放到右侧, 最大的数自然被交换到了v[i]
        flag = false;   // 检测此次循环是否交换过, 如果没发生过交换则数组已经有序
        for(int j=0;j<i;++j) {
            // 两两比较
            if(v[j]>v[j+1]) {
                // 左侧较大则交换, 使得保持右侧较大
                tmp = v[j];
                v[j] = v[j+1];
                v[j+1] = tmp;
                flag = true;
            }
        }
        if(!flag)
            break;  //没有发生交换, 数组已经有序, 直接退出
    }
}

最近在学习某个效果的实现, 然而看着一堆function堆在一起的代码很难受, 想来封装一下. 然而一动起手来发现要写的东西还真不少, 所以想着分成几部分来做, 先就从事件开始.
本人接触前端时间不长, 也没有企业的项目经历(毕竟还没毕业), 只能把之前学到的一些东西东拼西凑起来, 可能封装的不是很优美. 如果有什么错误或者有更好更优美的姿势, 希望能够留言告诉我, 共同学习进步.
雷姆是我的!

指定事件处理程序处理程序

事件处理是JS中的重头戏. 为事件指定其处理程序的方法有很多, 如HTML事件处理, DOM0级事件处理和DOM2级事件处理, DOM事件对象也不尽相同. 本文就通过封装, 提供一个跨浏览器的事件处理对象.

首先从指定事件处理程序的方式来说, 可以从HTML直接指定事件处理程序:

1
2

<!-- Professional JavaScript for Web Developer 3rd Edition - Chinese - P348 -->
<input type="button" value="Click Me" onclick="alert('Clicked')"/>

更详细的用法这里不多说了, 现在几乎没人会这样做了, 因为这种写法有几个缺陷.

• 如果这个元素显示在页面上了, 而在HTML中指定的事件处理方法还未被解析到, 这样会引发错误(例如你调用的方法在外部js脚本中, 而DOM加载并显示后, 脚本却还没下载解析完成, 这样就找不到这个方法).
• 作用域链难以确定, 不同的JS引擎有不同的解析方式, 会导致不同浏览器下的作用域链不相同.
• HTML与JS代码耦合, 常常需要同时修改HTML代码和JS代码.

DOM0级事件通过给事件处理程序属性赋值实现指定处理程序:

1
2
3
4
5
6

// Professional JavaScript for Web Developer 3rd Edition - Chinese - P350
var btn = document.getElementByID("myBtn");
btn.onclick = function() {
	alert('Clicked');
	alert(this.id);
};

这样的事件被视为元素的方法, this指向触发事件的元素, 事件在冒泡阶段被处理, 通过赋值null删除事件处理程序.
DOM0级事件的缺点在于, 其只能指定一个事件处理程序, 后面指定的程序会覆盖前面指定的程序. 也就是说, 如果JS代码的两个地方为一个元素指定了不同的事件处理程序, 那么只有后面指定的程序会执行.

1. Two Sum

第一想法是枚举每个数,然后看总数减这个数的差值在不在原数组中.直接用map存数,枚举的时候在map里面查,复杂度Nlog(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> m;
        vector<int> ret;
        for(int i=0;i<nums.size();++i) {
            m[nums[i]] = i+1;
        }
        for(int i=0;i<nums.size();++i) {
            int b = m[target - nums[i]];
            if(b&&b!=i+1) {
                ret.push_back(i);
                ret.push_back(b-1);
                return ret;
            }
        }
        return ret;
    }
};

其实后来发现可以合并两个循环.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> m;
        vector<int> ret;
        for(int i=0;i<nums.size();++i) {
            int b = m[target - nums[i]];
            if(b) {
                ret.push_back(i);
                ret.push_back(b-1);
                return ret;
            }
            m[nums[i]] = i+1;
        }
        return ret;
    }
};

今天群里大神给大家出了一道思考题:

给一个数组, 将另一个数组插入其指定位置, 用ES5和ES6语法分别如何实现.

比如给数组[3,4], 要在位置1插入数组[1,2], 要得到的结果是[3,1,2,4].

说道插入,最先想到的就应该是Arrary的splice方法了.语法如下

1

array.splice(start, deleteCount[, item1[, item2[, ...]]])

这个方法会修改数组本身.
start表示数组从哪一位开始修改,超过长度则视为数组末尾,接受负数参数表示从末尾开始计数.
deleteCount表示从start开始(包括start)要删除的元素个数,超过后面元素的总数则删除后面所有.
itemN是要加进数组的元素,可以不指定.
返回值是被删除元素的数组,没有则返回空数组.

但是问题在于,要添加元素需要用参数的形式加入,如何能把数组展开成参数(迭代每次加一个显然没有充分利用这个方法).

据说这次过了下轮就不能参加了呢,遗憾…查重结束, 可以贴代码出来了.

A. Country Leader

选领导人,名字里面字母种类多的当选,如果有多人名字种类一样多,则选名字字典序靠前的.给你$N$个名字$N ≤ 100$,问那个人会当选.所有的名字只有大写字母,长度不超过$20$,大数据的名字会有空格.

这题就把名字一行一行读进来,统计每个名字的字符种类.对名字排序以后找第一个字符种类最多的就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

//省略头文件
using namespace std;
typedef long long ll;
void useFile(string f) {
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
}
struct Person {
	char name[30]; 
	int v;
} p[110];
int n;
bool used[30];
bool cmp(const Person &a, const Person &b) {
	return (strcmp(a.name, b.name)<0);
}

void gao(){
	scanf("%d",&n);
	getchar(); 
	int maxv = 0;
	for(int i=0;i<n;++i){
		gets(p[i].name);
		int l = strlen(p[i].name);
		memset(used,0,sizeof(used));
		int cnt = 0;
		for(int j=0;j<l;++j) {
			if(p[i].name[j]==' ')
			continue;
			if(!used[p[i].name[j]-'A']) {
				++cnt;
				used[p[i].name[j]-'A'] = 1;
			}
		}
		p[i].v = cnt;
		maxv = max(maxv,p[i].v);
	}
	sort(p,p+n,cmp);
	for(int i=0;i<n;++i)
	if(p[i].v==maxv) {
		puts(p[i].name);
		break;
	}
}
int main()
{
	useFile("A-large");
	int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
    	printf("Case #%d: ",i);
    	gao();
    }
    return 0;
}

比GCJ简单多了,题目大都很暴力(虽然最后一题还是不大会)

A. Lazy Spelling Bee

给一个字符串$a$,问有多少种字符串$b$满足长度与$a$相同且每一位$b[i] = a[i] OR a[i-1] OR a[i+1]$,结果模$10^9 + 7$.Case数$T$不大于$100$,字符串长度$L$不大于$1000$.

直接枚举每一位,统计相邻的位上有几种字符,然后乘起来就行了.复杂度$O(TL)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//省略头文件
using namespace std;
typedef long long ll;
string s;
const ll M = 1000000007;
void useFile(string f) {
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
} 
void gao(){
	cin>>s;	
	ll ans = 1;
	for(int i=0;i<s.length();++i) {
		int cnt = 0;
		bool used[30] = {0};
		for(int j=i-1;j<=i+1;++j) {
			if(j<0||j>=s.length())
				continue;
			if(!used[s[j]-'a']) {
				used[s[j]-'a'] = 1;
				++cnt;
			}
		}
		ans*=cnt;
		ans%=M;
	}
	printf("%lld\n",ans);
}
int main()
{
	//useFile("A-large-practice");
	int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
    	printf("Case #%d: ",i);
    	gao();
    }
    return 0;
}

最长回文串是一个经典问题,要求对给定的字符串,找出其中的一个最长子串,满足其顺序和逆序相同.例如对于原字符串$aaaabaa$,其最长回文子串是$aabaa$.
对于这个问题(例题可以戳这里),一般有$O(n^2)$的暴力或DP解法,$O(n\log(n))$的后缀树解法,以及下面要讲的$O(n)$的manacher.

首先,回文串的奇偶问题对于编程来说一直是个麻烦事,因为一个回文串既可以以一个字符为中心(如$abcba$),也可以以两个字符中间为中心(如$abccba$).为了方便处理,manacher在原串的每个字符间中加入一个原串中没有的字符(包括开头和结尾).例如原串为$aaaabaa$,我们加入#,那么新串就是#$a$#$a$#$a$#$a$#$b$#$a$#$a$#.这样做的好处是,当我以#为中心查找最大回文的时候,对应就是原串中以字符间为中心查找;当以某字符查找的时候,对应在原串中以此字符为中心查找,只是最后找到的长度翻倍了而已.例如上面的新串可以找到最长回文串#$a$#$a$#$b$#$a$#$a$#,长度为$11$,而在原串中为$\lfloor\frac{11}2\rfloor=5$

接下来我们定义”回文半径”.所谓回文半径,指的是回文串从中心到其一个端点中含有的字符数量(包含端点),如#$a$#$a$#$b$#$a$#$a$#的回文半径是$6$.容易发现,一个点在新串的最长回文半径$r$比原串对应位置的最长回文子串长度$l$多$1$,即$l=r-1$.
我们用一个数组表示以每个位置为中心能得到的最长回文半径

如果能计算出这个数组,那么只要遍历一下找到最大值,便可以得到最长回文子串.

内容主要参考《算法导论》(原书第3版) 中第3章:函数的增长.
其在第17章中介绍了一些高级的分析方法,用来分析一些复杂问题的复杂度,这里暂时不做介绍,以后有机会另讲.

复杂度简介

所谓算法的复杂度,指的是一个算法所需要消耗的资源,通常包含时间资源(时间复杂度)和内存资源(空间复杂度).复杂度是评价算法的重要指标,它直接决定了算法的执行效率.
这里以时间复杂度为例.当一个问题的输入规模为$n$时(例如对一个含有$n$个数的数组排序),通常可以用一个函数$f(n)$表示算法在解决该问题的时候需要的基本操作次数,函数$f(n)$便可以代表一个算法的时间效率(通常我们认为一次基本操作所需的时间是一个常数).
比如对插入排序最坏情况的运行效率我们可以用一个多项式刻画:
$$f(n) = an^2 + bn + c$$
其中$a,b,c$是常量.
绝大多数情况下,我们并不需要知道精确的算法效率,而更加关心的是在大输入规模下算法运行时间的增长量级,也就是渐进效率.
例如上面的$f(n)$,可以看出当输入规模$n$足够大时,运行时间的增长主要受到$an^2$项的影响,甚至常数$a$本身的影响都可以忽略,因此我们可以用$n^2$来表示这个算法的渐进效率.