C语言指针的个人见解（二）

发表于 2017-12-30

C语言指针的个人见解（二）

1.关于数组

1.1什么是数组

在C语言中，数组指的是一系列相同数据组成的集合
数组有以下性质

除去变长数组之外，声明数组的时候数组的大小必须由常量提供
数组的大小在声明之后不可更改
C语言不对越界做处理，需要coder自己注意
数组名在使用上可以当做是指向数组第一个元素的该类型的指针

数组的元素有如下性质

每个元素的类型都相同
元素名被隐藏，通过首地址+索引来找到元素
因为类型相同，可知元素储存时所需的内存、字节数也相同
在C语言中，数组的元素在内存中的排列是紧挨着的，并且地址依次递增

1.2数组举例

假设有int a[3]={0,1,2}
a[3]中的三个元素的地址和如下举例有相同性质

a[0]：007FFE20 007FFE21 007FFE22 007FFE23
a[1]：007FFE24 007FFE25 007FFE26 007FFE27
a[2]：007FFE28 007FFE29 007FFE30 007FFE31

可以看见最后两位是依次++的

1.3指针与数组名

还是使用上面的例子

1 2	int a[3] = {0,1,2}; int* int_pa = a;

在这个前提下，会发现几个基本等价的语句

1
2
3

a[i];
int_pa[i];
*(int_pa+i)

在C语言指针的个人见解（一）中，已经讲过指针自增的效果
当int_pa指向a[0]时，int_pa的值就是007FFE20
所以(int_pa+1)的值就是007FFE24，也就是a[1]的地址，这个时候使用*解引用，自然就拿到了a[1]

再复杂一点，下面几个也是等价的

*(*(*(*(X+i)+j)+k)+t);
*(*(*(X[i]+j)+k)+t);
*(*(X[i][j]+k)+t);
*(X[i][j][k]+t);
X[i][j][k][t];

1.4指针数组与数组指针

众所周知，读书要从右到左（滑稽）
所以指针数组就是指针组成的数组，是个数组
所以数组指针就是指向数组的指针，是个指针

int *pa[3];//指针数组
//这样用
int a[3] = {0,1,2}
pa[0] = a + 0;
pa[1] = a + 1;
pa[2] = a + 2;
//之后就有以下几组等价的语句
*pa[0]和a[0]
**(pa+1)和a[1]

可以画个图理解一下

int (*pa)[3];//数组指针
//这样用
int a[3][3];
pa = a;

画图理解的时候，指针不要只画一个箭头，建议在箭头的重点把指针指向的内容用圈圈括起来，比如这个，就要把一整行都圈起来。（a[0][0],a[0][1],a[0][2]这一行）

在上一次的文章中已经讲过，这里类似理解
pa指向的类型是三个int组成的数组

a[0][0]：007FFE20 007FFE21 007FFE22 007FFE23
a[0][1]：007FFE24 007FFE25 007FFE26 007FFE27
a[0][2]：007FFE28 007FFE29 007FFE30 007FFE31

那么pa就要把这十二个字节都括起来
当pa++时，pa的值变为007FFE32

所以万变不离其宗，不管指针指向的是什么乱七八糟的玩意儿，指针的几条性质是不会变的。
这里可以思考一下在把一整个数组当做参数传递的时候的指针的使用

下一期就谈一谈函数指针，好了，开始拖更

C语言指针的个人见解（一）

发表于 2017-12-27

C语言指针的个人见解（一）

关于内存

内存基础

1位 = 1bit = (0, 1)
1字节 = 8位（一般情况下）
一般来讲，可以把一个字节当成最小寻址单位，也就是最小的可以区分的、可以定位的一个内存。
8位，也就是2⁸种数据，也就是256种，如果是无符号整形数据的话就是0~255。

C语言变量的内存与变量地址

而在C语言中，假如有一个int类型的值（int_32），那么int应当是有四个字节的存储空间。

1	int a = 2;

声明并初始化一个名为a的变量，那么a就被分配了4个字节的存储空间，并让a的值为2。

使用%p说明符可以查看一个指针指向的地址。

1 2	char pa = &a;//注意此处使用的是char，而不是int* printf("a的地址为：%p %p %p %p\n", pa, pa + 1, pa + 2, pa + 3);

可以看到以下输出

1	a的地址为：00EFFC14 00EFFC15 00EFFC16 00EFFC17

