关于多态

发表于 2018-04-02 |

我发现我还是没搞清楚多态这个东西, 今天正好有时间研究一下.

~~好渴我没找到哪里能接水好渴啊啊啊啊啊~~
~~原来超类就是父类吗我勒个去~~

继承

首先是继承,继承在概念上很好理解. 这篇文章(http://www.cnblogs.com/chenssy/p/3354884.html) 中提到了关于继承的三个注意点:

构造器

1
2

对于构造器而言，它只能够被调用，而不能被继承。 调用父类的构造方法我们使用super()即可。
子类会默认调用父类的构造器，但如果没有默认的父类构造器，子类必须要显示的指定父类的构造器，而且必须是在子类构造器中做的第一件事(第一行代码)

这个主要是讲了子类怎么调用父类的构造器

2 . protected: 可被1)此类的子类; 2)位于同一包的子类访问.
private: 可被1)此类访问

附上一个方便分类的图表(https://stackoverflow.com/questions/215497/in-java-difference-between-package-private-public-protected-and-private)

            | Class | Package | Subclass | Subclass | World
            |       |         |(same pkg)|(diff pkg)| 
————————————+———————+—————————+——————————+——————————+————————
public      |   +   |    +    |    +     |     +    |   +   
————————————+———————+—————————+——————————+——————————+————————
protected   |   +   |    +    |    +     |     +    |       
————————————+———————+—————————+——————————+——————————+————————
no modifier |   +   |    +    |    +     |          |  
————————————+———————+—————————+——————————+——————————+————————
private     |   +   |         |          |          |    
+: accessible
blank: not accessible

3 . 向上转型
向上继承是把子类放入原本是父类格式的参数/变量来用

这篇文章还说明了继承的缺陷:

1、父类变，子类就必须变。
2、继承破坏了封装，对于父类而言，它的实现细节对与子类来说都是透明的。
3、继承是一种强耦合关系。     
所以说当我们使用继承的时候，我们需要确信使用继承确实是有效可行的办法。
那么到底要不要使用继承呢？《Think in java》中提供了解决办法：问一问自己是否需要从子类向父类进行向上转型。如果必须向上转型，则继承是必要的，但是如果不需要，则应当好好考虑自己是否需要继承。

耦合的定义:

耦合性（英语：Coupling，dependency，或称耦合力或耦合度）是一种软件度量，是指一程序中，模块及模块之间信息或参数依赖的程度。

多态

多态就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编程时并不确定，而是在程序运行期间才确定，即一个引用变量倒底会指向哪个类的实例对象，该引用变量发出的方法调用到底是哪个类中实现的方法，必须在由程序运行期间才能决定。因为在程序运行时才确定具体的类，这样，不用修改源程序代码，就可以让引用变量绑定到各种不同的类实现上，从而导致该引用调用的具体方法随之改变，即不修改程序代码就可以改变程序运行时所绑定的具体代码，让程序可以选择多个运行状态，这就是多态性。

重载(overload)和重写(override)
重载: 方法名字相同, 参数不同, 返回值可同/可不同.
重写: 返回值/参数不变, 内容重写.

2.1 多态的实现条件

Java实现多态有三个必要条件：继承、重写、向上转型。
继承：在多态中必须存在有继承关系的子类和父类。
重写：子类对父类中某些方法进行重新定义，在调用这些方法时就会调用子类的方法。
向上转型：在多态中需要将子类的引用赋给父类对象，只有这样该引用才能够具备技能调用父类的方法和子类的方法。

对于Java而言，它多态的实现机制遵循一个原则：当超类对象引用变量引用子类对象时，被引用对象的类型而不是引用变量的类型决定了调用谁的成员方法，但是这个被调用的方法必须是在超类中定义过的，也就是说被子类覆盖的方法。

2.2 多态的实现形式
1) 基于继承
2) 基于接口
这里又涉及到了接口这个小妖精

-L= 有点累一会再写

xqw爬虫

发表于 2017-11-30 |

实验物, 主要目的是对xqwh.org进行帖子爬虫, 顺带学习一下python爬虫

~~好难!!我是谁我在哪~~

关于线程分离的一点整理

发表于 2017-11-28 |

