LeetCode: Add Two Numbers 解题报告

题目描述:
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


分析:对两个链表进行带进位求和,若长度不一致填零

题解:没什么算法,模拟。

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
#include <cstddef>

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ans_pointer = NULL, *ans_head = NULL;

int sum = 0;
bool carry_flag = false;
while (true) {
sum = getSum(getNodeVal(l1), getNodeVal(l2), carry_flag);

if (ans_pointer) {
ans_pointer->next = new ListNode(sum);
ans_pointer = ans_pointer->next;
} else {
ans_head = new ListNode(sum);
ans_pointer = ans_head;
}
nextPointer(l1);
nextPointer(l2);
if ( !(l1 || l2) ) {
if (carry_flag) { ans_pointer->next = new ListNode(1); }
break;
}
}
return ans_head;
}
private:
int getNodeVal(const ListNode* const node) const {
return node ? node->val : 0;
}

int getSum(const int val1, const int val2, bool &carry_flag) const {
int sum = val1 + val2 + carry_flag;
carry_flag = (sum >= 10);
return sum % 10;
}

void nextPointer(ListNode* &node) const {
node = node ? node->next : NULL;
}
};

LeetCode: Two Sum 解题报告

题目描述:
Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2


分析:题中要求找到数组number中“和”为target的两个元素对应的索引。

题解:首先构造一个Hash{ value->idx },之后遍历每个元素Numbers[i]对应的Target - Numbers[i]是否在Hash Table中,若存在则输出解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <unordered_map>

class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
std::unordered_map<int, int> num_idx_map;
auto n = numbers.size();
for (int i = 0; i < n; i++) num_idx_map[numbers[i]] = i + 1;

for (int i = 0; i < n - 1; i++) {
if ( num_idx_map.find(target - numbers[i]) != num_idx_map.end() ) {
int current_num_idx = i + 1;
int match_num_idx = num_idx_map[target - numbers[i]];

if (match_num_idx != current_num_idx) return { current_num_idx, match_num_idx };
}
}
}
};

从Octopress迁移到Hexo

前阵子有幸地参与到一个 Road Map Project 从无到有的开发过程,整个项目做下来,感触很多。随着项目进入收官阶段,可以自由支配的时间渐渐多一些,准备有规律地更新博文。

难得一见的北京蓝

这次正式从Octopress迁移到Hexo,个人感觉Hexo更加的 Simple Stupid,从Setup到Deploy的过程相当流畅。

关于Hexo的部署,国内朋友的最佳实践是同时发布在GithubGitcafe上,之后通过DNSpod分散国内外的流量,保证访问速度。感兴趣的同学可以去读一下Reference中的两篇文章。

我个人比较懒,并没有通过DNS来分流,只是单纯地在Github上备份source文件夹,将其软链到Hexo中。然后在Gitcafe上托管Blog Site

更新于:2015.6.23
现在还是部署回Github,因为Gitcafe常常出现无法访问的情况。

Reference

Hexo Landscape主题的字体和JS库优化
Hexo 同时支持Github和Gitcafe

所谓工作经验

在学校的时候,不理解为什么有些职位,对工作经验有很严苛的要求。因为我并不认为工作经验和技术能力之间存在这什么必然的联系。

不过近些天来开始意识到:工作经验真的不一定和技术能力成正比,但是和团队协作能力基本上是成正比的。

可爱的Advertising Team同学们

到公司后,逐渐地参加到商业软件项目的开发中,通过这段时间的观察,发现到对于一个职业的软件工程师,需要具备的能力并不限于算法和工程问题。还要学会换位思考,站在多个角色的角度来看同一个问题,来保证顺畅的沟通。

软件开发的流程中通常包含了:

  • 产品经理
    • 需求分析文档
  • 开发工程师
    • 技术设计文档, 编码, 时间估算, 代码审查
  • 测试工程师
    • 用例设计文档, 时间估算, 自动化测试, 本地测试, 集成测试
  • 运维工程师
    • 部署上线

