题目描述

785. Is Graph Bipartite?

Given a graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

即判断给定的图是否是二分图：

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B)，则称图G为一个二分图。

算法分析

二分图的判断可以看作染色问题。对于图中的每一个顶点S，与它直接相邻的任一顶点N，其颜色必然与S不同，则这样的图是一个二分图。

最常用也最简单的方法就是遍历（DFS或BFS）整张图，用两种不同的颜色A和B，对每个顶点染色。选定一个顶点S开始，对其进行染色，再访问它的邻居顶点N。若：

• N还未被染色，即对它染色与S不同的颜色，并继续访问S的邻居顶点。
• N已被染色，且其颜色与S相同，则该图不是一个二分图。
• N已被染色，但其颜色与S不同，则继续查看和访问其它邻居节点。

Hexo入门

安装Node.js和npm

前往Node.js官网下载并安装Node.js。新版的Node.js已经集成了npm。在命令行中检测安装：

1
2
3
4

> node -v
v6.10.1
> npm -v
3.10.10

安装Hexo

使用npm安装Hexo：

1

> npm install -g hexo-cli

初始化博客

在你准备存放博客本地文件的目录下，输入：

1

> hexo init blog

在当前目录下，会新建一个blog文件夹，即你的博客在本地所有资源的根目录。

之后，进入到根目录下，创建你的第一篇博客：

1
2

> cd blog
> hexo new my-firts-post

利用Hexo生成静态文件：

1

> hexo g

启动本地服务器查看博客：

1

> hexo s

默认下访问网址为http://localhost:4000/。在浏览器输入后就可以看到整个博客的雏形了。

题目描述

72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

算法分析

这是一道很经典的动态规划问题。使用dp[i][j]来表示word1的前i个字符转变为word2的前j个字符的编辑距离。为了方便，以下假设word1/word2的下标由1开始，即word1[1:3]表示字符串{word1[0], word[1], word[2]}。那么，dp[i][j]表示word1[1:i]和word2[1:j]的编辑距离。

基本解法

题目描述

LeetCode 55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

算法分析

首先，通过遍历每个点所能到达的下标，是最基本的思路。通过用-1来标记表示通过该点可以到达最后一个位置。

题目描述

LeetCode 10. Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘‘.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “ca*b”) → true

即要求实现简单的包含'.'和'*'的正则表达式匹配。

8.9 In the HITTING SET problem, we are given a family of sets {S1,S2,…,Sn}, and a budget b, and we wish to find a set H of size ≤b which intersects every Si, if such an H exists, In other words, we want H⋂Si≠∅ for all i.

Show that HITTING SET is NP-complete.

碰撞集（Hitting Set）问题是指给定一组集合 {S1,S2,…,Sn}和一个预算b，我们希望找到一个集合H，满足H与所有的Si相交（存在公共元素）且H的大小不超过预算b。即是说，H⋂Si≠∅。

现在要求证明碰撞集问题是一个NP完全问题。

证明如下：

首先需要知道顶点覆盖问题。顶点覆盖（Vertex Cover）问题是指给定图G(V, E)和预算k，希望从V中找到一个大小小于等于k的顶点集合U，使得U能够覆盖所有的边，即V每一条边至少有一个顶点属于U。

基本解法

题目描述

题目链接

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Read more »

在apiary.io上，单纯使用mock server进行测试显然是不够的。当试图使用localhost进行Production测试时，会提示“Proxy request fail”的提示。这是因为apiary需要通过远程代理来访问你的本地服务器，因此在Host属性中填写localhost是无法达到目的的。利用ngrok，便可以在开发完成后运行本地服务器进行测试。

1. 下载安装ngrok:

   在官网下载压缩包，并解压，安装：

   1	$ unzip /path/ngrok.zip

2. 利用ngrok代理本地服务器：

   首先要在本地运行服务器。

   以localhost:8080为例，在ngrok安装目录下：

   1	$ ./ngrok http 8080

   得到：

   1 2 3 4 5 6 7 8 9 10 11

   ngrok by @inconshreveable (Ctrl+C to quit) Session Status online Version 2.2.8 Region United States (us) Web Interface http://127.0.0.1:4040 Forwarding http://33059e51.ngrok.io -> localhost:8080 Forwarding https://33059e51.ngrok.io -> localhost:8080 Connections ttl opn rt1 rt5 p50 p90 0 0 0.00 0.00 0.00 0.00

   其中http://33059e51.ngrok.io就是代理后的服务器地址。

   Read more »