Event dispatch thread EDT事件指派线程

!!!注意：线程分离(thread detached)和事件指派线程(event dispatch thread)并不是一个东西，线程分离是一个更为广域的概念，应用的场景也比事件指派要广；

线程的分离/可结合的 detached/joinable

线程的分离状态决定线程的终止模式。
分离：运行结束，线程即终止；
可结合的：在pthread_join()获得结合的另一个线程的中止状态才能释放此线程的资源。
pthread_join():暂停（阻塞）此线程（即自身）的运行，直到目标线程终止。

线程分离的原因：

串行执行任务（单线程）时，当遇到耗时较长的任务，线程将等待很长时间（进行任务），此时线程类似于进入阻塞状态，特别是对于UI操作，用户在这段时间无法对UI进行任何操作，故为了避免这种情况，线程中引入了线程并发（也就是将主线程和子线程分离）。

Java中的EDT线程

http://www.oracle.com/technetwork/articles/javase/swingworker-137249.html
Java的线程大致可分为三类：

起始线程（initial thread）
EDT
多个工作线程（work threads）

main运行产生了起始线程，对于有GUI的java程序而言，initial thread在产生GUI后基本结束了自己的使命。
Swing应用中包含一个单独的EDT用于UI相关的操作。EDT线程绘制/更新GUI组件，并对用户交互做出反馈（通过event handler）。Java规定用户不能直接对（线程不安全）Swing部件直接进行调用，而是必须要通过EDT和EDT对应的event queue对Swing部件进行调用。

在Java中对于线程分离的规定：

在java中，特别是对于UI的Swing线程这种实际上是单线程处理的线程而言，涉及到UI相关的操作，将耗时较长的线程单独分离出去是非常必要的，并且是Java强制规定的。

Java的规定当中，如果Swing部件的方法被标明”thread safe”，那么这个线程可以从其它线程中被调用，但是其他所有Swing部件的方法都必须被放在Event dispatch thread中被调用，而非从主线程或其他工作线程中被调用。

总结起来一共2点：

耗时的任务不应在EDT中被运行
Swing部件应在并且只在EDT被获取（即GUI相关的任务活动）。
https://docs.oracle.com/javase/6/docs/api/javax/swing/SwingWorker.html

Java GUI中与EDT交互的方法：

常用的方法有使用event-handling 方法，比如ActionListener.actionPerformed，或者可以使用invokeLater或者invokeAndWait方法。后两者的区别是later中主线程不会等待子线程而是继续运行，wait则会让主线程等待子线程运行完后才继续运行。

不过，由于Swing本身运行仍是串行运行在EDT上的，所以分离出的线程会进入一个线程队列中，等到线程拿到运行权，分离的线程才会运行。所以这就产生的一个新的问题发生点，分离出的子线程可能会在主线程运行很久以后才能得到运行。

多线程分离返回值或进行对UI操作的问题：

分离线程后，如果遇到主线程需要子线程的返回值再操作，或者需要子线程结束刷新UI的操作时，子线程的操作可能不能及时传达到主线程/UI中。对于这种情况，可以采取一些方法来处理：1）循环判断：主线程循环判断子线程是否完成操作，但这种方法占用很多内存，而且最坏的情况是由于主线程的循环判断子线程无法拿到运行权；2）回调：子线程调用主线程中的回调方法，从而进行继续的赋值或渲染操作；3）使用自带返回值的Callable接口，向主线程返回值；4）对于GUI相关操作，可以使用invokeAndWait方法；5）使用SwingWorker。

源码分析

EventQueue类:

isDispatchThread

1	public static boolean isDispatchThread()

如果正在调用的线程是当前 AWT EventQueue 的指派线程，则返回 true。使用此调用确保给定的任务正在当前 AWT EventDispatchThread 上执行（或没有执行）。
返回：
如果给定的任务正在当前 AWT EventQueue 的指派线程上运行，则返回 true。

invokeAndWait

1
2
3

public static void invokeAndWait(Runnable runnable)
                          throws InterruptedException,
                                 InvocationTargetException

