好久不见

发表于 2017-11-04 |

上次发日志还在读书呢，临近毕业的时候。现在来到深圳依然工作3个月了，生活很忙碌很充实，几乎没有自己的时间。目前还是蛮喜欢这种节奏的，希望能快速成长。

一切都是最好的安排

2017年11月04日11:48:04

答辩完成,坐等毕业

发表于 2017-05-30 |

一年以来

好久没回来了..多说的插件貌似也跪了囧

这一年来真的压力蛮大的，回想一年前的今天，先是感情问题，后来又是应届找工作，又是毕业论文，搞的整个人都蛮疲惫的，特别是这学期，除了3月初跟发小去乌镇转了一圈之外，天天在实验室，回来之后又是连续79天实验室了。好在运气还算不错，顺利发表了一篇；到了答辩，老师们也蛮友好的，也算是跌跌撞撞。马上就要踏进下一段旅程了。

阅读全文 »

Google onsite and Move on

发表于 2016-12-24 |

Google onsite

趁记忆还鲜活，记录下 Google 的经历吧。

阅读全文 »

New Journey

发表于 2016-10-07 |

生活不总是如意的，每个人都有选择的权利。做到问心无愧。

不悔过往，不惧将来

真的要 move forward 了

2016年10月07日20:52:11

滴滴2017秋招笔试地下迷宫

发表于 2016-09-20 |

##题目描述

小青蛙有一天不小心落入了一个地下迷宫，小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单，假设这是一个n*m的迷宫。迷宫每个位置为0或者1. 0代表这个位置有障碍物，小青蛙到达不了这个位置；1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置。地下迷宫的出口在(0,m-1)(保证这两个位置都是1，并且保证一定有起点到终点可达的路径)。小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值。向上爬一个单位距离需要消耗3个体力值，向下移动不消耗体力值。当小青蛙的体力值等于0时候还没有到达出口，小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用今生的体力值跳出迷宫（即达到(0,m-1)的位置

输入：

输入 n+1行：
第一行为3个整数n,m(3<=m,n<=10),P(1<=P<=100)
接下来的n行：
每行m个0或者1，以空格分隔
输出：
如果能逃离迷宫，则输出一行体力消耗最小的路径，输出格式见样例所示；如果不能逃离迷宫，则输出“Can not escape!”。
测试数据保证答案唯一
输入例子：

4 4 10
1 0 0 1
1 1 0 1
0 1 1 1
0 0 1 1

输出例子：

