eriol
- 浏览: 401138 次
- 性别:
- 来自: 上海
-
最新评论
-
handong1587：
代码有一处错.query函数最后一行return的应该是:re ...
RMQ -
yuandong0828：
简洁的特别透彻细致，多谢，
虚函数、虚指针和虚表 -
adam_zs：
谢谢分享！
括号匹配问题 -
hongloumengyanzxw：
good[b][/b]
dup和dup2函数 -
chriszeng87：
最后第二种情况右下角的那个点是不是可以看作相交点的?上面的那种 ...
判断两个链表是否相交
文章列表
单向链表操作总结
- 博客分类：
- DS & Algorithm
1. 有可能会改变链表第一个元素的任何子函数都必须把一个指针传递给头指针。
2. 在遍历链表的时候，千万不要忘记检查自己是否已经到达了它的末尾。
3. 如果要在单向链表中删除或插入一个元素，就必须知道指向删除点或插入点前面那个元素的指针才行。
4. 单向链表的元素删除操作至少要使用两个指针才能正确完成。事实上，单向链表的元素插入操作也需要两个指针才能正确完成，它们一个负责给出插入点在链表中的位置，另一个则指向由内存分配调用返回的新元素；只是人们在进行插入操作时很少会像在进行删除操作时那样忘记需要使用两个指针而已。
5. 当遇到长度为0、1、2个元素 ...
1. 在一个单向链表中，寻找链表中间节点。
使用两个指针，快指针每次步进为2，慢指针每次步进为1。当快指针到达链表尾部时，慢指针指向的就是链表的中间。
Node findMiddleNode(Node head) {
if (head == null)
return head;
Node p1 = head;
Node p2 = p1.next;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 ...
问题描述：给出一个数列，找出其中最长的单调递减（或递增）子序列。
解题思路：动态规划。假设0到i-1这段数列的最长递减序列的长度为s，且这些序列们的末尾值中的最大值是t。对于a[i]有一下情况：
(1) 如果a[i]比t小，那么将a[i]加入任何一个子序列都会使0到i的最长单调序列长度变成s+1，这样的话，在0到i的数列中，长度为s+1的递减子序列的末尾值最大值就是a[i]；
(2) 如果a[i]和t相等，那么说明数列从0项到i项的最长单调子序列长度就是s；
(3) 如果a[i]比t大，那么a[i]就不一定能够成为长度为s的递减子序列的末项，这取决于长度为s-1的各个递减子序 ...
问题描述：若一个数组为[A1, A2, ..., An]，若有i<j且Aj>Ai，那么Ai和Aj就构成一个逆序对。该问题是求出数组中所有逆序对的数目。
算法思想：使用分治法可以在O(nlogn)的时间复杂度下，求出逆序对。其思想为，把一个数组拆分为两个子数组，不妨称为L和R，那么原数组的逆序对数就等于L的逆序对数加上R的逆序对数，再加上一个元素在L中另一个元素在R中构成的逆序对数。可以在分解时独立求出L和R中逆序对数，然后合并时再加上L和R共同构成的逆序对数。
public class reverseOrder {
private static in ...
问题描述：
有一串数字（可正可负的int，放在数组Num里），要求找到起始位置start和终止位置end，使得从start位置到end位置的所有数字之和最大，返回这个最大值max。
算法思想：使用动态规划。
设 f[x] 为以 a[x] 终止且包含 a[x] 的最大序列的和，有：
f[1] = a[1];
f[x+1] = f[x] > 0 ? f[x] + a[x+1] : a[x+1]
那么最大子序列的和就是 f[1] .. f[n] 中最大的一个。其算法的时间复杂度为O(n)，代码实现如下：
void maxSubse(int[] a ...
问题描述：求一个序列的所有排列情况。
算法思路：使用递归的思想。将每个元素放到长度为n的序列的第一个，然后对剩余的元素进行全排列。
参数说明：in表示输入的字符串，out用来存放输出的字符串，length表示字符串长度，used用来标记哪些字符已经被使用，level用来表示递归的深度。注意，当递归返回时，要将used相应项恢复。
void permute(char[] in, char[] out, int length, int[] used, int level) {
if (level == length) {
System.out.println( ...
问题描述：给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
算法思想：原地排列给定的数列，在第i次迭代时，元素A[i]是从A[i]到A[n]中随机选取的，第i次迭代后，A[i]保持不变。时间复杂度为O(n)。该程序将会产生n*(n-1)*(n-2)*...*1种等可能的情况，它们正好与1至n的n!种排列一一对应。
void shuffle(int[] a) {
int n = a.length;
for (int i = 1; i <= n; i++) {
swap(a[i], a[random(i, n)]);
...
拓扑排序是对依赖关系的排序，使得如果A必须在B前发生，则A的顺序在B的前面。一般我们使用有向无回路图（DAG）来说明事件发生的先后次序。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列）。这样，一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。
拓扑排序的思想是：首先找到一个入度为0的顶点，删除它及射出的边，然后再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑 ...
C++ 内联函数（inline）
概念：内联函数是为了解决C++预处理器宏存在的问题所提出一种解决方案，用来提高函数使用效率。
目的：在程序编译时，编译器会将程序中出现的内联函数的调用表达式用内联函数的函数体来进行替换。由于在编译时将内联函数体中的代码替代到程序中，因此会增加目标程序代码量，进而增加空间开销，而在时间开销上不象函数调用时那么大，所以它是以目标代码的增加为代价来换取时间的节省。即inline函数是为了提高运行时间效率，但却增加了空间开销。
定义：
(1) 内联函数使用inline关键字定义。关键字inline 必须与函数定义体放在一起才能使函数成为内联，仅 ...
OO基础
抽象
封装
多态
继承
OO原则
封装变化
多用组合，少用继承
针对接口编程，不针对实现编程
为交互对象之间的松耦合设计而努力
对扩展开放，对修改关闭
依赖抽象，不要依赖具体类
只和朋友交谈
别找我， ...
Chapter 2 --观察者模式
让你的对象知悉现况
1. 有一个模式可以帮你的对象知悉现况，不会错过该对象感兴趣的事。对象甚至在运行时可决定是否要继续被通知。
2. 出版者+订阅者=观察者模式（类似于报纸订阅服务）
观察者模式：
定义了对象之间的一对多依赖，这样一来，当一个对象改变状态时，它的所有依赖者都会收到通知并自动更新。
Structure
Subject: 这是主题接口，对象使用此接口注册为观察者，或者把自己从观察者中删除。
Observer: ...
S先生、P先生、Q先生他们知道桌子的抽屉里有16张扑克牌：
红桃A、Q、4
黑桃J、8、4、2、7、3
草花K、Q、5、4、6
方块A、5
约翰教授从这16张牌中挑出一张牌来，并把这张牌的点数告诉 P先生，把这张牌的花色告诉Q先生。这时，约翰教授问P先生和Q 先生：你们能从已知的点数或花色中推知这张牌是什么牌吗？ 于是，S先生听到如下的对话：
P先生：我不知道这张牌。
Q先生：我知道你不知道这张牌。
P先生：现在我知道这张牌了。
Q先生：我也知道了。
听罢以上的对话，S先生想了一想之后，就正确地推出这张牌是什么牌。
请问：这张牌是什么牌？
----- ...
本系列是我自己学习“Head First Design Pattern”一书的读书笔记和心得。将按照每次一个Chapter的顺序进行记录。欢迎大家分享你的学习心得。
Chapter 1 --设计模式入门
1. 对代码的局部修改，影响的层面不只是局部（会影响到 ...
你见，或者不见我
我就在那里
不悲 不喜
你念，或者不念我
情就在那里
不来 不去
你爱，或者不爱我
爱就在那里
不增 不减
你跟，或者不跟我
我的手就在你手里
不舍 不弃
来我的怀里
或者
让我住进你的心里
默然 相爱
寂静 欢喜
在看一段代码的时候，看到了抽象类竟然有定义的构造函数，当时十分不解。因为记得Abstract类不能被实例化，所以理所当然的认为Abstract类不会有构造函数。结果编译成功，程序能正常运行。
测试的程序为：
public abstract class Base {
public Base() {
System.out.println("In the Base Constrction");
}
public Base(int i) {
System.out.println(i);
}
...