条件一：上面说过，最小寻址单位是字节，那么一个地址变量==一个字节
条件二：一个char型变量是大小为一个字节的变量（因为ASCII码只有128个）
结论：（一个地址变量==一个字节）==（一个char*指针==一个最小的寻址指针）

所以上面四个十六进制数就是变量a的四个字节的地址，可以看到他们是连续的。

关于指针

指针

上面的尝试使用了char*当辅助工具。

那如果换用int 指针，而不是char指针呢？

1
2
3

char *char_pa = &a;//注意此处使用的是char*，而不是int*
int *int_pa = &a;
printf("a的地址为：%p  %p  %p  %p\n%p", char_pa, char_pa + 1, char_pa + 2, char_pa + 3, int_pa);

结果应该是

1 2	a的地址为：00EFFC14 00EFFC15 00EFFC16 00EFFC17 00EFFC14

可以看到int_pa和char_pa的输出结果是一样的。

那么结论是：一个指针变量的值永远是它指向的变量的第一个字节的地址。

指针类型

从上面的例子可以看到，char_pa和int_pa的值其实是一样的，但是两个指针的类型不同，值一样是因为上面的结论。

那么指针的类型有什么用呢？

int a = 1;
int *int_pa = &a;
char *char_pa = &a;
printf("char_pa:%p  char_pa+1:%p\n", char_pa, char_pa + 1);
printf("int_pa:%p  int_pa+1:%p\n", int_pa, int_pa + 1);

1 2	char_pa:007FFE20 char_pa+1:007FFE21 int_pa:007FFE20 int_pa+1:007FFE24

可以看到
char_pa+1的时候，地址变量增加了一个单位
int_pa+1的时候，地址变量增加了四个单位

回想一下
char类型是一个字节，需要一个单位来存储
int类型是四个字节，需要四个单位来存储

所以结论：

指针类型标记了指针做增减的时候移动的地址单位长度。
指针增减的长度为指针指向的变量的类型的字节数。
指针增减的长度恰好够指针跳出当前指向的变量，从而指向下一个变量。

也就是说，如果a，b的地址如下所示

1 2	a：007FFE20 007FFE21 007FFE22 007FFE23 b：007FFE24 007FFE25 007FFE26 007FFE27

那么int_pa++之后，int_pa就指向变量b了（同样的，指针的值还是b的第一个字节的地址，也就是007FFE24）
这个时候 *int_pa 就可以拿到b的值

好了，开始拖更

hexo+node.js+github的博客搭建教程

发表于 2017-12-17

菜的一批的hexo+node.js+github搭建个人博客的教程

hexo大概的原理

hexo基于node.js框架，可以通过简单的命令生成一个静态的html页面

1 2	hexo generate hexo g

以及通过读取配置文件中的信息一键化部署到github

1 2	hexo deploy hexo d

我们需要做的只有配置好hexo环境，然后使用命令来生成新文章

1 2	hexo new "文章标题" hexo n "文章标题"

注意hexo生成的是静态页面，也就是说其实所有的网页生成在generate的时候就已经完成，每次对文章有改动，都必须重新generate，然后再部署到github，这个时候博客才会更新。

node.js环境

node.js官网
 node.js国内镜像（好像是阿里爸爸的）
推荐用阿里爸爸的，毕竟比较快。。

Windows

win就是懒人操作嘛，，下载–解压–安装–疯狂点next，连环境变量都帮你配好

Linux

我对linux不算是特别熟悉，命令可能有错，你们谨慎Ctrl c+v

先下载

1	wget https://npm.taobao.org/mirrors/node/v8.9.0/node-v8.9.0-linux-x64.tar.xz

然后解压

1	tar xvf node-v8.9.0-linux-x64.tar.xz

然后就安装完成了，不过这个时候node命令的环境变量还没有配置，这个配置就自己百度/Google吧，方法有好多种

Mac

ummm个人猜测和Linux差不多

检查安装

在命令行里面输入

1 2	node -v npm -v

如果查看到了版本号，那就说明安装+配置完毕了，可以开始使用hexo了。

hexo下载

首先，找一个看起来比较顺眼的文件夹，我们在这个文件夹里面放我们的hexo和blog

1
2
3

npm install hexo-cli -g
npm install hexo --save
hexo -v

依次键入以上命令后，可以看见hexo的一些版本信息

接下来生成blog