[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

思路：层次遍历（这个思想真的蛮重要的..），每次更新最佳值，直到找到了终点，个人感觉比 dfs 好使..（也有 dfs 代码）。后来做的乐视那个蚂蚱跳跃的题目也是如此，过几天忙过去在更新上来.做题的时候一定要先想思路，别急着代码..磨刀不误砍柴工！

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * @author houweitao
 * @date 2016年9月18日下午2:59:03
 */

// 4 4 10
// 1 0 0 1
// 1 1 0 1
// 0 1 1 1
// 0 0 1 1

public class Main {
	public static void main(String[] args) {
		Main main = new Main();
		main.init();
	}

	private void init() {
		Scanner scanner = new Scanner(System.in);
		String[] first = scanner.nextLine().split(" ");

		int n = Integer.valueOf(first[0]);
		int m = Integer.valueOf(first[1]);
		int have = Integer.valueOf(first[2]);

		int[][] map = new int[n][m];

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				map[i][j] = scanner.nextInt();
			}
		}
		forgEscapeBFS(map, have);

		forgEscapeDFS(map, have);
	}

	void forgEscapeBFS(int[][] map, int have) {
		int m = map[0].length;

		Map<Point, Point> record = new HashMap<>();
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] == 1) {
					Point cur = new Point(i, j, Integer.MAX_VALUE);
					record.put(cur, cur);
				}
			}
		}
		Point end = new Point(0, m - 1, 0);

		Map<Point, Point> leaf = new HashMap<>();
		record.put(end, end);
		leaf.put(end, end);

		while (!leaf.isEmpty()) {
			Map<Point, Point> tmp = new HashMap<>();
			for (Map.Entry<Point, Point> entry : leaf.entrySet()) {
				Point point = entry.getValue();
				int x = point.x, y = point.y;
				help(x, y, point, tmp, map, record);
			}
			leaf = tmp;
		}

		Point getStart = new Point(0, 0, Integer.MAX_VALUE);
		Point start = record.get(getStart);

		if (have >= start.need) {
			StringBuffer sb = new StringBuffer();
			while (start != null) {
				sb.append(start + ",");
				start = start.next;
			}
			System.out.println(sb.toString().substring(0, sb.toString().length() - 1));
		} else
			System.out.println("can not secape");
	}

	private void help(int x, int y, Point point, Map<Point, Point> tmp, int[][] map, Map<Point, Point> record) {
		doubleHelp(x + 1, y, 3, point, tmp, map, record);
		doubleHelp(x - 1, y, 0, point, tmp, map, record);
		doubleHelp(x, y + 1, 1, point, tmp, map, record);
		doubleHelp(x, y - 1, 1, point, tmp, map, record);
	}

	private void doubleHelp(int x, int y, int now, Point point, Map<Point, Point> tmp, int[][] map,
			Map<Point, Point> record) {
		if (in(map, x, y) && map[x][y] == 1) {
			now = point.need + now;
			Point seed = new Point(x, y, now);
			if (now < record.get(seed).need) {
				boolean judge = true;
				if (tmp.containsKey(seed))
					if (now > tmp.get(seed).need)
						judge = false;

				if (judge) {
					tmp.put(seed, record.get(seed));
					record.get(seed).next = point;
					record.get(seed).need = now;
				}
			}
		}
	}

	private boolean in(int[][] map, int x, int y) {
		if (x >= 0 && x < map.length && y >= 0 && y < map[0].length)
			return true;
		else
			return false;

	}

	class Point {
		int x;
		int y;
		int need;
		Point next;

		Point(int x, int y, int need) {
			this.x = x;
			this.y = y;
			this.need = need;
		}

		@Override
		public String toString() {
			return "[" + x + "," + y + "]";
		}

		@Override
		public int hashCode() {
			return x + y;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Point) {
				Point o = (Point) obj;
				return o.x == x && o.y == y;
			}
			return false;
		}
	}

	// -------------

	int cost = Integer.MAX_VALUE;
	List<Point> finalPath = new ArrayList<>();

	void forgEscapeDFS(int[][] map, int have) {
		List<Point> tmp = new ArrayList<>();
		Set<Point> set = new HashSet<>();

		// dfs(0, 0, 0, map, tmp, set);
		dfs(0, 0, 0, map, tmp);
		System.out.println(finalPath);
	}

	private void dfs(int x, int y, int curCost, int[][] map, List<Point> tmp, Set<Point> set) {
		if (!in(map, x, y) || map[x][y] == 0) {
			return;
		} else if (x == 0 && y == map[0].length - 1) {
			Point cur = new Point(x, y, 1);
			tmp.add(cur);
			System.out.println(curCost + ": " + tmp);
			if (curCost < cost) {
				finalPath = new ArrayList<>(tmp);
			}
			tmp.remove(tmp.size() - 1);
		} else {
			Point cur = new Point(x, y, 1);
			if (!set.contains(cur)) {
				set.add(cur);
				tmp.add(cur);

				dfs(x + 1, y, curCost, map, tmp, set);
				dfs(x - 1, y, curCost + 3, map, tmp, set);
				dfs(x, y + 1, curCost + 1, map, tmp, set);
				dfs(x, y - 1, curCost + 1, map, tmp, set);

				tmp.remove(tmp.size() - 1);
				set.remove(cur);
			}
		}
	}

	// 不用 set 判断。更加节省空间和时间 2016年09月18日18:53:16
	private void dfs(int x, int y, int curCost, int[][] map, List<Point> tmp) {
		if (!in(map, x, y) || map[x][y] == 0) {
			return;
		} else if (x == 0 && y == map[0].length - 1) {
			Point cur = new Point(x, y, 1);
			tmp.add(cur);
			System.out.println(curCost + ": " + tmp);
			if (curCost < cost) {
				finalPath = new ArrayList<>(tmp);
			}
			tmp.remove(tmp.size() - 1);
		} else {
			Point cur = new Point(x, y, 1);
			map[x][y] = 0;
			tmp.add(cur);

			dfs(x + 1, y, curCost, map, tmp);
			dfs(x - 1, y, curCost + 3, map, tmp);
			dfs(x, y + 1, curCost + 1, map, tmp);
			dfs(x, y - 1, curCost + 1, map, tmp);

			tmp.remove(tmp.size() - 1);
			map[x][y] = 1;
		}
	}

}

2016年09月20日01:05:30

一个月以来

发表于 2016-08-06 |

一个月之前，因为种种原因，决定要加强代码，为了以后。为了2个人。于是乎在 leetcode 上新建了一个 session，废弃掉之前大半年陆陆续续刷的120道题目，从头再来。

2016年07月06日到现在 2016年08月06日

整整一个月了。

这一个月以来真的不容易。同时兼顾百度那边的实习，以及这里的算法。基本上一回到家就是刷题，或者想类似的事情。睡觉睡觉从1点半到4不等，每天得花3~4小时在上面。

成果如何呢？

这一个月以来做了250道题目。每道题50行代码的话，这一个月写了大概 15K 行的代码。真的有不小进步。

给自己鼓励下。革命尚未成功。

周日加油。