导致 runnable 的 run 方法在 the system EventQueue 的指派线程中被调用。在所有挂起事件被处理后才发生。在这发生之前调用被阻塞。如果从事件指派线程进行调用，则该方法将抛出 Error。
参数：
runnable - Runnable 对象，其 run 方法应该在 EventQueue 上同步执行
抛出：
InterruptedException - 如果任何线程中断了该线程
InvocationTargetException - 如果运行 runnable 时抛出一个 throwable

/**
     * Causes <code>runnable</code> to have its <code>run</code>
     * method called in the {@link #isDispatchThread dispatch thread} of
     * {@link Toolkit#getSystemEventQueue the system EventQueue}.
     * This will happen after all pending events are processed.
     * The call blocks until this has happened.  This method
     * will throw an Error if called from the
     */
    public static void invokeAndWait(Runnable runnable)
        throws InterruptedException, InvocationTargetException
    {
        invokeAndWait(Toolkit.getDefaultToolkit(), runnable);
    }
    static void invokeAndWait(Object source, Runnable runnable)
        throws InterruptedException, InvocationTargetException
    {
        if (EventQueue.isDispatchThread()) {
            throw new Error("Cannot call invokeAndWait from the event dispatcher thread");
        }
        class AWTInvocationLock {}
        Object lock = new AWTInvocationLock();//加了一个AWT invocation锁
        InvocationEvent event =
            new InvocationEvent(source, runnable, lock, true);
        synchronized (lock) {
            Toolkit.getEventQueue().postEvent(event);
            while (!event.isDispatched()) {
                lock.wait();
            }
        }
        Throwable eventThrowable = event.getThrowable();
        if (eventThrowable != null) {
            throw new InvocationTargetException(eventThrowable);
        }
    }

invokelater

public static void invokeLater(Runnable runnable)
导致 runnable 的 run 方法在 the system EventQueue 的指派线程中被调用。
参数：
runnable - Runnable 对象，其 run 方法应该在 EventQueue 上同步执行

/**
     * Causes <code>runnable</code> to have its <code>run</code>
     * method called in the {@link #isDispatchThread dispatch thread} of
     * {@link Toolkit#getSystemEventQueue the system EventQueue}.
     * This will happen after all pending events are processed.
     * 会在其他EDT中等待的进程结束运行后再运行
     */
    public static void invokeLater(Runnable runnable) {
        Toolkit.getEventQueue().postEvent(
            new InvocationEvent(Toolkit.getDefaultToolkit(), runnable));
    }

getEventQueue()获取了应用的event queue实例，
postEvent(): 令eventQueue中的线程呈现1.1关系。即每个队列中的线程都有着不同的ID和事件源（event source）（把runnable的事件放入EventQueue）
getDefaultToolkit(): 获取默认工具包
（关于java toolkit： http://blog.csdn.net/linhu007/article/details/18505423）
//InvocationEvent(): 创建一个源为DefaultToolkit的invacationEvent, 此源会在被指派时执行runnable的run方法（即执行invokelater中的被分离的子线程）

http://www.blogjava.net/vincent/archive/2008/08/24/223933.html
http://www.360doc.com/content/12/1022/01/820209_242886827.shtml
http://www.importnew.com/15761.html

EDT(事件派发线程) 此线程会调用事件队列（event queue）依次进行事件处理。InvokeLater和invokeAndWait都会把参数中的runnable事件放入事件队列尾，等待EDT派发。二者的区别是Wait会在完成事件后才返回（实现机制是给线程加锁），Later则是把事件放入就直接返回。

SwingWalker

https://docs.oracle.com/javase/6/docs/api/javax/swing/SwingWorker.html
http://www.oracle.com/technetwork/articles/javase/swingworker-137249.html
SwingWalker的出现替代了前两个方法的工作，SwingWorker同样是创建了新的子线程，使用SwingWorker的doInBackground方法，把耗时的任务放到方法中，在方法完成后，SwingWorkder调用EDT中的done()方法，可用于返回结果值。

SwingWorker适用于需要在后台线程中执行长时间的运算工作时，对于运算完成时对UI的更新通知或者在运算过程中的更新。为了描述后台线程执行的具体工作，在继承抽象类SwingWorker的子类一定要实现doInBackground()方法。

在SwingWorker的生命循环中涉及到3个线程：

