yunchow
- 浏览: 324201 次
- 性别:
- 来自: 南京
-
文章分类
最新评论
-
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 11916滑动窗口计数有很多使用场景，比如说限流防止系统雪崩。相比计 ... -
面向对象程序设计思想（精华）
2014-11-12 15:52 1482面向对象语言具有封装，继承，多态的特征。那么在用面象对象语言 ... -
YY直播厅蠕虫病毒代码
2014-09-22 21:52 2504本来是可以直接通过<script>标签实现的， ... -
Apache Http Server Rewrite
2012-06-04 13:13 1192apache的rewrite功能很强大，详细参考：http:/ ... -
java操作MQ
2011-12-30 14:21 2874package mq; import jav ... -
实现动态验证码
2011-07-08 13:10 1193import java.awt.Color; imp ... -
简单统计代码行数
2010-12-30 17:34 1472真的很多,我刚写了个程序统计了一下,我们项目才695个类 并 ... -
采用MD5单向加密
2010-11-26 10:42 1319public static String get ... -
在报表中格式化货币
2010-11-25 10:01 1765最近在用FineReport这个工具进行系统的报表开发,发现在 ... -
Struts + JSP导出Excel报表
2010-11-07 20:21 2419据我所知 Java 导 Excel 报表有三种方法: 1, 在 ... -
Java正则实现EL表达式
2010-11-04 16:19 4492public static void main(Stri ... -
js格式化货币格式
2010-11-01 13:41 3808String.prototype.asCurren ... -
Hessian 发布服务及客户端实现
2010-10-19 13:36 2110服务接口： package com.test; pub ... -
java 项目中嵌入 jetty，并发布servlet
2010-10-13 11:47 2191package com.utan.tfs.jetty; ... -
TreeSet<T> 简单实现
2010-08-26 17:31 1558package com.mypack.ds; i ... -
SAX 解析 XML 实例
2010-08-21 14:32 2409xml文件： <?xml version=" ... -
利用 Spring 中的 Resource 读取文件和网络资源
2010-08-21 12:04 3783利用 Spring 中的 Resource 读取文件和网络资源 ... -
NIO SAX
2010-08-20 18:51 1089NIO与SAX 直接上教程 -
socket 发送 soap 请求
2010-08-19 23:46 3863package com.mypack.soap.client; ... -
HttpUrlConnection 发送 SOAP 请求，SAX 解析 SOAP 响应
2010-08-19 23:38 8232HttpUrlConnection 发送 SOAP 请求，SA ...
相关推荐
首先，取数组的第一个、最后一个和中间元素，找出三个中最小的作为新的枢轴，然后根据枢轴的位置将数组分为三部分：小于枢轴、等于枢轴和大于枢轴。如果k在小于枢轴的区间，就在这个区间重复此过程；如果k在大于枢轴...
在这个特定的问题中，我们要利用分治法来实现“元素选择”，即找出线性序列集中第k小的元素及其位置。下面我们将深入探讨这个过程。 首先，理解问题的关键在于如何有效地比较并排序序列中的元素。分治法的基本步骤...
这种算法常用于密码学、数据加密以及计算机科学中的各种组合优化问题，例如在处理含有重复字母的字符串时，找出所有可能的重组方式。 #### 知识点二：算法实现原理 在Java中实现重复元素全排列，通常采用递归的...
总结来说，最长不减子序列问题是一个典型的动态规划问题，通过维护一个动态规划数组，可以有效地找出给定序列的最长不减子序列的长度。这种思想在解决许多其他序列相关的优化问题时也非常有用，比如最长递增子序列、...
该算法的目标是找出两个序列中的最长公共子序列，即一个序列中存在但不一定是连续的子序列，同时这个子序列也是另一个序列的子序列。LCS 不考虑子序列在原序列中的相对位置，只关注它们的元素。 动态规划方法是解决...
最长递增子序列...总结来说，最长递增子序列问题是一个经典的动态规划问题，通过维护一个动态规划数组来找出序列中的最长递增子序列。理解并熟练掌握这种问题的解决方法对于提升算法设计和编程能力非常有帮助。
奇异序列是一种特殊的数字序列，其特点可能包含但不限于以下几点：每个元素是前两个或前若干个元素的某种组合（如求和、乘积等）、序列中特定位置的元素遵循特定规律或者序列本身具有某种数学上的奇特性质。...
该问题旨在找到两个序列（通常是字符串）的最长子序列，这个子序列不需要在原序列中连续出现，但必须保持原有顺序。在本问题中，我们有两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，目标是找到它们的LCS。 解决LCS...
在JavaScript编程中，"数组的最大不重复连续子序列"是一个常见的算法问题，它涉及到数组处理、动态规划或者滑动窗口等技术。这个问题的目标是从给定的数组中找到一个最长的子序列，这个子序列中的元素既不重复且是...
关于如何用JavaScript实现找出数组中最长的连续数字序列，以下是一些重要的知识点。 首先，需要理解连续数字序列的定义：在一个整数序列中，连续数字是指按数值顺序排列，且数值相邻的数字序列。例如，序列[1, 2, 3...
这个代码首先初始化了 `dp` 数组，然后通过两层循环找出所有可能的子序列，根据元素之间的大小关系更新子序列长度。最后返回最长子序列的长度。 **总结：** 最长子序列问题是一个典型的动态规划问题，适用于解决一...
其核心定义是给定一个由不同序列组成的集合，序列中的每个元素由不同项目按顺序组成，并且给定一个最小支持度阈值，序列模式挖掘的目标是找出所有在序列集中出现频率不低于该最小支持度阈值的频繁子序列。...
- LIS问题是在一个序列中找出最长的严格递增子序列。 - 动态规划解法：dp[i]表示以第i个元素结尾的LIS的长度。状态转移方程为dp[i] = max(dp[j] + 1)，其中j 且nums[j] [i]。 - 输出位置：可以使用单调栈或二分...
设定一个固定长度的窗口，滑动并比对每个可能的子序列，找出与目标序列得分最高的子序列，这就是所谓的局部比对。 在MFC（Microsoft Foundation Classes）环境中实现这样的程序，需要利用MFC的事件驱动模型和控件来...
`Union()`方法也是LINQ的一部分，用于返回两个序列的唯一元素集合并删除重复项。在这个场景下，如果数组元素有重复，它会自动去除。但如果数组元素无重复，`Union()`等同于`Concat()`。 ```csharp int[] ...
我们的任务是找出这样的序列中最长的一个。 在C语言中解决这个问题，我们需要利用字符串处理函数，如`strlen()`来获取字符串长度，`strcpy()`和`strcat()`来复制和连接字符串，以及指针来遍历字符串。但关键在于...
这是因为每个元素都需要与其他所有元素比较一次，以找出最小的元素。因此，尽管线性选择排序的实现相对简单，但在处理大量数据时效率较低，通常不推荐在实际应用中使用。对于大数据集，更高效的排序算法如快速排序、...
最长公共子序列是指两个序列中存在的一段序列，它既出现在第一个序列中，也出现在第二个序列中，但不考虑元素的相对顺序。例如，"ABCDGH"和"AEDFHR"的最长公共子序列是"ADH"。 在给定的代码中，`LCSLength`函数用于...
4. **结果获取**：遍历`dp`数组，找出其中的最大值即为最长递增子序列的长度。 #### Java实现示例： ```java public class LongestIncreasingSubsequence { public int lengthOfLIS(int[] nums) { if (nums == ...