2016年08月06日01:06:03

离开光谷，下一段旅程开始！

发表于 2016-05-20 |

今天收拾了下桌子，收拾了下电脑，把个人信息都抹去。想起我去年4月份来这里的时候，浏览器里面还可以自动登录师姐的百度网盘、新浪微博等账号..

上周的时候吧，先后跟姬老师、聂老师讲了下自己的打算，离开光谷，回到学校，去准备即将到来的校招以及毕业论文。2位老师都很爽快的答应了，去年的2个师兄都是留到了8月底，所以真的特别感激。今天下午的时候，去跟聂老师讨论了下文档的事情，然后就是这样了。感觉少了点什么。

回想去年刚来的时候，可以说是很水很水的一个人，聂老师给我出了一个题目，让我找出小于 N 的所有的素数，我磕磕绊绊，写的很慢，很囧。不过聂老师还是收留了我。这一年里，真的进步了不少，参与了一些项目，写了不少代码，认识了不少人。BYS,XCL,GS,GR,SJW,CX,HJW..真的是一段很特别的旅程。感谢大家的关照。

很后悔离开的时候没有去聂老师办公室道谢，我这人总是这样丢三落四，过了才想起来..

anyway，这一页翻过去了。摆在眼前的：腾飞杯淘汰赛，她回来了，百度实习。慢慢走，比较快。加油！

2016年05月20日21:31:24

实现虾米音乐免虾币下载

发表于 2016-05-01 |

平心而论，虽然没了杰伦 coldplay，但是对于冷门的歌曲，虾米的曲库还算比较全的，是一个不错的选择。之前下载歌曲的时候用过各种 chrome 插件，大概的原理都是浏览器听歌的时候嗅探访问地址，或者到浏览器缓存中招到歌曲。也一直没去深究没想去做一个自己的下载器。

昨天晚上的时候看到有人提到歌曲下载：据网易云音乐上面的歌单来下载 FLAC 无损音乐，于是乎研究了下虾米的歌曲下载。今天花了2个小时把虾米的下载写了出来。

分析

通过对浏览器发出请求的分析容易得出，歌曲的下载地址是如下形式的url：http://m5.file.xiami.com/46/1046/2100200848/1774781460_58802904_l.mp3?auth_key=3200136d589894789ba042e2843e2b0c-1462147200-0-null

这里关键是要找出auth_key。

这里要用到这个地址：http://www.xiami.com/song/playlist/id/[歌曲ID]/object_name/default/object_id/0

根据歌曲的 ID,找到上面的链接，你会看到一个 xml，然后根据里面的 locations 来找出原始的下载链接，这里 locations 是用凯撒方阵加密的，破解不难，不过要注意不是齐整方阵的情况。

拿到下载链接后，下载就简单啦~！能下载一首歌，下载一个专辑也不是难事啦~！

GitHub 地址：DownloadXiaMi

效率

本地测试：此时时刻巡回演唱会 25+1 首歌曲，全部下载成功，共133M，10M电信带宽，耗时1分38秒。

简单的数学：1.25M/S * 98S = 122.5M

说明本程序的速度还是相当可以的（电信带宽竟然超过了平均？）

Just For Fun ^_^

2016年05月01日16:41:15

好的程序员和差的程序员差别是什么

发表于 2016-04-24 |

最近在想这个问题，找工作的事情让我有点迷惘。问的问题都是做过什么项目，JVM的垃圾回收，java 里面 HashMap 和 HashTable 的区别，诸如此类，问算法的几乎没有，问过的，找出出现次数超过二分之一的元素；从100W 个数据中找出前100个。

项目当然是要问的，但是我个人觉得算法真的这么无关紧要吗？jvm 啊 hashmap 啊这些，都是可以背下来的啊！难道公司真的希望招到一些这样子的同学吗？这样子面试不就成了应试考试了吗？

一个好的程序员比差的程序员除了知道更多的框架是什么怎么用（这是项目教给他的），编码的习惯好些，然后呢？

其实我本身也有点找不着方向了，我做了那么多算法题，刷了 leetcode，到头来是不是完全跑偏了？回头想想，我做的项目好些也并没有用到什么高深的算法..

哎。

2016年04月24日18:13:39

吐槽elasticsearch

发表于 2016-03-27 |

ElasticSearch是一个非常非常好的工具，用它来处理拿到的数据很赞~可以用到网站上或者其他别的地方。不过有个非常不爽的地方就是，我说的都是java用起来，就是它对elasticsearch的jar包的版本，以及依赖的lucene包的版本要求非常高。二者必须和你安装的Elasticsearch一致才行。

之前用的是1.3.1版本的，现在换成最新版本的，一开始是找不到可用节点，换成对应的jar包之后，发现之前写的代码竟然不能用了…api都变了啊..这可不太好。

2016年03月27日16:51:58