当前线程（current thread）:
execute()让SwingWorker开始运行工作在workder thread上; get()可以让current thread等待SwingWorker完成任务之后再继续进行；一般来说，current thread就是EDT本身。
工作线程（worker thread）：
doBackGround()；使用firePropertyChange and getPropertyChangeSupport() methods. By default there are two bound properties available: state and progress.
EDT：
SwingWorkder触发done()并通知所有在此线程上的PropertyChangeListeners。

Before the doInBackground method is invoked on a worker thread, SwingWorker notifies any PropertyChangeListeners about the state property change to StateValue.STARTED. After the doInBackground method is finished the done method is executed. Then SwingWorker notifies any PropertyChangeListeners about the state property change to StateValue.DONE.
在SwingWorker开始和结束工作的时候，都会向Listeners发送通知。
SwingWorker is only designed to be executed once. Executing a SwingWorker more than once will not result in invoking the doInBackground method twice.
SwingWorker只能被运行一次。
SwingWorker实现了Runnable借口，所以SwingWorker可以被提交到Executor中运行。

关于Executor (待更新)

顺便整理一个好用的在线markdown编辑器：https://pandao.github.io/editor.md/

关系数据库中的范式

发表于 2017-11-28 |

~~准备面试,整理一下范式相关~~
部分NF定义参考于 https://www.zhihu.com/question/24696366/answer/29189700 <-这个答案中对于2NF/3NF定义中的码我认为应该是主码而非码(候选码), 其他的表述还是可以参考的.
英文定义部分参考的数据库课上的课件

各种NF:

1. 1NF

Domain is atomic,不可再分
A relational schema R is in first normal form if the domains of all attributes of R are atomic.

2. 2NF

条件1: 满足1NF
条件2: 非主属性完全依赖于主键, 即不存在非主属性部分依赖于主键.<-非主属性指不包含在任何候选键中的一个属性
部分依赖举例: R{A,B,C}, 主键为(AB), 存在A->C, B->C, 此时即为部分依赖.
必须是AB->C才是完全依赖

3. 3NF

条件1: 满足2NF
条件2: 非主属性不传递依赖于主键
A relation schema R is in 3rd normal form (3NF) if for all α → β in F+, at least one of the following holds:

α → β is trivial (i.e., β ∈ α)
α is a superkey for R
Each attribute A in β – α is contained in a candidate key for R. (A-B means union belongs to A but not to B). (NOTE: each attribute may be in a different cand. key)

4. BCNF

条件1: 满足2NF
条件3: 每个属性(含主属性)都不传递依赖于主键
非主键传递依赖于主键举例: R{A,B,C}, A为主键, 存在A->B, B->C, 此时非主键C传递依赖于主键A
A relation schema R is in BCNF with respect to a set F of functional dependencies if for all functional dependencies in F+ of the form (α → β) where α ⊆ R and β ⊆ R, at least one of the following holds:

α → β is trivial (i.e., β ⊆ α)
α is a superkey for R
BCNF的限制要低于高于3NF. BCNF一定是3NF

Functional Dependencies 函数依赖

1. 函数依赖

X->Y
不存在X1=X2时, Y1!=Y2.

2. 完全(函数)依赖

X->Y, 且不存在(X的真子集)->Y, 称Y完全依赖于X;

3. 部分(函数)依赖

X->Y, 且存在(X的真子集)->Y, 称Y部分依赖于X;

4. 传递(函数)依赖