1	hexo init blog

然后进入blog目录
继续输入

1	npm install

npm install命令会根据json配置文件自动安装所需的库。

这个时候就已经完成了，然后我们就可以生成blog页面

1
2
3

hexo g
hexo d
hexo s

https://xuanwo.org/2015/03/26/hexo-intor/
https://linghucong.js.org/2016/04/15/2016-04-15-hexo-github-pages-blog/
注意hexo s命令是在本地建立服务器，根据提示的网址进行访问，我们就可以看见这个网页了。（当然，hexo s命令被终止了我们就看不见了）

一般来说，这个服务器监听的端口是4000，在浏览器中尝试访问一下这个端口

http://localhost:4000/

可以看见自己的博客了。

部署到github

其实也可以部署到其他地方，因为静态网页已经生成了，要做的只是让他可以被获取到。

配置github pages

首先需要一个存放hexo页面的仓库

这里我们new一个，记住这个仓库的命名方式必须是 “用户名”+”.github.io”
（比如我的用户名是xiaoyuoshu，这里仓库名就应该是xiaoyuoshu.github.io）

然后点击这个仓库的settings，在option菜单里下拉找到github pages，然后开启Automatic page generator。
这个时候访问
https://xiaoyuoshu.github.io/
应该就可以访问成功。（请改成你自己的用户名，谢谢）

配置deploy config

这个时候我们已经有了两个资源，1.我们本地的博客静态html。2.一个可以访问并获取到静态html的github仓库。
现在要做的就是把本地的上传到github上。

1	npm install hexo-deployer-git --save

先安装deploy到github上的node扩展。
在blog目录下打开_config.yml文件（yml里面不要随便打空格和回车和换行，格式要求极其严格。）然后下拉，找到最底下的deploy,按照如下格式修改他，还是记住把所有的我的用户名换成你的！！！

deploy:
  type: git
  repo: git@github.com:xiaoyuoshu/xiaoyuoshu.github.io.git
  branch: master

然后保存这个文件。
我们再使用

hexo d

就可以部署到github了，这个时候再打开博客的链接，就可以看见自己的博客了。

写文章

写文章使用的是markdown语法。
这里我们先在blog目录下

1	hexo new "文章标题"

然后

1 2	cd source cd _posts

dir

我们就可以看见我们的所有文章了，这个时候应该有一个helloworld.md和一个我们新建的文章标题.md

使用文本编辑器打开这个新的文章标题.md文件，可以看到开头是一段配置，不用管。

把写好的markdown文本复制到配置之后，保存

1 2	hexo g hexo d

就可以看见我们的文章了。

gaoji配置

主题

嫌博客页面太丑怎么办，，我们来换个主题吧。

首先，默认的主题都是存在themes目录下的，有几个主题就有几个文件夹。
这个主题就自己去网上找吧，蛮多的，甚至还有二刺猿主题？？？

下载好之后，还是进入_config.yml文件
找到这一段

# Extensions
## Plugins: https://hexo.io/plugins/
## Themes: https://hexo.io/themes/
theme: kael

这里我的主题是kael，假设要换成landscape，就把kael替换掉就可以了。注意冒号和主题名之间有一个空格，这个空格别删掉了。

然后

1
2
3

hexo clean
hexo d
hexo s

就可以看见更换后的主题啦。

其他

其他的功能我也没怎么多用，不敢细讲，不过谷歌和百度上超多教程。我就列举一下吧。

配置域名，如果嫌带github.io的域名太low，可以自己去买一个域名，然后解析到github给你分配的ip
配置文章标签
配置文章目录
配置页面中的一些链接
等等

其他

hexo已经是给小白搭建博客的福音了，希望各位常写博客，不要跟我一样当鸽子。

在以后能力强大了之后，我们可以自己购买服务器，并使用一些比较火的框架（如worldpress）搭建自己的博客，并实现更多的功能。

互勉

c语言 qsort() 函数的一些理解

发表于 2017-12-17

qsort函数与mysort函数详解

菜鸡的我来发教程啦。

1.如何使用qsort

#include<stdio.h>
#include<stdlib.h>
int compare(const void* a, const void* b) { return *(int*)a - *(int*)b; }
int main() {
	int nums1[] = {1, 489, 4591, 189, 123, 189, 56, 6};
	qsort(nums1, sizeof(nums1) / sizeof(int), sizeof(int), compare);
	for (int i = 0; i < sizeof(nums1) / sizeof(int); i++)
	{
		printf("%d ", nums1[i]);
	}
}

