yunchow
- 浏览: 318752 次
- 性别:
- 来自: 南京
-
文章分类
最新评论
-
huangyunbin：
swc.advance(); 这个什么时候被调用是最核心的 ...
滑动窗口计数java实现 -
80后的童年2：
深入浅出MongoDB应用实战开发网盘地址：https://p ...
MongoDB 从入门到精通专题教程 -
rryymmoK：
深入浅出MongoDB应用实战开发下载地址：http://pa ...
MongoDB 从入门到精通专题教程 -
u012352249：
怎么支持多个窗口啊？
滑动窗口计数java实现 -
rryymmoK：
深入浅出MongoDB应用实战开发百度网盘下载：链接：http ...
MongoDB 从入门到精通专题教程
阿里的一个面试题：
一个序列里除了一个元素，其他元素都会重复出现3次，设计一个时间复杂度与空间复杂度最低的算法，找出这个不重复的元素。
实现如下：
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
如果要算最多重复出现4~7次的，则需要3位bit来存储；如果8~15次，则需要4位bit来存储。而树有叶子节点等概念，跟这个场景没什么太大关系啊。
你只见过三叉树啊，我说的是树，三叉四叉五叉。反正我试了用三位只能算出最多五个重复的，不知道你怎么能最多算出7次。付上代码
：package bitmap;
import java.util.BitSet;
public class BitThreeMapMain {
static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 9, 9, 7,7,7,7,7,9,9};
public static void main(String[] args) {
int len =list.length * 3;
BitSet bs = new BitSet(len);
for (int i = 0; i < list.length; i++) {
int n = 3 * list[i];
boolean b0 = bs.get(n - 1);
boolean b1 = bs.get(n);
boolean b2 = bs.get(n + 1);
if (!b0&&!b1 && !b2) { // 000
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, false);
}
if (b0&&!b1 && !b2) { // 100
bs.set(n-1, false);
bs.set(n, true);
bs.set(n + 1, false);
}
if (!b0&&b1 && !b2) { // 010
bs.set(n-1, false);
bs.set(n, false);
bs.set(n + 1, true);
}
if (!b0&&!b1 && b2) { // 001
bs.set(n-1, true);
bs.set(n, true);
bs.set(n + 1, false);
}
if (b0&&b1 && !b2) { // 110
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, true);
}
if (b0&&!b1 && b2) { // 101
bs.set(n-1,n + 1, true);
}
}
System.out.println(bs.length());
for (int i = 3; i < bs.length(); i += 3) {
boolean b0 = bs.get(i-1);
boolean b1 = bs.get(i);
boolean b2 = bs.get(i + 1);
if (!b0&&!b1 && !b2) { // 000
// 0次
}
if (b0&&!b1 && !b2) { // 100
System.out.println(i / 3 + "=1次");
}
if (!b0&&b1 && !b2) { // 010
System.out.println(i / 3 + "=2次");
}
if (!b0&&!b1 && b2) { // 001
System.out.println(i / 3 + "=3次");
}
if (b0&&b1 && !b2) { // 110
System.out.println(i / 3 + "=4次");
}
if (b0&&!b1 && b2) { // 101
System.out.println(i / 3 + "=5次");
}
}
}
}
哦，是的，你是对的。是2^n次冥关系。我还写少了两种。但真的可以抽象成一个多叉树来算。
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
如果要算最多重复出现4~7次的，则需要3位bit来存储；如果8~15次，则需要4位bit来存储。而树有叶子节点等概念，跟这个场景没什么太大关系啊。
你只见过三叉树啊，我说的是树，三叉四叉五叉。反正我试了用三位只能算出最多五个重复的，不知道你怎么能最多算出7次。付上代码
：package bitmap;
import java.util.BitSet;
public class BitThreeMapMain {
static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 9, 9, 7,7,7,7,7,9,9};
public static void main(String[] args) {
int len =list.length * 3;
BitSet bs = new BitSet(len);
for (int i = 0; i < list.length; i++) {
int n = 3 * list[i];
boolean b0 = bs.get(n - 1);
boolean b1 = bs.get(n);
boolean b2 = bs.get(n + 1);
if (!b0&&!b1 && !b2) { // 000
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, false);
}
if (b0&&!b1 && !b2) { // 100
bs.set(n-1, false);
bs.set(n, true);
bs.set(n + 1, false);
}
if (!b0&&b1 && !b2) { // 010
bs.set(n-1, false);
bs.set(n, false);
bs.set(n + 1, true);
}
if (!b0&&!b1 && b2) { // 001
bs.set(n-1, true);
bs.set(n, true);
bs.set(n + 1, false);
}
if (b0&&b1 && !b2) { // 110
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, true);
}
if (b0&&!b1 && b2) { // 101
bs.set(n-1,n + 1, true);
}
}
System.out.println(bs.length());
for (int i = 3; i < bs.length(); i += 3) {
boolean b0 = bs.get(i-1);
boolean b1 = bs.get(i);
boolean b2 = bs.get(i + 1);
if (!b0&&!b1 && !b2) { // 000
// 0次
}
if (b0&&!b1 && !b2) { // 100
System.out.println(i / 3 + "=1次");
}
if (!b0&&b1 && !b2) { // 010
System.out.println(i / 3 + "=2次");
}
if (!b0&&!b1 && b2) { // 001
System.out.println(i / 3 + "=3次");
}
if (b0&&b1 && !b2) { // 110
System.out.println(i / 3 + "=4次");
}
if (b0&&!b1 && b2) { // 101
System.out.println(i / 3 + "=5次");
}
}
}
}
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
如果要算最多重复出现4~7次的，则需要3位bit来存储；如果8~15次，则需要4位bit来存储。而树有叶子节点等概念，跟这个场景没什么太大关系啊。
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
是不是log2n呢，所以应该是二叉树的深度，而不是n叉树吧
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
这。。好像没有二叉树的原理吧，只是位图的原理，两位来存重复的次数，时间复杂度为n
一个序列里除了一个元素，其他元素都会重复出现3次，设计一个时间复杂度与空间复杂度最低的算法，找出这个不重复的元素。
实现如下：
package bitmap;
import java.util.BitSet;
public class BitMapMain {
static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 6, 9, 9, 7, 7};
public static void main(String[] args) {
int len = list.length * 2;
BitSet bs = new BitSet(len);
for (int i = 0; i < list.length; i++) {
int n = 2 * list[i];
boolean b1 = bs.get(n);
boolean b2 = bs.get(n + 1);
if (!b1 && !b2) { // 00
bs.set(n, true);
bs.set(n + 1, false);
}
else if (b1 && !b2) { // 01
bs.set(n + 1, true);
bs.set(n, false);
}
else if (!b1 && b2) { // 10
bs.set(n, n + 1, true);
}
}
for (int i = 0; i < bs.length(); i += 2) {
boolean b1 = bs.get(i);
boolean b2 = bs.get(i + 1);
if (!b1 && !b2) { // 00
// 0次
}
else if (b1 && !b2) { // 01
System.out.println(i / 2 + "一次");
}
else if (!b1 && b2) { // 10
System.out.println(i / 2 + "两次");
}
else if (b1 && b2) { // 10
System.out.println(i / 2 + "三次");
}
}
}
}
3
顶
顶
1
踩
踩
分享到：
评论
9 楼
113.com
2014-09-23
113.com 写道
jag522 写道
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
如果要算最多重复出现4~7次的，则需要3位bit来存储；如果8~15次，则需要4位bit来存储。而树有叶子节点等概念，跟这个场景没什么太大关系啊。
你只见过三叉树啊，我说的是树，三叉四叉五叉。反正我试了用三位只能算出最多五个重复的，不知道你怎么能最多算出7次。付上代码
：package bitmap;
import java.util.BitSet;
public class BitThreeMapMain {
static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 9, 9, 7,7,7,7,7,9,9};
public static void main(String[] args) {
int len =list.length * 3;
BitSet bs = new BitSet(len);
for (int i = 0; i < list.length; i++) {
int n = 3 * list[i];
boolean b0 = bs.get(n - 1);
boolean b1 = bs.get(n);
boolean b2 = bs.get(n + 1);
if (!b0&&!b1 && !b2) { // 000
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, false);
}
if (b0&&!b1 && !b2) { // 100
bs.set(n-1, false);
bs.set(n, true);
bs.set(n + 1, false);
}
if (!b0&&b1 && !b2) { // 010
bs.set(n-1, false);
bs.set(n, false);
bs.set(n + 1, true);
}
if (!b0&&!b1 && b2) { // 001
bs.set(n-1, true);
bs.set(n, true);
bs.set(n + 1, false);
}
if (b0&&b1 && !b2) { // 110
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, true);
}
if (b0&&!b1 && b2) { // 101
bs.set(n-1,n + 1, true);
}
}
System.out.println(bs.length());
for (int i = 3; i < bs.length(); i += 3) {
boolean b0 = bs.get(i-1);
boolean b1 = bs.get(i);
boolean b2 = bs.get(i + 1);
if (!b0&&!b1 && !b2) { // 000
// 0次
}
if (b0&&!b1 && !b2) { // 100
System.out.println(i / 3 + "=1次");
}
if (!b0&&b1 && !b2) { // 010
System.out.println(i / 3 + "=2次");
}
if (!b0&&!b1 && b2) { // 001
System.out.println(i / 3 + "=3次");
}
if (b0&&b1 && !b2) { // 110
System.out.println(i / 3 + "=4次");
}
if (b0&&!b1 && b2) { // 101
System.out.println(i / 3 + "=5次");
}
}
}
}
哦，是的，你是对的。是2^n次冥关系。我还写少了两种。但真的可以抽象成一个多叉树来算。
8 楼
113.com
2014-09-23
jag522 写道
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
如果要算最多重复出现4~7次的，则需要3位bit来存储；如果8~15次，则需要4位bit来存储。而树有叶子节点等概念，跟这个场景没什么太大关系啊。
你只见过三叉树啊，我说的是树，三叉四叉五叉。反正我试了用三位只能算出最多五个重复的，不知道你怎么能最多算出7次。付上代码
：package bitmap;
import java.util.BitSet;
public class BitThreeMapMain {
static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 9, 9, 7,7,7,7,7,9,9};
public static void main(String[] args) {
int len =list.length * 3;
BitSet bs = new BitSet(len);
for (int i = 0; i < list.length; i++) {
int n = 3 * list[i];
boolean b0 = bs.get(n - 1);
boolean b1 = bs.get(n);
boolean b2 = bs.get(n + 1);
if (!b0&&!b1 && !b2) { // 000
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, false);
}
if (b0&&!b1 && !b2) { // 100
bs.set(n-1, false);
bs.set(n, true);
bs.set(n + 1, false);
}
if (!b0&&b1 && !b2) { // 010
bs.set(n-1, false);
bs.set(n, false);
bs.set(n + 1, true);
}
if (!b0&&!b1 && b2) { // 001
bs.set(n-1, true);
bs.set(n, true);
bs.set(n + 1, false);
}
if (b0&&b1 && !b2) { // 110
bs.set(n-1, true);
bs.set(n, false);
bs.set(n + 1, true);
}
if (b0&&!b1 && b2) { // 101
bs.set(n-1,n + 1, true);
}
}
System.out.println(bs.length());
for (int i = 3; i < bs.length(); i += 3) {
boolean b0 = bs.get(i-1);
boolean b1 = bs.get(i);
boolean b2 = bs.get(i + 1);
if (!b0&&!b1 && !b2) { // 000
// 0次
}
if (b0&&!b1 && !b2) { // 100
System.out.println(i / 3 + "=1次");
}
if (!b0&&b1 && !b2) { // 010
System.out.println(i / 3 + "=2次");
}
if (!b0&&!b1 && b2) { // 001
System.out.println(i / 3 + "=3次");
}
if (b0&&b1 && !b2) { // 110
System.out.println(i / 3 + "=4次");
}
if (b0&&!b1 && b2) { // 101
System.out.println(i / 3 + "=5次");
}
}
}
}
7 楼
jag522
2014-09-23
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
如果要算最多重复出现4~7次的，则需要3位bit来存储；如果8~15次，则需要4位bit来存储。而树有叶子节点等概念，跟这个场景没什么太大关系啊。
6 楼
yunchow
2014-09-23
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
是不是log2n呢，所以应该是二叉树的深度，而不是n叉树吧
5 楼
113.com
2014-09-23
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
有很大关系好不，你看用这个就只能算最多出现2n-1三次的，如要算最多出现5次要用三叉树，如果最多出现7次要四叉，以此类推。你没看清这算法其中的本质。
4 楼
jag522
2014-09-22
113.com 写道
很巧妙使用二叉树原理。厉害
跟二叉树没什么关系吧。。00表示0次，01表示1次，10表示2次，11表示3次
3 楼
yunchow
2014-09-22
113.com 写道
很巧妙使用二叉树原理。厉害
这。。好像没有二叉树的原理吧，只是位图的原理，两位来存重复的次数，时间复杂度为n
2 楼
113.com
2014-09-18
很巧妙使用二叉树原理。厉害
1 楼
pi88dian88
2014-09-18
赞
发表评论
-
滑动窗口计数java实现
2016-02-20 13:13 11840滑动窗口计数有很多使用场景，比如说限流防止系统雪崩。相比计 ... -
面向对象程序设计思想（精华）
2014-11-12 15:52 1414面向对象语言具有封装，继承，多态的特征。那么在用面象对象语言 ... -
YY直播厅蠕虫病毒代码
2014-09-22 21:52 2459本来是可以直接通过<script>标签实现的， ... -
Apache Http Server Rewrite
2012-06-04 13:13 1132apache的rewrite功能很强大，详细参考：http:/ ... -
java操作MQ
2011-12-30 14:21 2835package mq; import jav ... -
实现动态验证码
2011-07-08 13:10 1156import java.awt.Color; imp ... -
简单统计代码行数
2010-12-30 17:34 1440真的很多,我刚写了个程序统计了一下,我们项目才695个类 并 ... -
采用MD5单向加密
2010-11-26 10:42 1271public static String get ... -
在报表中格式化货币
2010-11-25 10:01 1734最近在用FineReport这个工具进行系统的报表开发,发现在 ... -
Struts + JSP导出Excel报表
2010-11-07 20:21 2392据我所知 Java 导 Excel 报表有三种方法: 1, 在 ... -
Java正则实现EL表达式
2010-11-04 16:19 4455public static void main(Stri ... -
js格式化货币格式
2010-11-01 13:41 3776String.prototype.asCurren ... -
Hessian 发布服务及客户端实现
2010-10-19 13:36 2070服务接口： package com.test; pub ... -
java 项目中嵌入 jetty，并发布servlet
2010-10-13 11:47 2153package com.utan.tfs.jetty; ... -
TreeSet<T> 简单实现
2010-08-26 17:31 1519package com.mypack.ds; i ... -
SAX 解析 XML 实例
2010-08-21 14:32 2348xml文件： <?xml version=" ... -
利用 Spring 中的 Resource 读取文件和网络资源
2010-08-21 12:04 3752利用 Spring 中的 Resource 读取文件和网络资源 ... -
NIO SAX
2010-08-20 18:51 1037NIO与SAX 直接上教程 -
socket 发送 soap 请求
2010-08-19 23:46 3836package com.mypack.soap.client; ... -
HttpUrlConnection 发送 SOAP 请求，SAX 解析 SOAP 响应
2010-08-19 23:38 8161HttpUrlConnection 发送 SOAP 请求，SA ...
相关推荐
//例如：F[1][2]存储的是与数字1的和为质数的第二个数字，我们可以通过查询数组F[][]的第一行找出第二个不为0 //值，然后将当前数组单元的列号存储到F[1][2]中，即F[1][2] = 4。 //算法思想是通过查询二维数组F[][]...
重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。 ///////////////////////////////////////// 算法 1. 将两序列合并为一个序列，并排序，为序列Source 2. 拿出最大元素Big，次大的元素Small 3. 在余下...
5，给定一个所有元素都是正数的数组，找到一个子序列的最大和，并限制序列中的任何2个数字都不应该在数组中相邻。 例如。 i）3 2 7 10应该返回13（3和10之和）ii）3 2 5 10 7应该返回15（3、5和7之和） 6.给出一个...
通过算法的调用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。 Procedure LCS(b,X,i,j);beginif i=0 or j=0 then return;if b[i,j]="↖" thenbeginLCS(b,X,i-1,j-1);print(x[i]); {打印x[i]}...
常见的二分法两种模版：如不能写作while(l ) 因为序列中如果存在重复值 且正好在最后一次迭代的位置 没有=就会忽略掉 如果这里不写= 可以用下面的方式 背包问题详解： dp[i]中的i表示背包内总和 题目中说：每个...
将一个无序序列调整为一个堆，就可以找出这个序列的最大值（或最小值），然后将找出的这个值交换到序列的最后一个，这样有序序列就元素就增加一个，无序序列元素就减少一个，对新的无序序列重复这样的操作，就实现...
例如，在一维数组[21，46，24，99，57，77，86]中，查找数据元素99，首先从第1个元素21开始进行比较，比较结果与要查找的数据不相等，接着与第2个元素46进行比较，以此类推，当进行到与第4个元素比较时，它们相等，...
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符...
若找不到，则函数返回NULL； B． 球最大值函数max：通过单链表的一趟遍历，在单链表中确定值最大的结点； C． 统计函数number：统计单链表中具有给定值x的所有元素数量； D． *建立函数create：根据一维...
//不重复插入 taller=false; return false; } if(num<T->data) //继续在T的左子树中进行搜索 { if(!Insert_Avl(T->lchild,num,taller))//插入不成功 return false; if(taller) //已插入T的左子树,...
找出数组中所有消失的数字 报价 51. 重复 矩阵 LC 363. 不大于 K 的矩形的最大和（谷歌） Hiho 1502. 最大子矩阵 其他 LC 215. 数组中的第 K 个最大元素（与 Offer 30.GetLeastNumbers 相同） LC 594. 最长和谐子...
10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )【华南理工大学 2002 一、2 （1分）】 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )【上海海运学院 1999 一、1（1分）】 12....
(62) 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是(D) A. ABCED B. DBCEA C. CDABE D. DCBEA (63) 线性表的顺序存储结构和线性表的链式存储结构分别是(B) A. 顺序...
在客户关系管理中，通过对企业的客户数据库里的大量数据进行挖掘，可以从大量的记录中发现有趣的关联关系，找出影响市场营销效果的关键因素，为产品定位、定价与定制客户群，客户寻求、细分与保持，市场营销与推销...
leetcode中国数据结构和算法 数组 问题： 完成[是或否] 反转数组 查找数组中的最大和最小元素 ...k，找出出现次数超过“n/k”次的所有元素。 最多两次买卖股票的最大利润 判断一个数组是否是另一个数组的子集 找
扩展： 问题实例： 1).2.5亿个整数中找出不重复的整数的个数，内存空间不⾜以容纳这2.5亿个整数。 有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(⽐如⽤单个⽂件代表⼀个区域)，...
注册表将不能读取、写出或刷新包含注册表系统映像的其中一个文件。 1017 系统试图将文件加载或还原到注册表中，但是，指定的文件不是注册表文件格式。 1018 试图在注册表键（已经标记为删除）中完成的操作...
使用数据透视图汇总数百万行数据，在不使用图表的情况下以图形方式显示数据，使用SmartArt图形绘制流程图和关系图，使用VBA创建图表，将数据绘制到地图中，将图表导出到网页或PowerPoint中，找出图表背后的谎言等。...