产品经理在做需求文档的时候,一定征求会开发人员的意见,来做出一个可行的产品设计。

工程师在做技术文档设计和时间估算的时候,也会在团队中其他工程师的建议下,调整设计文档和Story Point预估,来保证设计的逻辑正确性以及可实施性。

部署的过程更需要开发工程师和运维工程师完全地理解彼此的需求,才能保证项目上线不出差错。

在每个环节,如果可以理解每个角色对于一个项目的关切是什么,定会催化团队内部的化学作用,提高团队产出的质量。

[Rails] 所谓MVC

使用MVC的Web开发框架有很多,比如PHPZendPythonDjangoGolangBeego。这篇文章主要介绍一下MVC的基本概念。

何为MVC

为了明确一个Web Application中各个部分的职责,我们人为规定三个层级:控制器(Controller),模型(Model)和视图(View),这是一种设计上的解耦。

为了直观地解释这三个层级的概念,我们假设这它们分别对应代码层面的三个类:

1
2
class FooModel
end
1
2
class FooView
end
1
2
class FooController
end

调度器(Controller) — 完整的request生命周期

我们可以简单的理解为:用户在浏览器上输入的每个合法的URL,都将被映射到Controller类上的一个实例方法。该实例方法是一次request入口,负责调度程序的各个部分,返回web response给浏览器。

所谓入口,指的是一次访问的整个生命周期,都随着这个方法的开始而开始,结束而结束。从这个角度来看,我们完全可以不使用模型和视图,就能完成一个Web应用。

1
2
3
4
5
6
7
8
9
10
11
12
# Rails中URL和实例方法的映射关系在routes.rb中设置
# 比如 '/index' => Controller#index 可以规定:
# 当用户在browser中输入"http://yoursiteurl.com/index"时
# 执行Controller类的index方法

class FooController
def index
@counter = @counter ? @counter + 1 : 0

render html: "<p>你是该网站的第#{@counter}名访客</p>".html_safe
end
end

模型(Model) — 数据持久化存储

我们可以看到,在一次request结束后,Controller实例方法中分配的内存会被回收,无法再次被使用。为了能够将Controller处理过程中的数据在今后继续使用,我们需要对这部分数据进行持久化存储。

所以我们期望有一个类,他的所有变量都永远不会消失。同时,我们还希望它可以提取对数据操作的逻辑(如例中的counter计数),方便今后复用。我们将它叫做模型(Model),至于它如何做到所有的变量永不消失,我们回头再讲。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class FooModel
# ...
def counter
@counter = @counter ? @counter + 1 : 0
save # 持久化存储,具体实现细节在后面的文章会讲

@counter
end
# ...
end

class FooController
def index
model = FooModel.new
render html: "<p>你是该网站的第#{model.counter}名访客</p>".html_safe
end
end

视图(View) — 页面展示

在上面的两个例子中都出现了类似render html: xxx之类的代码。如果我们不想在Controller中出现HTML代码,可以把它放在View层。

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
class FooModel
# ...
def counter
@counter = @counter ? @counter + 1 : 0
save # 持久化存储,具体实现细节在后面的文章会讲

@counter
end
# ...
end

class FooView
def index(counter)
"<p>你是该网站的第#{counter}名访客</p>"
end
end

class FooController
def index
model = FooModel.new
view = FooView.new

render html: view.index(model.counter).html_safe
end
end

小节

1. 调度器(Controller)对于一个程序来说是必须存在的,它负责得到输入,返回输出
2. 我们用模型(Model)这个概念来抽象调度器(Controller)中,关于数据存取、逻辑运算相关的代码,以便独立地维护它们。
3. 我们用视图(View)这个概念来抽象调度器(Controller)中,关于数据展示格式相关的代码,以便独立地维护它们。

[Rails] 学习报告

在阅读这个系列文章之前,希望读者对于网络开发有一些了解,最好能够先完成以下课程的学习:

哈佛大学公开课:计算机科学cs50 (Web部分)
哈佛大学公开课:构建动态网站

其实,终究Rails只是一个框架,他只是一种设计思想的实体化的产物。你不能说傻学怎么用这个框架,所以你不能一上来就直接学各种Rails的feature。

最好的学习方法,是学习这个框架的设计思路。因为如果这样,即使之后你们不再使用rails,你也可以用ruby开发或者组装出另一套新的框架。甚至如果你们不再使用ruby,你也可以用其他语言,写出基于另一个语言的开发框架。这些都超越了语言和框架的本身,是大家共性的东西,是精髓。而且就我个人来讲,这个概念可以更广义地应用到更多的方面,此处不多深入,有机会时会写一篇文章。

[Rails] 所谓MVC
[Rails] 从Request到Response

sudo brew install

近些天来一直受到一个问题的困扰,在执行activemq start后,能够看到进程已经启动,然而根本没有什么卵用,完全连不上localhost:8161/admin/。改成sudo activemq start,问题就解决了。

今天终于发现了问题的原因:当初我在用brew安装activemq的时候就是用的是:

1
$ sudo brew install activemq

而正确的安装方式是:

1
$ brew install activemq

解决方案:

1
$ brew reinstall activemq

如果再这么做的话,这个世界,就清静了:

1
$ brew reinstall `brew list`

关于Everkeyword

为什么叫Everkeyword

学生时期,比较爱想,有过一个创业的Idea。当时就觉得Everkeyword这个名字非常适合想象中的“产品”。从那时候开始,就一直想把这个域名注册下来。

Everkeyword是做什么的

Everkeyword现在是我的个人技术博客,而不再是那个产品。我会在上面分享一些技术方面的心得体会。

Ruby Metaprogramming

Bill is a good mentor.

长达三个月的培训过程,过得非常的舒心。在中后段期间,每天下午都能抽出一段时间,读一读《Ruby元编程》。

读过这本书的人,应该都会爱上Ruby这门语言,并且理解它为何要设计成这个样子。书中的描写十分生动,有时甚至会让人觉得,自己真的和Bill工作在一起,每天在他的身上学习新的知识。找时间写一篇这本书的读书报告。

目录
第一部分 Ruby元编程

  • 对象模型
  • 方法
  • 代码块
  • 类定义
  • 编写代码的代码

第二部分 “Rails中的元编程”

  • ActiveRecord的设计
  • 深入ActiveRecord
  • 安全元编程

Rails开发常用Vim插件

RailsCast China的时候,收集了一些常用来写Ruby on Rails的Vim插件:

  • commandT
    功能: 与Sublime的commandT快捷键类似,可以实现当前项目文件查找
  • CtrlP
    功能: 实现文件的查找,并快速切换;
    “CommandT”和”CtrlP”的功能基本一致,顾名思义,通过快捷键”command+T”和”Ctrl+P”,呼叫插件。

  • Rails.vim
    常用功能:
    “:Rfind/:1R/:find”: 可以用来查找目录中的文件
    “:Rfunctionaltest”: 跳转到单元测试
    “:RController”: 跳转到Controller
    “:RVfunctionaltest”: (横屏分屏)打开单元测试
    “gf”: 代码上线文相关跳转
    详见文档

  • snipMate
    功能: 输入简写展开
    例: ‘bt’+Tab->‘belongs_to’, ‘hm’+Tab-‘has_many’, ‘rp’+Tab->“render :partial => ‘item’”, …
    ruby.snippets文件中有各个简写展开形式的记录,也可以通过改写这个文件,自定义展开形式

  • ack.vim
    功能: 根据文件内容查找文件,并切换文件
    例: “:Ack ‘pattern’”

  • The NERD tree
    功能: 显示文件目录;

Reference:

Rails with Vim : http://Railscasts-china.com/episodes/Rails-with-vim