chriszeng87
- 浏览: 717900 次
- 性别:
- 来自: 北京
-
文章分类
- 全部博客 (439)
- 生活小感 (9)
- Java (65)
- 笔面经 (18)
- 算法 (45)
- 读书笔记 (1)
- Android (147)
- 设计模式 (7)
- C语言 (7)
- 职业生涯 (6)
- 网络 (5)
- 数据库 (3)
- Linux/Unix (21)
- C++ (7)
- 思考 (3)
- WinPhone (4)
- Git (6)
- http (1)
- UML (1)
- SQL (2)
- Ant (1)
- iOS (14)
- FFmpeg (22)
- WebRTC (10)
- Mac (2)
- web (0)
- TCP (2)
- Vim (2)
- OpenSSL (1)
- OpenGL (6)
- 多媒体 (10)
- cocos2d (2)
- svn (1)
最新评论
-
wahahachuang8：
我觉得这种东西自己开发太麻烦了，就别自己捣鼓了，找个第三方，方 ...
WebSocket初探【转】 -
ding335306：
这个目录下没有找到此文件
eclipse.ini in MAC -
songshuaiyang：
哥们写东西可真乱啊
Android获取cpu和内存信息、网址的代码 -
zhoutao_temp：
这是自己能看懂还是让别人能看得懂，您就不能把版面稍微整理一下吗 ...
FFMPEG源码分析 -
chriszeng87：
string2020 写道git clone --bare表示 ...
复制git库
1. 在一个图里面给一个点，每个点都有颜色，要求给出与这个点相同着色且相邻的最大区域，写算法实现
2.给定一个序列如{A,B,C,D},先序关系，如<A,B>(A先于B),<C,D>,<D,A>，要求按先序关系给出整个序列的顺序，如<A,B>,<C,D>,<D,A>的顺序为C,D,A,B，
3.求证一个链表里是否有环
4.二维的空间中有很多点，要求求出所有点中最近的一对点，时间复杂度要好。
多做算法题，topcoder,pojonline，研究设计模式，msdn，底层和高层都要兼顾到
今天被bs的不行了，加油，Chris
得到出现次数了，再算面积就简单了吧！
感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法
时间复杂度已经是最小了，你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。
额，请教下，包围该颜色相邻颜色的次数，这句话啥意思的
得到出现次数了，再算面积就简单了吧！
感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法
时间复杂度已经是最小了，你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。
得到出现次数了，再算面积就简单了吧！
感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法
得到出现次数了，再算面积就简单了吧！
写出来的才是真正懂了，从厚到薄，再从薄到厚
Software Design Engineer
能不能再详细一点的，您说的闭包是不是您楼下所说的凸包啊?
看再多的书，如果没有记录下来，过一个时间后就跟没看一样 这句话有感觉......
某已故日本音乐人
2.给定一个序列如{A,B,C,D},先序关系，如<A,B>(A先于B),<C,D>,<D,A>，要求按先序关系给出整个序列的顺序，如<A,B>,<C,D>,<D,A>的顺序为C,D,A,B，
3.求证一个链表里是否有环
4.二维的空间中有很多点，要求求出所有点中最近的一对点，时间复杂度要好。
多做算法题，topcoder,pojonline，研究设计模式，msdn，底层和高层都要兼顾到
今天被bs的不行了，加油，Chris
分享到：
评论
22 楼
thihy
2010-12-30
基本上都见过。所以多面试&多看面试题还是有好处的。
21 楼
chriszeng87
2010-12-22
izhangh 写道
chriszeng87 写道
izhangh 写道
class Question {
/**
* 标记该点是否遍历过，遍历过的值为1
*/
private static int[][] flgs;
/**
*
* @param values
* 二维数组，表示各点对应颜色值
* @param x
* 需比较点坐标
* @param y
* 点比较坐标
* @return 与values[x][y]值相等且相邻点出现的次数
*/
public static int run(int[][] values, int x, int y) {
flgs = new int[values.length][values[0].length];
Count count = new Count();
research(values, values[x][y], count, x, y);
return count.getCount();
}
/**
*
* @param values二维数组
* ，表示各点对应颜色值
* @param desValue比较的颜色值
* @param count出现次数
* @param x
* 点坐标
* @param y
* 点坐标
*/
private static void research(int[][] values, int desValue, Count count, int x, int y) {
// 该点未遍历过,且颜色相同,继续遍历
if (flgs[x][y] != 1 && values[x][y] == desValue) {
// 标记该点遍历过
flgs[x][y] = 1;
// 计数器加一
count.addOne();
// 向左遍历
if (x > 0) {
research(values, desValue, count, x - 1, y);
}
// 向上遍历
if (y > 0) {
research(values, desValue, count, x, y - 1);
}
// 向右遍历
if (x < values.length - 1) {
research(values, desValue, count, x + 1, y);
}
// 向下遍历
if (y < values[0].length - 1) {
research(values, desValue, count, x, y + 1);
}
}
}
}
public class Count {
private int count;
public void addOne() {
count++;
}
public int getCount() {
return count;
}
}
class Test3Main {
private static int[][] points = new int[][] {
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
},
};
public static void main(String[] args) {
System.out.println(Question.run(points, 4, 3));
}
}
得到出现次数了，再算面积就简单了吧！
感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法
时间复杂度已经是最小了，你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。
额，请教下，包围该颜色相邻颜色的次数，这句话啥意思的
20 楼
izhangh
2010-12-22
chriszeng87 写道
izhangh 写道
class Question {
/**
* 标记该点是否遍历过，遍历过的值为1
*/
private static int[][] flgs;
/**
*
* @param values
* 二维数组，表示各点对应颜色值
* @param x
* 需比较点坐标
* @param y
* 点比较坐标
* @return 与values[x][y]值相等且相邻点出现的次数
*/
public static int run(int[][] values, int x, int y) {
flgs = new int[values.length][values[0].length];
Count count = new Count();
research(values, values[x][y], count, x, y);
return count.getCount();
}
/**
*
* @param values二维数组
* ，表示各点对应颜色值
* @param desValue比较的颜色值
* @param count出现次数
* @param x
* 点坐标
* @param y
* 点坐标
*/
private static void research(int[][] values, int desValue, Count count, int x, int y) {
// 该点未遍历过,且颜色相同,继续遍历
if (flgs[x][y] != 1 && values[x][y] == desValue) {
// 标记该点遍历过
flgs[x][y] = 1;
// 计数器加一
count.addOne();
// 向左遍历
if (x > 0) {
research(values, desValue, count, x - 1, y);
}
// 向上遍历
if (y > 0) {
research(values, desValue, count, x, y - 1);
}
// 向右遍历
if (x < values.length - 1) {
research(values, desValue, count, x + 1, y);
}
// 向下遍历
if (y < values[0].length - 1) {
research(values, desValue, count, x, y + 1);
}
}
}
}
public class Count {
private int count;
public void addOne() {
count++;
}
public int getCount() {
return count;
}
}
class Test3Main {
private static int[][] points = new int[][] {
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
},
};
public static void main(String[] args) {
System.out.println(Question.run(points, 4, 3));
}
}
得到出现次数了，再算面积就简单了吧！
感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法
时间复杂度已经是最小了，你仔细看下吧!它遍历的只是颜色相同的次数+包围该颜色相邻颜色的次数。
19 楼
chriszeng87
2010-12-22
izhangh 写道
class Question {
/**
* 标记该点是否遍历过，遍历过的值为1
*/
private static int[][] flgs;
/**
*
* @param values
* 二维数组，表示各点对应颜色值
* @param x
* 需比较点坐标
* @param y
* 点比较坐标
* @return 与values[x][y]值相等且相邻点出现的次数
*/
public static int run(int[][] values, int x, int y) {
flgs = new int[values.length][values[0].length];
Count count = new Count();
research(values, values[x][y], count, x, y);
return count.getCount();
}
/**
*
* @param values二维数组
* ，表示各点对应颜色值
* @param desValue比较的颜色值
* @param count出现次数
* @param x
* 点坐标
* @param y
* 点坐标
*/
private static void research(int[][] values, int desValue, Count count, int x, int y) {
// 该点未遍历过,且颜色相同,继续遍历
if (flgs[x][y] != 1 && values[x][y] == desValue) {
// 标记该点遍历过
flgs[x][y] = 1;
// 计数器加一
count.addOne();
// 向左遍历
if (x > 0) {
research(values, desValue, count, x - 1, y);
}
// 向上遍历
if (y > 0) {
research(values, desValue, count, x, y - 1);
}
// 向右遍历
if (x < values.length - 1) {
research(values, desValue, count, x + 1, y);
}
// 向下遍历
if (y < values[0].length - 1) {
research(values, desValue, count, x, y + 1);
}
}
}
}
public class Count {
private int count;
public void addOne() {
count++;
}
public int getCount() {
return count;
}
}
class Test3Main {
private static int[][] points = new int[][] {
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
},
};
public static void main(String[] args) {
System.out.println(Question.run(points, 4, 3));
}
}
得到出现次数了，再算面积就简单了吧！
感觉这样做确实可以，不过觉得是不是还有非递归、时间复杂度更好的算法
18 楼
izhangh
2010-12-22
上面是第一问的答案，请多多讨论。
17 楼
izhangh
2010-12-22
class Question {
/**
* 标记该点是否遍历过，遍历过的值为1
*/
private static int[][] flgs;
/**
*
* @param values
* 二维数组，表示各点对应颜色值
* @param x
* 需比较点坐标
* @param y
* 点比较坐标
* @return 与values[x][y]值相等且相邻点出现的次数
*/
public static int run(int[][] values, int x, int y) {
flgs = new int[values.length][values[0].length];
Count count = new Count();
research(values, values[x][y], count, x, y);
return count.getCount();
}
/**
*
* @param values二维数组
* ，表示各点对应颜色值
* @param desValue比较的颜色值
* @param count出现次数
* @param x
* 点坐标
* @param y
* 点坐标
*/
private static void research(int[][] values, int desValue, Count count, int x, int y) {
// 该点未遍历过,且颜色相同,继续遍历
if (flgs[x][y] != 1 && values[x][y] == desValue) {
// 标记该点遍历过
flgs[x][y] = 1;
// 计数器加一
count.addOne();
// 向左遍历
if (x > 0) {
research(values, desValue, count, x - 1, y);
}
// 向上遍历
if (y > 0) {
research(values, desValue, count, x, y - 1);
}
// 向右遍历
if (x < values.length - 1) {
research(values, desValue, count, x + 1, y);
}
// 向下遍历
if (y < values[0].length - 1) {
research(values, desValue, count, x, y + 1);
}
}
}
}
public class Count {
private int count;
public void addOne() {
count++;
}
public int getCount() {
return count;
}
}
class Test3Main {
private static int[][] points = new int[][] {
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 0, 0, 0, 1, 1, 1, 1, 1
}, {
1, 1, 1, 1, 0, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 1, 1, 1, 1
}, {
1, 1, 1, 1, 1, 0, 0, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 0, 1, 1
}, {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
},
};
public static void main(String[] args) {
System.out.println(Question.run(points, 4, 3));
}
}
得到出现次数了，再算面积就简单了吧！
16 楼
chriszeng87
2010-12-21
不知道发到这里合不合适了，这道题想了好久了，也没什么思路： 对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。 求指点。
15 楼
asle
2010-12-19
chriszeng87 写道
让记录成为一种习惯,是一个想要在以后留下点什么东西的人该做的事。记录是一个人积累的过程，看再多的书，如果没有记录下来，过一个时间后就跟没看一样。看自己写下的东西和看别人写的东西是不一样的，主要体现在理解速度上，因为中间缺少了将别人的思维翻译成自己思维的过程。
在记录中学会思考、学会探索。
记录可以消除自己烦躁的情绪。
每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。
转的，说的真不错
在记录中学会思考、学会探索。
记录可以消除自己烦躁的情绪。
每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。
转的，说的真不错
写出来的才是真正懂了，从厚到薄，再从薄到厚
14 楼
chriszeng87
2010-12-19
meiyoudao 写道
你这是啥职位啊???? 这些东西..见都没见过
Software Design Engineer
13 楼
meiyoudao
2010-12-19
你这是啥职位啊???? 这些东西..见都没见过
12 楼
chriszeng87
2010-12-18
kdlan 写道
1 应该是算闭包的变形吧
能不能再详细一点的，您说的闭包是不是您楼下所说的凸包啊?
11 楼
uddjatigmh199
2010-12-18
1.对每种颜色应用凸包.....
10 楼
kdlan
2010-12-17
1 应该是算闭包的变形吧
9 楼
生活小丑
2010-12-17
chriszeng87 写道
让记录成为一种习惯,是一个想要在以后留下点什么东西的人该做的事。记录是一个人积累的过程，看再多的书，如果没有记录下来，过一个时间后就跟没看一样。看自己写下的东西和看别人写的东西是不一样的，主要体现在理解速度上，因为中间缺少了将别人的思维翻译成自己思维的过程。
在记录中学会思考、学会探索。
记录可以消除自己烦躁的情绪。
每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。
转的，说的真不错
在记录中学会思考、学会探索。
记录可以消除自己烦躁的情绪。
每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。
转的，说的真不错
看再多的书，如果没有记录下来，过一个时间后就跟没看一样 这句话有感觉......
8 楼
jasin2008
2010-12-16
算法
心中永远的痛
心中永远的痛
7 楼
chriszeng87
2010-12-16
4在很多书上有，《编程之美》上感觉写的不太好，不过还有个扩展题：求空间中n个点中距离最远的两点，这个有人想过么? http://yinhail.ycool.com/post.4507062.html 上有解，不过我没看懂额
6 楼
lj30936
2010-12-16
1。好像就是广度优先搜索吧
2。根据边建图，然后拓扑遍历图
3。同楼上
4。最小距离点对，网上有nlogn算法
2。根据边建图，然后拓扑遍历图
3。同楼上
4。最小距离点对，网上有nlogn算法
5 楼
lykm02
2010-12-16
1 暂没思路
2 好像是图的拓扑有序。数据结构课本里面有的吧
3 快慢指针，如果相遇说明有环
4 算法课本上有的，经典算法
ok
2 好像是图的拓扑有序。数据结构课本里面有的吧
3 快慢指针，如果相遇说明有环
4 算法课本上有的，经典算法
ok
4 楼
chriszeng87
2010-12-16
cectsky 写道
你的头像很像土匪
某已故日本音乐人
3 楼
chriszeng87
2010-12-16
让记录成为一种习惯,是一个想要在以后留下点什么东西的人该做的事。记录是一个人积累的过程，看再多的书，如果没有记录下来，过一个时间后就跟没看一样。看自己写下的东西和看别人写的东西是不一样的，主要体现在理解速度上，因为中间缺少了将别人的思维翻译成自己思维的过程。
在记录中学会思考、学会探索。
记录可以消除自己烦躁的情绪。
每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。
转的，说的真不错
在记录中学会思考、学会探索。
记录可以消除自己烦躁的情绪。
每天抽出一到两个小时来记录自己的所学和自己的思考，这样一直的坚持那么当你回过头来看看的时候，你会发现你已经收获了很多了。
转的，说的真不错
发表评论
-
leetcode之 median of two sorted arrays
2015-07-30 00:08 744另一种方法即是利用类似merge的操作找到中位数，利用两个分 ... -
LeetCode – Min Stack
2015-06-11 18:27 609转自：http://www.programcreek.com ... -
二叉树中所有节点的左右子树相互交换 递归与非递归程序
2015-06-11 14:18 3048//将二叉树中所有节点的左右子树相互交换 转自：http: ... -
Word Break II
2015-06-09 23:38 642转自：http://www.acmerblog.com/ ... -
最大子序列和问题
2015-06-08 09:10 699问题描述： 输入一组整数，求出这组数字子序列和 ... -
判断是否二叉搜索树
2015-05-31 16:49 850转自：http://blog.163.com/yichan ... -
LeetCode | Decode Ways
2015-05-28 22:09 621题目： A message containing le ... -
A* Pathfinding for Beginners
2014-11-01 10:40 647转自：http://www.policyalmanac.o ... -
P问题、NP问题和NP完全问题
2014-10-28 23:47 22581、P问题 P是一个判定 ... -
外部排序技术之多路归并
2014-10-19 11:32 928转自：http://blog.chinaunix.net/u ... -
利用动态规划求连续数组最大和以及最大子矩阵的和
2014-09-11 09:14 1960题目一： 给定一个整型数组，数组中有正有负，求最大连续子序 ... -
一些算法刷题的网站
2014-09-04 22:31 38251. leetcode http://leetcode ... -
[leetcode] A Distance Maximizing Problem的疑问
2014-08-25 22:38 1471http://leetcode.com/2011/05/a- ... -
二叉树中两个结点的最近公共祖先
2014-08-03 11:30 510Node* findComAncestor(No ... -
单链表原地逆置递归与非递归解法
2014-07-24 23:48 1125#include <stdio.h> t ... -
Google面试题：赛马问题
2013-07-10 23:52 2100转自： http://coolshell.c ... -
《单链表的环的入口点一个小证明》
2013-06-16 23:14 1391http://blog.csdn.net/learniti ... -
[转]稳定排序和不稳定排序
2013-04-21 12:11 883首先，排序算法的稳定 ... -
最大子矩阵和问题
2011-10-06 23:20 2850最大子矩阵问题：问题描述：(具体见http://acm ... -
EMC面试题
2011-10-02 22:29 14261.一个未排序整数数组 ...
相关推荐
几道算法选择题几道算法选择题几道算法选择题几道算法选择题几道算法选择题几道算法选择题几道算法选择题
经典面试算法题N道，经典面试算法题N道，经典面试算法题N道，经典面试算法题N道
100道入门级算法题～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
这是网上关于Java的50道算法程序题的代码，有需要的可以下载参考
C语言100道逻辑经典算法题，都是一些基础的语法，如for等基本语法，做完了这100道题可以让你更深刻的理解这些语法
这里有8道原创的经典算法思想题，源于谭浩强C语言课本例题，希望通过几道算法题，把握其思想，达到举一反三的学习效果。
C语言100道经典算法题
大厂算法面试题库中,高频出现的30道典型题
兔子繁殖 半段质数 水仙花数 最大公约数 最小公倍数 数字排序等经典的编程问题
Java32道算法题，有答案可以运行int i=0; for(i=1;i;i++) System.out.println(f(i)); { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2);
76经典道算法题及解答(欢迎下载我的其他资源)
java的2道算法题，笔试面试题。有需要的可以看看
26道算法笔试题，包含常用的算法的过程，流程，精简易用。
scratch10道算法题及答案
JAVA经典算法30题JAVA经典算法30题JAVA经典算法30题JAVA经典算法30题
资料总结了苏州大学2005-2019年的所有考研专业课算法题，共40多道，想考苏大的会很有帮助，苏大计算机专业课是要考3道算法题，因此算法不可轻视
js所有的算法，自己总结的，如有遗漏，请留言。希望可以帮助到需要的人
程序员面试时经常会有结构算法题，这22道数据结构算法题各有特点，会有所帮助
大厂算法面试题，高频出现的30题，面试绝对有用。如果你刷leetcode题目很多，为了面试不如看看高频题，这30到够用了，经常会被笔试到，资料很好。