先看compare函数，传入了两个void指针，但是交换的时候使用了(int )a的强制类型转换。至于为什么，先放一放。

然后是qsort使用，这个上次的邮件里已经写了，我就不赘述了。

注意sizeof(nums1) / sizeof(int)可以获取所需的数组的长度。

**2.关于void*指针**

先看一下基本的内容，可能有错，但是对理解没什么影响。

1.指针有四个相关的参数：a.自己的名字。b.自己本身的地址。c.储存的、也就是指向的地址。d.指向的变量的类型。

2.现在如果int a有4个字节，也就是32位，那么int p = &a，那么首先p指向的地址是a的*第一个字节的地址。

3.继续，当p++时，p会跳过几个字节呢？答案是四个，也就是说现在p指向a的最后一个字节的后一个字节。

也就是说，指针需要知道自己指向的变量的地址，还要知道指向的变量的长度，这个长度一方面是为了做++的操作，另一方面是为了解引用（如*p=1）时，能够获取到完整的变量。

好了，现在回到void，先明确一点：void指针是没有“指向变量的类型”这个参数的。

所以：1.void不允许自增，2.void不允许解引用

3.回到compare函数

1
2
3

int compare(const void* a, const void* b) { 
    return *(int*)a - *(int*)b; 
}

传入了两个常量void指针a，b，这个函数要做的就是比较待排序元素。
因为这里我要排序的是int数组，所以使用(int)a，把a变成一个int类型的指针，这样子a就拥有了指向的变量的长度这个参数，然后(int)a，对(int)a解引用，获取那个int类型的值。b同理。然后比较a和b的大小。注意，在compare函数中，要求compare返回的值的格式为：a要排在b后面，则a>b时返回正值，反之同理。

4.如何实现自己的mysort函数

先看mysort函数原型

1	void mysort(void* base, size_t num, size_t size, int(comparator)(const void, const void*)) ;

可以发现，为了让mysort函数可以排序任意的类型的数组，就必须让base这个参数为void，因为任意的指针都可以赋值给void指针。

但是现在问题来了，我们手里只有三个值，没有保存变量类型的基地址base，待排序的元素数量num，待排序的元素的类型所占的字节大小size。

主要要实现以下三点：1.把每个待排序的元素区分开来。2.实现待排序元素之间的交换。3.实现待排序元素之间的比较。

这三点按理来说都是需要知道待排序元素的类型的，但是mysort是获取不到的。（其中第三点因为比较是使用compare函数实现的，而用户自定义的compare函数，用户肯定是知道元素类型的，这个可以不用烧脑了）

先看一段普通的带参选择排序

for (i = 0; i < num; i++) {
		key = i;
		for (j = i + 1; j < num; j++) {
			if (nums[key]>nums[j]) {
				key = j;
			}
			if (key != i) {
                int temp = nums[key];
                nums[key] = nums[i];
                nums[i] = temp; 
			}
		}
	}

对比刚才要实现的三点，我们可以发现重点在第4行和第8-10行。

先上一段代码

for (i = 0; i < num; i++) {
		key = i;
		for (j = i + 1; j < num; j++) {
			if (comparator((char*)base + size * key, (char*)base + size * j) > 0) {
				key = j;
			}
			// 进行交换
			if (key != i) {
				exchangeVoid((char*)base + size * key, (char*)base + size * i, size);
			}
		}
	}

其中exchangeVoid()函数定义如下。（此处征得sya同学的同意，偷懒的我直接用他写好的代码了）

void exchangeVoid(void * from, void *  to, size_t size) {
	char * fromPtr = (char *)from;
	char * toPtr = (char *)to;
	char temp;
	for (int i = 0; i < (int)size; i++) {
		temp = *(fromPtr + i);
		*(fromPtr + i) = *(toPtr + i);
		*(toPtr + i) = temp;
	}
}

先来解决第四行的问题，也就是使用comparator()来比较。

comparator()函数需要拿到已经分开的两个待排序的元素（这里只用把待排序的元素的void*地址传过去即可，因为在comparator()函数里已经实现了强制类型转换）

这一步呢，应该是比较nums[key]和nums[j]的大小，所以使用了(char)base + size key来拿到nums[key]，nums[j]同理。

