yunchow
- 浏览: 328737 次
- 性别:
- 来自: 南京
-
文章分类
最新评论
-
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 11997滑动窗口计数有很多使用场景，比如说限流防止系统雪崩。相比计 ... -
面向对象程序设计思想（精华）
2014-11-12 15:52 1533面向对象语言具有封装，继承，多态的特征。那么在用面象对象语言 ... -
YY直播厅蠕虫病毒代码
2014-09-22 21:52 2545本来是可以直接通过<script>标签实现的， ... -
Apache Http Server Rewrite
2012-06-04 13:13 1250apache的rewrite功能很强大，详细参考：http:/ ... -
java操作MQ
2011-12-30 14:21 2895package mq; import jav ... -
实现动态验证码
2011-07-08 13:10 1215import java.awt.Color; imp ... -
简单统计代码行数
2010-12-30 17:34 1517真的很多,我刚写了个程序统计了一下,我们项目才695个类 并 ... -
采用MD5单向加密
2010-11-26 10:42 1379public static String get ... -
在报表中格式化货币
2010-11-25 10:01 1792最近在用FineReport这个工具进行系统的报表开发,发现在 ... -
Struts + JSP导出Excel报表
2010-11-07 20:21 2458据我所知 Java 导 Excel 报表有三种方法: 1, 在 ... -
Java正则实现EL表达式
2010-11-04 16:19 4517public static void main(Stri ... -
js格式化货币格式
2010-11-01 13:41 3854String.prototype.asCurren ... -
Hessian 发布服务及客户端实现
2010-10-19 13:36 2137服务接口： package com.test; pub ... -
java 项目中嵌入 jetty，并发布servlet
2010-10-13 11:47 2219package com.utan.tfs.jetty; ... -
TreeSet<T> 简单实现
2010-08-26 17:31 1602package com.mypack.ds; i ... -
SAX 解析 XML 实例
2010-08-21 14:32 2452xml文件： <?xml version=" ... -
利用 Spring 中的 Resource 读取文件和网络资源
2010-08-21 12:04 3806利用 Spring 中的 Resource 读取文件和网络资源 ... -
NIO SAX
2010-08-20 18:51 1135NIO与SAX 直接上教程 -
socket 发送 soap 请求
2010-08-19 23:46 3888package com.mypack.soap.client; ... -
HttpUrlConnection 发送 SOAP 请求，SAX 解析 SOAP 响应
2010-08-19 23:38 8270HttpUrlConnection 发送 SOAP 请求，SA ...
相关推荐
wangtengfei-hn_EmployeesExample_23540_1745868671962
scratch少儿编程逻辑思维游戏源码-汽车冲突.zip
scratch少儿编程逻辑思维游戏源码-棱镜.zip
少儿编程scratch项目源代码文件案例素材-直升机坠毁.zip
输入法优化与定制_五笔编码编辑与词库管理_Rime输入法引擎与86极点码表_跨平台五笔码表编辑器工具_for_macOS与Windows系统_支持用户自定义词条添加删除与排序_提供
少儿编程scratch项目源代码文件案例素材-主题乐园大亨.zip
scratch少儿编程逻辑思维游戏源码-迷失在像素平原.zip
少儿编程scratch项目源代码文件案例素材-纸格通关 云变量.zip
wanjunshe_Python-Tensorflow_12888_1745868924470
scratch少儿编程逻辑思维游戏源码-深入海底.zip
驾校自动化_网页自动化爬虫技术_Python27多线程HTTP请求模拟_龙泉驾校2014版约车系统自动预约助手_通过模拟登录和循环请求实现自动约车功能_支持失败自动递增车号重试_
scratch少儿编程逻辑思维游戏源码-南瓜危机.zip
scratch少儿编程逻辑思维游戏源码-皮博冒险者.zip
基于c++开发的网络嗅探器，重点对TCP、UDP、ARP、IGMP、ICMP 等数据包进行分析，实现捕捉前过滤、数据包统计、流量统计等功能+源码+项目文档，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用，详情见md文档 基于c++开发的网络嗅探器，重点对TCP、UDP、ARP、IGMP、ICMP 等数据包进行分析，实现捕捉前过滤、数据包统计、流量统计等功能+源码+项目文档，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用，详情见md文档~ 基于c++开发的网络嗅探器，重点对TCP、UDP、ARP、IGMP、ICMP 等数据包进行分析，实现捕捉前过滤、数据包统计、流量统计等功能+源码+项目文档，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用，详情见md文档 基于c++开发的网络嗅探器，重点对TCP、UDP、ARP、IGMP、ICMP 等数据包进行分析，实现捕捉前过滤、数据包统计、流量统计等功能+源码+项目文档，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用，详情见md文档 基于c++开发的网络嗅探器，重点对TCP、UDP、ARP、IGMP、ICMP 等数据包进行分析，实现捕捉前过滤、数据包统计、流量统计等功能+源码+项目文档，适合毕业设计、课程设计、项目开发。项目源码已经过严格测试，可以放心参考并在此基础上延申使用，详情见md文档
用于释放电脑的内存，很好用。
scratch少儿编程逻辑思维游戏源码-气球足球.zip
ollama 0.6.6.0官网下载，不方便的可以从这里下载
scratch少儿编程逻辑思维游戏源码-魔幻之塔.zip
scratch少儿编程逻辑思维游戏源码-楼层酷跑.zip
scratch少儿编程逻辑思维游戏源码-披萨机器人.zip