By

转载自 http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html
原文格式不太好，调整下格式

今天看算法分析是，看到一个这样的问题，就是在一堆数据中查找到第k个大的值。

题目

设计一组N个数，确定其中第k个最大值

这是一个选择问题，当然，解决这个问题的方法很多，本人在网上搜索了一番，查找到以下的方式，决定很好，推荐给大家。
所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。

解法

  • 解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
  • 解法2： 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
  • 解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
    • Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
    • Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
  • 解法4： 二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
  • 解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)
  • 解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
  • 解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

    更多

By

题目

用两个栈实现队列

解法

  1. stack1 为进栈，添加数据都push到本栈
  2. stack2 为出栈，删除数据都从本栈pop。
    如果删除时 stack2 为空而 stack1 不为空，则先将stack1中的数据全部 pop 出来依次 push 到 stack2 中，然后再从 stack2 pop。

举一反三

也可使用两个队列实现栈，方法类似。

By

题目

某招聘笔试共有120人参加，考试有6道题。1-6道分别有86人，88人，92人，76人，72人和70人答对，如果答对3道或3道以上通过笔试，问至少有多少人通过？

解法

最差的情况是答对2道题和6题的人足够多总共答对题次86+88+92+76+72+70=484
每人至少答对2题，答对6题的人有：(484-240)/4=61

By

题目

个学校的15个女生一直3个一群上学。请问该如何安排才能使这些女生每周7天每天都和两个不同的同伴结伴同行呢？例如：用A到O来标识这些女孩，7天A正好和B到O这14个女孩各同行一次。而B到O每个人和都和其他14个女孩各同行一次。

更多

By

  1. Java8 中引入 default 关键字，从而有了多继承问题，那么继承规则是什么？
    基本上，你可以根据以下三条原则判断多继承的实现规则。
    • 类优先于接口。 如果一个子类继承的父类和接口有相同的方法实现， 那么接口中的定义会被忽略。 这是为了让代码向后兼容。
    • 子类型中的方法优先于父类型中的方法。
    • 如果以上条件都不满足，则必须显示覆盖/实现其方法，或者声明成abstract。

      更多

By

目的

　垃圾回收可以有效的防止内存泄露，有效的使用空闲的内存。

算法

引用计数法(Reference Counting Collector)

  • 被引用则计数加１，不再引用则减１。为０则标为垃圾，可被回收。
  • 很快，但无法检测出循环引用。

标记-清除算法(mark and sweep)

  • 标记：　把所有的引用关系看作一张图，从一个节点GC ROOT开始，寻找对应的引用节点，找到这个节点以后，继续寻找这个节点的引用节点，当所有的引用节点寻找完毕之后，剩余的节点则被认为是没有被引用到的节点，即无用的节点。
  • 清除：　直接回收无用的节点（会造成内存碎片）
  • java中可作为GC Root的对象有　【虚拟机栈中引用的对象（本地变量表），　方法区中静态属性引用的对象，方法区中常量引用的对象，本地方法栈中引用的对象（Native对象）】

标记-整理算法(mark and compact)

  • 在标记－清除算法的基础上，将存活对象往空闲空间移动
  • 一般增加句柄和句柄表, 解决了内存碎片问题，但成本更高

复制算法(Compacting Collector)

  • 开始时把堆分成 一个对象 面和多个空闲面， 程序从对象面为对象分配空间，当对象满了，基于copying算法的垃圾收集就从根集中扫描活动对象，并将每个 活动对象复制到空闲面(使得活动对象所占的内存之间没有空闲洞)，这样空闲面变成了对象面，原来的对象面变成了空闲面，程序会在新的对象面中分配内存。
  • 一种典型的基于coping算法的垃圾回收是stop-and-copy算法，它将堆分成对象面和空闲区域面，在对象面与空闲区域面的切换过程中，程序暂停执行。
  • 克服句柄的开销 , 解决堆碎片

generation算法(Generational Collector)

Generational Collector

更多

By

  1. 静态导入（Static Import）
    一般情况下，我们调用余弦的方式如下：

    1
    double r = Math.cos(Math.PI * theta);

    即在前面加入引用类 Math , 当我们经常使用这个函数时就会显得不厌其烦。一种解决方案是静态导入。
    使用

    1
    2
    import static java.lang.Math.PI;
    import static java.lang.Math.cos;

    或

    1
    import static java.lang.Math.*;

    则可以这样调用：

    1
    double r = cos(PI * theta);

    需要注意的是：并不推荐这样做。只有当一个方法或是变量经常使用时才使用静态导入，不然很容易造成误解，以为 cos 方法是当前类的方法，可读性差。个人比较喜欢在测试用例或是非产品类的项目中使用静态导入。
    参考: http://docs.oracle.com/javase/1.5.0/docs/guide/language/static-import.html

  2. 接口都继承自Object吗？如果不是，那为什么接口有equals方法？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class Test {
        public static void main(String[] args) {
            Employee e = null;
            e.equals(null);
        }
    }

    interface Employee {
    }

    首先接口与Object没有继承关系。其次接口对于Object中的每个public方法都有一个隐式声明，如果对 final 方法覆盖，则会编译错误。
    参考：http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2

    更多

By

在博客上写LaTex数学公式

参见在博客上写LaTex数学公式

#LaTeX数学公式输入

标识

$math_expression$ 或 \( math_expression \) 表示内嵌公式
$$math_expression$$ 或 \[math_expression \] 表示公式独占一行
\begin{equation} math_expression \end{equation}，则公式除了独占一行还会自动被添加序号， 如何公式不想编号则使用 \begin{equation*} math_expression \end{equation*}。

字符转义

　对于特殊字符# $ % & ~ _ ^ \ { }，在前面加转义符\，表示原字符

上标和下标

用 ^ 来表示上标，用 _ 来表示下标，看一简单例子：

1
2
$$\sum_{i=1}^n a_i=0$$
$$f(x)=x^{x^x}$$ //上下标可以嵌套

效果:
$$\sum_{i=1}^n a_i=0$$
$$f(x)=x^{x^x}$$

数学符号及公式

参见常用数学符号的 LaTeX 表示方法

更多

By

界面设计工具包

AWT、Swing、SWT 3种工具包，Swing最好

类层次

3种窗体 ： JFrame、JDialog、JWindow
×××Model 组件模型基类
JComponent 组件基类
×××UI 设置样式

界面消息提示JOptionPane

showConfirmedDialog显示确认对话框

Swing 菜单 JMenu

JMenuBar、JMenu、JMenuItem
后两者之间的关系类似于文件夹和文件

Menu的事件应该用Actionlistener而非MouseListener

自定义绘图组件

Graphic 、Graphic2D 优先使用后者，，能消除锯齿，且方法更多
drawXXX方法绘图，fillXXX方法填充
LookAndFeel改变界面的样式，Nis***最好，一般是System默认

每次组件更新都会调用paint函数
paint函数也会依次调用paintComponent（绘制自身）、paintBorder（绘制边界）和paintChildren（绘制子对象）

布局管理器 Layout

absolute、flow、border、grid、group 主要有这五中，最后一种最好用

文件选择器JFileChooser

setFileSelectionMode 可设置是否能够选择目录
setMultiSelectionEnabled 可设置是否能够多选

showOpenDialog 和 showSaveDialog 打开文件选择器，根据返回值做不同处理
getSelectedFile 和 getSelectedFiles获取选择的文件，后者用于多选情况

FileNameExtensionFilter文件扩展名过滤器
setFilter需要再show×××Dialog之前