现在先暂停一下，看看为什么要突然使用一个char*。

回忆一下char的大小，是一个字节，而c语言中没有半个字节的变量，所以可以把char的大小当成单位长度。

所以我们先把base指针变成单位长度的指针，然后加上size*key，跳过key个size，拿到nums[key]。（推荐在草稿纸上画一个图来理解）。这里假如待排序的是整数，那么size就是4个单位长度。

实际上如果编译器6一点，可以直接这样写：base + size * key，但是推荐还是加上char*强制类型转换，比较稳妥。

好了第一个问题解决了，我们继续解决下一个问题：交换。

我们还是使用char*这个骚操作来完成。

现在先好好读一下sya大佬的exchangeVoid()函数，同样使用了类似上一步的方法，拿到了nums[key]和nums[i]。

但是这个函数与comparator()函数不同的是，这个函数不是由用户自定义的，也就是说需要适应所有的可能的数据类型，并对他们交换。

怎么做呢？其实第一部里面的(char *)理解了，这一步也就显而易见了。

假设现在有待排序元素是有46个字节大小（这个字节大小通过size参数获得）的结构体。同样，把这个结构体拆分成46个单位长度（也就是46个char）。

然后我们就有了第一组拆分成46个char的结构体，和第二组46个char的结构体，然后要实现他们的交换。显而易见，一次把第一个char和第一个char交换、把第二个char和第二个char交换······

这样我们就实现了比较和交换，就可以用来排序啦！

5.memcpy函数

先看百度百科：

void memcpy(void dest, const void *src, size_t n);
从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中

再来新的mysort函数：

void mysort(void* base, size_t num, size_t size, int(*comparator)(const void*, const void*)) {
	int i, j, key;
	void* temp = malloc(size);
	for (i = 0; i < num; i++) {
		key = i;
		for (j = i + 1; j < num; j++) {
			if (comparator((char*)base + size * key, (char*)base + size * j) > 0) {
				key = j;
			}
			// 进行交换
			if (key != i) {
				//exchangeVoid((char*)base + size * key, (char*)base + size * i, size);
				memcpy(temp, (char*)base + size * key, size);
				memcpy((char*)base + size * key, (char*)base + size * i, size);
				memcpy((char*)base + size * i, temp, size);
			}
		}
	}
};

我觉得已经不需要讲那么多啦，上面的能理解，这个soeasy。

然后部长我去翻了一翻qsort() memset() memcpy()的源码，惊讶的发现原来也是用char*来操作的，，，

不过这样写简洁一点嘛，而且库函数一定写的比自己好.jpg。

第三期Task-LeetCode算法题

发表于 2017-07-24

第三期Task-LeetCode算法题

3Sum

先附上题目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

看到这道题我的第一想法就是用调用2Sum函数来写，但是发现2Sum返回的是索引，而这题需要的是数值。想通这点之后就意识到了重复查找的问题。

因为2Sum是用的hash表做的，速度还不错，因此最开始我的想法也还是用hash来写。然后有了如下的solution1。

public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> for_return = new LinkedList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i != 0 && nums[i] == nums[i-1]) continue;
            Hashtable hashtable = new Hashtable();
            for(int j = i + 1; j < nums.length; j++){
                int tag = 0 - nums[i] - nums[j];
                if(hashtable.containsKey(tag)){
                    if((int)hashtable.get(tag) == 0){
                        for_return.add(Arrays.asList(nums[i],tag,nums[j]));
                        hashtable.replace(tag, 0, 1);
                    }
                }
                else hashtable.put(nums[j] , 0);
            }
        }
        return for_return;
    }

首先，调用了Arrays类的方法sort对nums数组进行排序。然后进入外部循环，循环体内的第一句是后续优化时加上的，因为排序之后，当最小的数都大于0，结果一定大于0，所以也就不需要继续判断了（加上这句才AC的）。第二句是防止重复（因为已经排序好了，相同的数已经放在了一起，所以很容易跳过不需要判断的重复数）。在内部循环中，从索引i+1开始，使用类似2Sum的hash解法的方法判断结果。为了避免重复，在每个数第一次进入hash表时，给的值是0，然后在这个数被使用之后，调用replace方法，把值修改为1，下次不再使用这组数。

这里贴上2Sum的hash解法。

