一直都是自学,时间跨度比较长,学的也很杂, Java 后端 ,做过练手的小 case
基本上该知道的都知道 该入门的都入了一遍 ( Java SQL Spring 反射 事务 前端 xx 之类)
前段时间报了九章的算法班,打算加强下 刷题的能力
(自学过一段时间的 算法 x 数据结构 都限于了解, 一编程就懵逼 思路全断,这也是后来报班的缘故, 说实话 收获还是有的,开阔了一些解题的思路,以及解题的思维)
(我个人觉得解决这些算法问题,在实际工作中应用不大, 但是 这些算法的思路 以及 数据结构 又培养了我分析解决问题的思维模式)
http://www.lintcode.com/zh-cn/problem/number-of-islands/
像以前这道题,我 看到是半天拿不出半点思路的,
但是我昨天 只用了 2 分钟 想出 队列结合 hash 表的方式 就 AC 了,复杂度虽然下不来,终归还是 AC 了
以上是问题背景
问题:
作为一个转行狗,没有经验,求职 Java 实习生, 只剩下一个月的时间,
方案一:用功复习下 《Think in Java》 《Spring in Action《 java 多线程》 等等这些经典应用书籍,顺带写个小 case 出来
方案二:继续刷 OJ 把精力放在面试算法题上?
顺带有春招新手 方便留个邮箱 我会投递简历 [email protected]
1
johnj 2017-01-31 00:11:34 +08:00
还是要结合要找的工种来决定努力方向
要是 web 方向,可能算法面的不多,主要还是关心你 Java 基础怎么样,实践能力怎么样,多久能上手出活 一家之言,仅供参考 |
2
scnace 2017-01-31 01:57:50 +08:00 via Android
mark 下…
|
3
tscat 2017-01-31 02:02:25 +08:00 via iPhone
看你面试公司的级别了, bat 之类的准备算法吧。其他不入流 IT 公司就做一两个项目。使用框架的那种
|
4
ryd994 2017-01-31 05:35:58 +08:00 via Android
同等春招,找实习中
看到题拔不出来了,你说用队列和 hash 我不太懂 我想到的是着色 从左上开始遍历,找到 1 的话检查左侧和上侧,如果有已着色的,就把当前涂上同样颜色,如果没有,就分配新颜色 然后考虑 corner case 就是如果是十字形的会存在问题。 dirty patch :如果左侧上侧都有色而且颜色不同,对左侧元素重新着色,检查左边的延伸。 |
5
ryd994 2017-01-31 05:50:32 +08:00 via Android
刚刚突然想到,这不就是个图么?求连通性而已,有更简单的
数 1 的个数 遍历每一个元素,如果和其他 1 贴,就减 1 复杂度和上面的差不多,一回事 |
6
zhy0216 2017-01-31 06:00:30 +08:00
九章还有个强化班 楼主也可以试试~~
|
7
Allianzcortex 2017-01-31 07:12:03 +08:00 via iPhone
这道题是刘汝佳算法里的题目,求油田的联通性。 dfs 。
|
8
q397064399 OP r#4 @Allianzcortex #7
@ryd994 #4 ``` public class Solution { int total; int mapX, mapY; class Node { public int x, y; public Node(int x, int y) { this.x = x; this.y = y; } @Override public int hashCode() { return (x + y) / 20; } @Override public boolean equals(Object obj) { Node objNode = (Node) obj; if (objNode.x == this.x && objNode.y == this.y) { return true; } return false; } } Set<Node> nodeSet = new HashSet<Node>(); public int numIslands(boolean[][] grid) { if (grid.length == 0){ return 0; } mapY = grid.length; mapX = grid[0].length; // Write your code here for (int y = 0; y < grid.length; y++) { for (int x = 0; x < grid[0].length; x++) { if (grid[y][x] == false) { continue; } Node temp = new Node(x, y); if (grid[y][x] == true && !nodeSet.contains(temp)) { nodeSet.add(temp); buildIsland(temp, grid); //todo total++; } } } return total; } private void buildIsland(Node node, boolean[][] grid) { Node curNode; Stack<Node> stack = new Stack<Node>(); stack.push(node); while (!stack.isEmpty()) { Node temp = stack.pop(); int x = temp.x; int y = temp.y; if (isLegalNode(x - 1, y) && grid[y][x-1]) { curNode = new Node(x - 1, y); if (nodeSet.add(curNode)) {//第一次出现 stack.push(curNode); } } if (isLegalNode(x + 1, y) && grid[y][x+1]) { curNode = new Node(x + 1, y); if (nodeSet.add(curNode)) { stack.push(curNode); } } if (isLegalNode(x, y - 1) && grid[y-1][x]) { curNode = new Node(x, y - 1); if (nodeSet.add(curNode)) { stack.push(curNode); } } if (isLegalNode(x, y + 1) && grid[y+1][x]) { curNode = new Node(x, y + 1); if (nodeSet.add(curNode)) { stack.push(curNode); } } } } private boolean isLegalNode(int x, int y) { if (x >= 0 && x < mapX && y >= 0 && y < mapY) { return true; } return false; } } ``` |
9
q397064399 OP r#6 @zhy0216 #6 找工作 重要啊,都吃不起饭了,再搞强化班的话
|
10
arnofeng 2017-01-31 08:30:05 +08:00 via iPhone
人人都转程序员。
|
12
Cbdy 2017-01-31 09:20:46 +08:00 via Android
现在 Java 流行什么框架?
|
13
Allianzcortex 2017-01-31 09:37:55 +08:00
@q397064399 我是 Python 党啊(大雾)。你用 Hash 的目的是为了每个 i,j 的位置生成一个唯一的 ID?我贴一下我之前学的时候写的解法,没有检验参数,但基本就是这样啦。也改成 Java 版了:
``` public class NumberOfIslands { int count = 2; public int solve(int[][] island) { for (int i = 0; i < island.length; i++) for (int j = 0; j < island[0].length; j++) { if (island[i][j] == 1) { dfs(island, i, j); count += 1; } } for (int i = 0; i < island.length; i++) { for (int j = 0; j < island[0].length; j++) { System.out.print(island[i][j] + " "); } System.out.println(); } return count-2; } public void dfs(int[][] island, int i, int j) { if (i < 0 || i >= island.length || j < 0 || j >= island[0].length || island[i][j] == 0) return; if (island[i][j] == 1) { island[i][j] = count; dfs(island, i + 1, j); dfs(island, i - 1, j); dfs(island, i, j - 1); dfs(island, i, j + 1); } } public static void main(String[] args) { int[][] island = { {1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, }; NumberOfIslands s = new NumberOfIslands(); System.out.println(s.solve(island)); } } ``` |
14
Allianzcortex 2017-01-31 09:48:10 +08:00
对了,我最近在写这个: https://github.com/Allianzcortex/bweever :-D 把之前零散的东西聚起来~~
|
15
xpol 2017-01-31 10:21:26 +08:00 via iPhone
复习一下概率论。面试官喜欢问这个。
|
16
byebyejude 2017-01-31 11:04:20 +08:00 via Android
免费劳动力大神 你怎么也开始慌了。。。。
|
17
SourceMan 2017-01-31 13:33:15 +08:00 via iPhone
iOS
|
18
hxndg 2017-01-31 13:50:10 +08:00
岛屿那个不就是寻找岛屿的头部么?
|
19
q397064399 OP r#16 @byebyejude #16 我可不是什么大神 ,兄台
|
20
nbndco 2017-01-31 15:16:11 +08:00
完全取决于你要面什么类型的公司,大体上,从最好的公司排起
纯算法加智力题或者概率题的公司 算法加上基础的公司/算法同时偏重语言细节的公司,会加若干项目经历如果面试官有兴趣的话,也可能只字不提 只问项目和 API 背诵的公司,或者只问面试官知道的不多的莫名其妙的技术细节的公司 看你想去和能去哪一种了 |
21
timothyye 2017-02-01 16:06:11 +08:00
还以为 lz 转行写 Go 了……
|
23
yang2yang 2017-02-01 22:20:20 +08:00
@nbndco 想问一下,概率题会面什么样的?举个例子?话说面 Java ,为什么面概率题啊??(同楼主找个 Java 实习呀....)
|
24
nbndco 2017-02-02 09:59:41 +08:00
@yang2yang 说是概率其实主要考智商反应而已,也不一定是概率题,类似的都有可能,只不过以概率形式出现的我感觉最多而已,本质上利用的概率知识都是很简单的,高中生应该也差不多够了,关键是看思路。
给你看个题,朋友面到过,似乎是 BAT ,显然不需要什么前置知识, https://www.nowcoder.com/questionTerminal/d6a7abaeef2a42709d778720b5f2df63 至于为什么问智力题,部分公司才会这么做,有些公司根本不会问你 java 的问题啊,只问纯算法,大概是觉得根本的东西万变不离其宗,语言这种表象基础好的聪明人很快也就会了,没有必要问吧。 不同的公司面试差别比较大,找好目标公司再去了解他们的面试类型吧。 |
25
bintianbaihua 2017-02-03 14:00:56 +08:00
大家都在考虑着转行做程序员,很多都是为了工资,但真的适合自己吗?有时候,是不是得好好考虑考虑。
|
26
q397064399 OP r#25 @bintianbaihua #25 找到合适的工作,跟找到合适的对象 有什么区别?几乎没有任何标准答案,一千个人就有一千个选择,大多时候都是权衡利弊而已,我自认为 写代码的思维能力还是够用的,而且学了很久,谈不上多么喜欢,
|