Y不属于X && Y!->X, X->Y, Y->Z, 称Z传递依赖于X.
(http://blog.csdn.net/crave_shy/article/details/12401935)

5. trivial function

α → β is trivial if β ⊆ α.
Example: ID, name → ID; name → name

各种键

Key：

关系中的某个属性或者某几个属性的组合，用于区分每个元组(tuple)(每一行)

Super key:

超键(super key): 在关系中能唯一标识元组的属性集称为关系模式的超键
K is a superkey for relation schema R if and only if K → R
超键中可以包含非候选键.

Candidate key:

K is a candidate key for R if and only if

K → R, and
for no α ⊂ K, α → R

候选键(candidate key): 不含有多余属性的超键称为候选键, 即实现了候选键之外的其余属性对于候选键的完全依赖.
候选键可能有多个, 一个候选键可能包含一个或多个属性.

Primary key:

主键(primary key):用户选作元组标识的一个候选键作为程序主键
主键只有一个, 主键可能包含一个或多个属性.

Foreign key:

外键(foreign key): 如果关系模式R1中的某属性集不是R1的主键，而是另一个关系R2的主键则该属性集是关系模式R1的外键。

Reverse Integer

发表于 2017-09-19 |

7. Reverse Integer 整数取反

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

SOL

稍微处理一下即可, 详见代码

//32 bit int max = 2,147,483,647
//直接存储过大的数会报错, 但是对int做加法不会直接报错，而是变成其他值
//无需对负数单独处理
class Solution {
    public int reverse(int x) {
        //boolean minus = false;
        //if (x<0) minus = true;
        int result=0;
        while(x!=0){
            int tail = x%10; 
            int newResult = result*10+tail;
            if((newResult-tail)/10!=result) return 0;
            result = newResult;
            x=x/10;
        }
        return result;
    }
}

排序算法笔记2

发表于 2017-09-16 |

归并排序
(待更新)

排序算法笔记1

发表于 2017-09-14 |

一些碎碎念
切实感到了自己体质的差劲, 家里人病倒了过去照顾了几天, 自己也被传染了, 一个月感冒发烧两次真的是破了自己这辈子的记录了.

选择排序 Selection Sort

思路: 从所有字符里找出最小的, 放到第一个位置, 继续对剩下的字符找出最小的, 放到第二个位置, 以此类推.

数据移动: N次(最少), 运行时间和输入(eg.部分有序或部分相同)无关
比较: N2/2次, 复杂度n2

实现思路: 为了方便实现, 程序实现往往和算法本身的思路会有一些区别.
在比较寻找最小的过程中, 用一个变量min来记录最小值的index, 随着每次比较(j和min)不断刷新min的index即可.

public class SelectionSort {
    public static void sort(int[] a){
        for(int i = 0; i<a.length; i++){
            int min = i;//<--!!!不是0!!!-L-
            for(int j=i+1; j<a.length; j++){
                if(a[min]>a[j])   min = j;
            }
            //swap三板斧 a[i]<->a[min]
            int temp = a[i]; a[i]=a[min]; a[min]=temp;
        }
    }
}

插入排序 Insertion Sort
一张一张插到合适的位置, 和整理牌类似

思路: 当前索引左边都是有序的, 但位置还不确定因为可能会插入新数字, 当索引到达最右端, 排序完成.

运行时间和输入有关, 接近整理好的数组的排序时间会远小于杂乱的数组.
交换: ~N2/4次(平均), ~N2/2次(最差-完全倒序), 0次(最优)
比较: ~N2/4次(平均), ~N2/2次(最差-完全倒序), N-1次(最优)

复杂度n2

实现思路: 虽然左侧序列是不确定的, 但在每次循环都只是多加了1个或者不加而已, 还是基本确定的(加一个也只是一次往前交换而已), 所以索引只要从0开始+1+1就可以了.

public static void insertionSort(int[] a){
        for (int i = 0; i<a.length; i++){
            for(int j=i; j>0 && a[j-1]>a[j]; j--){
                //swap
                int temp = a[j]; a[j]=a[j-1]; a[j-1]=temp;
            }
        }
    }

插入排序对于部分有序/小规模的数组非常高效.

希尔排序 Shell Sort

希尔排序的思想是使数组中任意间隔为h的元素都是有序的.

ZigZag Conversion

发表于 2017-09-03 |

6. ZigZag Conversion zigzag模式转换

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

SOL

很容易能看出字符串的排列位置是以(2n-2)的间隔重复, 直接循环取值形成每行字符串即可.
一个小注意点在于对于每个循环内部两端对称的字符并不是完全的等差序列, 而是相对于每个循环首尾字符等差, 所以在这个基础上加上一些小判定和处理即可. 思路比较直接.
复杂度O(n).

实际上实现的难点是各种+1-2….等的处理, 以及小心不要数组越界, 稍有不慎就会加错/越界orz导致整个结果出错.

注意点:

边界条件, 对于边界条件的思索和处理应该是第一步, 而不是等到submit/test返回error才想到忘记处理边界了.
对于数组内部数字的运算, 想好再写, 不然复杂的处理很容易越界.

class Solution {
    public String convert(String s, int numRows) {
        //别忘了第一件事处理边界！！
        if (s.length()<=1 || numRows<=1) return s;
        String innerPart = "";
        String result = "";
        for(int i=0; i<numRows; i++){//处理
            innerPart="";
            int j=0;
            while(j<(s.length())/(2*numRows-2)){//只处理可整除部分
                innerPart+=s.charAt(i+(2*numRows-2)*j);
                if (i!=0 && i!=numRows-1) innerPart+=s.charAt((2*numRows-2)*(j+1)-i);
                j++;
            }
            //处理余数
            int mod=s.length()%(2*numRows-2);
            if (mod>i) {
                innerPart+=s.charAt((s.length()/(2*numRows-2))*(2*numRows-2)+i);
                if(i!=0 && i!=numRows-1 && ((2*numRows-2)-i) <mod){
                    innerPart+=s.charAt(((s.length()/(2*numRows-2))+1)*(2*numRows-2)-i);
                }    
            }
            result+=innerPart;
            //System.out.print(result);
        }
        return result;
    }
}

Longest Palindromic Substring

发表于 2017-08-31 |

5. Longest Palindromic Substring 最长回文子字符串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”

单个字符也会返回回文

SOL

解法1

暴力搜索, 直接对字符串中每个字符左右搜索, 每次搜索分别会搜索奇数和偶数两种情况, 复杂度O(n2).

一些tip:

substring的范围是[startIndex, endIndex-1], 分场令人悲愤
使用字符串时要时刻注意下标越界的情况, 会直接返回error –> 而如果想防止越界, 也可以给首位再加上符号
在字符串每个字符中间插入一个特殊符号, 可以一次处理奇偶两种情况, 会更加方便. (这也是Manache方法的核心之一)
看上去很简单的暴力算法实现时也是有很多地方需要注意的, 而且出现数组/字符串/多对象时, index的加减运算一定要注意, 不要越界
2k之类的是不对的, 乘法要写作2*k (内心崩溃, 感到自己的傻)

/*法1：暴力枚举*/
class Solution {
    public String longestPalindrome(String s) {
        int i= 0;
        int j =0;
        String result = "";
        if(s.length()<3) return s;//boundary
        while(i<s.length()-1){
            //even//没考虑到ccc这种情况 修正一下
                while(i-j>=0 && i+j+1<s.length()){
                    if(s.charAt(i-j)==s.charAt(i+1+j)){
                        j++;
                     } else{
                        break;
                    }
                }
                if(result.length()<2*j){
                    result = s.substring(i-j+1, i+j+1);
                    //尼玛substring范围竟然是[startIndex, endIndex-1] 吐血 查半天bug
                }         
            j=0;//清零
             //else //odd
                while(i-j>=0 && i+j<s.length()){
                    if(s.charAt(i-j)==s.charAt(i+j)){
                        j++;
                     } else{ 
                        break;
                    }
                }
                if(result.length()<2*j-1){
                    result = s.substring(i-j+1, i+j);
                }       
            
            i++; j=0;
            }
            
        return result;
    }
}

解法2

解法1的复杂度超时, 故开始写解法2. 查询到名为Manacher算法(马拉车算法~~这个翻译-_,-~~)的方法, 复杂度O(n)

算法有三个核心:

在每个字符中间加上特殊符号来合并对于奇偶中心对偶回文的处理, 同时增加一个同长度的数组来存储各字符可生成的最长回文串半径.
算法的核心是根据大回文中轴线两侧若出现小回文,一定会在对侧有同样的小回文这一原理, 来减少不必要的回文字符检查数量, 加快确定最大回文串的中心
在循环过程中, 对于已知最大回文串中心右侧从第一个字符到此串最右端最后一个字符, 中间的每个字符, 判定各个字符的回文串半径初始值的预估方法. 即根据已知最大回文串最右端字符位置和此字符位置的大小判定, 有三种可能:
- 最右字符位置<=此字符位置, 超出最大串范围, 直接对初始值赋0;
- 最右字符位置>此字符位置,未超出最大串范围, 有两种可能.
  i: (最右字符位置-此字符位置)<此字符以已知最大回文串中心为轴作轴对称得到的字符回文串半径, 即此字符到最右字符的距离比较短, 不够形成和轴对称字符完全相等长度的对称串, 此时初始半径值=(最右字符位置-此字符位置);
- 最右字符位置>此字符位置,未超出最大串范围.
  ii: (最右字符位置-此字符位置)>=此字符以已知最大回文串中心为轴作轴对称得到的字符回文串半径, 即此字符到最右字符的距离比较长, 足够形成和轴对称字符完全相等长度的对称串, 此时初始半径值=此字符以已知最大回文串中心为轴作轴对称得到的字符回文串半径.
- 在给回文串半径赋好初始值之后, 继续进行初始值+1, +2….的判定处理直到找到最大值. 之后若此字符半径最大值大于已知最大值, 那么更新最大回文中心的位置到此字符, 并延展最大回文串最右端的位置.
  读起来比较拗口, 不过代码实现实际上比较简单. 马拉车算法对于字符串子回文串的处理非常全面, 可以处理很多回文串的相关问题.

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<2) return s;//记住处理边界条件=L-
        String pre = preProcess(s);
        return manacherProcess(pre, s);
    }
    //预处理输入字符串
    public String preProcess(String s){
        String sout = "$#";
        for(int i=0;i<s.length();i++){
            sout = sout+s.charAt(i)+"#";
        }
        sout+="&";//这里最好和首字符不一样，不然处理时会处理不掉
        return sout;
    }
    public String manacherProcess(String s, String formal){
        int nowMaxCenter = 0;//注意这里和后面初始值是0,特别是后面的,不然会越界
        int nowMaxRight = 0;
        int[] palinRadius = new int[s.length()];
        String result;
        for(int i=1; i<s.length()-1; i++){
            palinRadius[i] = nowMaxRight > i ? Math.min(nowMaxRight-i, palinRadius[2*nowMaxCenter-i]) : 0;
            while(s.charAt(i+palinRadius[i]+1) == s.charAt(i-palinRadius[i]-1)){
                palinRadius[i]++;
            }
            if(palinRadius[i]>palinRadius[nowMaxCenter]){
                nowMaxCenter = i;
                nowMaxRight = i+palinRadius[i];
            }
        }
        
        //这段是不需要的, 因为上面for循环结束时一定会得到最大的回文串之中心与半径.
        //for(int i=1; i<palinRadius.length()-1; i++){
        //    int maxValue = 0;
        //    maxValue = Math.max(palinRadius[i], maxValue);
        //}
        
        //返回结果
        //下面这两行去掉了, 会超时(估计是replace函数导致的), 直接用倒数第二行直接返回的结果
        //result = s.substring(nowMaxCenter-palinRadius[nowMaxCenter], nowMaxCenter+palinRadius[nowMaxCenter]+1);
        //return result.replace("#", "");//记得最后去掉“#”！
        
        result = formal.substring((nowMaxCenter-palinRadius[nowMaxCenter]-1)/2, (nowMaxCenter+palinRadius[nowMaxCenter]-1)/2);
        return result;
    }
}

关于最后那行, 根据处理过的字符串求原字符串中的子串位置, 大概解释一下为什么会是[(中心位置-半径-1)/2, (中心位置+半径-1)/2)
首先, 假设原字符串位置是从0,1,2,…i,i+1,….n-1, 被处理过的字符串分别在首尾加了”$#”和”#&” 然后在原字符串中间插入字符”#”, 假设新字符串位置为0,1,2,…,j,j+1,…,2n+3.
那么原字符串对应新字符串的关系是: j = 2*(i+1), 但是实际上新字符串获得的子串首尾是”#”符号, 串首”#”符号的位置要+1才是正确的起点, 串尾”#”位置-1才是正确的终点.
故对于首位位置i对应新字符串位置j: ((j+1)/2)-1=i => i=(j-1)/2, j=中心位置-半径 => 首位位置=(中心位置-半径-1)/2;
对于尾位位置i对应新字符串位置j: ((j-1)/2)-1=i, 又因为substring右端index是不包含的,所以还要再给i+1, 最后函数才会取到位置(否则是i-1位置),则给i+1=(j-1)/2, j=中心位置-半径 => 尾位位置=(中心位置+半径-1)/2.

解法3

动态规划方法, 一个关于动规的解说链接
 参考答案链接

睡觉去了, 明天写~~病了一周的孱弱的胖子留~~

数据结构笔记1

发表于 2017-08-21 |

声明：大部分内容来自《大话数据结构》一书

Ch1 数据结构一些基本概念和术语

1.1 基本概念

数据
数据元素：组成数据的、有一定意义的基本单位。通常作为整体被计算机处理。也被称为记录
数据项：数据元素可由多个数据项组成，数据项是数据不可分割的最小单位
数据对象：性质相同的数据元素的集合，是数据的子集。
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

关系：

数据_由多个..组成>数据对象
^|
性质相同的数据元素的集合||包含多个
|v
数据元素_>数据项（最小单位）
eg：
生物——————————————>禽类
|
|
v
鸡——————>嘴/眼睛/….

1.2 逻辑结构和物理结构

逻辑结构：

集合结构：结构中的数据元素出了同属于一个集合外，没有其他关系
线性结构：一对一
树结构：一对多
图结构：多对多

物理结构：

顺序存储结构
链式存储结构

Ch2 算法

函数的渐进增长：
两个函数h(n)和g(n)，如果存在一个n值使得n选值大于此n时h(n)总大于g(n)，那么我们称h(n)的渐进增长快于g(n)。
推导大O阶方法：

用常数1取代运行时间中的加法常数。（所以常数阶全都是O（1）而非O（某个常数））
在修改后的运行次数函数中，只保留最高阶项。
若最高阶项存在且不是1，则去除与这个项相乘的常数。

常见的时间复杂度排序：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2^n)<O(n!)<O(n^n)
左3：比较优秀；中2：一般：右：差

Ch3 线性表

零个或多个相同类型的数据元素的有限序列。
3.1 特点：

a1~an-1有且只有一个后继元素，a2~an有且只有一个前驱元素

表内元素个数有限

表内元素从1开始标识（实现时使用的数组本身则是从0计数）

n=0时称为空表

在较复杂的线性表中，一个数据元素可由多个数据项组成（eg：学号+姓名+性别+出生年月……）

3.2 存储结构
1) 顺序存储
指用一段地址连续的存储单元依次存储线性表的数据元素。

可用一维数组类实现顺序存储结构。
优点：查找复杂度O(1)；无需为表示表中元素间的逻辑关系增加额外的存储空间
缺点：插入/删除复杂度O(n)；线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的碎片

由于顺序存储这样那样的问题，我们有了另外一种存储方法：
2) 链式存储
链式存储中，对每个数据元素来说，出了存储其本身的信息外，还要存储一个指示其直接后继（的存储位置）的信息。
数据域：存储数据元素信息的域
指针域：存储直接后继位置的域，指针域中存储的信息称作指针或链
结点：指针域和数据域组成的数据元素映像，称为结点

n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以称为单链表

头指针：链表中第一个结点的存储位置称为头指针（是个指向第一个结点的指针），若链表有头结点，头指针则是指向头结点的指针。

线性链表的最后一个结点指针为“空”。
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：在单链表的第一个结点前附设一个结点，称为头结点，里面的数据域可以不存储任何信息，指针域存储指向第一个结点的指针
(！注意这个指针不是头指针，头指针指向的头结点本身)。

头结点不一定是链表必须要素
头结点是为了操作的统一/方便设定的，这样对第一元素结点前插入结点和删除第一结点放在第一元素的结点之前，其数据域一般无意义。
参考：http://blog.csdn.net/zhenyusoso/article/details/6092843 中图2

空表：线性表为空表时，头结点的指针域为“空”。

代码描述：p是指向线性表第i个元素的指针，则该结点ai的数据域可用p->data表示，p->data的值是一个数据元素，结点ai的指针域可用p-next来表示（指向第ai+1个元素的指针），如果p->data=ai，那么p->next->data=ai+1

AWKWARD-SS

一个衰弱的自我怀疑患者的复健记录站点

GitHub E-Mail Weibo