public int[] twoSum(int[] nums, int target) {
        Hashtable hashtable = new Hashtable();
        int for_return[] = new int[2];
        for(int i = 0;i < nums.length;i++){
            int tag = target - nums[i];
            if(hashtable.containsKey(tag)){
                for_return[0] = (int)hashtable.get(tag);
                for_return[1] = i;
                break;
            }
            hashtable.put(nums[i],i);
        }
        return for_return;
    }

这个解法跑完之后险险AC（多次优化后421ms），但是只beat了2.31%。然后我就去看了看这题的标签，2333竟然在Two Pointer里面。然后才有了solution2。

public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> for_return = new LinkedList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i != 0 && nums[i] == nums[i-1]) continue;
            int low = i + 1, high = nums.length -1;
            while(low < high){
                if(nums[i] + nums[low] + nums[high] >0){
                    high--;
                }
                else if(nums[i] + nums[low] + nums[high] < 0){
                    low++;
                }
                else{
                    for_return.add(Arrays.asList(nums[i],nums[low],nums[high]));
                    while(low < high && nums[low] == nums[low + 1]) low++;
                    while(low < high && nums[high] == nums[high - 1]) high--;
                    low++;
                    high--;
                }
            }
        }
        return for_return;
    }

这个思考的时间比hash长。但是感觉这个代码比hash要优雅。最主要的是时间短…一下子就77ms。

[x] 一味的使用hash表也不一定好，能不查找就不查找。

Climbing Stairs

emmm去年c语言大赛做过这道题，从后往前分析一下就是简单的斐波那契数列。附上代码走人。

public int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        int first = 1;
        int second = 1;
        int temp;
        for(int i = 1; i < n; i++){
            temp = second;
            second += first;
            first = temp;
        }
        return second;
    }

Course Schedule

先上题目

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

拓扑排序：

在有向图中选择一个没有前驱的节点进行操作。
从有向图中删除该顶点和所有以它为尾的弧。
重复1&2
之后两种情况，a.所有节点均被操作过–>没有环（也就是可以修完所有科目），b.存在没有被操作过的节点–>有环（准备收到一个环的你能做的岂止于此）。

那么思路其实就是判断第四步进入a还是b了。

public boolean canFinish(int numCourses, int[][] prerequisites) {
       List<List<Integer>> edges = new LinkedList<>();
        int[] in = new int[numCourses];
        List<Integer> temp;
        Queue<Integer> queueForFS = new LinkedList<>();
        int FScounter = 0;
		for (int i = 0; i < numCourses; i++) {
			temp = new LinkedList<>();
			edges.add(temp);	
		}
		for (int i = 0; i < prerequisites.length; i++){
			edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
		}
        for (int i = 0; i < prerequisites.length; i++) {
			in[prerequisites[i][0]]++;
		}
        for (int i = 0; i < numCourses; i++) {
			if(in[i] == 0){
				queueForFS.offer(i);
			}
		}
        while(!queueForFS.isEmpty()){
        	FScounter++;
        	for (int i : edges.get(queueForFS.poll())) {
				in[i]--;
				if(in[i] == 0){
					queueForFS.offer(i);
				}
			}
        }
        return FScounter == numCourses;
    }

第一个循环初始化List>。第二个循环建立表。第三个循环统计入度。第四个循环将所有没有前驱的节点入队。准备工作完成之后，就可以进行环的判断。这里使用了一个FScounter来统计遍历过的节点数量。（至今没搞清楚foreach循环和for循环哪个快…）

MinStack

开始觉得不优雅，不想用第二个List来实现。然后就…各种尴尬，最后还是妥协了。另外真的觉得java的栈和队列是过度包装了。。。

public class MinStack {
    private List<Integer> head;
    private List<Integer> mIntegers;
    /** initialize your data structure here. */
    public MinStack() {
        head = new LinkedList<>();
        mIntegers = new LinkedList<>();
    }
    
    public void push(int x) {
        head.add(0,x);
        if(mIntegers.isEmpty() || x <= getMin()){
        	mIntegers.add(0,x);
        }
    }
    
    public void pop() {
    	if(!head.isEmpty()){
    		if(head.get(0) == getMin())
    			mIntegers.remove(0);
    		head.remove(0);
    	}
    }
    
    public int top() {
        return head.get(0);
    }
    
    public int getMin() {
        return mIntegers.get(0);
    }
}

Hello World

发表于 2017-06-28

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment